<p>Demazure (in <em>Cours d'algèbre</em>) writes:</p>
<blockquote>
<p>Let <span class="math-container">$C$</span> a binary <span class="math-container">$t$</span>-error correcting code of length <span class="math-container">$n$</span> and let <span class="math-container">$N$</span> the number of elements of <span class="math-container">$C$</span>. Then <span class="math-container">$N(n + 1) \leqslant 2^n$</span>. Moreover, the following conditions are equivalent:</p>
<ol>
<li><span class="math-container">$C$</span> is perfect</li>
<li><span class="math-container">$N(n + 1) = 2^n$</span></li>
<li>there exists <span class="math-container">$r &gt; 1$</span> such that <span class="math-container">$n = 2^r - 1$</span> and <span class="math-container">$N = 2^{n - r}$</span>.</li>
</ol>
</blockquote>
<p><em>Proof</em>. Each ball of radius 1 has <span class="math-container">$n + 1$</span> elements (its center plus <span class="math-container">$n$</span> elements around). All <span class="math-container">$N$</span> balls centered in the codewords are disjoint (because <span class="math-container">$C$</span> is 1-error correcting) so they cover <span class="math-container">$N(n + 1)$</span> elements among the <span class="math-container">$2^n$</span> possible words. The equality characterizes the perfect codes, for which <span class="math-container">$N$</span> divides <span class="math-container">$2^n$</span>.</p>

CC BY-SA 3.0
2014-01-03T11:55:29.727Z
Thank you, but i was aware of the upper bounds, i am interested in lower bounds. I edited the question to emphasize this.
Daniel Soltész
CC BY-SA 3.0
2014-01-03T13:38:20.163Z
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.
Jill-Jênn Vie
CC BY-SA 3.0
2014-01-03T14:47:50.977Z
The OP is interested in lower bounds like the [Gilbert-Varshamov bound](http://en.wikipedia.org/wiki/Gilbert–Varshamov_bound) (although this isn't applicable, since it doesn't apply to distance-3 codes).
Peter Shor 
CC BY-SA 3.0
2014-01-03T11:37:10.477Z
2014-01-03T11:37:10.477Z
2020-06-17T09:38:08.363Z
Jill-Jênn Vie
<p>Here is a <a href="http://www.eng.tau.ac.il/~litsyn/tableand/index.html#dist3">table</a> 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.</p>

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

CC BY-SA 3.0
2014-01-03T14:02:19.390Z
2014-01-03T17:21:09.623Z
2014-01-03T17:21:09.623Z
Peter Shor 
<p>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.</p>

<reference-request><graph-theory><it.information-theory><coding-theory>
The length of non perfect binary 1 error correcting codes
Daniel Soltész
# The length of non perfect binary 1 error correcting codes

(Asked by: username_0 on 2014-01-03)

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.

**Tags:** reference-request, graph-theory, it.information-theory, coding-theory

---

## 2 answers

### Answer by username_2 on 2014-01-03. Score: 7 | Accepted answer

Here is a [table](http://www.eng.tau.ac.il/~litsyn/tableand/index.html#dist3) 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.


---

### Answer by username_1 on 2014-01-03. Score: 0

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

> **Comments:**
> **username_0**: Thank you, but i was aware of the upper bounds, i am interested in lower bounds. I edited the question to emphasize this.  
> **username_1**: 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.  
> **username_2**: The OP is interested in lower bounds like the [Gilbert-Varshamov bound](http://en.wikipedia.org/wiki/Gilbert–Varshamov_bound) (although this isn't applicable, since it doesn't apply to distance-3 codes).  

---

