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

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:

Complete the square:If $M$ is even, an integer $N$ can equal $M/2$, giving the maximum $M^2/4$. If $M$ is odd, every integer $N$ is at least $1/2$ from $M/2$, giving the maximum $(M^2-1)/4$. Thus

At coordinate $j$, addition in ${\mathbb{F}}_2$ gives $x_j+y_j=1$ exactly when $x_j\ne y_j$. Therefore the number of ones in $x+y$ is exactly the number of coordinates in which the two words differ:

For column $j$, let $N_j$ of the $M$ codewords have a one. A pair contributes a one in that column exactly when one word is chosen from those $N_j$ words and the other from the remaining $M-N_j$. Hence column $j$ containsones among all pairwise sums. Part (i), summed over the $n$ columns, gives the upper boundThere are $\left(\genfrac{}{}{0ex}{}{M}{2}\right)$ rows, one for each unordered pair of codewords. By part (ii), every row has weight equal to that pair's distance, which is at least $d$. Therefore

Put $q=2d-n>0$. If $M$ is even, part (iii) givessoBecause $M$ is even,

If $M$ is odd, part (iii) instead givesCancelling $M-1$ yields $qM\le n=2d-q$, and thereforeSince $M$ is an integer, the same desired upper bound follows. Thus the binary Plotkin bound is