Index Coding with Side Information

Motivated by a problem of transmitting data over broadcast channels (BirkandKol, INFOCOM1998), we study the following coding problem: a sender communicates with n receivers R l, .. , R n. He holds an input x isin {0, 1} n and wishes to broadcast a single message so that each receiver R i can recover the bit x i. Each R i has prior side information about x, induced by a directed graph G on n nodes; R i knows the bits of x in the positions {j | (i, j) is anedge of G}. We call encoding schemes that achieve this goal INDEX codes for {0, 1} n with side information graph G. In this paper we identify a measure on graphs, the minrank, which we conjecture to exactly characterize the minimum length of INDEX codes. We resolve the conjecture for certain natural classes of graphs. For arbitrary graphs, we show that the minrank bound is tight for both linear codes and certain classes of non-linear codes. For the general problem, we obtain a (weaker) lower bound that the length of an INDEX code for any graph G is at least the size of the maximum acyclic induced subgraph of G

Authors

• Ziv Bar-Yossef
• Yitzhak Birk
• T. S. Jayram
• Tomer Kol

Keywords

• Source coding
• Length measurement
• Entropy
• Satellite broadcasting
• Position measurement
• Linear code
• Coaxial cables
• Filters
• Information theory
• Index Coding
• Conjecture
• Directed Graph
• Code Length
• Index Codes
• Induced Subgraph
• Class Of Graphs
• Side Of The Graph
• Broadcast Channel
• Lower Bound
• Fit Index
• Source Code
• Undirected
• Partial Information
• Linear Constraints
• Cost Information
• Codeword
• Linear Algebra
• Decoding Function
• Standard Basis Vector
• Boolean Function
• Multiple Clients
• Direct Sum
• Proof Of The Lemma
• Collection Of Vectors
• Self-loops
• Entropy Source
• Shannon Capacity