Singleton Bound

Every orthogonal array OA(M, s, Sb, k) satisfies Mbk, which follows directly from the definition of orthogonal arrays. Therefore the index λ = M/bk = bt must be ≥ 1 and t must be non-negative.

The dual result for codes is less obvious and is known as Singleton bound [1]. It states that every (s, N, d)-code over Fb satisfies Nbs−d+1. For linear codes, this implies that every linear [s, n, d]-code over Fb satisfies n + ds + 1.

Codes and Orthogonal Arrays Meeting the Singleton Bound

Codes meeting the Singleton bound with equality are traditionally called maximum distance separable codes or MDS-codes. The dual of a linear MDS-code is a linear orthogonal array with index unity.

The most important class of MDS-codes are extended Reed-Solomon codes and the codes obtained from the hyperoval as well as codes obtained from them by truncation. However, codes without redundancy (minimum distance d = 1), parity check codes (minimum distance d = 2), repetition codes (minimum distance d = s), and trivial codes (minimum distance d = s + 1) are also MDS-codes.

The MDS-code conjecture states that no other MDS-codes exist.

See also

References

[1]Richard C. Singleton.
Maximum distance q-nary codes.
IEEE Transactions on Information Theory, 10(2):116–118, April 1964.
[2]F. Jessie MacWilliams and Neil J. A. Sloane.
The Theory of Error-Correcting Codes.
North-Holland, Amsterdam, 1977.
[3]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. “Singleton Bound.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2008-04-04. http://mint.sbg.ac.at/desc_CBoundSingleton.html

Show usage of this method