Gilbert–Varshamov bound


In coding theory, the Gilbert–Varshamov bound is a limit on the parameters of a code. It is occasionally known as the Gilbert–Shannon–Varshamov 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

Let
denote the maximum possible size of a q-ary code with length n and minimum Hamming distance d.
Then:

Proof

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 up to of the components of a codeword to deviate to one of possible other values. Hence we deduce
That is:

An improvement in the prime power case

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