Optimal Code Constructions for Some Multisender Index Coding Problems
Abstract
An instance of the multisender 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 multisender index coding problem is
related to many problems of practical interest such as multisource satellite communication,
multisource coded caching, coded cooperative data exchange and
distributed computing among many others. The multisender index coding problem
is NPhard 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
: RankInvariant Extensions," arXiv preprint arXiv:1704.00687 [cs.IT], 3 Apr,
2017), some classes of singlesender 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 TwoSender Index Coding," Entropy 21, no. 6, 615, 2019), optimal codes
for some classes of the twosender index coding problem were constructed using
those of its subproblems.
In this work, we identify some classes of singlesender 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 singlesender problems for
optimal scalar linear codes. This result is also applied to construct optimal scalar
linear codes for some classes of the twosender index coding problem. Moreover, all
unsolved problems belonging to a fundamental class of the twosender problem are
solved for optimal broadcast rates. Optimal linear codelength of error correcting
index codes are established for some classes of singlesender problems and multisender
problems using related parameters of some subproblems. Weakly secure
index codes are constructed for some classes of the twosender problem using
those of its singlesender problems. Many results presented in this thesis can be
extended to solve many multisender 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 twosender 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 twosender unicast
index coding problem introduced by Thapa et al. Related code constructions with
finite length messages make use of optimal codes of the singlesender 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 multisender unicast problems We then consider the problem of multisender 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 singlesender
index coding problem. These results are used to construct optimal linear error
correcting index codes for some classes of the multisender 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 twosender
groupcast index coding problem, using weakly secure codes of singlesender subproblems
are also weakly secure. A subclass of the twosender 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 fieldsize 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.
Collections
Related items
Showing items related by title, author, creator and subject.

Functional Index Coding, Network Function Computation, and SumProduct Algorithm for Decoding Network Codes
Gupta, Anindya (20180110)Network coding was introduced as a means to increase throughput in communication networks when compared to routing. Network coding can be used not only to communicate messages from some nodes in the network to other nodes ... 
Voltage Stability Analysis of Unbalanced Power Systems
Santosh Kumar, A (20180207)The modern day power system is witnessing a tremendous change. There has been a rapid rise in the distributed generation, along with this the deregulation has resulted in a more complex system. The power demand is on a ... 
Characterization and Assessment of Organically Modified Clays for Geo Environmental Applications
Sreedharan, Vandana (20180411)Clays are used for long for the control of soil and water pollution as they are inexpensive natural materials with a high adsorption capacity for a wide range of pollutants. However their use as components in engineered ...