Matpic
mathematics, in pictures
Concept

Bound — where it appears

A number known to lie above or below a quantity nobody can compute exactly. Its value is in being provable rather than sharp, and a bound met exactly somewhere is worth far more than one that is merely close everywhere.

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

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 How many codewords lie within each radius, for a [7,3] code over 11 symbols. A bar for each decoding radius, its height the largest number of codewords found inside a ball of that radius around a randomly drawn received word, with the unique-decoding radius and the Johnson radius marked.

Past half the distance

A code of minimum distance five corrects two errors, and every account stops there. Two is the largest number for which the answer is unique — and a decoder that returns a short list instead of one answer reaches considerably further, which can be measured by counting the codewords in a ball.

computation · Error-correcting codes

Named alongside it

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

Error-correcting codeExhaustive searchHamming distanceList decodingPerfect codeRateReed solomonSphere-packingUniqueness

All concepts