A flipped bit in your memory, on a disk, or in a radio signal can silently turn a 0 into a 1. You can't ask the bit whether it is wrong. Yet there is a tiny code that finds the bad bit and flips it back, using only three extra bits for every four of data. It is called a Hamming code, and you can break one yourself below.

The idea: parity checks that overlap

A parity bit is the simplest check there is: add one extra bit so the number of 1s in a group comes out even. If a single bit flips, the count turns odd and you know something went wrong. But you don't know which bit.

Richard Hamming, working at Bell Labs, published the fix in 1950. Don't use one parity check. Use several, each covering a different overlapping subset of the bits, so that every bit is covered by a unique combination of checks. When a bit flips, exactly the checks that cover it fail. The pattern of failures is a fingerprint that points at the culprit.

Seven slots, three checks

The classic version is called Hamming(7,4): seven bits, four of them your message, three of them checks. Number the slots 1 to 7. The check bits sit at the slots that are powers of two: 1, 2 and 4. The data fills slots 3, 5, 6 and 7.

Write the slot numbers in binary and each check gets a job. Check 1 looks at every slot whose binary number has a 1 in the ones place (1, 3, 5, 7). Check 2 looks at those with a 1 in the twos place (2, 3, 6, 7). Check 4 looks at those with a 1 in the fours place (4, 5, 6, 7). Each check bit is set so its group has an even number of 1s.

Now the neat part. If slot 5 flips, checks 1 and 4 fail but check 2 doesn't. Read the failures as a binary number, with check 4 as the leftmost digit: 1, 0, 1, which is 5. The failing checks literally spell out the position of the error.

What you just saw

Flip any single slot, including a check bit, and the failing checks always spell its number, so the receiver flips that slot back and recovers the message. With no damage, all three checks pass and the syndrome reads 000.

Now flip two slots at once and press correct. The checks still point to a slot, but it is the wrong one, and the "fixed" word is now wrong in a third place. Hamming(7,4) corrects one error. Two errors can fool it. Adding one more overall parity bit (called SECDED, single-error-correct, double-error-detect) lets it at least notice the double error, and that is the idea used in the error-correcting memory of many servers.

Why it is so efficient

Three check bits can produce 2³ = 8 different failure patterns. One means "all fine" and the other seven name the seven slots. The code uses every pattern, so it wastes nothing. This is what makes it a perfect code. The trick scales: with r check bits you protect 2^r − 1 slots in total, so 4 check bits guard 11 data bits, and 5 check bits guard 26.

The longer the block, the smaller the overhead, but the more likely it is that two errors land in the same block. Real systems choose the balance for the noise they expect. Hamming's idea, that the pattern of failed checks can name the culprit, still sits underneath much of the error correction in computing.