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. 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.
Let
denote the maximal 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. is the number of s with precisely 1s (Sloane and Plouffe 1995). Since it is not possible for
-vectors
to differ in
places and since -vectors
which differ in all places partition into disparate sets of two,
(1)
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 size of a clique for a given graph
is an NP-complete problem.
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.
. 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.
denote the maximal number of 
(0,1)-vectors having the property that any two of the set
differ in at least 
places. The corresponding vectors can correct ![[(d-1)/2]](/images/equations/Error-CorrectingCode/Inline8.svg)
errors. 
is the number of 
s with precisely 
1s (Sloane and Plouffe 1995). Since it is not possible for
-vectors
to differ in 
places and since 
-vectors
which differ in all 
places partition into disparate sets of two,
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 size of a clique for a given graph
is an NP-complete problem.
Gachkov, I. "Error-Correcting Codes with
Mathematica."