Editing Reed–Solomon error correction (section)

==History==
Reed–Solomon codes were developed in 1960 by [[Irving S. Reed]] and [[Gustave Solomon]], who were then staff members of [[MIT Lincoln Laboratory]]. Their seminal article was titled "Polynomial Codes over Certain Finite Fields".<ref name="ReedSolomon"/> The original encoding scheme described in the Reed and Solomon article used a variable polynomial based on the message to be encoded where only a fixed set of values (evaluation points) to be encoded are known to encoder and decoder. The original theoretical decoder generated potential polynomials based on subsets of ''k'' (unencoded message length) out of ''n'' (encoded message length) values of a received message, choosing the most popular polynomial as the correct one, which was impractical for all but the simplest of cases. This was initially resolved by changing the original scheme to a [[BCH code|BCH-code]]-like scheme based on a fixed polynomial known to both encoder and decoder, but later, practical decoders based on the original scheme were developed, although slower than the BCH schemes. The result of this is that there are two main types of Reed–Solomon codes: ones that use the original encoding scheme and ones that use the BCH encoding scheme.

Also in 1960, a practical fixed polynomial decoder for [[BCH codes]] developed by [[Daniel Gorenstein]] and Neal Zierler was described in an [[MIT Lincoln Laboratory]] report by Zierler in January 1960 and later in an article in June 1961.<ref>{{cite journal |first1=D. |last1=Gorenstein |first2=N. |last2=Zierler |title=A class of cyclic linear error-correcting codes in ''p<sup>m</sup>'' symbols |journal=J. SIAM |volume=9 |issue=2 |pages=207–214 |date=June 1961 |doi=10.1137/0109020 |jstor=2098821}}</ref> The Gorenstein–Zierler decoder and the related work on BCH codes are described in a book "Error-Correcting Codes" by [[W. Wesley Peterson]] (1961).<ref name="Peterson61">{{cite book |first=W. Wesley |last=Peterson |title=Error-Correcting Codes |publisher=MIT Press |date=1961 |oclc=859669631 |isbn=978-0262160063 }}</ref>{{page needed|date=March 2025}} By 1963 (or possibly earlier), J.J. Stone (and others){{who?|date=March 2025}} recognized that Reed–Solomon codes could use the BCH scheme of using a fixed generator polynomial, making such codes a special class of BCH codes,<ref name="Peterson96">{{cite book |first1=W. Wesley |last1=Peterson |first2=E. J. |last2=Weldon |title=Error Correcting Codes |publisher=MIT Press |location= |date=1996 |isbn=978-0-585-30709-1 |oclc=45727875 |url={{GBurl|5kfwlFeklx0C|dq=9780262160391|pg=PP11}} |edition=2nd |orig-year=1972 }}</ref> but Reed–Solomon codes based on the original encoding scheme are not a class of BCH codes, and depending on the set of evaluation points, they are not even [[cyclic code]]s.

In 1969, an improved BCH scheme decoder was developed by [[Elwyn Berlekamp]] and [[James Massey]] and has since been known as the [[Berlekamp–Massey algorithm|Berlekamp–Massey decoding algorithm]].

In 1975, another improved BCH scheme decoder was developed by Yasuo Sugiyama, based on the [[extended Euclidean algorithm]].<ref>{{cite journal |last1=Sugiyama |first1=Y. |last2=Kasahara |first2=M. |last3=Hirasawa |first3=S. |last4=Namekawa |first4=T. |title=A method for solving key equation for decoding Goppa codes |journal=Information and Control |volume=27 |issue=1 |pages=87–99 |date=1975 |doi=10.1016/S0019-9958(75)90090-X |doi-access=free }}</ref>

[[File:DVB-vs-DVB-X2.png|thumb|350px]]

In 1977, Reed–Solomon codes were implemented in the [[Voyager program]] in the form of [[concatenated error correction code]]s. The first commercial application in mass-produced consumer products appeared in 1982 with the [[compact disc]], where two [[forward error correction#Interleaving|interleaved]] Reed–Solomon codes are used. Today, Reed–Solomon codes are widely implemented in [[Data storage device|digital storage]] devices and [[Data transmission|digital communication]] standards, though they are being slowly replaced by [[BCH code|Bose–Chaudhuri–Hocquenghem (BCH) codes]]. For example, Reed–Solomon codes are used in the [[Digital Video Broadcasting]] (DVB) standard [[DVB-S]], in conjunction with a [[convolutional coding|convolutional]] [[inner code]], but BCH codes are used with [[Low-density parity-check code|LDPC]] in its successor, [[DVB-S2]].

In 1986, an original scheme decoder known as the [[Berlekamp–Welch algorithm]] was developed.

In 1996, variations of original scheme decoders called list decoders or soft decoders were developed by Madhu Sudan and others, and work continues on these types of decoders (see [[Guruswami–Sudan list decoding algorithm]]).

In 2002, another original scheme decoder was developed by Shuhong Gao, based on the [[extended Euclidean algorithm]].<ref name="gao">{{Citation
 |last= Gao
 |first= Shuhong
 |title= New Algorithm For Decoding Reed-Solomon Codes
 |date= January 2002
 |url= http://www.math.clemson.edu/~sgao/papers/RS.pdf
 |publisher= Clemson
 }}.</ref>