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

Let Aq(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. \textrm D_H(w,w')\ge d for any distinct words w and w' in the code.

Then:

A_q(n,d) \leq q^{n-d+1}

[edit] Proof

First observe that the maximum size r of a q-ary code of length n is qn 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 c \in C 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

qn − d + 1

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

A_q(n,d) \leq q^{n-d+1}

[edit] See also