1950

Error-Correcting Codes

Richard Hamming (1915–1998)

After he got his PhD in mathematics and worked on the mathematical modeling for the atomic bomb, Richard Hamming took a job at Bell Telephone Labs, where he worked with Claude Shannon and John Tukey and wrote programs for the laboratory’s computers. Hamming noticed that these digital machines had to perform their calculations perfectly. But they didn’t. According to Hamming, a relay computer that Bell had built for the Aberdeen Proving Ground, a US Army facility in Maryland, had 8,900 relays and typically experienced two or three failures per day. When such a failure occurred, the entire computation would be ruined and need to be restarted from the beginning.

At the time, it was becoming popular for computer designers to devote an extra bit, called a parity bit, to detect errors when data was transmitted or stored. Hamming reasoned that if it was possible to automatically detect errors, it must also be possible to automatically correct them. He figured out how to do this and published his seminal article, “Error Detecting and Error Correcting Codes,” in the April 1950 issue of the Bell System Technical Journal.

Error-correcting codes (ECCs) play a critical role in increasing the reliability of modern computer systems. Without ECCs, whenever there is a minor error on the receipt of data, the sender must retransmit. So modern cellular data systems use ECCs to let the receiver fix those minor errors, without requesting that the sender retransmit a clean copy. Today ECCs are also used to correct errors in stored data. For example, cosmic rays can scramble the bits of a dynamic random access memory (DRAM) chip, so it’s common for internet servers to be protected with ECC memory, allowing them to automatically correct most errors resulting from stray background radiation. Compact discs (CDs) and digital video discs (DVDs) use ECC to make their playback unaffected by surface scratches. And increasingly, ECCs are being incorporated into high-performance wireless communications protocols to reduce the need for data to be resent in the event of noise.

Hamming was awarded the 1968 A.M. Turing Award “for his work on numerical methods, automatic coding systems, and error-detecting and error-correcting codes.”

SEE ALSO The Bit (1948)

The 4-bit Hamming codes (on right) for binary numbers 00000000001 through 00000000H0 and 111H1H001 through 11111111111.