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 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:

[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}

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

[edit] MDS codes

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 (F_q)ⁿ (minimum distance 1) and codes with a single parity symbol (minimum distance 2). These are often called trivial MDS codes.

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

[edit] See also

[edit] References