Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 2 / 3K (Coding and Cryptography)

The original binary Hamming code has parameters $[7,4,3]$, so it has $2^4=16$ codewords. Its minimum distance three makes the radius-one balls about its codewords disjoint. Each ball hasvectors, and $16\cdot 8=128=2^7$, the size of the ambient space. Equality in the Hamming bound therefore shows that these balls partition ${\mathbb{F}}_2^7$: the code is perfect.

The added bit is the overall parity bit. The original minimum-weight words have weight three, so they acquire a parity bit equal to one and have extended weight four. Every original even-weight difference keeps its weight, while every odd-weight difference gains one; hence the new minimum distance is four.

The minimum-distance error-detection and correction guarantee therefore says that the code detects three errors and corrects one error.

Yes, for a binary code. Correcting $e$ errors requires minimum distance at least $2e+1$. Apply the parity extension: append to each word the bit that makes its total weight even. Every odd distance increases by one and every even distance is unchanged, so the extended minimum distance is at least $2e+2$. It therefore detects every pattern of at most $2e+1$ errors.