Singleton bound; p w </math>

Thursday, January 31st, 2008

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

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

Then:

<math>A_q(n,d) \leq q^{n-d+1}</math>


Proof

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

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

The new code has length

<math>n-(d-1)=n-d+1</math>

and thus has maximum possible size

<math>q^{n-d+1}</math>

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

<math>A_q(n,d) \leq q^{n-d+1}</math>


See also

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