TOPICS
Search

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_1a_2a_3...a_(13). Take a_1+a_3+...+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+...+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.

Let A(n,d) denote the maximal number of n (0,1)-vectors having the property that any two of the set differ in at least d places. The corresponding vectors can correct [(d-1)/2] errors. A(n,d,w) is the number of A(n,d)s with precisely w 1s (Sloane and Plouffe 1995). Since it is not possible for n-vectors to differ in d>n places and since n-vectors which differ in all n places partition into disparate sets of two,

 A(n,d)={1   n<d; 2   n=d.
(1)

Values of A(n,d) can be found by labeling the 2^n (0,1)-n-vectors, finding all unordered pairs (a_i,a_j) of n-vectors which differ from each other in at least d places, forming a graph from these unordered pairs, and then finding the clique number of this graph. Unfortunately, finding the size of a clique for a given graph is an NP-complete problem.

dOEISA(n,d)
1A0000792, 4, 8, 16, 32, 64, 128, ...
21, 2, 4, 8, ...
31, 1, 2, 2, ...
4A0058641, 1, 1, 2, 4, 8, 16, 20, 40, ...
51, 1, 1, 1, 2, ...
6A0058651, 1, 1, 1, 1, 2, 2, 2, 4, 6, 12, ...
71, 1, 1, 1, 1, 1, 2, ...
8A0058661, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 4, ...

See also

Checksum, Clique, Clique Number, Coding Theory, Finite Field, Golay Code, Hadamard Matrix, Halved Cube Graph, Hamming Code, ISBN, Perfect Code, UPC

Explore with Wolfram|Alpha

References

Baylis, J. Error Correcting Codes: A Mathematical Introduction. Boca Raton, FL: CRC Press, 1998.Berlekamp, E. R. Algebraic Coding Theory, rev. ed. New York: McGraw-Hill, 1968.Brouwer, A. E.; Shearer, J. B.; Sloane, N. J. A.; and Smith, W. D. "A New Table of Constant Weight Codes." IEEE Trans. Inform. Th. 36, 1334-1380, 1990.Calderbank, A. R.; Hammons, A. R. Jr.; Kumar, P. V.; Sloane, N. J. A.; and Solé, P. "A Linear Construction for Certain Kerdock and Preparata Codes." Bull. Amer. Math. Soc. 29, 218-222, 1993.Conway, J. H. and Sloane, N. J. A. "Quaternary Constructions for the Binary Single-Error-Correcting Codes of Julin, Best and Others." Des. Codes Cryptogr. 4, 31-42, 1994.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. Gachkov, I. "Error-Correcting Codes with Mathematica." http://library.wolfram.com/infocenter/MathSource/5085/.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.Sloane, N. J. A. Sequences A000079/M1129, A005864/M1111, A005865/M0240, and A005866/M0226 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. Figure M0240 in The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Referenced on Wolfram|Alpha

Error-Correcting Code

Cite this as:

Weisstein, Eric W. "Error-Correcting Code." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Error-CorrectingCode.html

Subject classifications