Editing Reed–Solomon error correction (section)

==Properties==

The Reed–Solomon code is a [''n'', ''k'', ''n'' &minus; ''k'' + 1] code; in other words, it is a [[linear code|linear block code]] of length ''n'' (over ''F'') with [[Dimension (vector space)|dimension]] ''k'' and minimum [[Hamming distance]] <math display="inline">d_{\min} = n-k+1.</math> The Reed–Solomon code is optimal in the sense that the minimum distance has the maximum value possible for a linear code of size (''n'',&nbsp;''k''); this is known as the [[Singleton bound]]. Such a code is also called a [[MDS code|maximum distance separable (MDS) code]].

The error-correcting ability of a Reed–Solomon code is determined by its minimum distance, or equivalently, by <math>n - k</math>, the measure of redundancy in the block. If the locations of the error symbols are not known in advance, then a Reed–Solomon code can correct up to <math>(n-k)/2</math> erroneous symbols, i.e., it can correct half as many errors as there are redundant symbols added to the block. Sometimes error locations are known in advance (e.g., "side information" in [[demodulator]] [[signal-to-noise ratio]]s)—these are called [[Erasure channel|erasures]]. A Reed–Solomon code (like any [[Maximum distance separable code|MDS code]]) is able to correct twice as many erasures as errors, and any combination of errors and erasures can be corrected as long as the relation {{math|2''E'' + ''S'' ≤ ''n'' &minus; ''k''}} is satisfied, where <math>E</math> is the number of errors and <math>S</math> is the number of erasures in the block.

[[File:RS BER.png|400px|right|thumb| Theoretical BER performance of the Reed-Solomon code (N=255, K=233, QPSK, AWGN). Step-like characteristic.]]

The theoretical error bound can be described via the following formula for the [[Additive white Gaussian noise|AWGN]] channel for [[Frequency-shift keying|FSK]]:<ref>{{Cite web |url=https://www.mathworks.com/help/comm/ug/bit-error-rate-ber.html#brck0zf |title=Analytical Expressions Used in bercoding and BERTool |access-date=2019-02-01 |archive-date=2019-02-01 |archive-url=https://web.archive.org/web/20190201172027/https://www.mathworks.com/help/comm/ug/bit-error-rate-ber.html#brck0zf |url-status=live }}</ref>
<math display="block">P_b \approx \frac{2^{m-1}}{2^m-1}\frac{1}{n}\sum_{\ell=t+1}^n \ell {n\choose \ell}P_s^\ell(1-P_s)^{n-\ell}</math>
and for other modulation schemes:
<math display="block">P_b \approx \frac{1}{m}\frac{1}{n}\sum_{\ell=t+1}^n \ell {n\choose \ell} P_s^\ell(1-P_s)^{n-\ell}</math>
where <math display="inline">t = \frac{1}{2}(d_{\min}-1)</math>, <math>P_s = 1-(1-s)^h</math>, <math>h = \frac{m}{\log_2M}</math>, <math>s</math> is the symbol error rate in uncoded AWGN case and <math>M</math> is the modulation order.

For practical uses of Reed–Solomon codes, it is common to use a finite field <math>F</math> with <math>2^m</math> elements. In this case, each symbol can be represented as an <math>m</math>-bit value.
The sender sends the data points as encoded blocks, and the number of symbols in the encoded block is <math>n = 2^m - 1</math>. Thus a Reed–Solomon code operating on 8-bit symbols has <math>n = 2^8 - 1 = 255</math> symbols per block. (This is a very popular value because of the prevalence of [[byte-oriented]] computer systems.) The number <math>k</math>, with <math>k < n</math>, of ''data'' symbols in the block is a design parameter. A commonly used code encodes <math>k = 223</math> eight-bit data symbols plus 32 eight-bit parity symbols in an <math>n = 255</math>-symbol block; this is denoted as a <math>(n, k) = (255,223)</math> code, and is capable of correcting up to 16 symbol errors per block.

The Reed–Solomon code properties discussed above make them especially well-suited to applications where errors occur in [[burst error|burst]]s. This is because it does not matter to the code how many bits in a symbol are in error — if multiple bits in a symbol are corrupted it only counts as a single error. Conversely, if a data stream is not characterized by error bursts or drop-outs but by random single bit errors, a Reed–Solomon code is usually a poor choice compared to a binary code.

The Reed–Solomon code, like the [[convolutional code]], is a transparent code. This means that if the channel symbols have been [[bitwise NOT|inverted]] somewhere along the line, the decoders will still operate. The result will be the inversion of the original data. However, the Reed–Solomon code loses its transparency when the code is shortened (''see 'Remarks' at the end of this section''). The "missing" bits in a shortened code need to be filled by either zeros or ones, depending on whether the data is complemented or not. (To put it another way, if the symbols are inverted, then the zero-fill needs to be inverted to a one-fill.) For this reason it is mandatory that the sense of the data (i.e., true or complemented) be resolved before Reed–Solomon decoding.

Whether the Reed–Solomon code is [[cyclic code|cyclic]] or not depends on subtle details of the construction. In the original view of Reed and Solomon, where the codewords are the values of a polynomial, one can choose the sequence of evaluation points in such a way as to make the code cyclic. In particular, if <math>\alpha</math> is a [[primitive root modulo n|primitive root]] of the field <math>F</math>, then by definition all non-zero elements of <math>F</math> take the form <math>\alpha^i</math> for <math>i\in\{1,\dots,q-1\}</math>, where <math>q=|F|</math>. Each polynomial <math>p</math> over <math>F</math> gives rise to a codeword <math>(p(\alpha^1),\dots,p(\alpha^{q-1}))</math>. Since the function <math>a \mapsto p(\alpha a)</math> is also a polynomial of the same degree, this function gives rise to a codeword <math>(p(\alpha^2),\dots,p(\alpha^{q}))</math>; since <math>\alpha^{q}=\alpha^1</math> holds, this codeword is the [[circular shift|cyclic left-shift]] of the original codeword derived from <math>p</math>. So choosing a sequence of primitive root powers as the evaluation points makes the original view Reed–Solomon code [[cyclic code|cyclic]]. Reed–Solomon codes in the BCH view are always cyclic because [[BCH code#Properties|BCH codes are cyclic]].

===Remarks===

Designers are not required to use the "natural" sizes of Reed–Solomon code blocks. A technique known as "shortening" can produce a smaller code of any desired size from a larger code. For example, the widely used (255,223) code can be converted to a (160,128) code by padding the unused portion of the source block with 95 binary zeroes and not transmitting them. At the decoder, the same portion of the block is loaded locally with binary zeroes.

The QR code, Ver 3 (29×29) uses interleaved blocks. The message has 26 data bytes and is encoded using two Reed-Solomon code blocks. Each block is a (255,233) Reed Solomon code shortened to a (35,13) code.

The Delsarte–Goethals–Seidel<ref>{{Citation |first1=Florian |last1=Pfender |first2=Günter M. |last2=Ziegler |title=Kissing Numbers, Sphere Packings, and Some Unexpected Proofs |journal=Notices of the American Mathematical Society |volume=51 |issue=8 |pages=873&ndash;883 |date=September 2004 |url=https://www.ams.org/notices/200408/fea-pfender.pdf |access-date=2009-09-28 |archive-date=2008-05-09 |archive-url = https://web.archive.org/web/20080509183217/http://www.ams.org/notices/200408/fea-pfender.pdf |url-status=live }}. Explains the Delsarte-Goethals-Seidel theorem as used in the context of the error correcting code for [[compact disc]].</ref> theorem illustrates an example of an application of shortened Reed–Solomon codes. In parallel to shortening, a technique known as [[Punctured code|puncturing]] allows omitting some of the encoded parity symbols.