Error correction for index coding with side information

Abstract—A problem of index coding with side information was first considered by Birk and Kol in 1998. In this study, a gener-alization of index coding scheme, where transmitted symbols are subject to errors, is studied. Error-correcting methods for such a scheme, and their parameters, are investigated. In particular, the following question is discussed: given the side information hypergraph of index coding scheme and the maximal number of erroneous symbols, what is the shortest length of a linear index code, such that every receiver is able to recover the required information? This question turns out to be a generalization of the problem of finding a shortest length error-correcting code with a prescribed error-correcting capability in the classical coding theory. The Singleton bound and two other bounds, referred to as the-bound and the-bound, for the optimal length of a linear error-correcting index code (ECIC) are established. For larg