Locality in Index Coding for Large Min-Rank

Natarajan, Lakshmi Prasad and Dau, Hoang and Krishnan, Prasad and V, Lalitha (2018) Locality in Index Coding for Large Min-Rank. arXiv. pp. 1-8.

Text (arXiv Copy)
1901.05908.pdf - Accepted Version

Download (301kB) | Preview


An index code is said to be locally decodable if each receiver can decode its demand using its side information and by querying only a subset of the transmitted codeword symbols instead of observing the entire codeword. Local decodability can be a beneficial feature in some communication scenarios, such as when the receivers can afford to listen to only a part of the transmissions because of limited availability of power. The locality of an index code is the ratio of the maximum number of codeword symbols queried by a receiver to the message length. In this paper we analyze the optimum locality of linear codes for the family of index coding problems whose min-rank is one less than the number of receivers in the network. We first derive the optimal trade-off between the index coding rate and locality with vector linear coding when the side information graph is a directed cycle. We then provide the optimal trade-off achieved by scalar linear coding for a larger family of problems, viz., problems where the min-rank is only one less than the number of receivers. While the arguments used for achievability are based on known coding techniques, the converse arguments rely on new results on the structure of locally decodable index codes.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Natarajan, Lakshmi Prasadhttp://orcid.org/0000-0003-1552-5240
Item Type: Article
Subjects: Electrical Engineering
Divisions: Department of Electrical Engineering
Depositing User: Team Library
Date Deposited: 22 Jan 2019 11:34
Last Modified: 22 Jan 2019 11:34
URI: http://raiith.iith.ac.in/id/eprint/4743
Publisher URL:
OA policy: http://www.sherpa.ac.uk/romeo/issn/2168-6165/
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 4743 Statistics for this ePrint Item