Improved error correction with hints extends decoding range for Reed-Solomon codes
An Improved Johnson Bound for List-Decoding with Hints
Information Theory
Summary
When messages are sent and get partially messed up, error-correcting codes help fix them. Usually, there's a limit called the Johnson bound beyond which reliable correction can be hard. This paper shows that if you already have one or more clues about close original messages (called hints), you can fix even more errors beyond that limit. The authors also provide a practical method to do this for a common type of code called Reed-Solomon codes, making error correction more powerful when hints are available.
What this means in practice
- •For communications engineers: Enhance decoding algorithms for data transmission systems when near-correct codewords are partially known.
- •For data storage system developers: Improve error correction performance in storage devices by leveraging partial knowledge about corrupted codewords.
Authors
Swastik Kopparty, Harry Sha
Abstract
This paper studies when list-decodability guarantees for error-correcting codes of good distance can go beyond the classical Johnson radius and gives a corresponding efficient list-decoding algorithm for Reed-Solomon codes up to this new radius. The Johnson bound shows that any error-correcting code with distance $δ$ is automatically list-decodable with small list size up to a certain radius $J(δ)$ around any received word $r$. We show that if the received word $r$ is known to have some codewords that are somewhat close to it (we call these ``hints"), then $C$ is list-decodable with small list size up to an even larger radius around $r$. We determine the optimal list-decoding radius in this setting for single and multiple hints over both large and small alphabets and show that this radius is the optimum of a natural convex program. Remarkably, even a single hint that is $(J(δ)-ε)$-close to $r$ improves the list-decoding radius around $r$ to $J(δ)+ε'$. Finally, we give an efficient algorithm, based on the weighted Guruswami-Sudan decoder, that list-decodes Reed-Solomon codes up to this optimal radius.