Fixing a flipped bit

A single digit in a long binary word flips from 1 to 0. A parity check can tell you that something went wrong. R. W. Hamming's 1950 paper showed how to add just three check digits to four digits of data so that the checks do more: read together, they spell out the position of the digit that flipped, and the receiver can flip it back.

Detecting was not enough

Hamming came to the problem from computing machines. The Model 5 relay computers that Bell Telephone Laboratories built for the Aberdeen Proving Grounds showed, early on, about two or three relay failures per day among their 8900 relays, which the paper puts at about one failure per two to three million relay operations. The machines checked themselves, so these failures did not slip through unnoticed. But the computers ran unattended over nights and weekends, and a detected error often meant the computation simply came to a halt. So Hamming set out to examine “the next step beyond error detection, namely error correction.”

One parity check

Some notation first. A code word has n binary digits: m of them carry information and the other k = n − m are check digits. The simplest check adds one digit chosen so that the whole word holds an even number of 1s. This is a parity check. Any single flipped digit leaves an odd number of 1s, so the error is detected, though the check cannot say where it is. Nor can it make a word arbitrarily long. Hamming notes that when n reaches about 1/p, where p is the small chance that any one digit goes wrong, a word arrives intact only about 1/e = 0.3679 of the time, and an undetected double error has probability about 1/(2e) = 0.1839. His key remark is that a parity check need not cover every position. It can cover a chosen set.

Checks that spell a position

Run k such checks on a received word. Write 0 for each check that passes and 1 for each that fails, and read the results right to left as a binary number. Hamming calls it the checking number. He asks that it give the position of any single error, with 0 meaning no error. Then it must be able to name m + k + 1 different things: every position, plus “none.” k binary digits can name 2^k things, so the code needs 2^k ≥ m + k + 1.

That requirement fixes which positions each check must cover. The first check fails exactly when the error sits in a position whose binary form ends in 1: positions 1, 3, 5, 7 and so on. The second covers positions with a 1 in the second binary place: 2, 3, 6, 7. The third covers 4, 5, 6, 7. Hamming puts the check digits themselves at positions 1, 2 and 4, so that each is set by one check alone.

With three checks, 2³ = 8 = 4 + 3 + 1, so the word has seven positions: three check digits and four data digits, the data sitting at positions 3, 5, 6 and 7. That gives 2⁴ = 16 code words out of 2⁷ = 128 possible seven-digit strings, leaving 112 strings that mean nothing.

Hamming's own example

Take the code word 0111100, which carries the message 12, and flip its fifth digit to get 0111000. The first check covers positions 1, 3, 5, 7. It predicts a 1 in position 1 and finds a 0, so write 1. The second check covers 2, 3, 6, 7 and is satisfied, so write 0 to its left. The third check covers 4, 5, 6, 7 and fails, so write 1 to the left again. The checking number is 101 in binary, which is 5. Flip position 5 back and the word is repaired. The same arithmetic works when the flipped digit is a check digit: if position 2 flips, only the second check fails, and the number reads 010, which is 2.

Two errors, and an eighth digit

Flip two digits and the seven-digit code is fooled. The checking number is then the two positions combined digit by digit, which names a third position that was never touched, and “correcting” it makes three errors. Hamming's fix is one more even-parity digit over all the others, for an eight-digit word. A single error now always breaks the overall check, and the checking number says where it is, with 0 now meaning the eighth digit itself. With two errors, “the last parity check is satisfied, and the checking number indicates some kind of error.” The receiver knows the word is damaged and does not guess.

Why three check digits is the minimum

Hamming also gave this a picture. Treat each word as a corner of a cube in n dimensions, and define the distance between two words as the number of positions in which they differ. That is the fewest cube edges between them. If every pair of code words is at least 3 apart, a single error leaves the word closer to where it started than to any other code word. Each code word then owns a small ball: itself plus the n words one flip away, n + 1 corners in all. The balls cannot overlap, so there are at most 2ⁿ/(n + 1) code words, which is “exactly the bound we found before.” For n = 7 that is 128/8 = 16, and the seven-position code reaches it. Adding the parity digit turns a minimum distance of 3 into 4, and in general 2k − 1 into 2k.

The paper is candid about its limits. Nobody then knew a general way to build the best codes when the minimum distance exceeds four, and the ball-counting bound can overshoot: for distance 5 and seven digits it allows four code words, while the true maximum is two. Hamming credits one earlier published work in the field, that of M. J. E. Golay in 1949.

In short

A parity check over chosen positions answers one yes-or-no question about where an error is. Three such questions, chosen so that their answers form a binary number, name any one of seven positions or say that there is no error. Three check digits protect four data digits, and one more parity digit turns a silent miscorrection of two errors into a detected one.