Gilbert–Varshamov Bound

A sphere-covering guarantee that good codes exist.

The idea

Theorem (Gilbert–Varshamov bound).

Over an alphabet of size $q$ there exists a code of length $n$ and minimum distance at least $d$ with at least $M \ge \frac{q^{n}}{V_q(n,\, d-1)}$ codewords, where $V_q(n, r) = \sum_{i=0}^{r} \binom{n}{i}(q-1)^{i}$ is the number of words in a Hamming ball of radius $r$.

Unlike a packing bound, which caps how large a code can be, this is an existence statement: it guarantees a code at least this large without constructing one.

The denominator is the number of words that a single codeword rules out, namely everything within distance $d - 1$ of it, the shaded balls in the figure. The bound is a guaranteed minimum, not the best possible: better codes at the same parameters often exist.

Ways to work on it

• Walkthrough. Ball volume, the bound, and the greedy existence proof.
• Practice. Compute the guaranteed code size for given parameters.
• Hardest. Build a ternary ball volume and certify an existence floor.

Not sure where to start? Take the ten-question placement test.