Here is an example of a simple error-correcting code with a Hamming distance of 3 bits, that is, you have to change at least three bits to get from any code to any other code.
|
Symbol
|
Code
|
|
A
|
000000
|
|
B
|
001111
|
|
C
|
010011
|
|
D
|
011100
|
|
E
|
100110
|
|
F
|
101001
|
|
G
|
110101
|
|
H
|
111010
|
Imagine that you and a friend agree to use this coding scheme. Now, your friend sends you a message. If you receive 101001, you know that the symbol being sent was F.
If, on the other hand, you receive 101101, you know that there was a transmission error; 101101 is not in the table. However, you also know that the greatest likelihood is that the symbol was an F. Why is this?
Well, for example, assume that errors are unlikely (if this is not the case, then the system is probably unusable). Then, the probability of multiple errors is exponential. For instance, if the probability of a single error is 1:10, then the probability of two errors is 1:100 (10 squared). Moreover, the probability of three errors is 1:1000 (10 cubed). The bottom line is that, if we have determined that there is at least one error, the greatest likelihood is that it is the only error.
Now, of course it is possible that more than one bit has been received incorrectly. Indeed, once in a great while you may receive 101001, where in fact 000000 was sent and there were three errors. But, that is very unlikely, indeed, in the example above, the chance is one in a thousand.
Moreover, you can improve your odds by using a larger Hamming distance. If you use a Hamming distance of six, the probability of an undetected error becomes 1:1,000,000.
Error-correcting codes are used in networking, and also in storage devices. For example, audio CDs use a degree of error correcting that works out to about one error every two CDs. Data CD-ROMs, by contrast, use error correcting that minimizes errors to about one in 20,000 CDs.