Index Coding and Error Correction

Details Index Coding and Error Correction Index Coding and Error Correction

2011-01-14

arxiv.org/abs/1101.2728v1

Computer Science

Information Theory

5 pages, submitted

Scientific paper

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 $\delta$, 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 $\alpha$-bound and the $\kappa$-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 inexplicit bound on the length of an optimal linear ECIC. Finally, the decoding of linear ECIC's is discussed. The syndrome decoding is shown to output the exact message if the weight of the error vector is less or equal to the error-correcting capability of the corresponding ECIC.

Affiliated with

Also associated with

No associations

Rating

Index Coding and Error Correction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Index Coding and Error Correction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Index Coding and Error Correction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-78544