Singleton bound

From Wikipedia, the free encyclopedia

The Singleton bound (named after RC Singleton) is a relatively crude bound on the size of a code C of length n, size r and minimum Hamming weight d.

Let

A_q(n,d)

denote the maximum possible size of a q-ary code with length n and minimum Hamming weight d (a q-ary code is a linear code over the field of q elements).

Then:

[edit] Proof

First observe that the maximum size r of a q-ary code of length n is qⁿ since each component of a given codeword may take one of q different values independently of all other components.

Let C be a q-ary code. Then clearly all codewords are distinct. If we delete the first d − 1 components of each codeword, then each resulting codeword must still be distinct since all codewords have Hamming distance at least d from each other. Thus the size r of the code is unchanged.

The new code has length

n − (d − 1) = n − d + 1

and thus has maximum possible size

q^{n − d + 1}

(by the argument presented in the first paragraph of the proof). Hence the original code shares the same bound on its size:

[edit] See also

• Gilbert-Varshamov bound
• Plotkin bound
• Hamming bound
• Johnson bound