On the Minrank of Symmetric and Neighboring Side-information Index Coding Problems
Mahesh Babu Vaddi, Balaji Sundar Rajan · 2019
The length of an optimal scalar linear index code of a single unicast index coding problem (SUICP) is equal to the minrank of its side-information graph. A single unicast index coding problem is called symmetric neighboring and consecutive (SNC) side-information problem if it has K messages and K receivers, the kth receiver Rkwanting the kth message xkand having the side-information D messages immediately after xkand U (D ≥ U) messages immediately before xk. Maleki, Cadambe and Jafar obtained the capacity of this SUICP(SNC) and proposed (U + 1)-dimensional optimal length vector linear index codes by using Vandermonde matrices. However, for a b-dimensional vector linear index code, the transmitter needs to wait for b realizations of each message and hence the latency introduced at the transmitter is proportional to b. For any given single unicast index coding problem with the side-information graph G, MAIS(G) is used to give a lower-bound on the broadcast rate of the ICP. In this paper, we analyse the properties of minrank of SUICP(SNC) side-information graph. We derive the MAIS(G) of side-information graph G of SUICP(SNC). For arbitrary K, D and U, we construct scalar linear index codes lfor SUICP(SNC) with length ⌈K/U+1⌉ - ⌊D-U/U+1⌋. We obtain the minrank of SUICP(SNC) side-information graph and show that the length of the constructed scalar linear index codes is equal to minrank of SUICP(SNC) side-information graph for some combinations of K, D and U.