Broadcasting with Side Information

A sender holds a word x consisting of n blocks x i, each of t bits, and wishes to broadcast a codeword to m receivers, R 1, .. ., R m. Each receiver R i is interested in one block, and has prior side information consisting of some subset of the other blocks. Let beta t be the minimum number of bits that has to be transmitted when each block is of length t, and let beta be the limit beta=lim trarrinfin beta t /t. Informally, beta is the average communication cost per bit in each block (for long blocks). Finding the coding rate beta, for such an informed broadcast setting, generalizes several coding theoretic parameters related to Informed Source Coding on Demand, Index Coding and Network Coding. In this work we show that usage of large data blocks may strictly improve upon the trivial encoding which treats each bit in the block independently. To this end, we provide general bounds on beta t, and prove that for any constant C there is an explicit broadcast setting in which beta = 2 but beta 1 > C. One of these examples answers a question of. In addition, we provide examples with the following counterintuitive direct-sum phenomena. Consider a union of several mutually independent broadcast settings. The optimal code for the combined setting may yield a significant saving in communication over concatenating optimal encodings for the individual settings. This result also provides new non-linear coding schemes which improve upon the largest known gap between linear and non-linear Network Coding, thus improving the results of. The proofs are based on a relation between this problem and results in the study of Witsenhausen's rate, OR graph products, colorings of Cayley graphs, and the chromatic numbers of Kneser graphs.

Authors

• Noga Alon
• Eyal Lubetzky
• Uri Stav
• Amit Weinstein
• Avinatan Hassidim

Keywords

• Source coding
• Computer science
• USA Councils
• Network coding
• Satellite broadcasting
• Mathematics
• Costs
• Binary codes
• Video on demand
• Multimedia communication
• Source Code
• Prior Information
• Codeword
• Linear Code
• Number Of Graphs
• Restricted Model
• Communication Network
• Partial Data
• Directed Graph
• Fraction Of Number
• Nonzero Elements
• Block Length
• Hypergraph
• Broadcast Channel
• Broadcast Networks
• Family Of Graphs
• Source coding on demand
• Index coding