MinT - Extended Reed–Solomon Code

Extended 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₁,…, x_b denote the b elements of F_b. The Reed-Solomon code RS(n, b) for n = 0,…, b is given by

RS(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ⁿ, 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

RS_e(n, b) := {(f (x₁),…, f (x_b), f (∞)) : f ∈ F_b[X]withdeg f < n},

where f (∞) denotes the coefficient of Xⁿ⁻¹ 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ⁿ, 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.

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. “Extended Reed–Solomon Code.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. http://mint.sbg.ac.at/desc_CReedSolomon-extended.html

Show usage of this method