Hamming's code is perfect How does one prove that Hamming's code is perfect (i.e. it is the 1-error correcting code that has the smallest possible size). I haven't found a complete proof using Google.
 A: Given an $e$-error-correcting code $C$ of length $n$ and over $\mathbb{F}_q$, the sphere packing bound asserts that spheres of radius $e$ centered at the codewords are disjoint.  Hence, we have the inequality $|C| \sum_{i=0}^e {n \choose i} (q-1)^i \le q^n$.  A code is perfect if equality holds in the sphere packing bound.
An $[n,k]_q$ Hamming code can be defined by its parity check matrix, which consists of $n$ vectors in $\mathbb{F}_q^k$ such that any two vectors are linearly independent and with $n$ maximum possible.  Hence, $n$ is the number of 1-dimensional subspaces in $\mathbb{F}_q^k$, ie $n=\frac{q^k-1}{q-1}$.
Since some three columns of the parity check matrix are linearly dependent (and any two columns are linearly independent), the Hamming code has minimum distance $3$ and hence is 1-error-correcting.  The union of all spheres of radius $1$ centered at the codewords contain $|C| (1+{n \choose 1}(q-1)) = q^{n-k} (1+\frac{q^k-1}{q-1} (q-1)) = q^{n-k} q^k = q^n$ codewords.  Because the sphere packing bound holds with equality for Hamming codes, the Hamming codes are perfect.
