Slashdot Mirror
60 Years of Hamming Codes
swandives writes "In 1950 Bell Labs researcher Richard W. Hamming made a discovery that would lay an important foundation for the modern computing and communications industries — coming up with a method for performing computing operations on a large scale without errors. Hamming wrote about how self-checking circuits help eliminate errors in telephone central offices. He speculated the 'special codes' he proposed — which became known as Hamming codes — would only need to be applied to systems requiring unattended operation for long periods or 'extremely large and tightly integrated' systems where a single failure would incapacitate the entire installation. Hamming code was the first discovery in an immense field called coding theory. This article looks back on the history of Hamming codes, their applications, and includes interviews with Todd Moon, Professor of electrical and computer engineering at Utah State University and David MacKay, Professor of natural philosophy in the department of Physics at the University of Cambridge and chief scientific adviser to the UK Department of Energy and Climate Change. An interesting read, about a little-known but fundamental element of information theory."
News for nerds, stuff that matters.
This submission qualifies.
"There is a way that seems right to a man, but its end is the way of death." Proverbs 16:25 (NKJV)
Feynman's excellent book 'Lectures on Computation' has a fantastic explanation of Hamming codes and distance, error correction etc.
If you're even remotely interested in information theory you *must* read this book! No prior knowledge required.
If you're a cheap bastard I'm sure you can find a pdf, but it's well worth the asking price.
That's right. Had Hamming's discovery been more well known, he might have won the Claude E. Shannon Award.
DUCWIDT?
No folly is more costly than the folly of intolerant idealism. - Winston Churchill
If you know anything about information theory, you know about hamming codes.
If you know anything about information theory, you know about hamming codes.
If you know anything about information theory, you know about hamming codes.
If you know anything about information theory, you know about hamming codes.
If you know anything about information theory, you know about hamming codes.
I'm sure a whole bunch of people know about Bill Gates and Steve Jobs, but their impact upon computing and information theory is comparatively minor compared to Richard Hamming. There are many such individuals who if you have studied your history of computing that really ought to be much better known but little is really talked about even in computing circles. Usually there is a theorem or algorithm which bears the name of an individual like Dijkstra's algorithm, but who really knows much about Edsger Dijkstra, the guy who came up with the concept in the first place, or for that matter even knows the names behind the LZW compression algorithm?
If you went to a group of college seniors in computer science, how many of them would have ever heard about Grace Hooper? First classmen in the Naval Academy? (I would sure hope that the U.S. Naval Academy at least would have taught their computer science cadets something about Admiral Hooper, especially if they get assigned to the USS Hooper).
There are a bunch of people you should know in the history of computing, and unless you have a very good professor who doesn't claim to have invented the integrated circuit and every other part of computing, you generally don't know the whys for how most concepts in computer science were ever derived.
Hamming codes are practical things, while Shannon's analyses of codes were more abstract (though still hugely useful and important)
Consider the checksum bit. It helps to catch errors but there are 2 problems. First, if there is a double error (more likely if the checksum is on a longer string), then the error isn't caught Second, even if we know there is an error, we can't recover, but have to resend.
The easiest error-correcting code is to replace every bit with a triple copy of itself. So
101 becomes 111000111
This way, we can recover from any single error, but the scheme is very inefficient.
Hamming's simplest code takes a 4 bit message and adds 3 very special parity bits (think partial checksums) arranged in a clever way so that any one bit error can be isolated and corrected.
That's the basic idea. The details are many places, such as http://en.wikipedia.org/wiki/Hamming(7,4)
There is no Admiral Grace Hooper. There was, however, an Admiral Grace Hopper, who has a few things (including Hopper Hall at Dam Neck), named after her.
I do not read or respond to AC's. If you want a discussion, log in. Otherwise, don't waste your time.
Actually, Hamming is a bit overrated. He was a tireless self-promotor who himself named these things after himself. Really a no-no. Hamming codes and Hamming distance are fairly simple constructs and by no means the first, the last, or the most significant in the field. The real giant in the field is of course Claude Shannon, who, in my opinion, has been more important for the field of computing as a whole than even Alan Turing himself (Shannon's master thesis for instance proved how to do arbitrary boolean circuitry in hardware. 1932). Hamming is just a footnote. He found a good algorithm, and ran with it for fame and glory.
I just downloaded it.
http://www.inference.phy.cam.ac.uk/mackay/itila/book.html
thegodmovie.com - watch it
Shannon only proved that those codes exist. Hamming gave the first examples. So it's fair to say that Shannon was about information theory, not coding theory.
thegodmovie.com - watch it
"Sustainable energy - without the hot air", available as a free PDF download.
I haven't read it yet, but I will given his credibility with the article and other book.
http://www.withouthotair.com/ or http://www.inference.phy.cam.ac.uk/withouthotair/
Here is a podcast of a lecture he gave at Cambridge on the topic of sustainable energy.
http://mediaplayer.group.cam.ac.uk/component/option,com_mediadb/task,play/idstr,CU-CSF-Lectures_2008-12_David_MacKay/vv,-1/Itemid,42
Want to be like Hamming? Here's how:
In summary, I claim that some of the reasons why so many people who have greatness within their grasp don't succeed are:
* they don't work on important problems,
* they don't become emotionally involved,
* they don't try and change what is difficult to some other situation which is easily done but is still important,
* and they keep giving themselves alibis why they don't.
* They keep saying that it is a matter of luck.
I've told you how easy it is; furthermore I've told you how to reform. Therefore, go forth and become great scientists!
Source: http://paulgraham.com/hamming.html
His book Coding and Information Theory is by far the best written and most readable hard science textbook I ever had in my university career. Read it if you want to understand the subject, read it if you want to understand how to write a good textbook!
Yup, a brilliant guy I'm sure, but not the guy I want teaching me. At the end of a course, (call me greedy), _I_ want to know how to do everything in the course, not merely have a warm fuzzy WEE-WOW feeling that something exciting just went by that I can't quite reproduce.
Give me Richard Hamming's books instead of Feynman's any day. Ok, they won't make you go "WEEE WOW!!!", but on the other hand you will have an excellent understanding of the material AND be able to reproduce and USE any result in them yourself.
Shannon's work was general over the error model. Coding theory assumes a specific error model (such as bit error rates, insertion, deletion, magnitude distortion).
It doesn't take much wits to translate Shannon's work into a rudimentary code. Constructing codes near the bounds of optimality is extremely difficult, especially if the decoder corrects errors with better efficiency than combinatorial trial and error.
I wouldn't say Shannon's work was light on coding theory, much of which was implied pretty directly. I would say instead that his work was light on algorithmic efficiency of sophisticated codes.
By the time you're correcting 5 bit errors in a 256 bit packet, you don't want to have to search for the nearest valid codeword combinatorially.