Gilbert-Varshamov bound
From Wikipedia, the free encyclopedia
The Gilbert-Varshamov bound is a bound on the parameters of a (not necessarily linear) code. It is occasionally known as the Gilbert-Shannon-Varshamov bound (or the GSV bound), but the Gilbert-Varshamov bound is by far the most popular name.
[edit] Statement of the bound
Let
- Aq(n,d)
denote the maximum possible size of a q-ary code C with length n and minimum Hamming weight d (a q-ary code is a code over the field 
of q elements).
Then:
For the q a prime power, one can improve the bound to 
where k is the greatest integer for which 
[edit] Proof
Let C be a code of length n and minimum Hamming distance d having maximal size:
- | C | = Aq(n,d).
Then for all 
there exists a codeword 
such that the Hamming distance d(x,c) between x and c satisfies
since otherwise we could add x to the code whilst maintaining the code's minimum Hamming distance d - a contradiction on the maximality of | C | .
Hence the whole of is contained in the union of all balls of radius d − 1 having their centre at some :
.
Now each ball has size
since we may allow (or choose) up to d − 1 of the n components of a codeword to deviate (from the value of the corresponding component of the ball's centre) to one of (q − 1) possible other values (recall: the code is q-ary: it takes values in ). Hence we deduce
That is:
(using the fact: 
).
