The Singleton bound is often the strongest bound for codes over a large alphabet, but for a binary $(2 d, M, d)$ -code it only gives the bound $M \leq 2^{d+1}$. The following result leads to a stronger bound on $A_{2}(2 d, d)$.
Plotkin bound. Let $n, d \in \mathbb{N}$ be such that $2 d>n$. Then
$$
A_{2}(n, d) \leq \frac{2 d}{2 d-n}
$$
The proof of this bound is non-examinable. For example, taking $n=8$ and $d=5$ we get
$$
A_{2}(8,5) \leq 10 /(10-8)=5
$$
$A_{2}(8,5)=4$ so the Plotkin bound comes close to the strongest possible result. In other cases the Plotkin bound is sharp.
Exercise Use the Plotkin bound to prove that $A_{2}(9,6)=4$. Can the Plotkin bound be used to show that $A_{2}(8,5)=4 ?$
Corollary (Another Plotkin bound). If $d \in \mathbb{N}$ then
$$
A_{2}(2 d, d) \leq 4 d
$$
We will see a class of binary codes that attain the Plotkin bound of Corollary 9.3. Hadamard codes are a family of binary codes that have high minimum distance and so can detect and correct many errors. We shall see that, like the codes constructed from MOLS, Hadamard codes have the largest possible size for their length and minimum distance.
The Hadamard $(32,64,16)$ -code used in the 1971 Mariner 9 mission to Mars was discussed in Example 1.17. Since the code has minimum distance 16 , it follows from Theorem that it is 7 -error correcting, as claimed (informally) in the example. Hadamard codes are constructed using certain matrices with entries $+1$ and $-1$.
Definition 9.4. Let $n \in \mathbb{N} .$ A Hadamard matrix of order $n$ is an $n \times n$ matrix $H$ such that each entry of $H$ is either $+1$ or $-1$ and $H H^{t r}=n I$. Here $I$ is the $n \times n$ identity matrix and $H^{t r}$ is the transpose matrix of $H$.
Example 9.5. If $H=\left(\begin{array}{cc}1 & 1 \ 1 & -1\end{array}\right)$ then $H$ is a Hadamard matrix of order $2 .$ Two Hadamard matrices of order 4 are shown below; in these matrices we write $+$ for 1 and $-$ for $-1$.
Lemma Suppose $H$ is a Hadamard matrix of order $n$ where $n \geq 2$. If $i, k \in{1,2, \ldots, n}$ and $i \neq k$ then row $i$ and row $k$ of $H$ are equal in exactly $n / 2$ positions.
The connection with coding theory is as follows.
Theorem 9.7. Suppose that $H$ is a Hadamard matrix of order $n \geq 2$. Let $B$ be the $2 n \times n$ matrix defined by
$$
B=\left(\begin{array}{c}
H \
-H
\end{array}\right) .
$$
The rows of $B$ are the codewords in a $(n, 2 n, n / 2)$ -code over the alphabet ${+,-}$.
We say that any code given by the construction in Theorem $9.7$ is a Hadamard code. These codes can be converted into binary codes over the usual alphabet of bits ${0,1}$ by replacing each $+$ with 0 and each $-$ with 1 .
