## Singleton Bound

Every orthogonal array OA(*M*, *s*, *S*_{b}, *k*) satisfies *M* ≥ *b*^{k}, which follows directly from the definition of orthogonal arrays. Therefore the index *λ* = *M*/*b*^{k} = *b*^{t} 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 **F**_{b} satisfies *N* ≤ *b*^{s−d+1}. For linear codes, this implies that every linear [*s*, *n*, *d*]-code over **F**_{b} 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: 2008-04-04.
http://mint.sbg.ac.at/desc_CBoundSingleton.html