ERROR-CORRECTING CODES

So what's there left to write about for an editor who has been hanging around hospitals instead of doing his homework?

Codes and languages.

Suppose I am using binary code (all zeros and ones) in groups of three:

001, 010, 011, 011, 100, etc. What message this might code is of no interest here. In a perfect world, the groups would all arrive the way they were sent. In reality, channel noise will distort some of the 1s into 0s and some of the 0s into 1s. To protect myself against this, I will count the number of 1s in a group of information digits and add a check digit by the following arbitrary rule: if the number of 1s is even, I add another 1 as a check digit, otherwise 1 add a 0. Thus (the hyphen is not transmitted, just inserted here for clarity) my groups become 001-0, 010-0, 011-1, 100-0, etc.

If now the receiver gets a group 011-0, he does not know what went wrong, but he knows that something went wrong, for such a group does not exist. He can request that the group be repeated, all of which can, of course, be easily automated.

The example above is that of an error-detecting code. By adding more check digits per information digit, the receiver can be told which of the digits is wrong. This is an error-correcting code.

There are thousands of error correcting codes around, not necessarily for binary codes. For example, librarians are fond of reversing the order of digits in a book number, so the Library of Congress numbers protect the number against that kind of distortion.

All of these methods have certain traits in common: