Singleton Bound
Every orthogonal array OA(M, s, Sb, k) satisfies M ≥ bk, 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 N ≤ bs−d+1. For linear codes, this implies that every linear [s, n, d]-code over Fb satisfies n + d ≤ s + 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
Generalization for arbitrary OOAs
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: 2024-09-05.
http://mint.sbg.ac.at/desc_CBoundSingleton.html