Error-Correcting Code

An error-correcting code is an algorithm for expressing a sequence of numbers such that any errors which are introduced can be detected and corrected (within certain limitations) based on the remaining numbers. The study of error-correcting codes and the associated mathematics is known as Coding Theory.

Error detection is much simpler than error correction, and one or more ``check'' digits are commonly embedded in credit card numbers in order to detect mistakes. Early space probes like Mariner used a type of error-correcting code called a block code, and more recent space probes use convolution codes. Error-correcting codes are also used in CD players, high speed modems, and cellular phones. Modems use error detection when they compute Checksums, which are sums of the digits in a given transmission modulo some number. The ISBN used to identify books also incorporates a check Digit.

A powerful check for 13 Digit numbers consists of the following. Write the number as a string of Digits $a_1 a_2 a_3 \cdots a_{13}$. Take $a_1+a_3+\ldots+a_{13}$ and double. Now add the number of Digits in Odd positions which are $>4$ to this number. Now add $a_2+a_4 +\ldots+a_{12}$. The check number is then the number required to bring the last Digit to 0. This scheme detects all single Digit errors and all Transpositions of adjacent Digits except 0 and 9.

See also Checksum, Coding Theory, Galois Field, Hadamard Matrix, ISBN

References

Conway, J. H. and Sloane, N. J. A. ``Error-Correcting Codes.'' §3.2 in Sphere Packings, Lattices, and Groups, 2nd ed. New York: Springer-Verlag, pp. 75-88, 1993.

Gallian, J. ``How Computers Can Read and Correct ID Numbers.'' Math Horizons, pp. 14-15, Winter 1993.

Guy, R. K. Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 119-121, 1994.

MacWilliams, F. J. and Sloane, N. J. A. The Theory of Error-Correcting Codes. Amsterdam, Netherlands: North-Holland, 1977.