Reed–Solomon Code
For every field Fb and k with 0 ≤ k ≤ b there is a linear orthogonal array with bk runs, b + 1 factors, strength k and minimum distance b + 2−k. In other words, it can be interpreted either as a linear OA(bk, b + 1, b, k) or as a linear [b + 1, k, b + 2−k]-code.
Construction of the Reed-Solomon Code
Let x1,…, xb denote the b elements of Fb. The Reed-Solomon code RS(n, b) for n = 0,…, b is given by
It is a linear [b, n, b−n + 1]-code as well as a linear OA(bn, b,Fb, n).
Reed-Solomon codes over a given field Fb 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 Fb(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 RSe(n, b) for n = 0,…, b is given by
where f (∞) denotes the coefficient of Xn−1 in f.
RSe(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. RSe(n, b) is a linear [b + 1, n, b−n + 2]-code as well as a linear OA(bn, 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.
RSe(0, b) is the [b + 1, 0, b + 2]-trivial code.
RSe(1, b) is the [b + 1, 1, b + 1]-repetition code.
RSe(2, b) is the [b + 1, 2, b]-Simplex code S(2, b).
RSe(b−1, b) has the same parameters as the [b + 1, b−1, 3]-Hamming code H(2, b).
RSe(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 Gustave 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: 2024-09-05.
http://mint.sbg.ac.at/desc_CReedSolomon.html