Digital Revolution (Part III) - Error Correction Codes
2. Basic ideas
The diagram above suggests what is going on. The dark dots are codewords. The circles of radius e around these dots are shown. As long as these circles are disjoint from each other, that is, do not overlap, a received string that has no more than d transmission errors lies within one of the circles and can be properly decoded. Of course, one can not know in advance how many errors might actually be made. In some very special cases all potential messages of the codeword length are included in the circles centered around the code words. When this happens, the code is known as perfect. Perfect codes are especially appealing and by 1975 a complete list of such codes was known. The number of errors that occurs is related to the "quality of the hardware" used in the given situation (a malfunction in the hardware might increase the number of errors) and the amount of noise. NASA might design a code for use by a spacecraft under normal solar conditions, but an unexpected solar flare might create a situation where many more errors would occur than might have been expected .
The system above would enable the correction of up to one error per original information symbol because if, say, 001 were the first three symbols received, one would reason that the symbol consonant was meant because 001 differs from 000 in one position, while 001 differs from 111 in two positions. It seems more likely that one error occurred than two errors, so it is reasonable to conclude that the first letter of the text was a consonant. Two aspects of this system are noteworthy. One feature is that it is very easy to encode the message; just repeat each binary symbol three times. Secondly, it is also relatively easy to decode the message. Merely group the received string (assuming no digits are created or dropped) and decode triples with more zeros than ones to 000 and triples with more ones than zeros to 111. Questions about transmission rates versus noise and the correction of errors lay at the heart of what Shannon was trying to understand.
Amazingly, the ideas of Shannon (shown below), Hamming, and Marcel J. E. Golay (1902-1989) have given rise to a whole new subfield of mathematics known as coding theory.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance