# 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.

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.