Error Correction

One extra bit makes a line of bits count even, so a single flip is noticed. Lay the bits out as a grid with a parity bit per row and per column, and the failing lines cross at the flip.

A code is a set of words, and what it can do is one number: the fewest positions two of its words differ in. That distance fixes what is noticed, what is undone, and what is perfect.

Three parity bits guard four data bits, each over a different group of positions. Any single flip fails exactly the groups that spell its position, so the receiver can put it back without asking.

An eighth parity bit over the whole Hamming word tells one flip from two: a single flip is fixed as before and a double is reported, not mended wrong. ECC memory does this on every read.

The message as a polynomial over GF(2), divided by a generator with shift-and-XOR steps, its remainder sent along: any burst up to the generator's degree leaves a nonzero remainder at the far end.

Four-bit strings add without carries and multiply as polynomials reduced by a fixed quartic. Every nonzero element is a power of x, so a log table turns products into sums and every element divides.

Treat four-bit symbols as a polynomial over GF(16), append a remainder so the generator's four roots all give zero, and solve four equations to find and undo any two changed symbols.

A burst of noise wrecks the one word it lands on. Write the words into a block by row, send the block by column, and the same burst leaves one flip in every word, which each word can fix.