Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 2 / 12I (Coding and Cryptography)

The columns of the parity-check matrix of the binary Hamming code are precisely the $n=2^d-1$ distinct nonzero vectors of ${\mathbb{F}}_2^d$. If $h_1\ne h_2$, then $h_1+h_2$ is nonzero and differs from both summands, so it occurs as a unique third column $h_3$.

A word supported on three positions is a codeword exactly when the corresponding three columns sum to zero. Every unordered pair of columns determines one such triple, and each triple is counted once by each of its three pairs. Therefore

Sum all nonzero vectors of ${\mathbb{F}}_2^d$. In each coordinate, exactly $2^{d-1}$ vectors have entry one, which is even because $d>1$. The sum is therefore zero, soThus the all-one word belongs to the Hamming code and has Hamming weight $n$.

Adding the all-one codeword is a bijection from $C$ to itself, and it replaces every bit by its complement. It therefore sends weight $j$ to weight $n-j$, provingThe code has one word of weight zero and, since its minimum Hamming distance is three, no words of weight one or two. Combining this with part (i) gives