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.