Extended Reed–Solomon Code

For every field Fb and k with 0 ≤ kb 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

RS(n, b) := {(f (xi))i=1,…, b  :  fFb[X] with deg f < n}.

It is a linear [b, n, bn + 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(bn, 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 sn + 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

RSe(n, b) := {(f (x1),…, f (xb), f (∞))  :  fFb[X]withdeg f < n},

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, bn + 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

See also

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. “Extended 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-extended.html

Show usage of this method