(a) What does it mean to say that a binary code has length $n$, size $M$ and minimum distance d?

Let $A(n, d)$ be the largest value of $M$ for which there exists a binary $[n, M, d]$-code.

(i) Show that $A(n, 1)=2^{n}$.

(ii) Suppose that $n, d>1$. Show that if a binary $[n, M, d]$-code exists, then a binary $[n-1, M, d-1]$-code exists. Deduce that $A(n, d) \leqslant A(n-1, d-1)$.

(iii) Suppose that $n, d \geqslant 1$. Show that $A(n, d) \leqslant 2^{n-d+1}$.

(b) (i) For integers $M$ and $N$ with $0 \leqslant N \leqslant M$, show that

$$N(M-N) \leqslant\left\{\begin{array}{cl} M^{2} / 4, & \text { if } M \text { is even }, \\ \left(M^{2}-1\right) / 4, & \text { if } M \text { is odd } \end{array}\right.$$

For the remainder of this question, suppose that $C$ is a binary $[n, M, d]$-code. For codewords $x=\left(x_{1} \ldots x_{n}\right), y=\left(y_{1} \ldots y_{n}\right) \in C$ of length $n$, we define $x+y$ to be the word $\left(\left(x_{1}+y_{1}\right) \ldots\left(x_{n}+y_{n}\right)\right)$ with addition modulo $2 .$

(ii) Explain why the Hamming distance $d(x, y)$ is the number of 1 s in $x+y$.

(iii) Now we construct an $\left(\begin{array}{c}M \\ 2\end{array}\right) \times n$ array $A$ whose rows are all the words $x+y$ for pairs of distinct codewords $x, y$. Show that the number of $1 \mathrm{~s}$ in $A$ is at most

$$\begin{cases}n M^{2} / 4, & \text { if } M \text { is even } \\ n\left(M^{2}-1\right) / 4, & \text { if } M \text { is odd }\end{cases}$$

Show also that the number of $1 \mathrm{~s}$ in $A$ is at least $d\left(\begin{array}{c}M \\ 2\end{array}\right)$.

(iv) Using the inequalities derived in part(b) (iii), deduce that if $d$ is even and $n<2 d$ then

$$A(n, d) \leqslant 2\left\lfloor\frac{d}{2 d-n}\right\rfloor$$