Past exam of the mathematics course of the University of Cambridge / 2009 / ii / Paper 3 / 4H (Coding and Cryptography)

Use the binary Hamming code $C=\ker H\subset {\mathbb{F}}_2^{15}$, where the $j$th column $h_j$ of the $4\times 15$ parity-check matrix $H$ is the four-digit binary expansion of $j$, for $1\le j\le 15$. Thus the columns are precisely the nonzero vectors of ${\mathbb{F}}_2^4$. They include the four coordinate vectors, so $\mathrm{rank}H=4$ and $\dim C=15-4=11$. Its code rate is therefore $\boxed{11/15}$.

For a received word $y$, compute its syndrome $s=Hy$. If $s=0$, report no error. Otherwise identify the unique column $h_j=s$ and flip bit $j$. Indeed, if $y=c+e_j$ with $c\in C$, then $Hy=Hc+H{e}_j=h_j$, so this procedure recovers $c$ exactly. No column is zero and no two columns coincide; hence no nonzero codeword has Hamming weight one or two. Some three columns sum to zero, for example those indexed by $1,2,3$, so the minimum distance is exactly three. Thus every single-bit error is corrected. The assertion requires at most one error; arbitrary multiple errors need not be detected by this procedure.