Index Codes with Minimum Locality for Three Receiver Unicast Problems

Joy, S K and Natarajan, Lakshmi Prasad (2019) Index Codes with Minimum Locality for Three Receiver Unicast Problems. arXiv. pp. 1-7. (In Press)

1904.04753.pdf - Accepted Version

Download (625kB) | Preview


An index code for a broadcast channel with receiver side information is locally decodable if every receiver can decode its demand using only a subset of the codeword symbols transmitted by the sender instead of observing the entire codeword. Local decodability in index coding improves the error performance when used in wireless broadcast channels, reduces the receiver complexity and improves privacy in index coding. The locality of an index code is the ratio of the number of codeword symbols used by each receiver to the number message symbols demanded by the receiver. Prior work on locality in index coding have considered only single unicast and singleuniprior problems, and the optimal trade-off between broadcast rate and locality is known only for a few cases. In this paper we identify the optimal broadcast rate (including among non-linear codes) for all three receiver unicast problems when the locality is equal to the minimum possible value, i.e., equal to one. The index code that achieves this optimal rate is based on a clique covering technique and is well known. The main contribution of this paper is in providing tight converse results by relating locality to broadcast rate, and showing that this known index coding scheme is optimal when locality is equal to one. Towards this we derive several structural properties of the side information graphs of three receiver unicast problems, and combine them with information theoretic arguments to arrive at a converse.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Natarajan, Lakshmi Prasad
Item Type: Article
Subjects: Electrical Engineering
Divisions: Department of Electrical Engineering
Depositing User: Team Library
Date Deposited: 15 Apr 2019 04:16
Last Modified: 15 Apr 2019 04:24
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 4948 Statistics for this ePrint Item