Gilbert-Varshamov bound

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.

tatement of the bound

Let

:$$A_q(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 $$mathbb{F}_q of $$q elements).

Then:

:$$A_q(n,d) geq frac{q^n}{sum_{j=0}^{d-1} inom{n}{j}(q-1)^j}

For the q a prime power, one can improve the bound to $$A_q(n,d)ge q^k where k is the greatest integer for which $$A_q(n,d) geq frac{q^n}{sum_{j=0}^{d-2} inom{n-1}{j}(q-1)^j}

Proof

Let $$C be a code of length $$n and minimum Hamming distance $$d having maximal size:

:$$|C|=A_q(n,d).

Then for all $$xinmathbb{F}_q^n there exists at least one codeword $$c_x in C such that the Hamming distance $$d(x,c_x) between $$x and $$c_x satisfies

:$$d(x,c_x)leq d-1

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 $$mathbb{F}_q^n is contained in the union of all balls of radius $$d-1 having their centre at some $$c in C :

:$$mathbb{F}_q^n =cup_{c in C} B(c,d-1) .

Now each ball has size

:$$egin{matrix}sum_{j=0}^{d-1} inom{n}{j}(q-1)^j \end{matrix}

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 $$mathbb{F}_q^n). Hence we deduce

:$$egin{matrix}
mathbb{F}_q^n| & =& |cup_{c in C} B(c,d-1)| \\& leq& cup_{c in C} |B(c,d-1)| \\& = & |C|sum_{j=0}^{d-1} inom{n}{j}(q-1)^j \\end{matrix}

That is:

:$$egin{matrix}A_q(n,d) & geq & frac{q^n}{sum_{j=0}^{d-1} inom{n}{j}(q-1)^j} \end{matrix}

(using the fact: $$|mathbb{F}_q^n|=q^n).

ee also

*Singleton bound
*Hamming bound
*Johnson bound
*Plotkin bound