Matpic
mathematics, in pictures
Concept

Hamming code

A code of sixteen seven-bit words whose balls of radius one fill the whole space exactly, correcting any single error.

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

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

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 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

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 · error correcting codes

Named alongside it

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

CosetError correcting codeCounting argumentDecision procedureHamming distanceLinearityMinimum distanceParityParity checkPerfect codeSphere packing boundSyndrome

All concepts