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)
You're kidding, right?
" about a little-known but fundamental element of information theory."
little-known? If you know anything about information theory, you know about hamming codes.
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.
TFA mentions Mackay's book. It is an awesome book, and is free online. I have a dead-tree copy, too. Well worth the price.
SJW n. One who posts facts.
I've been assured many times by Slashdotters that the only reason we have technology and computers is because of the '60s Space Race. I refuse to believe that people are smart by default and discover things on their own. Obviously there can only be progress when there's rockets or people floating around in free fall doing nothing. So clearly, Hamming codes were invented in space, by Mars colonists mining asteroids or something. This whole "telecom" thing and using computers for scientific purposes is a fad.
Hamcode, hamcode, where you been? Around the world and I'm going again...
Does having a witty signature really indicate normality?
Hamming code was the first discovery in an immense field called coding theory
First discovery? I would say Shannon's historic paper on coding theory "A Mathematical Theory of Communication" from 1948 was earlier.
For the record, Dr. Moon is the Department Head of ECE. He gives killer lectures, but his tests will make you wish for death ;-).
I'm currently working on an MS there. Good to see him get some publicity.
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)
"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!
Not to hijack the information about important work by Hamming, but those interested in Grace will have an easier time locating information about her searching on Grace Hopper, Navy Rear Admiral, Lower Half. Her 1986 David Letterman interview: http://www.youtube.com/watch?v=57bfxsiVTd4
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.
Information theory was not my option, but I was in Telecom Bretagne when turbocodes were discovered and many theoretic aspects has been demonstrated. Did the turbocodes make the Hamming code obsolete or do I miss something ?
The history of cars was not my option but I was in Volkswagen when the Golf was released. Did the Golf make Ford's Model T obsolete or do I miss something?
In my Naval career, I was lucky enough to come across both of these titans of computing’s early age. RADM Hopper gave a lecture to every plebe class at the Naval Academy , including mine in 1984, where she would give each Midshipman a short length of wire of the length that light traveled in a nanosecond. She used these to illustrate stories she told of the early days of computers that were programmed by connecting wires differently. Her speech was the first place I heard “it was easier to beg forgiveness later than get permission before.”
I wasn’t a CS/EE major, so I hadn’t previously heard of Hamming when I went to the Naval Postgraduate School in 1993 to get a master’s in CS. He was teaching there as an adjunct since he retired from Bell Labs and the entire faculty talked about him as if he were God. I really didn’t know his history, and chalked it up to parochialism.
I was lucky enough to have him as my professor for Computer Automata. It was like taking physics from someone who had been a contemporary of Newton, Copernicus, Kepler, and Einstein. His stories about working on the Manhattan Project were fascinating. Whenever we came across any of the big names in early computing theory (with the possible exception of Turing, whom I’m not sure he met – I don’t remember any stories about him), Hamming had a personal story of his interaction with them. I will never get rid of my Automata book, because the margins are filled in with some of these. For example, next to the discussion of Backus-Naur form is the note, “Hamming told Backus not to become a hippie, because if he did, he would never do good work again. Backus didn’t listen, became a hippie, and did no good work again.” It really made what can be an otherwise dry class come alive, and it drove home exactly how young a field CS actually was.
A previous poster added a link to Hamming’s talk upon his retirement at Bell Labs, “You and Your Research”, which I cannot recommend highly enough. (http://paulgraham.com/hamming.html) Even if you’re not a researcher, it is worth reading. My favorite line in it is ”Given two people with exactly the same ability, the one person who manages day in and day out to get in one more hour of thinking will be tremendously more productive over a lifetime.”