Suppose you send a string of bits where a bit might have been flipped during the transmission. You can add an extra parity bit at the end that can be used to detect errors. What if you wanted to correct the error? Richard Hamming developed an error-correcting code (now called the Hamming code) that encodes 4 bits into 16 codewords of 7 bits each such that every two codewords differ in at least three bits (which we now call the Hamming distance).

0000000 1101001 0101010 1000011 1001100 0100101 1100110 0001111 1110000 0011001 1011010 0110011 0111100 1010101 0010110 1111111

If there is a single error then there is a unique codeword within one bit of the damaged string. By having an error-correcting code you can continue a process instead of just halting when you detect a bad code.

The Hamming code is a linear code, the bitwise sum mod 2 of any two codewords is another codeword. This linear idea led to many more sophisticated codes which have had many applications in computer science, practical and theoretical.

Hamming received several awards notably the 1968 ACM Turing Award and the inaugural IEEE Richard W. Hamming Medal in 1988 given for exceptional contributions to information sciences, systems, and technology. Hamming passed away in 1998.

ReplyDeleteNoteTerry Tao maintains a"Career Advice "web-page that specifically commends (and provide a link to) Richard Hamming's essay"A Stroke of Genius: Striving for Greatness in All You Do ."Two outstanding resources for students (needless to say).I remember Robert Gallager calling Hamming a "tireless self-promoter" in his lecture. I have wondered what prompted that remark. Any ideas?

ReplyDelete