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 codes. For more about that proof, see: GV-linear-code.
Contents
Statement of the bound
Let
denote the maximum possible size of a q-ary code
Then:
Proof
Let
Then for all
since otherwise we could add x to the code whilst maintaining the code's minimum Hamming distance
Hence the whole of
Now each ball has size
since we may allow (or choose) up to
That is:
An improvement in the prime power case
For q a prime power, one can improve the bound to