Theoretical Computer Science
reference-request graph-theory it.information-theory coding-theory
Updated Thu, 26 May 2022 22:17:16 GMT

# The length of non perfect binary 1 error correcting codes

I am interested in the best known number of code words in binary 1 error correcting codes of length $n$. I am aware of the Hamming code when $n=2^r-1$, but i would like to get lower bounds for other $n$ too. My motivation is completely theoretical and is related to graph theory.

## Solution

Here is a table of the best known (linear and non-linear) binary codes for distance 3, for $n \leq 512\,$. Distance 3 is equivalent to being able to correct one error. The table only gives you the number of codewords, but the references given in the table will tell you how to construct the codes themselves.

The best known codes for $n$ not in this table can be found by taking the code for the next larger $n$ in the table, repeatedly choosing a coordinate, and retaining only those codewords which have $0$'s (or $1$'s) in that position. You can delete $\ell$ coordinates and retain a $2^{-\ell}$ fraction of the codewords.