Index Codes with Minimum Locality for Three Receiver Unicast Problems

Joy, Smiju Kodamthuruthil and Natarajan, Lakshmi (2020) Index Codes with Minimum Locality for Three Receiver Unicast Problems. In: 26th National Conference on Communications, NCC 2020, 21 February 2020 - 23 February 2020.

Full text not available from this repository. (Request a copy)


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 single-uniprior 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 a class of unicast problems with three or fewer receivers 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 which 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
Joy, Smiju KodamthuruthilUNSPECIFIED
Natarajan, Lakshmi Prasad
Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: Broadcast channels; Error performance; Index coding; Optimal rate; Receiver complexity; Side information; Unicast problems; Wireless broadcast Engineering main heading
Subjects: Electrical Engineering
Divisions: Department of Electrical Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 06 Jul 2021 10:11
Last Modified: 06 Jul 2021 10:11
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 8141 Statistics for this ePrint Item