Richard Hamming and the Hamming Code

Richard Hamming - A two-dimensional visualisation of the Hamming distance. The color of each pixel indicates the Hamming distance between the binary representations of its x and y coordinates, modulo 16, in the 16-color system.

A two-dimensional visualisation of the Hamming distance. The color of each pixel indicates the Hamming distance between the binary representations of its x and y coordinates, modulo 16, in the 16-color system.

On February 11, 1915, American mathematician Richard Wesley Hamming was born. Hamming’s work had many implications for computer science and telecommunications. His contributions include the Hamming code (which makes use of a Hamming matrix), the Hamming window, Hamming numbers, sphere-packing (or Hamming bound), and the Hamming distance.

“The purpose of computation is insight, not numbers.”
– Richard Wesley Hamming (1962) as quoted in [2]

Richard Hamming – Youth and Education

Richard Wesley Hamming was born in Chicago, Illinois, the son of Richard J. Hamming, a credit manager. He grew up in Chicago, where he attended Crane Technical High School and Crane Junior College. Hamming initially wanted to study engineering, but money was scarce during the Great Depression, and the only scholarship offer he received came from the University of Chicago, which had no engineering school. Instead, he studied mathematics, which he later considered as a fortunate turn of events, and received his Bachelor of Science degree in 1937. Following his undergraduate studies, he went to the University of Nebraska where he was awarded his M.A. in 1939. He received his Ph.D. in mathematics in 1942 from the University of Illinois at Urbana-Champaign. His doctoral dissertation Some Problems in the Boundary Value Theory of Linear Differential Equation was supervised by Waldemar Trjitzinsky. While he was a graduate student, he discovered and read George Boole‘s The Laws of Thought.[6]

Manhattan Project

In 1944, Hamming became an Assistant Professor at the J.B. Speed Scientific School at the University of Louisville in Louisville, Kentucky. With World War II still ongoing, Hamming left Louisville in April 1945 to work on the Manhattan Project at the Los Alamos Laboratory, in Hans Bethe‘s division [7], programming the IBM calculating machines that computed the solution to equations provided by the project’s physicists. His wife Wanda soon followed, taking a job at Los Alamos as a human computer. Hamming relates an interesting episode in [2]:

… at Los Alamos … we were designing atomic bombs. Shortly before the first field test (you realize that no small scale experiment can be done – either you have a critical mass or you do not), a man asked me to check some arithmetic he had done, and I agreed, thinking to fob it off on some subordinate. When I asked what it was, he said, “It is the probability that the test bomb will ignite the whole atmosphere.” I decided I would check it myself! The next day when he came for the answers I remarked to him, “The arithmetic was apparently correct but I do not know about the formulas for the capture cross sections for oxygen and nitrogen – after all, there could be no experiments at the needed energy levels.” He replied, like a physicist talking to a mathematician, that he wanted me to check the arithmetic not the physics, and left. I said to myself, “What have you done, Hamming, you are involved in risking all of life that is known in the Universe, and you do not know much of an essential part?” I was pacing up and down the corridor when a friend asked me what was bothering me. I told him. His reply was, “Never mind, Hamming, no one will ever blame you.” [13]

At Bell Labs with Claude E. Shannon

Hamming remained at Los Alamos until 1946, when he accepted a post at the Bell Telephone Laboratories (BTL). For the trip to New Jersey, he bought Klaus Fuchs‘s old car.[8] When he later sold it just weeks before Fuchs was unmasked as a spy, the FBI regarded the timing as suspicious enough to interrogate Hamming. Then, he joined Claude E. Shannon at Bell Laboratories, where in 1950 he invented Hamming codes, which are used in telecommunications.[9] He realized that, by the appending of a parity check (an extra bit or block of bits) to each transmitted “word,” transmission errors could be corrected automatically, without having to resend the message.[3]

On Error Detection and Error Correction

”If you don’t work on important problems, it’s not likely that you’ll do important work.”
– Richard Wesley Hamming, as quoted in [15]

Although Hamming had been hired to work on elasticity theory, he still spent much of his time with the calculating machines. Before he went home on one Friday in 1947, he set the machines to perform a long and complex series of calculations over the weekend, only to find when he arrived on Monday morning that an error had occurred early in the process and the calculation had errored off. Digital machines manipulate information as sequences of zeroes and ones. If a single bit in a sequence was wrong, then the whole sequence would be. To detect this, a parity bit was used to verify the correctness of each sequence. “If the computer can tell when an error has occurred,” Hamming reasoned, “surely there is a way of telling where the error is so that the computer can correct the error itself.

In a landmark paper “Error detecting and error correcting codes” published in 1950,[13] Hamming introduced a concept of the number of positions in which two code words differ, and therefore how many changes are required to transform one code word into another, which is today known as the Hamming distance. Hamming thereby created a family of mathematical error-correcting code, which are called Hamming codes. This not only solved an important problem in telecommunications and computer science, it opened up a whole new field of study.

Later Life

In 1956 Hamming worked on the IBM 650, an early vacuum tube, drum memory, computer. His work led to the development of a rudimentary programming language. Hamming also worked on numerical analysis, especially integration of differential equations. The Hamming spectral window, still widely used in computation, is a special type of digital filter designed to pass certain frequencies and discriminate against closely related frequencies.[5] Hamming served as president of the Association for Computing Machinery from 1958 to 1960. In 1960, he predicted that one day half of the Bell Lab’s budget would be spent on computing. None of his colleagues thought that it would ever be so high, but his forecast actually proved to be too low. In addition to the most prestigious award in computer science, the Turing Award, Hamming received many awards for his pioneering work. He was made a fellow of the Association for Computing Machinery in 1994. In the late 1970s, Hamming gave up research, and concentrated on teaching and writing books. He became Professor Emeritus in June 1997, and delivered his last lecture in December 1997, just a few weeks before his death.

Ryan O’Donnell, Hamming Code and Hadamard Code || @ CMU || Lecture 11c of CS Theory Toolkit, [15]

References and Further Reading:

One comment

Leave a Reply

Your email address will not be published. Required fields are marked *

Relation Browser
0 Recommended Articles:
0 Recommended Articles: