Research‎ > ‎

Index Coding

An index coding problem  example with three receivers.

Fig. 1. An index coding problem example with three receivers. Each receiver knows two message packets as prior side information, and wants one unique message packet. The message packets are represented in colors.  Single transmission of coded symbol, which is formed by XORing red, green, and blue  packets, is enough to satisfy all three receivers in this example. 

Consider a source broadcasting message packets through a noiseless broadcast channel to multiple receivers, each knowing some message packets a priori, which is known as side information. The source is informed about the side information present at each receiver. During encoding process, the source utilizes the knowledge of side information at each receiver, and transmits such coded symbols that can reduce the number of transmission over this broadcast channel. The encoding scheme is called index coding, and the problem (i.e., reducing the number of transmission utilizing knowledge of side information) is called the index coding problem. This problem was introduced by Birk and Kol in 1998. Furthermore, its relation with network coding problems and distributed storage systems, the index coding problem has been receiving more attention. In an index coding problem setup, when all receivers are interested in only one unique message packet, this is called the index coding problem in the unicast message setting.  This problem can be described by a digraph (i.e., directed graph).

Our work examine a new index coding scheme, called interlinked cycle cover (ICC) which exploits the interlinked cycles (i.e., not disjoint) present in a digraph. The ICC scheme turns out to be a generalization of the two existing schemes, namely clique cover and cycle cover schemes.