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:

:

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

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

:

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

:
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:

:

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

ee also

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