= Solution
For $r\geq2$, 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 and
$$
|C|\,2^r=2^{2^r-1-r}2^r=2^{2^r-1}.
$$
Disjoint balls therefore cover the whole word space. This proves \b[linearity, one-error correction and perfection]. For $r=3$, the parameters are $[7,4,3]$, giving the 16 messages needed below.
Back to article page
