Index Coding With Coded Side-Information
Authors:
- 12 January 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Communications Letters
- Vol. 19 (3) , 319-322
Abstract
This letter investigates a new class of index coding problems. One sender broadcasts packets to multiple users, each desiring a subset, by exploiting prior knowledge of linear combinations of packets. We refer to this class of problems 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 user requests. We show that the optimal binary vector index code length is equal to the minimum rank (minrank) of a matrix whose elements consist of the sets of desired packet indices and side-information encoding matrices. This is the natural extension of matrix minrank in the presence of coded side information. Using the derived expression, we propose a greedy randomized algorithm to minimize the rank of the derived matrix.Keywords
All Related Versions
Funding Information
- Intel Labs
This publication has 10 references indexed in Scilit:
- Bounding multiple unicasts through index coding and Locally Repairable Codes2014
- Fundamental Limits of CachingIEEE Transactions on Information Theory, 2014
- Topological Interference Management Through Index CodingIEEE Transactions on Information Theory, 2013
- Local graph coloring and index coding2013
- Broadcasting with coded side information2012
- Rank Minimization Over Finite Fields: Fundamental Limits and Coding-Theoretic InterpretationsIEEE Transactions on Information Theory, 2011
- Exact Matrix Completion via Convex OptimizationFoundations of Computational Mathematics, 2009
- Broadcasting with Side Information2008
- Coding on demand by an informed source (ISCOD) for efficient broadcast of different supplemental data to caching clientsIEEE Transactions on Information Theory, 2006
- Index Coding with Side Information2006