5 Singleton Bound
5.1 Overview
This chapter proves the Singleton bound: any code \(C\subseteq \alpha ^n\) with minimum distance \(d\) has at most \(|\alpha |^{n-d+1}\) codewords.
The proof projects each codeword onto its first \(n-d+1\) coordinates. Two distinct codewords in \(C\) must have distinct projections (otherwise their Hamming distance would be less than \(d\)), so \(|C|\) is at most the number of possible projections.
5.2 Main result
Let \(\alpha \) be a finite alphabet with at least two symbols, and let \(C\) be a code of length \(n\) over \(\alpha \) — that is, a finite set of codewords \(c : \mathrm{Fin}\, n \to \alpha \). Suppose \(C\) has minimum distance \(d\), meaning that some two distinct codewords of \(C\) are at Hamming distance exactly \(d\) and no two distinct codewords are at distance less than \(d\). Then