En avsändare innehåller ett ord x bestående av n block x i, var och en av t bitar, och vill sända ett kodord till m mottagare, R 1,..., R m. Varje mottagare R i är intresserad av ett block, och har tidigare sidoinformation som består av någon delmängd av de andra blocken. Låt β t vara det minsta antalet bitar som måste överföras när varje block är av längd t, och låt β vara gränsen β = lim t→∞ β t /t. Informellt är β den genomsnittliga kommunikationskostnaden per bit i varje block (för långa block). Hittar kodningsfrekvensen β, för en sådan informerad sändning inställning, generaliserar flera kodning teoretiska parametrar relaterade till informerad källkod Kodning på begäran, Index Kodning och Nätverk Kodning. I detta arbete visar vi att användning av stora datablock kan strikt förbättra den triviala kodning som behandlar varje bit i blocket självständigt. För detta ändamål ger vi allmänna gränser på β t, och bevisa att för varje konstant C finns det en explicit sändningsinställning där β = 2 men β 1 > C. Ett av dessa exempel svarar på en fråga [15]. Dessutom ger vi exempel på följande kontraintuitiva direktsummor. Överväga en förening av flera ömsesidigt oberoende sändningsinställningar. Den optimala koden för den kombinerade inställningen kan ge en betydande besparing i kommunikationen över concretenating optimal kodning för de enskilda inställningarna. Detta resultat ger också nya icke-linjära kodningssystem som förbättrar den största kända klyftan mellan linjär och icke-linjär nätkodning, vilket förbättrar resultaten av [8]. Bevisen är baserade på ett samband mellan detta problem och resulterar i studien av Witsenhausens hastighet, OR grafprodukter, färgningar av Cayley grafer, och de kromatiska talen av Kneser grafer.
En något annorlunda modell beaktas i REF, där en avsändare vill sända datablock till flera mottagare, med varje mottagare har tidigare sidoinformation som består av någon delmängd av de andra blocken.
Broadcasting with Side Information
{'venue': '2008 49th Annual IEEE Symposium on Foundations of Computer Science', 'journal': '2008 49th Annual IEEE Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}