In the late 1940s, Richard Hamming, working at Bell Labs, was exasperated with the high level of errors occurring in the electro-mechanical computing equipment he was using. Punched card machines were constantly misreading, forcing him to restart his programs. He decided to do something about it. This was when error-correcting codes were invented.
A simple way to detect errors is to send a message twice. If both versions agree, they are probably correct; if not, there is an error somewhere. But the discrepancy gives us no clue where the error lies. Sensing the message three times is better: if two versions agree, we assume they are correct and ignore the third version. But there is a serious overhead: the total data transmitted is three times the data volume; the information factor is 1/3.
The (7,4)-Code
Hamming, an American mathematician and computer scientist, devised a much more efficient set of codes, now called Hamming Codes. The simplest of these is the (7,4)-Code. The message to be sent is split into groups of four binary digits or bits, denoted d1, d2, d3 and d4. Then three additional check-bits or parity bits p1, p2, and p3 are added, so the message becomes d1d2d3d4p1p2p3 with information content 4/7.
These parity bits are defined in such a way that, if any single bit is in error, it can be identified and corrected. In the Venn diagram above, the data bits and parity bits are shown in different regions of the diagram. The parity bits are chosen so that there is an even number of ones in each circular region. This can always be done.
If any single bit is in error (a zero instead of a one, or vice-versa), the evenness or parity is disrupted. Each of the seven bits destroys parity in a different set of circles, so the faulty bit can be detected and corrected. This is the genius of Hamming’s code: we know which bit is in error.
SECDED
Of course, if the message is badly contaminated, there may be more than one error in the string of seven bits. We may be able to detect this, but not to correct it. More sophisticated encodings are required for this. One such, deriving from Hamming’s code is SECDED (single error correction, double error detection) widely used in computer memories.
Coding Theory is an active field of mathematical research today. We depend on reliable communication channels that transmit large volumes of data. This data must be compressed before sending and accurately expanded on arrival. If it is sensitive, it must be encrypted. And inevitable errors in noisy transmission channels must be detected and corrected.
Many clever codes have been devised, such as the Reed-Solomon code used to eliminate noise in CD recordings. Richard Hamming’s wrestling match with punched card equipment has led to a world-wide industry.
* * * * * *
Peter Lynch’s book about walking around the coastal counties of Ireland is now available as an ebook (at a very low price!). For more information and photographs go to RRI.
ThatsMaths 