An error-correcting code is a set of codewords, usually finite sequences of symbols, chosen so that errors introduced during transmission or storage can be detected and corrected within certain limitations. 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 . Take and double. Now add the number of digits in odd positions which are to this number. Now add . 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.

As in binary code, for positive integers and , let denote the maximum number of (0,1)-vectors having the property that any two of the set differ in at least places. The corresponding vectors can correct errors, where is the floor function. Let denote the largest size of such a code whose vectors have exactly entries equal to 1 (Sloane and Plouffe 1995). Since two -vectors cannot differ in more than places, and a binary code with minimum distance can contain only a vector and its complement,

Values of can be found by labeling the (0,1)--vectors, finding all unordered pairs of -vectors which differ from each other in at least places, forming a graph from these unordered pairs, and then finding the clique number of this graph. Unfortunately, finding the clique number of a graph is an NP-hard problem.

For minimum Hamming distance 3, Milshtein (2026) constructed binary codes giving , , , and . Each construction is a union of cosets of a linear code. These are lower bounds, not assertions that the codes have maximum possible size.

Recent constructions and bounds for binary constant-weight codes are given by Dzoba (2026).

A different extremal problem limits the number of distinct pairwise Hamming distances. For , a binary code of length with at most three such distances between distinct codewords has maximum size (Djaljapayan et al. 2026). The code consisting of all binary vectors of Hamming weight 1 or 3 attains this size. At length 23, the dual code of the binary Golay code has 2048 codewords at three distances, exceeding .

See also

Anticode, Checksum, Clique, Clique Number, Coding Theory, Finite Field, Golay Code, Hadamard Matrix, Halved Cube Graph, Hamming Code, ISBN, Perfect Code, Two-Distance 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. "Error-Correcting Codes." §3.2 in Sphere Packings, Lattices, and Groups, 2nd ed. New York: Springer-Verlag, pp. 75-88, 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.Djaljapayan, V.; Huang, H.; and Yu, W.-H. "The Maximum Size of -Distance Binary Codes." 6 Nov 2026. https://arxiv.org/abs/2611.09675v1.Dzoba, C. "New Lower Bounds for Binary Constant-Weight Codes from Prescribed-Automorphism Search, and Two Quantum Codes Meeting Their Upper Bounds." 16 Oct 2026. https://arxiv.org/abs/2610.24025. Gachkov, I. "Error-Correcting Codes with Mathematica." https://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.Milshtein, M. "Four New Single-Error-Correcting Binary Codes." 16 Oct 2026. https://arxiv.org/abs/2610.23626.Numberphile. Featuring J. Grime. "Spheres and Code Words." Oct. 28, 2018. https://www.youtube.com/watch?v=T46FTuHnbvY.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, CA: Academic Press, 1995.

Referenced on Wolfram|Alpha

Error-Correcting Code

Cite this as:

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

Subject classifications