Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 1 / 9G / Solution

For $r\ge 2$, let $H$ be the $r\times (2^r-1)$ binary matrix whose columns are all distinct nonzero vectors of ${\mathbb{F}}_2^r$. The binary Hamming code is $C=\ker H$. Its parity-check matrix has rank $r$ since its columns include the standard basis. Hence $C$ is linear of length $2^r-1$ and dimension $2^r-1-r$.

No word of weight one or two lies in $C$, since columns are nonzero and distinct; three columns $u,v,u+v$ sum to zero, so the minimum distance of a code is exactly three. The syndrome of a single-bit error is its column of $H$, uniquely identifying the erroneous position. The $2^r$ possible syndromes correspond to no error or exactly one of $2^r-1$ single-bit errors. Alternatively, every radius-one Hamming ball has $2^r$ words andDisjoint balls therefore cover the whole word space. This proves linearity, one-error correction and perfection. For $r=3$, the parameters are $[7,4,3]$, giving the 16 messages needed below.