Index Coding over Noisy Channels and Some Applications

Abstract

A broadcast channel that is very effective for disseminating common content becomes highly inefficient when the users request different content. To address this inefficiency of the broadcast channel over which a server transmits distinct contents to different caching receivers, the concept of index coding was introduced by Birk and Kol in ``Informed-source coding-on-demand (ISCOD) over broadcast channels'' in Proceedings. IEEE INFOCOM, 1998. In an index coding problem (ICP), a server with access to a set of messages broadcasts over a forward channel to a group of caching receivers. Each receiver has a subset of the messages available in its cache and requests a non-intersecting subset of messages from the server. The server is informed about the cached contents at the receivers through a slow backward channel. Index coding aims to satisfy the message requests of all the receivers with the minimum number of server transmissions by utilizing the information of receivers' cached contents and their data requests. This problem, a variant of source coding with side information, has applications in several engineering problems in network communication, such as content broadcasting, device-to-device communication, distributed caching, distributed computation, and interference management. While most of the literature on index coding focuses on noiseless broadcast, our work focuses on various sub-classes of index coding problems and their applications, predominantly when the transmissions are over noisy broadcast channels.

We consider a binary-modulated transmission of index codes over continuous-output channels for single uniprior ICPs and develop algorithmic solutions which have reduced average probability of error. For the noisy ICP with M-ary modulated transmission, the ML decoding strategy proposed by Sudhakaran et al. in ``Index Coded PSK Modulation for Prioritized Receivers," in IEEE Transactions on Vehicular Technology, Dec. 2017, resulted in the question of whether the central server's encoding scheme should be an index code or whether any set of transmissions encoding across the entire library of messages is sufficient. We prove that index codes are necessary for solving such problems. We also address how to map index-coded vectors to signal points on a square QAM constellation and prove that unlike in uncoded point-to-point communication, cases can arise in a noisy ICP setting where M-PSK outperforms M-QAM. For the same class of ICPs, we propose multi-symbol PSK-modulated transmission, where the index-coded bits are mapped to complex symbols of multiple smaller-sized constellations for a bandwidth-performance trade-off.

Error correction for index coding was first considered by Dau et al. in the paper ``Error correction for index coding with side information,'' in IEEE Transactions on Information Theory, March 2013. A delta-error correcting index code is an encoding of the messages such that all the receivers can decode their required messages correctly in the presence of at most delta errors. Concatenating an optimal linear index code and a classical error-correcting code of minimum length, which can correct delta errors, will not always lead to optimal delta-error-correcting index codes. We develop optimal linear error-correcting transmission schemes for three different settings: a multi-access coded caching setting, a device-to-device coded caching setting, and a coded distributed computing setting. A few results in embedded index coding and coded caching derived using index coding techniques are also discussed. Finally, for two distributed computing settings, we propose a technique to reduce the recovery threshold, which is the minimum number of workers who should return their results for the master to be able to complete its task.

In short, this thesis focuses on various sub-classes of index coding problems and their applications in device-to-device communication, coded caching, and distributed computing, predominantly when the transmissions are over noisy broadcast channels.