|This article needs additional citations for verification. (December 2009)|
In coding theory, the Gilbert–Varshamov bound (due to Edgar Gilbert and independently Rom Varshamov) is a limit 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 name "Gilbert–Varshamov bound" is by far the most popular. Varshamov proved this bound by using the probabilistic method for linear code. For more about that proof, see: GV-linear-code.
Statement of the bound
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 d – a contradiction on the maximality of .
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
(using the fact: ).
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
- Singleton bound
- Hamming bound
- Johnson bound
- Plotkin bound
- Griesmer bound
- Grey–Rankin bound
- Gilbert–Varshamov bound for linear code
- Elias-Bassalygo bound