Near-Optimal Vector Linear Index Codes For Single Unicast Index Coding Problems with Symmetric Neighboring Interference

A single unicast index coding problem (SUICP) with symmetric neighboring interference (SNI) has equal number of $K$ messages and $K$ receivers, the $k$th receiver $R_k$ wanting the $k$th message $x_k$ and having the side-information ${\mathcal{K}}_k=({\mathcal{I}}_k\cup x_k{)}^c,$ where ${I}k= {x{k-U},\dots,x_{k-2},x_{k-1}}\cup{x_{k+1}, x_{k+2},\dots,x_{k+D}}$istheinterferencewith$D$messagesafterand$U$ messages before its desired message. Maleki, Cadambe and Jafar obtained the capacity of this single unicast index coding problem with symmetric neighboring interference (SUICP-SNI) with $K$ tending to infinity and Blasiak, Kleinberg and Lubetzky for the special case of $(D=U=1)$ with $K$ being finite. In our previous work, we proved the capacity of SUICP-SNI for arbitrary $K$ and $D$ with $U=\text{gcd}(K,D+1)-1$. This paper deals with near-optimal linear code construction for SUICP-SNI with arbitrary $K,U$ and $D\mathrm{.}$ For SUICP-SNI with arbitrary $K,U$ and $D$, we define a set of $2$-tuples such that for every $(a,b)$ in that set the rate $D+1+\frac{a}{b}$ is achieved by using vector linear index codes over every field. We prove that the set $\mathbf{S}$ consists of $(a,b)$ such that the rate of constructed vector linear index codes are at most $\frac{K~$\text{mod}$~(D+1)}{\left \lfloor \frac{K}{D+1} \right \rfloor}$ away from a known lower bound on broadcast rate of SUICP-SNI. The three known results on the exact capacity of the SUICP-SNI are recovered as special cases of our results. Also, we give a low complexity decoding procedure for the proposed vector linear index codes for the SUICP-SNI.