Perfect Codes

The sphere-packing bound and the codes that meet it: Hamming and Golay.

The idea

A perfect code meets the sphere-packing bound with equality: the balls around its codewords tile the whole space, with no gaps and no overlaps.

Theorem (Sphere-packing bound).

Let a code of length $n$ over an alphabet of size $q$ have $M$ codewords and minimum distance $d$, and let $t = \lfloor (d-1)/2 \rfloor$. Then $M \cdot V_q(n, t) \le q^{n}, \qquad \text{where } V_q(n, t) = \sum_{i=0}^{t} \binom{n}{i}(q-1)^{i}.$

Here $t$ is the number of errors the code corrects, and $V_q(n, t)$ counts the words in the Hamming ball of radius $t$ around a codeword — every word within distance $t$ of it. These balls are disjoint: a word inside two of them would sit within $t$ of two codewords and could not be decoded. So the balls take up $M \cdot V_q(n, t)$ of the $q^{n}$ words in the space, which is the bound.

Almost every code leaves the inequality strict, and the slack consists of words uncovered by any ball — farther than $t$ from every codeword, unresolvable by the decoder.

Definition (Perfect code).

A code is perfect when it meets the sphere-packing bound with equality, $M \cdot V_q(n, t) = q^{n}$, so that every word lies within $t$ of exactly one codeword.

Perfect parameters are scarce, since the ball volume must divide $q^{n}$ exactly and a code of the resulting size must exist. Beyond the trivial cases, the perfect codes are the Hamming codes, which correct $t = 1$, and two codes named after Golay: a binary code of length $23$ correcting $3$ errors, and a ternary code of length $11$ correcting $2$.

Ways to work on it

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