Index Coding with Coded Side-Information


Namyoon Lee, Alexandros G. Dimakis, and Robert W. Heath, Jr.


Submitted to IEEE Communication Letters.


This letter investigates a new class of index coding problems. One sender broadcasts multiple packets to multiple users, each of which desires to decode a subset of the packets by exploiting knowledge of coded packets a priori. Since each user has coded packets as side-information instead of knowing individual packets independently, this class of problems is termed as index coding with coded side-information. Our aim is to characterize the minimum index code length that the sender needs to transmit to simultaneously satisfy all users requests. Using an algebraic framework, it is shown that the optimal binary vector index code length equals to the minimum rank (minrank) of a matrix whose elements consists of the sets of desired packet indices and side-information encoding matrices. With the derived minrank expression, a random caching algorithm is proposed to guarantee a target transmission rate for caching systems.

[download full paper]