Matpic
mathematics, in pictures
Generator

hamming-code

A generator in the computation library, called 13 times across 3 essays. Below: what it draws at its defaults 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.

At its defaults

The sixteen words of the [7,4] Hamming codeA table of sixteen seven-bit codewords with their data bits, parity bits and weights.four data bits, three parity bitsdataparityweight00000000000101130010110300111014010011140101100301100013011101041000101310011104101001141011000311000103110100141110100411111117sixteen codewords of length seven, minimum distance 3 — measured over all 120pairsweights: 1×0 · 7×3 · 7×4 · 1×7, and the lightest non-zero one weighs 3

show: "bound"

How many words a code of distance 3 can holdA table of word lengths with the size of a correction ball and the maximum number of codewords the bound allows.nball size2ⁿ / ballexact?342.000yes — 2¹453.200no565.333no679.143no7816.000yes — 2⁴8928.444no91051.200no101193.091no1112170.667no1213315.077no1314585.143no14151092.3no15162048.0yes — 2¹¹balls of radius 1 hold 4–16 words, and 2ⁿ divided by that is the most codewordsdistance 3 allowsthe division comes out exactly at n = 3, 7, 15 — the only lengths where a perfectcode is arithmetically possible

show: "syndrome"

The syndrome of 1011010, and the bit it namesA parity-check matrix over a received word, with the resulting syndrome matched against the table of single-error syndromes.received1011010H111010001110101101001010synsyndromethe bit it names101bit 1111bit 2110bit 3011bit 4100bit 5010bit 6001bit 7000no error1011010 gives syndrome 010, which is column 6 — so bit 6 is wrong and 1011000 is thecodewordthe syndrome is three bits and the message is four: the check finds the error without everrecovering what was sent

show: "cosets"

The whole space of seven-bit words, split into eight classesEight columns of sixteen words each, one column per syndrome, with the lightest word of each column marked.every seven-bit word, filed by the syndrome it produces0000000000000000000010110010110010110001100011000101101100011000100011101010011101110101001110101001111010011110100111111100100000010000001000101001100001000100001110001001101010010110100000101110101101101100111000110111011100111111101011111110010000001000000100001001001010011000000100101011100010011001010001010111001100111000111101101000111111101011111011011111010110001000000100000000110100100101000000101010110010100011011000010011110011100110011011101010010111110110111111100111011110000001000000100001001001010001000001001100101000111001010111000000011110110101101110011001100111110101011111011011111011101100000010000000000101001100001000100001110001001101010010110100100101110101101101100111000110111011100111111101001111111100010000001000000001100100001100100000011010101010100001111001000011011011110010101011110010011011110111101111001110111111101000000100000000110000100011000010000011100110101001001101010001010110110110110010111110000111101110111011100111011111128 words, 8 classes of 16 — one class per syndrome, and each has exactly one lightest memberthose eight leaders are the zero word and the seven single errors: nothing heavier is ever the best explanation

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.

Where it is called

Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.

Computation

Distance is a picture

A message is a corner of a cube and an error is a step along an edge. Everything a code can do is decided by how far apart the corners it uses are — and that is a fact about a drawing.

 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.

The whole library · What the figures prove