Venkatesan Guruswami and Atri Rudra

Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy

Abstract : Suppose you want to communicate a message of k packets on a noisy communication channel. You judiciously encode it as a redundant collection of n = ck packets and transmit these. What is the fewest number of correct packets one needs to receive in order to have any hope of recovering the message?

Well, clearly one needs at least k correct packets. In this paper, we present an an encoding scheme that attains this information-theoretic limit: for any desired e> 0, it enables correct decoding of the message (in an error-recovery model called list decoding) as long as at least k(1+e) packets are received intact. The location of the correct packets and the errors on the remaining packets can be picked adversarially by the channel.

This achieves the optimal trade-off between redundancy and error-resilience for a worst-case noise model where the channel can corrupt the transmitted symbols arbitrarily subject to a bound on the total number of errors. Previously, such results were known for weaker stochastic noise models. This work closes one of the central open questions in algorithmic coding theory.

Additionally, our codes are very simple to describe: they are certain "folded" Reed-Solomon codes, which are just the well known Reed-Solomon codes, but viewed as a code over a larger alphabet via a bundling together of codeword symbols. Reed-Solomon codes are used in modern day storage devices (like CDs and DVDs). This connection enhances the practical aspect of our work.

Versions Some related articles