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.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
