Low Complexity Decoding and Capacity of Index Coding Problems with Symmetric Side-Information
Mahesh Babu Vaddi, Balaji Sundar Rajan · 2018
A single unicast index coding problem (SUICP) with symmetric side-information has K messages and K receivers, the kth receiver Rk wants xk, Rk has some subset of messages as side-information and the side-information is symmetric to its wanted message xk. Maleki, Cadambe and Jafar studied various symmetric index coding problems because of their importance in topological interference management problems. In our previous work, we constructed binary matrices of size mxn for any given arbitrary positive integers m and n such that any n adjacent rows of this matrix are linearly independent. We refer these matrices as Adjacent Independent Row (AIR) matrices. We designed optimal and near-optimal vector linear index codes for various symmetric SUICPs by using AIR matrices. To design the optimal and nearoptimal vector linear index codes, we convert the respective symmetric SUICP into an SUICP with symmetric neighboring and consecutive (SNC) side-information. Then, we use AIR matrix to encode the SUICP with SNC side-information. Hence, low-complexity decoding of SUICP with SNC side-information is important for efficient decoding of optimal and near-optimal index codes for various symmetric SUICPs. We analyse some of the combinatorial properties of AIR matrices in this work. By using these properties, we provide a low-complexity decoding for SUICP with SNC side-information. The low-complexity decoding explicitly identifies the set of broadcast symbols required at every receiver to decode its wanted message. By using lowcomplexity decoding, we find the capacity of SUICP with symmetric side-information Kk= {xk+g, xk+2g, . . . , xk+tg}, where g = gcd(K, D) and t = D/g for any positive integer D <; K.