In 1947, a Bell Labs relay computer dropped Richard Hamming’s calculations two weekends in a row, and the question it provoked led to the Hamming code. Versions of that code still correct errors in computer memory today.
The machine knew something had gone wrong. That was the maddening part.
Hamming was a mathematician who had joined Bell Labs in 1946. He was using a relay computer the company had built for the U.S. Army’s Aberdeen Proving Ground, one of the machines his 1950 paper calls the Model 5. It ran in Bell Labs’ West Street building in Manhattan. Hamming worked at Murray Hill, New Jersey, and could ride into the city in the company limousine that carried the mail.
Relays failed often enough to matter. Hamming’s 1950 paper reports roughly two or three failures a day among the 8,900 relays of the two Aberdeen machines in their early period, about one per two to three million relay operations. The machines caught those faults with two-out-of-five codes, the kind also used in Bell’s telephone switching systems: every valid digit had exactly two of its five positions switched on, so a single fault produced a pattern the machine could reject.
When a check failed, the machine tried again. After three failures, it dropped the problem and moved on to the next one.
Hamming would leave his work on the machine late on a Friday and come back on Monday for the answers. One Monday, every problem had been dropped. The next weekend, it happened again.
He later recalled his reaction in a taped interview quoted in Thomas M. Thompson’s 1983 book on the history of error-correcting codes: “Damn it, if the machine can detect an error, why can’t it locate the position of the error and correct it?”
In a 1995 lecture, Hamming explained why knowing the location would be enough. In binary, a wrong bit has only one other possible value: “if it could tell me where it is, I could change the bit from a one to a zero, or, a zero to a one.”
How Hamming got from a grid of parity checks to the code
The obvious fix was expensive. Hamming had discussed it years before: build three machines and let circuits take a majority vote. “But who wants to build three machines with inter-comparing circuits?” he asked his students.
He knew parity checks well: an extra bit that makes the count of ones come out even. If data bits are laid out in a rectangle with a parity check on every row and every column, a single error fails one row check and one column check. Together, as he put it, “I will have the coordinates.”
The closer the rectangle came to a square, the fewer check bits it needed, and he was content with that. Then, on one of those limousine rides across northern New Jersey — “reviewing my successes,” as he put it — he saw that a triangle with the checks along its diagonal would do better. He said he was humiliated. He had been telling himself the square was the best possible; now he told himself, “Hamming, you’re going to have to find the best possible code.”
The example he taught has seven positions — the next size up from simply sending each bit three times. Positions 1, 2 and 4 hold check bits; positions 3, 5, 6 and 7 hold data. The first check covers positions 1, 3, 5 and 7, the second covers 2, 3, 6 and 7, and the third covers 4, 5, 6 and 7. If the bit in position 6 flips, the second and third checks fail and the first passes. Write each failure as 1 and each pass as 0, third check first, and you get 110, which is six in binary. The code does not just say that something is wrong. It names the bit.
Add an eighth bit, a parity check over the whole word, and the code can also detect two simultaneous errors, though not fix them. His 1950 paper describes that extension too, and it defines the distance between two code words as the number of positions in which they differ, now called the Hamming distance.
Single-error correction with double-error detection is the scheme most error-correcting code (ECC) memory uses, in Hamming’s form or a 1970 variant of it. Hamming received the 1968 Turing Award, the third ever given, “for his work on numerical methods, automatic coding systems, and error-detecting and error-correcting codes.”
Three details the weekend anecdote leaves out
The code was in print before Hamming’s paper. His “Error Detecting and Error Correcting Codes” appeared in the Bell System Technical Journal in April 1950. But in July 1948, in the same journal, Claude Shannon’s “A Mathematical Theory of Communication” included a seven-symbol code that corrects single errors, “found by a method due to R. Hamming.”
A patent held up Hamming’s paper. Hamming said publication was delayed “eighteen months or so by patent troubles.” The patent, filed in January 1950 and granted in May 1951 as U.S. Patent 2,552,629, names Hamming and a Bell Labs colleague, B. D. Holbrook.
The code took months, not a moment. The weekends supplied the question. By Hamming’s own estimate, the answer took three to six months of “odd moments,” evenings and weekends included. Of the rectangle step he said that, given a knowledge of binary and of parity checks, “this is not a profound invention.” He credited preparation: “Luck favors a prepared mind.”
What Hamming’s question still explains about error correction
Detection and correction are different promises. The relay computer’s two-out-of-five code could show that a digit was invalid, but not which relay had failed, so the only safe moves were to retry or give up. A code with more structure turns “something is wrong” into an address, and in binary, an address is a repair.
The irritation mattered too. Hamming told students that great work comes from people who are deeply emotionally involved, and the example he gave was himself: a mathematician who would not shrug off two lost weekends.
The machine at West Street could only report that a digit was bad. ECC memory that quietly flips a bad bit back is answering the question Hamming asked after his second lost weekend.
Related stories
Sources
- R. W. Hamming, “Error Detecting and Error Correcting Codes,” Bell System Technical Journal 29, no. 2 (April 1950): 147–160 (Internet Archive)
- Richard W. Hamming, “Error-Correcting Codes,” lecture transcript, Naval Postgraduate School, April 21, 1995
- Thomas M. Thompson, From Error-Correcting Codes Through Sphere Packings to Simple Groups, Mathematical Association of America, 1983, Preface
- C. E. Shannon, “A Mathematical Theory of Communication,” Bell System Technical Journal 27, no. 3 (July 1948) (Internet Archive)
- U.S. Patent 2,552,629, “Error-detecting and correcting system,” R. W. Hamming and B. D. Holbrook, filed January 11, 1950, granted May 15, 1951
- MacTutor History of Mathematics, “Richard Wesley Hamming,” University of St Andrews
- IEEE Computer Society, “Computer Pioneers: Richard W. Hamming”
- Association for Computing Machinery, A.M. Turing Award: Richard W. Hamming, 1968
- Wikipedia, “ECC memory” (single-error correction and double-error detection codes in memory)
- Featured image: relay equipment room of the Bell Labs Model V computer at the Ballistic Research Laboratories, Aberdeen, Maryland; illustrative, date unknown. U.S. Army Photo A51244, via Wikimedia Commons, Public domain
SIGNAL TITANS
Leave a Reply