Generator

The sixteen words of the [7,4] Hamming code

A generator in the computation library, called 61 times across 11 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

hamming-code is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

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

The Golay code drawn from an icosahedron

Twelve rows that generate the Golay code

Only five weights occur

Balls of radius three that fill the space

Three errors always corrected, four never

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

GF(7): 1 has exactly one inverse ×31
the search agrees with the conjecture at q = 2, k = 2 ×27
the number of codewords of weight 0 matches the formula for any MDS code ×9
class 000 has as many words as the code has ×8
class 000 has exactly one lightest word ×8
lengths 6 to 12 ×2
words of 8 to 14 bits ×2
1122 has the smallest worst class among the five patterns, 256 ×1
759 octads ×1
a = 0 gives the largest of the codes ×1
a ball of radius three holds 2,048 words ×1
a length of 8 to 14 and two positions within it ×1
a random code of the same size has some dependent triples ×1
a random strategy's right and wrong guesses balance as well ×1
a row called exact really divides to a power of two ×1
a word with r runs leaves between C(r − 1, 2) and C(r + 1, 2) words ×1
above capacity it rises ×1
above it they take over ×1
an exhaustive search for lengths 3 to 9 ×1
and always reaches what Gilbert and Varshamov guarantee ×1
and it weighs no more than one, which is what perfection means ×1
and none of them is zero ×1
and the climb is not monotone — some length is worse than the one before it ×1
at distance three the bound is only ever exact one short of a power of two ×1
below capacity the error falls with length ×1
below the limit failures vanish with length ×1
each doubling gives 2n + k + 1 coins ×1
each of the 42,504 five-element sets lies in exactly one octad ×1
each span is a distance between three and five and a longest length up to eight ×1
each vertex is not joined to seven vertices, itself included ×1
every 3 columns of G are independent ×1
every 7 columns of the dual's generator are independent ×1
every codeword passes all three parity checks ×1
every Helberg class corrects two deletions ×1
every one of the 2²³ words lies within distance three of exactly one codeword ×1
every one of the single deletions is repaired to the codeword ×1
every pair of erasures is recoverable, since the distance is 3 ×1
every pattern of three or fewer errors is corrected ×1
every rate is between zero and one ×1
every row of H is orthogonal to every row of G ×1
every single deletion of every codeword of VT₀(n) is decoded correctly ×1
every three columns of the extended Reed–Solomon code are independent ×1
every two rows share an even number of ones ×1
every two words of the code found are at least the distance apart ×1
every vertex of the icosahedron has five neighbours ×1
every word in the space is repaired to a codeword by its own syndrome ×1
exactly one way of putting two bits back lands in the codeword's class, and it is the codeword ×1
five players need seven lost configurations ×1
four data bits give sixteen codewords ×1
four doublings give fifteen weighings for thirty-two coins ×1
four errors always lead to a wrong codeword, three away ×1
Knuth's rule never needs more than five guesses ×1
more repeats, fewer errors ×1
most of the probability lies within two spreads of np ×1
no single-deletion code of length up to 7 is larger than VT₀(n) ×1
no strategy beats n/(n + 1) ×1
no word of length n − 1 is one deletion from two codewords ×1
nor Plotkin's, where it applies ×1
nor the Singleton bound ×1
one deletion turns a word into exactly as many words as it has runs ×1
one rate below 1 − ε and one above ×1
seven players make 112 right and 112 wrong guesses across the configurations ×1
some length meets the sphere-packing bound exactly ×1
some pair of words in the one-deletion code shares a two-deletion remnant ×1
some triples are and some are not ×1
the 128 words fall into eight classes ×1
the block length is a whole number between 20 and 400 ×1
the bound is met exactly at 1, 3 and 7 players ×1
the chance of failure is below 2 to the −m ×1
the count for k points matches the design formula ×1
the count of VTₐ(n) matches Ginzburg's divisor sum ×1
the divisor sum is exact for every length ×1
the eight lists of distances are all different ×1
the exact answer never beats the sphere-packing bound ×1
the field order is one of 2, 3, 4, 5, 7, 8, 9 ×1
the flip probability is between 0 and a half ×1
the Golay code of length 23 has 253 words of weight 7 ×1
the Hamming code's rate is above capacity at p = 0.1 ×1
the highlighted codeword is a whole number between -1 and 15 ×1
the largest arc in the plane of order 8 has 10 points ×1
the lightest non-zero codeword weighs what the closest pair are apart ×1
the longest word length in the table is a whole number between 5 and 23 ×1
the longest word length searched is a whole number between 5 and 8 ×1
the mean of the distribution is the sum ×1
the minimum distance is a whole number between 3 and 5 ×1
the minimum distance over all 120 pairs is three ×1
the minimum distance the bound is taken at is a whole number between 3 and 7 ×1
the number of cosets shown across is a whole number between 4 and 8 ×1
the number of message bits is a whole number between 4 and 30 ×1
the option is one this view reads ×1
the rate at the longest length beats the rate at the shortest, at every distance drawn ×1
the received word is seven bits ×1
the repetition code and the Hamming code both meet the bound exactly ×1
the repetition code meets the bound at n = d ×1
the search finished rather than running out of budget ×1
the search reaches the published value ×1
the set of words found corrects two deletions ×1
the seven columns of the parity-check matrix are distinct ×1
the seven single errors give seven different syndromes ×1
the shares settle near 7/8, 1/2 and 1/128 ×1
the smallest distance between two codewords is eight ×1
the sum settles on the constant ×1
the syndrome of a single error is the column of the position it hit ×1
the table is symmetric ×1
the trials agree with the exact product ×1
the view is one of syndrome, cosets, bound, best, rate, capacity, typical, repetition, random, rank, erasures, becsim, overhead, mdserasure, mdstable, mdsprofile, mdsdual, mdsweights ×1
the weights are 0, 8, 12, 16, 24 with counts 1, 759, 2576, 759, 1 ×1
the word is 8 to 14 bits ×1
the word the syndrome repairs really is a codeword ×1

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Computation

A code built from an icosahedron

Write down which corners of an icosahedron are not joined by an edge, put the table beside a diagonal of ones, and add the twelve rows together in every combination. The 4,096 strings of 24 bits that come out differ from each other in at least eight places, occur in only five weights, and — with one bit deleted — fill the space of 23-bit strings so exactly that every one of the 8,388,608 lies within three flips of exactly one of them. This is the Golay code, which carried Voyager's pictures home, and its words of weight eight cover every five of the twenty-four positions exactly once.

Computation

A code that survives a lost bit

A flipped bit leaves the word the right length and wrong in one place; a lost bit leaves it one short, with no sign of where the gap was. Keep only the words whose 1s sit at positions adding up to a multiple of n + 1, and any single lost bit can be put back. The price is about log₂(n + 1) bits, the same as the Hamming code pays for a flip.

Computation

Erasures a code can see

If a channel loses bits instead of flipping them, and says which ones it lost, its limit rises from 1 − H(p) to 1 − p — and reaching it needs nothing cleverer than a random matrix and the solution of simultaneous equations. A random code needs, on average, 1.607 symbols more than the message it carries, whatever the message's length, and that number is a constant Erdős proved irrational.

Computation

Finding the error without reading the message

Three parity checks on a seven-bit word produce three bits. If they are all zero nothing is wrong; otherwise they are the number of the position that broke. The message is never consulted, because the answer does not depend on it.

Computation

How few distances fix a word

An unknown word of a thousand bits can be read one bit at a time with a thousand questions. Ask instead for its distance from a chosen word, and each answer is worth about half of log₂ n bits, so roughly two hundred distances fix it. A balance reading many coins at once is the same question. So is Mastermind, in which Knuth's rule finds any of the 1,296 codes in at most five guesses and a mean of 4.476, and no first guess is best on both counts.

Computation

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

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

The longest code that survives every erasure

A Reed–Solomon code of k symbols can lose any n − k of its n and still be read. Over an alphabet of q symbols it can be at most q + 1 long — and it is conjectured that no code with the same perfect tolerance can ever be longer, apart from one family of exceptions in even characteristic. A search through every possible code for small alphabets confirms it cell by cell, a proof exists when q is prime, and for every other q the question is open.

Computation

The rate a noisy channel allows

A channel that flips one bit in ten can still carry messages with as few errors as anyone likes — at up to 0.531 message bits per transmitted bit, and at no rate above that. The number is Shannon's capacity, 1 − H(p). Repetition reaches reliability only by sending nothing; a code chosen at random gets there at any rate below the limit; and the reason there is a limit at all is a count of how many flip patterns a block of noise can hold.

Computation

Two lost bits

One congruence repairs any single lost bit, and the set of words it defines is believed to be the best possible. Two lost bits defeat it. An exhaustive search finds the largest codes that survive two — 2, 2, 4, 5, 7 and 11 words for lengths 4 to 9 — and Helberg's congruence, with weights that grow like Fibonacci numbers, gives a code that provably works at every length but spends a fixed share of every bit on protection. The best codes need only about four times the logarithm of the length.

Computation

Wrong guesses that arrive together

Seven players in red or blue hats each see every hat but their own, and must guess their own colour or pass. Every guess is a coin toss, yet with the Hamming code the team wins seven times in eight — not by making guesses better, but by making the wrong ones arrive together. The best chance for any number of players is fixed by the fewest losses that cover the cube.

The whole library · What the figures prove