Past exam of the mathematics course of the University of Cambridge / 2006 / ii / Paper 3 / 4G / Solution

A binary block code is a subset $C\subseteq \{0,1{\}}^n$; its length is the common word length $n$, its size is $m=|C|$, and its minimum distance is the least Hamming distance between distinct words. There are $V(n,r)={\sum }_{j=0}^r\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ words in a radius-$r$ Hamming ball, since one chooses the positions to change.

Put $t=\lfloor (d-1)/2\rfloor$. Two radius-$t$ Hamming balls about different codewords cannot meet: otherwise the triangle inequality would make their centres at distance at most $2t<d$. Comparing their combined size with $2^n$ gives the Hamming boundFor the other direction, start with one word and repeatedly add any word at distance at least $d$ from every word already selected. Finiteness ensures that this process stops. At that point the radius-$(d-1)$ Hamming balls cover the entire cube; an uncovered word could otherwise be added. These balls may overlap, but their total size is at least $2^n$. This gives the Gilbert–Varshamov bound