Statement of the Bound
The minimum distance of a set of codewords of length is defined as
where is the Hamming distance between and . The expression represents the maximum number of possible codewords in a q-ary block code of length and minimum distance .
Then the Singleton bound states that
First observe that there are many q-ary words of length , since each letter in such a word may take one of different values, independently of the remaining letters.
Now let be an arbitrary q-ary block code of minimum distance . Clearly, all codewords are distinct. If we delete the first letters of each codeword, then all resulting codewords must still be pairwise different, since all original codewords in have Hamming distance at least from each other. Thus the size of the code remains unchanged.
The newly obtained codewords each have length
and thus there can be at most
of them. Hence the original code shares the same bound on its size :
Block codes that achieve equality in Singleton bound are called MDS (maximum distance separable) codes. Examples of such codes include codes that have only one codeword (minimum distance n), codes that use the whole of (minimum distance 1), codes with a single parity symbol (minimum distance 2) and their dual codes. These are often called trivial MDS codes.
In the case of binary alphabets, only trivial MDS codes exist.
- see e.g. Vermani (1996), Proposition 9.2.
- see e.g. MacWilliams and Sloane, Ch. 11.
- R.C. Singleton (1964). "Maximum distance q-nary codes". IEEE Trans. Inf. Theory 10 (2): 116–118. doi:10.1109/TIT.1964.1053661.
- J.H. van Lint (1992). Introduction to Coding Theory. GTM 86 (2nd ed.). Springer-Verlag. p. 61. ISBN 3-540-54894-7.
- F.J. MacWilliams; N.J.A. Sloane (1977). The Theory of Error-Correcting Codes. North-Holland. pp. 33,37. ISBN 0-444-85193-3.
- Niederreiter, Harald; Xing, Chaoping (2001). "6. Applications to algebraic coding theory". Rational points on curves over finite fields. Theory and Applications. London Mathematical Society Lecture Note Series 285. Cambridge: Cambridge University Press. ISBN 0-521-66543-4. Zbl 0971.11033.
- L. R. Vermani: Elements of algebraic coding theory, Chapman & Hall, 1996.