On this page
A computer that stops at every error is safer than one that carries on with a wrong answer, but it still wastes a weekend. That was the problem facing Richard Hamming at Bell Labs in the late 1940s. This post covers who he was, the problem in his own words, a complete worked example of a 7-bit Hamming code, and the habits a student can take from him.
Who was Richard Hamming?
His ACM Turing Award biography records that he was born in Chicago on 11 February 1915. He wanted to study engineering but the only scholarship offer came from the University of Chicago, which had no engineering department, so he took mathematics. He earned an M.A. at Nebraska in 1939 and a PhD at Illinois in 1942. In 1945 he joined the Manhattan Project at Los Alamos, where he ran the IBM calculating machines. In 1946 he moved to Bell Telephone Laboratories, where he shared an office with Claude Shannon.
He stayed at Bell Labs until 1976, then taught at the Naval Postgraduate School in Monterey until December 1997. He died the following month. ACM gave him the 1968 Turing Award for work on numerical methods, automatic coding systems, and error-detecting and error-correcting codes.
What problem pushed him to error correction?
His paper, Error Detecting and Error Correcting Codes, appeared in the Bell System Technical Journal in April 1950. The full text on the Internet Archive describes the relay computers Bell Labs built for the Aberdeen Proving Ground. In the early period there were about two or three relay failures per day among the 8,900 relays of the two machines, roughly one failure per two to three million relay operations. Self-checking caught them, but the machines ran unattended over nights and weekends, so the computations often came to a halt. "Thus it appears desirable to examine the next step beyond error detection, namely error correction."
How can a few extra bits find an error?
A parity bit is an extra 0 or 1 chosen so that a group of bits has an even number of 1s. If one bit flips, that group's parity goes wrong. One check tells you something is wrong, not where. Hamming's idea was to use several checks over overlapping groups, arranged so that the pattern of failed checks, read as a binary number, gives the position of the error. A result of zero means no error.
With m data bits and k check bits, the checks must be able to name any of the m + k positions or "no error", so 2^k ≥ m + k + 1. For 4 data bits, k = 3 works, since 2^3 = 8 = 4 + 3 + 1. The paper calls this the seven-position code. Its redundancy, total bits over data bits, is 7/4 = 1.75.
Worked example: a 7-bit Hamming code
Following the paper, put check bits at positions 1, 2 and 4, and data in positions 3, 5, 6 and 7.
Check 1 covers positions 1, 3, 5, 7.
Check 2 covers positions 2, 3, 6, 7.
Check 4 covers positions 4, 5, 6, 7.
Send the data 1, 0, 1, 1 in positions 3, 5, 6, 7.
Position 1 makes {1, 3, 5, 7} even: data bits are 1, 0, 1, so set it to 0.
Position 2 makes {2, 3, 6, 7} even: data bits are 1, 1, 1, so set it to 1.
Position 4 makes {4, 5, 6, 7} even: data bits are 0, 1, 1, so set it to 0.
The codeword is 0110011.
Now suppose noise flips position 6, and 0110001 arrives.
Check 1, positions 1, 3, 5, 7: bits 0, 1, 0, 1, two 1s, even. Write 0.
Check 2, positions 2, 3, 6, 7: bits 1, 1, 0, 1, three 1s, odd. Write 1.
Check 4, positions 4, 5, 6, 7: bits 0, 0, 0, 1, one 1, odd. Write 1.
Read from check 4 down to check 1: 110 in binary is 6. Flip position 6 back and you have 0110011 again.
Common mistakes:
Reading the checks in the wrong order. Check 4 is the left-hand binary digit, check 1 the right-hand one.
Forgetting the check bit itself. Each parity count includes its own check position.
Expecting it to fix two errors. This code corrects one flipped bit. Two flips give a wrong address.
Binary place value does all the work here; our post on binary number systems covers it if you need a refresher.
What came out of the paper?
The Turing biography says Hamming codes, Hamming distance and the Hamming metric all originated in this paper and created a new field within information theory. Shannon had shown that error correction was possible in principle, as our post on Claude Shannon and information explains; Hamming gave engineers explicit codes they could build. The IEEE later created the Richard W. Hamming Medal, and he was its first recipient in 1988.
When an idea like parity checking is easier to follow in steps than in prose, the Fermi Concept Library covers concepts across mathematics and computing, one idea at a time.
What can a student take from how he worked?
Turn an annoyance into a question. Halted weekend runs were a nuisance; he asked what the next step after detection would be.
Count before you design. The inequality 2^k ≥ m + k + 1 told him how many check bits he needed before he placed any.
Ask how ideas will be taught. Later in life he wrote textbooks because, his biography says, he thought mathematics was being taught the wrong way.
Try it now: encode the data 0, 1, 1, 0, flip any one bit, and use the three checks to find it.
