Error Correction for Index Coding With Side Information
From MaRDI portal
Publication:2989362
DOI10.1109/TIT.2012.2227674zbMATH Open1364.94285arXiv1105.2865OpenAlexW2013945717MaRDI QIDQ2989362FDOQ2989362
Authors: Son Hoang Dau, Vitaly Skachek, Yeow Meng Chee 
Publication date: 8 June 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: A problem of index coding with side information was first considered by Y. Birk and T. Kol (IEEE INFOCOM, 1998). In the present work, a generalization 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 large alphabets, a construction based on concatenation of an optimal index code with an MDS classical code, is shown to attain the Singleton bound. For smaller alphabets, however, this construction may not be optimal. A random construction is also analyzed. It yields another implicit bound on the length of an optimal linear ECIC. Further, the problem of error-correcting decoding by a linear ECIC is studied. It is shown that in order to decode correctly the desired symbol, the decoder is required to find one of the vectors, belonging to an affine space containing the actual error vector. The syndrome decoding is shown to produce the correct output if the weight of the error pattern is less or equal to the error-correcting capability of the corresponding ECIC. Finally, the notion of static ECIC, which is suitable for use with a family of instances of an index coding problem, is introduced.
Full work available at URL: https://arxiv.org/abs/1105.2865
Cited In (3)
This page was built for publication: Error Correction for Index Coding With Side Information
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989362)
