Matpic
mathematics, in pictures
Ladder

Error correcting codes — the ladder

4 distinct arguments against one idea, from the one that introduces it to the one that assumes the rest.
  1. 0000010100111001011101112 codewords in the 3-cube, minimum distance 3 — 1 error corrected, 2 detectedthe 2 balls of radius 1 hold 4 words each and cover all 8 exactly once: the code is perfect

    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.

    rung 1 · computation
  2. 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.

    rung 2 · computation
  3. 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.

    rung 3 · computation
  4. 012345678910012345678910sentf(0) = 4f(1) = 8f(2) = 7f(3) = 1f(4) = 1f(5) = 7f(6) = 8the message 4, 1, 3 read as 3x² + 1x + 4 over GF(11), evaluated at x = 0…6all 35 ways of keeping 3 of the 7 values were interpolated and every one returned the message

    A polynomial through the gaps

    Write the message as the coefficients of a polynomial and send its values instead. Any k of them determine the polynomial, so it does not matter which ones are lost — and it does not matter how many, as long as k survive.

    rung 4 · computation

All ladders