Optimal Code Constructions for Some Multi-sender Index Coding Problems

Abstract

An instance of the multi-sender index coding problem consists of a set of senders collectively having all the messages demanded by a set of receivers. Each receiver knows a subset of messages a priori, called its side information, and receives all the transmissions from all the senders. Each sender avails the knowledge of the side information and the demands of all the receivers, and the knowledge of messages available with other senders, to broadcast coded messages called an index code. Transmissions of each sender are orthogonal in time with those of others. The objective is to minimize the total number of coded transmissions, such that each receiver can decode its demands. The multi-sender index coding problem is related to many problems of practical interest such as multi-source satellite communication, multi-source coded caching, coded cooperative data exchange and distributed computing among many others. The multi-sender index coding problem is NP-hard and the optimal codelength is known only for a few special classes of the problem. In a prior work (V. K. Gummadi, A. Choudhary, and P. Krishnan, \Index Coding : Rank-Invariant Extensions," arXiv preprint arXiv:1704.00687 [cs.IT], 3 Apr, 2017), some classes of single-sender index coding problems called rank invariant extensions were identified. Optimal scalar linear codes of any problem belonging to this class were obtained using those of a particular subproblem. In another line of research ( C. Thapa, L. Ong, S. J. Johnson, and M. Li, \Structural Characteristics of Two-Sender Index Coding," Entropy 21, no. 6, 615, 2019), optimal codes for some classes of the two-sender index coding problem were constructed using those of its subproblems. In this work, we identify some classes of single-sender index coding problems, and construct optimal scalar linear codes for the same using scalar linear codes of some subproblems. All the scalar linear codes need not be optimal for the constructed codes to be scalar linear optimal. This result generalizes the notion of rank invariant extensions and solves many classes of single-sender problems for optimal scalar linear codes. This result is also applied to construct optimal scalar linear codes for some classes of the two-sender index coding problem. Moreover, all unsolved problems belonging to a fundamental class of the two-sender problem are solved for optimal broadcast rates. Optimal linear codelength of error correcting index codes are established for some classes of single-sender problems and multisender problems using related parameters of some subproblems. Weakly secure index codes are constructed for some classes of the two-sender problem using those of its single-sender problems. Many results presented in this thesis can be extended to solve many multi-sender index coding problems. We first introduce the notion of joint extensions of any finite number of single sender groupcast index coding problems which generalizes the notion of rank invariant extensions. A class of joint extensions is identi fied, where optimal scalar linear codes are constructed using those of the subproblems. This result is used to construct optimal scalar linear codes for some classes of the two-sender groupcast index coding problem. Another class of joint extensions referred to as base induced joint extensions is identi fied, where a problem called the base problem dictates the relations among the subproblems in the jointly extended problem. We present an algorithm to construct scalar linear codes using those of the subproblems, for any base induced joint extension. We observe that the algorithm constructs optimal scalar linear codes for a particular class of base induced joint extensions. An index coding problem is said to be unicast if each message is demanded by only one receiver. We establish the optimal broadcast rate (total number of transmitted bits per message bit as message length tends to in finity) for all the unsolved problems belonging to a fundamental class of the two-sender unicast index coding problem introduced by Thapa et al. Related code constructions with finite length messages make use of optimal codes of the single-sender subproblems. The established optimal broadcast rates take into account both linear and nonlinear encoding schemes at the senders. The proof techniques employed are used to construct optimal linear codes for some classes of multi-sender unicast problems We then consider the problem of multi-sender groupcast index coding with error correction, where any receiver receives atmost a speci fied number of coded symbols erroneously. A parameter called the generalized independence number is established for base induced joint extensions and rank invariant extensions in terms of those of its subproblems. Using this result, optimal length of linear error correcting index codes are provided for some classes of the single-sender index coding problem. These results are used to construct optimal linear error correcting index codes for some classes of the multi-sender groupcast index coding problem. We then consider the problem of index coding with weak security which consists of an adversary having some messages as side information. An index code is said to be weakly secure if the adversary can not obtain any information about any single message which it does not have using the index code and its side information. We show that the codes constructed for some classes of the two-sender groupcast index coding problem, using weakly secure codes of single-sender subproblems are also weakly secure. A subclass of the two-sender groupcast problem is identi fied where the constructed codes are optimal. Finally, we consider the problem of broadcasting with noisy side information introduced in S. Ghosh, and L. Natarajan, \Linear codes for broadcasting with noisy side information," arXiv preprint arXiv:1801.02868v1 [cs.IT], 9 Jan, 2018. Any wireless channel experiences outage due to fading. Some receivers erroneously decode their demanded messages during the fi rst round of transmissions from a sender. The sender can now avail the knowledge of the maximum number of erroneously decoded messages at any receiver (known as its error threshold), to reduce the number of retransmissions. The receivers make use of the erroneously decoded messages as side information (which is thus noisy) to decode their demands in the retransmission phase. We consider the problem with different error thresholds at different receivers and generalize a field-size independent encoding scheme given for the case with the same error threshold at every receiver. We show that this scheme saves at least two transmissions for a particular class of the problem with different error thresholds. We then extend the equivalence established between the problem of broadcasting with noisy side information and the index coding

problem to the case with different error thresholds. We use this result to obtain optimal linear codes for a special class of the problem.