Past exam of the mathematics course of the University of Cambridge / 2008 / ii / Paper 3 / 4G / Solution

One choice of the Hamming code of length seven is the linear mapover ${\mathbb{F}}_2$. Its image is the kernel of the parity-check matrixIndeed $Hh(a,b,c,d{)}^T=0$, the encoder is injective because positions $3,5,6,7$ recover its inputs, and $H$ has rank three. Its columns are nonzero and pairwise distinct. Hence no nonzero codeword has Hamming weight one or two. The word $h(1,0,0,0)=(1,1,1,0,0,0,0)$ has weight three, proving that the minimum Hamming distance is three.

If $r=h(a,b,c,d)+e_j$ is received with one erroneous bit, its syndrome $H{r}^T$ is column $j$ of $H$. These seven columns are distinct, so the syndrome identifies the bit to flip. A zero syndrome indicates no error under the assumption of at most one error.

For the extended Hamming code, append ${\sum }_{j=1}^7{h}_j=a+b+c$. Every extended codeword has even weight. Since every original nonzero word has weight at least three, its extended weight is at least four; the weight-three example attains four. ThusThe minimum-distance error-detection and correction guarantee gives detection of up to three errors and correction of one error. Detection here means rejecting a word outside the code, rather than simultaneously identifying and correcting every detected pattern; the usual combined decoder corrects single errors and flags double errors.