Generator

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

A generator in the computation library, called 32 times across 6 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.

Channel capacity 1 − H(p), and three codes at p = 0.1

Decoding from 20 + m random combinations: the chance it works

The extra combinations a random code needs: 1.6067 on average

Random linear codes on the erasure channel, at rates 0.6 and 0.8

Erasure patterns the [7,4] Hamming code survives

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
a random code of the same size has some dependent triples ×1
a row called exact really divides to a power of two ×1
above capacity it rises ×1
above it they take over ×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 span is a distance between three and five and a longest length up to eight ×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 pair of erasures is recoverable, since the distance is 3 ×1
every rate is between zero and one ×1
every row of H is orthogonal to every row of G ×1
every three columns of the extended Reed–Solomon code are independent ×1
every two words of the code found are at least the distance apart ×1
every word in the space is repaired to a codeword by its own syndrome ×1
four data bits give sixteen codewords ×1
more repeats, fewer errors ×1
most of the probability lies within two spreads of np ×1
nor Plotkin's, where it applies ×1
nor the Singleton bound ×1
one rate below 1 − ε and one above ×1
some length meets the sphere-packing bound exactly ×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 chance of failure is below 2 to the −m ×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 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 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 seven columns of the parity-check matrix are distinct ×1
the seven single errors give seven different syndromes ×1
the sum settles on the constant ×1
the syndrome of a single error is the column of the position it hit ×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 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

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

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.

The whole library · What the figures prove