Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 1 / 9G (Coding and Cryptography)

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.

Independence of individual bit errors gives $P=(1-p{)}^{4N}$. Independent retransmissions have a geometric distribution with success probability $P$, so the expected total number of transmissions, including the successful one, is $1/P$. At the supplied values, $P\approx 0.018279$ and $1/P\approx 54.71$.

A Hamming code decoder succeeds on a seven-bit block exactly when there are zero or one errors. Its radius-one decoding regions are disjoint, so an error of weight at least two cannot decode back to the original codeword. ThusNumerically $Q\approx 0.97929$, so only about $1.0212$ transmissions are expected. Even accounting for seven rather than four bits per letter, expected bits sent are $7N/Q\approx 7148$, compared with $4N/P\approx 218830$. The Hamming method is substantially better under the stated error detection and independent retransmission assumptions.