<p>You may also want to look at <a href="http://portal.acm.org/citation.cfm?id=1097468" rel="nofollow">Delsarte's linear programming bound</a>, and the <a href="http://en.wikipedia.org/wiki/Gilbert%E2%80%93Varshamov_bound" rel="nofollow">Gilbert-Varshamov bound</a>. The linear programming bound gives a lower bound on the number of redundant bits necessary. The Gilbert-Varshamov bound gives a non-constructive (randomized) upper bound on the number of redundant bits required.</p>

CC BY-SA 3.0
2011-07-17T08:42:58.473Z
Actually I think GV is constructive. Only thing is it takes exponential time for each choices of $t$ (half-min distance in the given metric) and $n$ dimension of the code space of the given alphabet $q$.
v s
CC BY-SA 3.0
2011-07-17T08:47:25.757Z
Only the asymptotic bounds are non-constructive. The finitary versions are always constructive. Actually Manin and Tsfasman have an argument saying the limit of the possible cardinality of the codes may be even undecidable. Manin and Marcolli have an interesting paper on this building on techniques from non-commutative geometry and motives.
v s
CC BY-SA 3.0
2011-07-18T00:35:32.657Z
@v s: Absolutely correct. But I think the definition of "constructive" may change depending on whether you're talking to a mathematician or a theoretical computer scientist.
Peter Shor 
CC BY-SA 3.0
2011-04-24T21:14:26.747Z
2011-04-24T21:14:26.747Z
Peter Shor 
<p>This is not meant to be a substitute to the bounds linked to by Peter Shor. Just a quick argument showing why the Singleton bound is inaccurate for long binary codes (transporting bulk data).</p>

<p>If your code length is $n$, and you can afford to use $r$ of those for redundancy, then the syndrome of your code has $2^r$ possible values. If you want to correct a single bit error, then using that syndrome alone you have to be able to distinguish between $n+1$ cases: no error, a single error at position $i$, $1\le i\le n$. To be able to do that we must have the inequality $2^r\ge n+1$, or in other words we need $r&gt; \log_2 n$. This is exactly what the Hamming code gives us. Note that the Singleton bound would suggest that you only need two bits of redundancy to correct a single error. In other words, the Singleton bound does not take into account the length of the code at all.</p>

<p>If we want to continue, and correct $t$ errors, then theory becomes more interesting. By the same argument we obviously need the inequality
$$
2^r\ge1+n+ {n\choose 2}+\cdots+{n\choose t},
$$
because $n\choose i$ tells us the number of patterns of $i$ errorneous bits. This leads us to a bound known as the Hamming bound. If we had here $n^t$ on the r.h.s., then we would need $r\approx t\log_2 n$ redundancy bits, which is what the BCH-codes give us. As you see, this estimate was too crude, but for small values of $t$ the error here (after taking the logarithm) is not very big.</p>

<p>Of course, in many a setting the channel is not really making hard bit errors, but soft errors (=reliability figures of individual received bits). Then we can, to an extent, throw away these bounds, and use LDPC or Turbo codes. Alas, I don't know too much about that theory.</p>

CC BY-SA 3.0
2011-07-17T13:24:48.517Z
For soft errors, you only can get results about decoding with high probability, and in this case it is Shannon's bound that applies. You can also throw away the bounds for hard bit errors when the errors are probabilistic (rather than worst-case), and you just care about decoding with very high probability, since then Shannon's bound also applies. In both cases, I believe that LDPC and Turbo codes get very close to Shannon's bound.
Peter Shor 
CC BY-SA 3.0
2011-07-17T05:54:54.627Z
2011-07-17T05:54:54.627Z
Jyrki Lahtonen
<p>As Tsuyoshi points out in the comments, there are a number of such bounds. However, for the sake of actually giving you an answer, let me point you to the <a href="http://en.m.wikipedia.org/wiki/Singleton_bound" rel="noreferrer">Singleton bound</a>, which states that for a $(s,N,d)$-code over $\mathbb{F}_b$ that $N\leq b^{s-d+1}$.</p>

CC BY-SA 3.0
2011-07-16T16:28:46.787Z
Be advised that the Singleton bound is unattainable for long codes. RS-codes achieve, if $s\le b$, and that's about it, so for binary codes, this bound is useless for $s>3$. If I had a dime for every time I have to explain that a binary code of length 1000 cannot correct 100 errors with 200 redundancy bits...
Jyrki Lahtonen
CC BY-SA 3.0
2011-07-17T00:30:20.230Z
@Jyrki: I didn't claim it was tight, and I do not see why a loose bound is necessarily 'useless'.
Joe Fitzsimons
CC BY-SA 3.0
2011-07-17T05:20:35.600Z
My remark was aimed at the OP. Sorry about not making that clear. I have just met too many people, who want to produce ballpark figures of system performance by using Singleton bound alone. A pet peeve, sorta.
Jyrki Lahtonen
CC BY-SA 3.0
2011-07-17T11:14:07.647Z
@Jyrki: ah, I see.
Joe Fitzsimons
CC BY-SA 3.0
2011-04-24T11:16:45.810Z
2011-04-24T19:45:19.697Z
2011-04-24T19:45:19.697Z
Joe Fitzsimons
<p>Is there a lower bound (in coding theory or elsewhere) of number of redundant bits necessary to encode a word with certain Hamming distance?</p>

<p>There is some known data for parity checks, CRC, Hamming encoding, but is there a theoretical limit?</p>

CC BY-SA 3.0
2011-04-23T13:01:37.113Z
Yes, there are several bounds.  Study coding theory, it is fun!
Tsuyoshi Ito
<co.combinatorics><it.information-theory><coding-theory>
Is there a lower bound of number of redundant bits necessary to encode a word with certain Hamming distance?
Halst
# Is there a lower bound of number of redundant bits necessary to encode a word with certain Hamming distance?

(Asked by: username_0 on 2011-04-23)

Is there a lower bound (in coding theory or elsewhere) of number of redundant bits necessary to encode a word with certain Hamming distance?

There is some known data for parity checks, CRC, Hamming encoding, but is there a theoretical limit?

**Tags:** co.combinatorics, it.information-theory, coding-theory
> **Comments:**
> **username_1**: Yes, there are several bounds.  Study coding theory, it is fun!  

---

## 3 answers

### Answer by username_5 on 2011-04-24. Score: 10 | Accepted answer

As Tsuyoshi points out in the comments, there are a number of such bounds. However, for the sake of actually giving you an answer, let me point you to the [Singleton bound](http://en.m.wikipedia.org/wiki/Singleton_bound), which states that for a $(s,N,d)$-code over $\mathbb{F}\_b$ that $N\leq b^{s-d+1}$.

> **Comments:**
> **username_4**: Be advised that the Singleton bound is unattainable for long codes. RS-codes achieve, if $s\le b$, and that's about it, so for binary codes, this bound is useless for $s>3$. If I had a dime for every time I have to explain that a binary code of length 1000 cannot correct 100 errors with 200 redundancy bits...  
> **username_5**: @Jyrki: I didn't claim it was tight, and I do not see why a loose bound is necessarily 'useless'.  
> **username_4**: My remark was aimed at the OP. Sorry about not making that clear. I have just met too many people, who want to produce ballpark figures of system performance by using Singleton bound alone. A pet peeve, sorta.  
> **username_5**: @Jyrki: ah, I see.  

---

### Answer by username_2 on 2011-04-24. Score: 9

You may also want to look at [Delsarte's linear programming bound](http://portal.acm.org/citation.cfm?id=1097468), and the [Gilbert-Varshamov bound](http://en.wikipedia.org/wiki/Gilbert%E2%80%93Varshamov_bound). The linear programming bound gives a lower bound on the number of redundant bits necessary. The Gilbert-Varshamov bound gives a non-constructive (randomized) upper bound on the number of redundant bits required.

> **Comments:**
> **username_3**: Actually I think GV is constructive. Only thing is it takes exponential time for each choices of $t$ (half-min distance in the given metric) and $n$ dimension of the code space of the given alphabet $q$.  
> **username_3**: Only the asymptotic bounds are non-constructive. The finitary versions are always constructive. Actually Manin and Tsfasman have an argument saying the limit of the possible cardinality of the codes may be even undecidable. Manin and Marcolli have an interesting paper on this building on techniques from non-commutative geometry and motives.  
> **username_2**: @v s: Absolutely correct. But I think the definition of "constructive" may change depending on whether you're talking to a mathematician or a theoretical computer scientist.  

---

### Answer by username_4 on 2011-07-17. Score: 2

This is not meant to be a substitute to the bounds linked to by Peter Shor. Just a quick argument showing why the Singleton bound is inaccurate for long binary codes (transporting bulk data).

If your code length is $n$, and you can afford to use $r$ of those for redundancy, then the syndrome of your code has $2^r$ possible values. If you want to correct a single bit error, then using that syndrome alone you have to be able to distinguish between $n+1$ cases: no error, a single error at position $i$, $1\le i\le n$. To be able to do that we must have the inequality $2^r\ge n+1$, or in other words we need $r> \log\_2 n$. This is exactly what the Hamming code gives us. Note that the Singleton bound would suggest that you only need two bits of redundancy to correct a single error. In other words, the Singleton bound does not take into account the length of the code at all.

If we want to continue, and correct $t$ errors, then theory becomes more interesting. By the same argument we obviously need the inequality
$$
2^r\ge1+n+ {n\choose 2}+\cdots+{n\choose t},
$$
because $n\choose i$ tells us the number of patterns of $i$ errorneous bits. This leads us to a bound known as the Hamming bound. If we had here $n^t$ on the r.h.s., then we would need $r\approx t\log\_2 n$ redundancy bits, which is what the BCH-codes give us. As you see, this estimate was too crude, but for small values of $t$ the error here (after taking the logarithm) is not very big.

Of course, in many a setting the channel is not really making hard bit errors, but soft errors (=reliability figures of individual received bits). Then we can, to an extent, throw away these bounds, and use LDPC or Turbo codes. Alas, I don't know too much about that theory.

> **Comments:**
> **username_2**: For soft errors, you only can get results about decoding with high probability, and in this case it is Shannon's bound that applies. You can also throw away the bounds for hard bit errors when the errors are probabilistic (rather than worst-case), and you just care about decoding with very high probability, since then Shannon's bound also applies. In both cases, I believe that LDPC and Turbo codes get very close to Shannon's bound.  

---

