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 . 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.

	Sloane
1	A000079	2, 4, 8, 16, 32, 64, 128, ...
2		1, 2, 4, 8, ...
3		1, 1, 2, 2, ...
4	A005864	1, 1, 1, 2, 4, 8, 16, 20, 40, ...
5		1, 1, 1, 1, 2, ...
6	A005865	1, 1, 1, 1, 1, 2, 2, 2, 4, 6, 12, ...
7		1, 1, 1, 1, 1, 1, 2, ...
8	A005866	1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 4, ...

Wolfram Web Resources