Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 1 / 11I / a

A binary block code of length $n$ is a subset $C\subseteq {\mathbb{F}}_2^n$. Its size is $M=|C|$, and its minimum Hamming distance isThus an $[n,M,d]$ code consists of $M$ binary words of length $n$ whose distinct pairs differ in at least $d$ coordinates. When $d=1$, every set of distinct words qualifies. Taking all of the binary vector space ${\mathbb{F}}_2^n$ gives $2^n$ words, and no code can contain more words than its ambient space. Hence

Form the punctured code by deleting one fixed coordinate from every codeword. Two distinct original words differ in at least $d>1$ positions, so after one deletion they still differ and cannot coalesce. The new code therefore retains size $M$, while every pairwise Hamming distance falls by at most one. It is an $[n-1,M,d^{\prime }]$ code with $d^{\prime }\ge d-1$, and hence also an $[n-1,M,d-1]$ code in the minimum-distance-at-least convention. Therefore

Iterate the puncturing inequality from part (ii) $d-1$ times and then use part (i):This is the binary Singleton bound: