Reed-Solomon codes can have unexpectedly large lists of close codewords

Combinatorial limitations of list-decoding Reed-Solomon codes

Information TheoryComputational Complexity

Summary

Reed-Solomon codes are methods used to detect and correct errors in data. The authors found that for some types of these codes, surprisingly many alternative codewords can be very close to one another, breaking a previous assumption. This means that decoding methods expecting only a few close possibilities must be adjusted. Their findings show inherent limits on how these codes can be used for error correction in certain cases.

What this means in practice

  • For error correction engineers: Avoid assuming a constant list size when designing decoders for Reed-Solomon codes over prime fields under certain rates and radius conditions.
  • For cryptography system designers: Recognize fundamental limits on list sizes in Reed-Solomon decoding to better assess security margins in cryptographic protocols relying on these codes.

A theory result. No direct application yet.

Authors

Omar Alrabiah, Rohan Goyal, Venkatesan Guruswami

Abstract

For infinitely many rates $R \in (0,1)$, we show that full-length Reed-Solomon codes over fields of low characteristic can contain super-polynomially many codewords in a Hamming ball of radius just exceeding the Johnson radius. Over prime fields, we exhibit full-length Reed-Solomon codes of constant rate $R$ with polynomially many codewords in a Hamming ball of relative radius bounded strictly below $1-R$. This refutes a recent conjecture that, over prime fields, list sizes below capacity are always bounded by a constant. Together, these results demonstrate that certain restrictions in recent works on explicit Reed-Solomon codes achieving list-decoding capacity, related to the choice of field or evaluation points or to the list-size guarantee, are inherent.