Singleton Bound

d ≤ n - k + 1 — the fundamental limit on rate vs. distance.

The idea

The Singleton bound limits how good a code's parameters can be. Here $n$ is the number of symbols in a codeword, $k$ is the number of message symbols it carries (so over an alphabet of size $q$ the code has $q^{k}$ codewords), and $d$ is the smallest number of positions in which two distinct codewords differ; such a code is written $[n, k, d]$.

Theorem (Singleton bound).

Every code of block length $n$, dimension $k$ and minimum distance $d$ satisfies $d \leq n - k + 1.$

To prove it, keep only the first $k - 1$ coordinates of each codeword. There are $q^{k-1}$ possible strings of that length but $q^{k}$ codewords, so by the pigeonhole principle two distinct codewords agree on all $k - 1$ kept coordinates. They can differ only in the remaining $n - (k - 1)$ positions, so their distance is at most $n - k + 1$, and the minimum distance is at most that as well.

The bound says that the rate $k/n$ and the distance $d$ compete for the same $n$ symbols: raising one lowers the ceiling on the other. A code that achieves $d = n - k + 1$ exactly is called MDS, for maximum distance separable; Reed–Solomon codes are the standard example.

Ways to work on it

• Walkthrough. What the bound says, why it holds, and which codes saturate it.
• Practice. Plug (n, k) into Singleton.
• Hardest. Compute the Singleton bound for a real code's parameters and decide whether it is MDS.

Not sure where to start? Take the ten-question placement test.