= Solution
Let $H$ be the $d\times(2^d-1)$ matrix whose columns are the distinct nonzero vectors of $\mathbb F_2^d$. The <Hamming code>[binary Hamming code] is
$$
C=\ker H.
$$
No column is zero and no two columns agree, so its minimum distance is three. A radius-one Hamming ball contains
$$
1+(2^d-1)=2^d
$$
words, while $|C|=2^{2^d-1-d}$. The radius-one balls about codewords are disjoint and their total size is $2^{2^d-1}$, so they partition the ambient space. Hence $C$ is a <perfectness of a Hamming code>[perfect code].
Let the received word be all ones except in the last coordinate. The sum of all nonzero vectors of $\mathbb F_2^d$ is zero for $d\geq2$, so its syndrome is the last column of $H$. Minimum-distance decoding therefore flips the last bit and returns the all-one word. A Hamming code corrects every single error because each nonzero syndrome identifies its unique erroneous coordinate.
Back to article page
