4 Singleton Bound

4.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.

4.2 Main result