Index Coding, Error Correcting Index Codes And Matroids

Abstract

In the problem of index coding, there is a central source sending messages to a set of receivers which demand messages over a noiseless broadcast channel. Each receiver knows a subset of messages which is referred to as side-information. A backward channel exists between each of the receivers and the source. Receivers use the reverse channel to communicate the side-information back to the source. The source uses this side-information to develop encoding schemes so that all the receivers are satisfied with minimum number of transmissions. In this work, we consider few problems related to index coding. First, we consider the informed source coding problem in which the receiver communicates only the cardinality of the side-information available to it and not the messages that constitute the side-information. We use l-th Near Maximum Distance Sep- arable (Near-MDS) codes to construct encoding schemes for the informed source coding problem. The advantage of using l-th Near-MDS codes is the reduction of required field size. For certain class of informed source coding problems, we show that the codes constructed from l`-th Near-MDS codes are optimal under some field size restrictions. Links between matroid theory, network coding and index coding problems have been an active area of research. The generalized index coding problem is a general version of the conventional index coding problem in which both the source and receivers possess linear functions of messages. We establish connections between representation of discrete polymatroids and generalized index coding. We show that the generalized index coding problem has a vector linear solution if and only if there exists a representable discrete polymatroid satisfying certain conditions. Further, from a discrete polymatroid a generalized index coding problem is con- structed. It is shown that if the generalized index coding problem has a vector linear solution over the binary eld then an associated discrete polymatroid is representable over the binary eld. For generalized index coding problems con- structed from matroids, we show that a scalar linear solution to the constructed problem exists if and only if the matroid is binary representable. We also consider the index coding with restricted information (ICRI) problem in which the source must ensure that each receiver will not be able to decode a certain subset of messages. Interference alignment techniques are used to obtain results on the ICRI problem. Necessary conditions for the existence of a solution to the ICRI problem is found. A technique to obtain solutions to the ICRI problem using contractions corresponding to restrictions is obtained. Index coding over noisy channels is also considered. Error correcting index codes are encoding schemes which enable every receiver to correct up to a certain number of errors in the received message. We allow each receiver to have a di erent error correcting capability and introduce di erential error correcting index codes to achieve this. A set of necessary and su cient conditions for a matrix to correspond to a vector linear di erential index code is found. We establish the link between vector linear di erential error correcting index codes and discrete polymatroids. It is shown that a vector linear di erential error correcting index code exists if and only if there exists a representable discrete polymatroid satisfying certain conditions. Lastly, index coding problem over binary symmetric channels is studied. It is observed that the probability of error at each receiver depends on the index code used. A condition on the optimal index codes which minimize the maximum error probability among all the receivers is derived. For a special class of index coding problems, an algorithm to identify an optimal index code which gives the best performance in terms of minimal maximum error probability across all the receivers is provided.