Adjacent Independent Row (Air) Matrices and Index Coding

Abstract

An index coding problem, comprises a transmitter that has a set of independent messages and a set of receivers. Each receiver knows a subset of messages, called its side-information, and demands another subset of messages, called its want-set. The transmitter can take cognizance of the side-information of the receivers and broadcast coded messages, called the index code, over a noiseless channel. The objective is to minimize the number of coded transmissions, called the length of the index code, such that each receiver can decode its wanted messages using its sideinformation and the coded messages. An index coding problem is single unicast if the want-sets of the receivers are disjoint and the cardinality of want-set of every receiver is one. In a single unicast index coding problem, we have equal number of messages and receivers. A single unicast index coding problem is called symmetric if the side-information of the receivers is symmetric with respect to their wanted message. Motivated with topological interference management problems, Maleki, Cadambe and Jafar studied the symmetric index coding problems. This thesis deals with the symmetric index coding problems and present some interesting results. In this work, we construct binary matrices of size m × n such that any n adjacent rows of the matrix are linearly independent over every finite field for any arbitrary positive integers m and n (m ≥ n). We call these matrices as Adjacency Independent Row (AIR) matrices. We derive combinatorial properties of AIR matrices. We use AIR matrices to construct optimal or near-optimal index codes for various symmetric settings. By using the combinatorial properties of AIR matrices, we give a simple low-complexity decoding procedure for the constructed optimal or near-optimal index codes. By using this decoding procedure, we give a reduced set of side-information required by each receiver to decode its wanted message. We also derive bounds on the broadcast rate of two well known classes of symmetric settings and derive the capacity for some special cases of the same. The interlinked cycle (IC) structure, that generalizes cycles and cliques was defined by Thapa, Ong and Johnson. Interlinked-cycle-cover (ICC) scheme that leverages IC structures as side-information graphs to construct scalar linear index codes was proposed. A class of infinitely many digraphs, where the proposed scalar linear codes based on ICC scheme are optimal were characterized. Thapa et. al. conjectured that for any IC structure, the ICC scheme is optimal. It was also conjectured that for any digraph, the ICC scheme performs at least as well as the partial-clique-cover scheme. In this work, we disprove both the conjectures. We provide an addition to the class of IC structures by providing optimal length index codes for IC structures with one cycle among non-inner vertex set.