Optimal Scalar Linear Index Codes for One-Sided Neighboring Side-Information Problems
Mahesh Babu Vaddi, Balaji Sundar Rajan · 2016
The capacity of symmetric neighboring and consecutive side-information single unicast index coding problem (SNC-SUICP) with number of messages equal to the number of receivers was given by Maleki, Cadambe and Jafar. In this paper, we construct binary matrices of size m ×n (m ≥ n) such that any n adjacent rows of the matrix are linearly independent over every field. By using such matrices, we give an optimal scalar linear index code for the one-sided SNC-SUICP considered by Maleki, Cadambe and Jafar for any given number of messages and onesided side-information. The constructed codes are independent of field size and hence works over every field.