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,
 |
(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 clique
number of a graph is an NP-hard
problem.
 | OEIS |  |
| 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, 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, ... |
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.
For a constant-weight code, Dzoba (2026) improved eight binary lower bounds at Hamming
distance 6, including 
. The constructions were generated using
Claude under human direction, with additional verification programs generated using
Codex.
Gachkov, I. "Error-Correcting Codes with Mathematica."
