Optimal Index Codes via a Duality between Index Coding and Network Coding

MaRDI QIDQ6294090zbMATH OpenFDO

Authors Ashok Choudhary, Vamsi Krishna Gummadi, Prasad Krishnan

Publication date 17 November 2017

Abstract: In Index Coding, the goal is to use a broadcast channel as efficiently as possible to communicate information from a source to multiple receivers which can possess some of the information symbols at the source as side-information. In this work, we present a duality relationship between index coding (IC) and multiple-unicast network coding (NC). It is known that the IC problem can be represented using a side-information graph $G$ (with number of vertices $n$ equal to the number of source symbols). The size of the maximum acyclic induced subgraph, denoted by $MAIS$ is a lower bound on the extit{broadcast rate}. For IC problems with $MAIS=n-1$ and $MAIS=n-2$, prior work has shown that binary (over ${mathbbF}_2$) linear index codes achieve the $MAIS$ lower bound for the broadcast rate and thus are optimal. In this work, we use the the duality relationship between NC and IC to show that for a class of IC problems with $MAIS=n-3$, binary linear index codes achieve the $MAIS$ lower bound on the broadcast rate. In contrast, it is known that there exists IC problems with $MAIS=n-3$ and optimal broadcast rate strictly greater than $MAIS$.

This page was built for publication: Optimal Index Codes via a Duality between Index Coding and Network Coding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6294090)