Editing Reed–Solomon error correction (section)

===Decoding beyond the error-correction bound===

The [[Singleton bound]] states that the minimum distance {{mvar|d}} of a linear block code of size ({{mvar|n}},{{mvar|k}}) is upper-bounded by {{math|''n'' - ''k'' + 1}}. The distance {{mvar|d}} was usually understood to limit the error-correction capability to {{math|⌊(''d'' - 1) / 2⌋}}. The Reed–Solomon code achieves this bound with equality, and can thus correct up to {{math|⌊(''n'' - ''k'') / 2⌋}} errors. However, this error-correction bound is not exact.

In 1999, [[Madhu Sudan]] and [[Venkatesan Guruswami]] at MIT published "Improved Decoding of Reed–Solomon and Algebraic-Geometry Codes" introducing an algorithm that allowed for the correction of errors beyond half the minimum distance of the code.<ref>{{Citation |first1=V. |last1=Guruswami |first2=M. |last2=Sudan |title=Improved decoding of Reed–Solomon codes and algebraic geometry codes |journal=[[IEEE Transactions on Information Theory]] |volume=45 |issue=6 |pages=1757&ndash;1767 |date=September 1999 |doi=10.1109/18.782097 |citeseerx=10.1.1.115.292 }}</ref> It applies to Reed–Solomon codes and more generally to [[algebraic geometric code]]s. This algorithm produces a list of codewords (it is a [[list-decoding]] algorithm) and is based on interpolation and factorization of polynomials over {{math|''GF''(2{{sup|''m''}})}} and its extensions.

In 2023, building on three exciting{{according to whom?|date=March 2025}} works,<ref>{{Cite book |last1=Brakensiek |first1=Joshua |last2=Gopi |first2=Sivakanth |last3=Makam |first3=Visu |chapter=Generic Reed-Solomon Codes Achieve List-Decoding Capacity |date=2023-06-02 |title=Proceedings of the 55th Annual ACM Symposium on Theory of Computing |chapter-url=https://doi.org/10.1145/3564246.3585128 |series=STOC 2023 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=1488–1501 |doi=10.1145/3564246.3585128 |isbn=978-1-4503-9913-5|arxiv=2206.05256 }}</ref><ref>{{Cite book |last1=Guo |first1=Zeyu |last2=Zhang |first2=Zihan |chapter=Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets |title=2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) |chapter-url=https://doi.org/10.1109/FOCS57990.2023.00019 |series=FOCS 2023, Santa Cruz, CA, USA, 2023 |date=2023 |pages=164–176 |doi=10.1109/FOCS57990.2023.00019 |isbn=979-8-3503-1894-4|arxiv=2304.01403 }}</ref><ref>{{Citation |last1=Alrabiah |first1=Omar |title=Randomly punctured Reed--Solomon codes achieve list-decoding capacity over linear-sized fields |date=2023-08-18 |arxiv=2304.09445 |last2=Guruswami |first2=Venkatesan |last3=Li |first3=Ray}}</ref> coding theorists showed that Reed-Solomon codes defined over random evaluation points can actually achieve [[list decoding]] capacity (up to {{math|''n'' - ''k''}} errors) over linear size alphabets with high probability. However, this result is combinatorial rather than algorithmic.{{Citation needed|date=March 2025}}