In coding theory

Coding theory

Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...

, the Singleton bound, named after Richard Collom Singleton, is a relatively crude bound on the size of a block code

Block code

In coding theory, block codes refers to the large and important family of error-correcting codes that encode data in blocks.There is a vast number of examples for block codes, many of which have a wide range of practical applications...

  with block length , size and minimum distance .

Statement of the Bound

The minimum distance of a set of codewords of length is defined as
where is the Hamming distance

Hamming distance

In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...

 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

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

Hamming distance

In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...

 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

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.

Examples of non-trivial MDS codes include Reed-Solomon codes

Reed–Solomon error correction

In coding theory, Reed–Solomon codes are non-binary cyclic error-correcting codes invented by Irving S. Reed and Gustave Solomon. They described a systematic way of building codes that could detect and correct multiple random symbol errors...

 and their extended versions.

See also

• Gilbert–Varshamov bound
• Plotkin bound
  Plotkin bound
  In the mathematics of coding theory, the Plotkin bound, named after Morris Plotkin, is a bound on the maximum possible number of codewords in binary codes of given length n and given minimum distance d.- Statement of the bound :...
  
  
• Hamming bound
  Hamming bound
  In mathematics and computer science, in the field of coding theory, the Hamming bound is a limit on the parameters of an arbitrary block code: it is also known as the sphere-packing bound or the volume bound from an interpretation in terms of packing balls in the Hamming metric into the space of...
  
  
• Johnson bound
• Griesmer bound
  Griesmer bound
  In the mathematics of coding theory, the Griesmer bound, named after James Hugo Griesmer, is a bound on the length of binary codes of dimension k and minimum distance d.There is also a very similar version for non-binary codes....