Gilbert–Varshamov bound

In coding theory, the Gilbert–Varshamov bound (due to Edgar Gilbert[1] and independently Rom Varshamov[2]) is a bound on the size of a (not necessarily linear) code. It is occasionally known as the Gilbert–Shannon–Varshamov bound (or the GSV bound), but the name "Gilbert–Varshamov bound" is by far the most popular. Varshamov proved this bound by using the probabilistic method for linear codes. For more about that proof, see Gilbert–Varshamov bound for linear codes.

Statement of the bound

edit

Recall that a code has a minimum distance   if any two elements in the code are at least a distance   apart. Let

 

denote the maximum possible size of a q-ary code   with length n and minimum Hamming distance d (a q-ary code is a code over the field   of q elements).

Then:

 

Proof

edit

Let   be a code of length   and minimum Hamming distance   having maximal size:

 

Then for all   , there exists at least one codeword   such that the Hamming distance   between   and   satisfies

 

since otherwise we could add x to the code whilst maintaining the code's minimum Hamming distance   – a contradiction on the maximality of  .

Hence the whole of   is contained in the union of all balls of radius   having their centre at some   :

 

Now each ball has size

 

since we may allow (or choose) up to   of the   components of a codeword to deviate (from the value of the corresponding component of the ball's centre) to one of   possible other values (recall: the code is q-ary: it takes values in  ). Hence we deduce

 

That is:

 

An improvement in the prime power case

edit

For q a prime power, one can improve the bound to   where k is the greatest integer for which

 

See also

edit

References

edit
  1. ^ Gilbert, E. N. (1952), "A comparison of signalling alphabets", Bell System Technical Journal, 31 (3): 504–522, doi:10.1002/j.1538-7305.1952.tb01393.x.
  2. ^ Varshamov, R. R. (1957), "Estimate of the number of signals in error correcting codes", Dokl. Akad. Nauk SSSR, 117: 739–741.