## Reed–Solomon Code

For every field **F**_{b} and *k* with 0 ≤ *k* ≤ *b* there is a linear orthogonal array with *b*^{k} runs, *b* + 1 factors, strength *k* and minimum distance *b* + 2−*k*. In other words, it can be interpreted either as a linear OA(*b*^{k}, *b* + 1, *b*, *k*) or as a linear [*b* + 1, *k*, *b* + 2−*k*]-code.

### Construction of the Reed-Solomon Code

Let *x*_{1},…, *x*_{b} denote the *b* elements of **F**_{b}. The Reed-Solomon code RS(*n*, *b*) for *n* = 0,…, *b* is given by

*n*,

*b*) := {(

*f*(

*x*

_{i}))

_{i=1,…, b}:

*f*∈

**F**

_{b}[

*X*] with deg

*f*<

*n*}.

It is a linear [*b*, *n*, *b*−*n* + 1]-code as well as a linear OA(*b*^{n}, *b*,**F**_{b}, *n*).

Reed-Solomon codes over a given field **F**_{b} are all subcodes of each other, i.e., we have RS(*n*, *b*) ⊂ RS(*n* + 1, *b*). The dual code of a Reed-Solomon code is again a Reed-Solomon code, namely RS(*n*, *b*)^{⊥} = RS(*b*−*n*, *b*).

Reed-Solomon codes can also be interpreted as algebraic-geometric codes defined by the rational function field **F**_{b}(*x*).

The Reed-Solomon code as an orthogonal array was first considered in [1], where the result on the minimum strength was established. That the same construction leads to a code with minimum distance *s*−*n* + 1 is due to [2].

### The Extended Reed-Solomon Code

The extended Reed-Solomon code RS_{e}(*n*, *b*) for *n* = 0,…, *b* is given by

_{e}(

*n*,

*b*) := {(

*f*(

*x*

_{1}),…,

*f*(

*x*

_{b}),

*f*(∞)) :

*f*∈

**F**

_{b}[

*X*]withdeg

*f*<

*n*},

where *f* (∞) denotes the coefficient of *X*^{n−1} in *f*.

RS_{e}(*n*, *b*) can also be obtained by extending RS(*n* – 1, *b*) ⊂ RS(*n*, *b*) with construction X and the [1, 1, 1]-code without redundancy. RS_{e}(*n*, *b*) is a linear [*b* + 1, *n*, *b*−*n* + 2]-code as well as a linear OA(*b*^{n}, *b* + 1, *b*, *n*).

Results for extended Reed-Solomon codes were established by [3], [4], and [5].

### Optimality

Reed-Solomon codes and extended Reed-Solomon codes meet the Singleton bound with equality, and are therefore MDS-codes. Viewed as an orthogonal array, they are OAs with index unity.

### Special Cases

RS(0,

*b*) is the [*b*, 0,*b*+ 1]-trivial code.RS(1,

*b*) is the [*b*, 1,*b*]-repetition code.RS(

*b*−1,*b*) is the [*b*,*b*−1, 2]-parity check code.RS(

*b*,*b*) is the [*b*,*b*, 1]-code without redundancy.RS

_{e}(0,*b*) is the [*b*+ 1, 0,*b*+ 2]-trivial code.RS

_{e}(1,*b*) is the [*b*+ 1, 1,*b*+ 1]-repetition code.RS

_{e}(2,*b*) is the [*b*+ 1, 2,*b*]-Simplex code S(2,*b*).RS

_{e}(*b*−1,*b*) has the same parameters as the [*b*+ 1,*b*−1, 3]-Hamming code H(2,*b*).RS

_{e}(*b*,*b*) has the same parameters as the [*b*+ 1,*b*, 2]-parity check code.

### See also

Generalization for arbitrary OOAs

Reed-Solomon codes can be generalized to algebraic-geometric codes by allowing a more general class of functions instead of polynomials.

[6, Chapter 4]

### References

[1] | Kenneth A. Bush. Orthogonal arrays of index unity. Annals of Mathematical Statistics, 13:426–434, 1952.MR0049146 (14,125b) |

[2] | Irving S. Reed and Gusatve Solomon. Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics, 8(2):300–304, 1960.doi:10.1137/0108018 |

[3] | J. K. Wolf. Adding two information symbols to certain nonbinary BCH codes and some applications. Bell System Technical Journal, 48:2405–2424, 1969. |

[4] | H. Tanaka and F. Nishida. A construction of a polynomial code. Electronics and Communications in Japan, 53-A(8):24–31, 1970. |

[5] | A. J. Gross. Some augmentations of Bose-Chaudhuri error correcting codes. In J. N. Srivastava, editor, A Survey of Combinatorial Theory, pages 209–216. North-Holland, 1973. |

[6] | Jürgen Bierbrauer.Introduction to Coding Theory.Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, London, New York, Washington D.C., 2004. MR2079734 (2005f:94001) |

### Copyright

Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.

Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Reed–Solomon Code.”
From MinT—the database of optimal net, code, OA, and OOA parameters.
Version: 2008-04-04.
http://mint.sbg.ac.at/desc_CReedSolomon.html