A New Upperbound on the Broadcast Rate and Near-Optimal Vector Linear Codes for Index Coding Problems with Symmetric Neighboring Interference
Mahesh Babu Vaddi, Balaji Sundar Rajan · 2018
A single unicast index coding problem (SUICP) with symmetric neighboring interference (SNI) has equal number of K messages and K receivers, the kth receiver Rkwanting the kth message xkand having the side-information Kk= (Ik∪xk)c, where Ik= {xk-U, ..., xk-2, xk-1} ∪{xk+1, xk+2, ..., xk+D} is the interference with D messages after and U messages before its desired message. The single unicast index coding problem with symmetric neighboring interference (SUICP-SNI) is motivated by topological interference management problems in wireless communication networks. Maleki, Cadambe and Jafar obtained the capacity of this SUICP-SNI with K tending to infinity and Blasiak, Kleinberg and Lubetzky for the special case of (D=U= 1) with K being finite. Finding the capacity of the SUICP-SNI for arbitrary K,D and U is a challenging open problem. In this paper, for an SUICP-SNI with arbitrary K,D and U, we define a set S of 2-tuples such that for every (a, b) in that set S, the rate D+1+[a/b] is achieved by using vector linear index codes over every finite field. We give an algorithm to find the values of a and b such that (a, b) ∈ S and [a/b] is minimum. We present a new upperbound on the broadcast rate of SUICP-SNI and prove that this upperbound coincides with the existing results on the exact value of the capacity of SUICP-SNI in the respective settings.