4
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Demazure (in Cours d'algèbre) writes:

Let $C$ a binary $t$-error correcting code of length $n$ and let $N$ the number of elements of $C$. Then $N(n + 1) \leqslant 2^n$. Moreover, the following conditions are equivalent:

  1. $C$ is perfect
  2. $N(n + 1) = 2^n$
  3. there exists $r > 1$ such that $n = 2^r - 1$ and $N = 2^{n - r}$.

Proof. Each ball of radius 1 has $n + 1$ elements (its center plus $n$ elements around). All $N$ balls centered in the codewords are disjoint (because $C$ is 1-error correcting) so they cover $N(n + 1)$ elements among the $2^n$ possible words. The equality characterizes the perfect codes, for which $N$ divides $2^n$.

$\endgroup$
  • $\begingroup$ Thank you, but i was aware of the upper bounds, i am interested in lower bounds. I edited the question to emphasize this. $\endgroup$ – Daniel Soltész Jan 3 '14 at 11:55
  • $\begingroup$ Then, I don't understand. If your code isn't perfect, you don't have to cover the whole space of possible words, so $C$ can contain only one codeword. $\endgroup$ – Jill-Jênn Vie Jan 3 '14 at 13:38
  • 2
    $\begingroup$ The OP is interested in lower bounds like the Gilbert-Varshamov bound (although this isn't applicable, since it doesn't apply to distance-3 codes). $\endgroup$ – Peter Shor Jan 3 '14 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.