Gilbert–Varshamov bound

Let

${\displaystyle A_{q}(n,d)}$

denote the maximum possible size of a q-ary code ${\displaystyle C}$ with length n and minimum Hamming distance d (a q-ary code is a code over the field ${\displaystyle \mathbb {F} _{q}}$ of q elements).

Then:

${\displaystyle A_{q}(n,d)\geqslant {\frac {q^{n}}{\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}}.}$

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

${\displaystyle |C|=A_{q}(n,d).}$

Then for all ${\displaystyle x\in \mathbb {F} _{q}^{n}}$ , there exists at least one codeword ${\displaystyle c_{x}\in C}$ such that the Hamming distance ${\displaystyle d(x,c_{x})}$ between ${\displaystyle x}$ and ${\displaystyle c_{x}}$ satisfies

${\displaystyle d(x,c_{x})\leqslant d-1}$

since otherwise we could add x to the code whilst maintaining the code's minimum Hamming distance ${\displaystyle d}$ – a contradiction on the maximality of ${\displaystyle |C|}$.

Hence the whole of ${\displaystyle \mathbb {F} _{q}^{n}}$ is contained in the union of all balls of radius ${\displaystyle d-1}$ having their centre at some ${\displaystyle c\in C}$ :

${\displaystyle \mathbb {F} _{q}^{n}=\bigcup _{c\in C}B(c,d-1).}$

Now each ball has size

${\displaystyle \sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}$

since we may allow (or choose) up to ${\displaystyle d-1}$ of the ${\displaystyle n}$ components of a codeword to deviate (from the value of the corresponding component of the ball's centre) to one of ${\displaystyle (q-1)}$ possible other values (recall: the code is q-ary: it takes values in ${\displaystyle \mathbb {F} _{q}^{n}}$). Hence we deduce

${\displaystyle q^{n}=\left|\mathbb {F} _{q}^{n}\right|=\left|\bigcup _{c\in C}B(c,d-1)\right|\leqslant \sum _{c\in C}|B(c,d-1)|=|C|\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}$

That is:

${\displaystyle A_{q}(n,d)=|C|\geqslant {\frac {q^{n}}{\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}}.}$

For q a prime power, one can improve the bound to ${\displaystyle A_{q}(n,d)\geq q^{k}}$ where k is the greatest integer for which

${\displaystyle q^{k}<{\frac {q^{n}}{\sum _{j=0}^{d-2}{\binom {n-1}{j}}(q-1)^{j}}}.}$

• Singleton bound
• Hamming bound
• Johnson bound
• Plotkin bound
• Griesmer bound
• Grey–Rankin bound
• Gilbert–Varshamov bound for linear codes
• Elias-Bassalygo bound