Jump to content

User:ECCclass/Singleton

From Wikipedia, the free encyclopedia

In coding theory, the Singleton bound, named after R.C. Singleton, is a relatively crude bound on the size of a block code with block length , size and minimum distance .

Statement of the Bound[edit]

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

Proof[edit]

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 :

MDS codes[edit]

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.[1]

Examples of non-trivial MDS codes include Reed-Solomon codes and their extended versions.[2]

See also[edit]

Notes[edit]

  1. ^ see e.g. Vermani (1996), Proposition 9.2.
  2. ^ see e.g. MacWilliams and Sloane, Ch. 11.

References[edit]

  • R.C. Singleton (1964). "Maximum distance q-nary codes". IEEE Trans. Inf. Theory. 10: 116–118. doi:10.1109/TIT.1964.1053661.

Further reading