Rate 1/3 index coding: Forbidden and feasible configurations
V. Lalitha, Prasad Krishnan · 2017
Linear index coding can be formulated as an interference alignment problem, in which precoding vectors of the minimum possible length are to be assigned to the messages in such a way that the precoding vector of a demand (at some receiver) is independent of the space of the interference (non side-information) precoding vectors. An index code has rate 1/l if the assigned vectors are of length l. In this paper, we introduce the notion of strictly rate 1/L message subsets which must necessarily be allocated precoding vectors from a strictly L-dimensional space (L = 1, 2, 3) in any rate 1/3 code. We develop a general necessary condition for rate 1/3 feasibility using intersections of strictly rate 1/L message subsets. We apply the necessary condition to show that the presence of certain interference configurations makes the index coding problem rate 1/3 infeasible. We also obtain a class of index coding problems, containing certain interference configurations, which are rate 1/3 feasible based on the idea of contractions of an index coding problem. Our necessary conditions for rate 1/3 feasibility and the class of rate 1/3 feasible problems obtained subsume all such known results for rate 1/3 index coding.