Optimal Scalar Linear Index Codes for One-Sided Neighboring Side-Information Problems

Abstract

The capacity of symmetric instance of the multiple unicast index coding problem with neighboring antidotes (side-information) with number of messages equal to the number of receivers was given by Maleki \textit{et al.} In this paper, we construct matrices of size $m\times n(m\ge n)$ over $F_q$ such that any $n$ adjacent rows of the matrix are linearly independent. By using such matrices, we give an optimal scalar linear index codes over $F_q$ for the symmetric one-sided antidote problems considered by Maleki \textit{et al.} for any given number of messages and one-sided antidotes. The constructed codes are independent of field size and hence works over every field.

11 pages, 5 figures and 4 tables. More examples and remarks are added along with fixing a mistake in Lemma 3 of the earlier version