Reed-Solomon codes show superpolynomial list sizes over binary extensions
Superpolynomial Lists for Reed-Solomon Codes over Binary Extension Fields
Information TheoryComputational Complexity
Summary
Reed-Solomon codes are widely used for correcting errors in data. Normally, for codes over prime number fields, the number of possible close matches stays manageable when decoding. This paper finds that for codes over binary extension fields, there can be an extremely large, superpolynomial number of close matches, making decoding much harder. The authors demonstrate this phenomenon happens at all fixed data rates and persist even when the code is modified slightly. This result challenges assumptions about decoding efficiency depending on the underlying field.
What this means in practice
- •For error correction engineers: Design error-correcting systems with awareness that Reed-Solomon decoding complexity can be superpolynomial over binary extension fields at all rates.
- •For coding theory tool developers: Adjust decoding algorithms for Reed-Solomon codes over binary fields to handle unexpectedly large decoding candidate lists.
A theory result. No direct application yet.
Authors
Minshen Zhu
Abstract
Recent work shows that ordinary Reed--Solomon codes over prime fields admit polynomial-size lists up to list-decoding capacity on every evaluation set. We show a contrasting phenomenon over binary extension fields. For every fixed rate $0<R<1$, there exists $\varepsilon_R>0$ such that, for all sufficiently large $h$, the full-field Reed--Solomon code over $\mathbb{F}_{2^h}$ has a received word with $n^{Ω_R(\log n)}$ codewords within relative distance $1-R-\varepsilon_R$. To our knowledge, these are the first superpolynomial ordinary Reed--Solomon list-size lower bounds at fixed positive rate and a fixed positive agreement gap above the rate. Thus capacity-approaching polynomial list size for Reed--Solomon codes is not uniform over the underlying field, and the obstruction occurs at every fixed rate. As a puncturing consequence, the same holds for primitive Reed--Solomon codes; the obstruction is also robust under controlled dense puncturing. The proof begins with an exact correspondence that turns certain binary Bose--Chaudhuri--Hocquenghem weight-enumerator coefficients into sizes of single Reed--Solomon lists. A classical binary weight family gives the initial quarter-rate construction, while a quadratic-form enumeration supplies its superpolynomial multiplicity. A common-kernel quotient/descent argument and common-root padding then extend the construction to all rates. We also determine the optimized agreement envelope achieved by the construction.