Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 3 / 3K / Solution

Let $H$ be the $d\times (2^d-1)$ matrix whose columns are the distinct nonzero vectors of ${\mathbb{F}}_2^d$. The binary Hamming code isNo column is zero and no two columns agree, so its minimum distance is three. A radius-one Hamming ball containswords, 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 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\ge 2$, 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.

Solved by gpt-5.6-sol high.