Hamming's code.

Step 1 of 6

Three overlapping checks

In 1950 Richard Hamming published a code that does not just catch a flip, but finds it. The Hamming (7,4) code adds three parity bits to every four data bits, making blocks of seven. Number the positions in a block from $1$⁠ to $7$⁠. The parity bits sit in positions $1$⁠, $2$⁠ and $4$⁠, and each belongs to a different check:

• Check A covers positions $1$⁠, $3$⁠, $5$⁠ and $7$⁠.
• Check B covers positions $2$⁠, $3$⁠, $6$⁠ and $7$⁠.
• Check C covers positions $4$⁠, $5$⁠, $6$⁠ and $7$⁠.

Each parity bit is set so that its check holds an even number of 1s. On the board above the line the checks are drawn as three overlapping circles, and each position has a region of its own.

Here the line is perfectly quiet, and Faulty bit picks one position that flips in every block, as if one wire in the cable were broken. This time it is position $6$⁠.

Step 2 of 6

Reading the checks

When one bit flips, every check that covers it fails, and the others pass. The checks were chosen so that this pattern is the position itself, written in base 2: check A is the ones digit, B the twos digit, and C the fours digit. So read them in the order C B A and write $1$⁠ for each check that failed. That number is called the block’s syndrome, and $0$⁠ means every check passed.

Now Faulty bit is hidden, and Look inside is closed.

Step 3 of 6

Parity bits flip too

The noise does not know which bits are data and which are parity: a parity bit can flip on the way too. Positions $1$⁠, $2$⁠ and $4$⁠, the powers of $2$⁠, are exactly the positions inside one circle only. Flipping one of them fails only its own check, and the syndrome points to it like any other position.

Step 4 of 6

Two flips

Look inside is open at Repaired: the receiver flips the bit the syndrome points to, and the display shows the repaired text. The line is noisy again, 5% per bit. The code assumes that at most one bit flips in each block. When two flip, what the receiver sees is the pattern of a single flip, somewhere else.

Step 5 of 6

How often the code fails

With the code, a block arrives wrong only if two or more of its seven bits flipped. The counter compares the last $50$⁠ blocks with and without the code.

Step 6 of 6

The price

Three bits out of every seven on the line carry no part of the message. That is the price of repair: the line carries data at only $\tfrac47$⁠ of its rate. Modern codes, in phones, on CDs and on spacecraft, repair far more errors at a lower price, but their idea is the same: overlapping parity checks whose answers together point to the error.