Singleton bound

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 distance d.

Let A_q(n,d) denote the maximum possible size of a q-ary code with length n (a q-ary code is a code over the field of q elements). Let the minimum Hamming distance between two codewords be d, i.e. for any distinct words w and w' in the code.

Then:

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}

Hence the original code shares the same bound on its size:

See also

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

Donate to Wikimedia