Concept

Perfect code

A code whose correction balls fill the whole space of words exactly once, with nothing left over. They are rare — the repetition codes, the Hamming codes and the Golay code are the complete binary list — and they are the codes that meet the sphere-packing bound.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

The sixteen words of the [7,4] Hamming code. A table of sixteen seven-bit codewords with their data bits, parity bits and weights.

Sixteen spheres that fill a cube

A hundred and twenty-eight seven-bit words, sixteen of them chosen, and a ball of eight around each. Sixteen times eight is a hundred and twenty-eight exactly — so the balls tile the space with nothing left over, and the code wastes nothing at all.

computation · Error-correcting codes

The largest code at each length, distance 3, against four bounds. A table with one row per word length, giving the exact size of the largest code of that length at the stated minimum distance and the values of the Singleton, Hamming, Plotkin and Gilbert-Varshamov bounds.

The best a code can be

A code is a set of words chosen far apart, and every construction answers "here is one" rather than "here is the best". The best can be computed at small lengths, and putting four classical bounds beside the exact answer shows which of them is doing the work and where none of them is.

computation · Error-correcting codes

Named alongside it

The objects these essays reach for when they reach for this one.

Error-correcting code Hamming distance Bound Coset Counting argument Exhaustive search Hamming code Minimum distance Rate Sphere-packing Sphere-packing bound

All concepts