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

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^n$ of $q$ elements).

Then:

$\begin{matrix} \\ A_q(n,d) \geq \frac{q^n}{\sum_{k=0}^{d-1} \binom{n}{k}(q-1)^k} \\ \\ \end{matrix}$

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_{k=0}^{d-2} \binom{n-1}{k}(q-1)^k}$

[edit] 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 $x\in\mathbb{F}_q^n$ there exists a codeword $c \in C$ such that the Hamming distance $d (x, c)$ between $x$ and $c$ satisfies

$d(x,c)\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 \subset \cup_{c \in C} B(c,d-1)$ .

Now each ball has size

$\begin{matrix} \sum_{k=0}^{d-1} \binom{n}{k}(q-1)^k \\ \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

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