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>
