Error-Correcting Codes: Mistakes That Fix
It is one thing to show a man that he is in an error, and another to
put him in possession of truth.
—JOHN LOCKE, Essay Concerning Human Understanding (1690)
These days, we’re used to accessing computers whenever we need them. Richard Hamming, a researcher working at the Bell Telephone Company labs in the 1940s, was not so lucky: the company computer he needed was used by other departments and available to him only on weekends. You can imagine his frustration, therefore, at the crashes that kept recurring due to the computer’s errors in reading its own data. Here is what Hamming himself had to say on the matter:
Two weekends in a row I came in and found that all my
stuff had been dumped and nothing was done. I was really
aroused and annoyed because I wanted those answers and
two weekends had been lost. And so I said, “Dammit, if
the machine can detect an error, why can’t it locate the
position of the error and correct it?”
There can be few more clear-cut cases of necessity being the mother of invention. Hamming had soon created the first ever errorcorrecting code: a seemingly magical algorithm that detects and corrects errors in computer data. Without these codes, our computers and communication systems would be drastically slower, less powerful, and less reliable than they are today.
Computers have three fundamental jobs. The most important job is to perform computations. That is, given some input data, the computer must transform the data in some way to produce a useful