TY - GEN

T1 - Index coding

T2 - 2012 IEEE International Symposium on Information Theory, ISIT 2012

AU - Maleki, Hamed

AU - Cadambe, Viveck

AU - Jafar, Syed

PY - 2012

Y1 - 2012

N2 - The index coding problem is a multiple unicast wireline communication network where the network is represented by a directed graph having exactly one link with finite capacity (also known as the bottleneck link). There are K independent sources which share the ingress of this bottleneck link. Correspondingly there are K destinations which are on the receiving end of the bottleneck link, with each destination intending to decode the message of one (unique) corresponding source. Each destination can have apriori side-information of a (different) subset of the original source messages. In this paper, we study the capacity of such a network from the perspective of interference alignment, and derive information theoretically optimal schemes for a class of networks. In our first main result, we identify the set of graphs where each user can achieve half rate in the index coding problem. In a second result, we derive the capacity for a class of symmetric index coding networks.

AB - The index coding problem is a multiple unicast wireline communication network where the network is represented by a directed graph having exactly one link with finite capacity (also known as the bottleneck link). There are K independent sources which share the ingress of this bottleneck link. Correspondingly there are K destinations which are on the receiving end of the bottleneck link, with each destination intending to decode the message of one (unique) corresponding source. Each destination can have apriori side-information of a (different) subset of the original source messages. In this paper, we study the capacity of such a network from the perspective of interference alignment, and derive information theoretically optimal schemes for a class of networks. In our first main result, we identify the set of graphs where each user can achieve half rate in the index coding problem. In a second result, we derive the capacity for a class of symmetric index coding networks.

UR - http://www.scopus.com/inward/record.url?scp=84867536071&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867536071&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2012.6283851

DO - 10.1109/ISIT.2012.6283851

M3 - Conference contribution

AN - SCOPUS:84867536071

SN - 9781467325790

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2236

EP - 2240

BT - 2012 IEEE International Symposium on Information Theory Proceedings, ISIT 2012

Y2 - 1 July 2012 through 6 July 2012

ER -