Joy, S K and Natarajan, Lakshmi Prasad
(2019)
Index Codes with Minimum Locality for
Three Receiver Unicast Problems.
arXiv.
pp. 1-7.
(In Press)
Abstract
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.
Actions (login required)
 |
View Item |
Altmetric
Altmetric