Hamming / Sphere-Packing Bound

Pack disjoint balls to cap code size; equality means perfect.

The idea

Theorem (Hamming (sphere-packing) bound).

A code $C$ of length $n$ over an alphabet of size $q$ that corrects $t$ errors satisfies $|C| \cdot V_q(n, t) \le q^{n}, \qquad V_q(n, t) = \sum_{i=0}^{t} \binom{n}{i}(q-1)^{i}.$

The quantity $V_q(n, t)$ is the volume of a Hamming ball: the ball of radius $t$ around a word is the set of words within distance $t$ of it. To sit at distance exactly $i$ from the center, choose which $i$ of the $n$ coordinates change, in $\binom{n}{i}$ ways, then a different symbol for each of them, in $(q-1)^{i}$ ways. Summing over $i = 0, 1, \ldots, t$ counts the whole ball, and the count is the same for every center.

The bound is a packing argument. Correcting $t$ errors means every word within distance $t$ of a codeword is decoded back to that codeword. No word can be decoded to two codewords at once, so no word lies within $t$ of two of them: the balls around the $|C|$ codewords are pairwise disjoint. Disjoint sets inside the $q^{n}$ words of the space together hold at most $q^{n}$ words, which is the bound.

Nothing forces the balls to fill the space, and normally they leave gaps — words farther than $t$ from every codeword. When equality holds and the balls tile the space with no gaps, the code is called perfect.

Ways to work on it

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