Math
A code that repairs itself
Sixteen bits in a square, eleven of them a message: click one and the four check lamps spell out its address, and the block puts itself right. Two errors are caught but not repairable; three, and the block lies with confidence. Every claim is exhaustive - all 32 768 single errors located, all 245 760 double errors caught, every triple mis-corrected.
What happens
Sixteen bits laid out four by four. Eleven carry a message; four are parity checks sitting at the powers of two - 1, 2, 4, 8 - and a fifth at position 0 checks the whole square. Each check watches exactly half the block: check 1 watches every odd index, check 2 watches indices 2, 3, 6, 7, 10, 11, 14, 15, and so on. Because every index belongs to a different combination of checks, the four answers read together are not an alarm but an ADDRESS: exclusive-or the indices of every set bit and the result is the number written under the wrong tile. Click any tile to flip it and watch the lamps spell it out. Flip a second and the block still knows something is wrong - the sixteenth bit, the one checking the whole square, is what separates "correct one error" from "correct one and know when there are two". Flip a third and the code lies: it names a tile with complete confidence and hands back the wrong message. Distance four buys one repair and two detections, and nothing beyond. Without that sixteenth bit the code is PERFECT in the technical sense: 2048 codewords, each with fifteen neighbours one flip away, and 2048 x 16 = 32 768 = 2^15 exactly - the spheres of radius one tile the space with nothing left over. This is the arithmetic inside ECC memory, inside every QR code, and on the surface of every optical disc; it is why a scratched CD still plays.
Equations used in the module
Equations syndrome: s = XOR of the indices of every set bit; s = 0 means the four checks agree, and s ≠ 0 IS the address of the wrong bit checks: check p watches every index i with (i AND p) ≠ 0; p = 1, 2, 4, 8, and position 0 checks the whole square verdict: s = 0 and parity even → whole; parity odd → one error at s (s = 0 means bit 0 itself); s ≠ 0 and parity even → two errors, detected and not repairable perfect code: Hamming(15,11) has 2^11 = 2048 codewords, each with 15 neighbours one flip away; 2048 × 16 = 32 768 = 2^15 exactly - the spheres of radius one tile the space with nothing left over distance: d = 3 for Hamming(15,11), d = 4 with the whole-square bit; correcting t errors needs d ≥ 2t + 1, detecting t needs d ≥ t + 1 exhaustive: 32 768 single-bit cases, 0 mislocated; 245 760 double-bit cases, 0 missed and 0 mis-corrected; 35 840 triple-bit cases, all 35 840 "corrected" wrongly rate: 11 message bits per 16 sent = 68.75 %; Hamming(7,4) 57.1 %, Hamming(31,26) 83.9 %, Hamming(63,57) 90.5 % - longer blocks are cheaper insurance and lose more to a second error
