2
$\begingroup$

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?

$\endgroup$
1
  • 7
    $\begingroup$ Yes, there are several bounds. Study coding theory, it is fun! $\endgroup$ – Tsuyoshi Ito Apr 23 '11 at 13:01
10
$\begingroup$

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, which states that for a $(s,N,d)$-code over $\mathbb{F}_b$ that $N\leq b^{s-d+1}$.

$\endgroup$
4
  • 2
    $\begingroup$ 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... $\endgroup$ – Jyrki Lahtonen Jul 16 '11 at 16:28
  • $\begingroup$ @Jyrki: I didn't claim it was tight, and I do not see why a loose bound is necessarily 'useless'. $\endgroup$ – Joe Fitzsimons Jul 17 '11 at 0:30
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jul 17 '11 at 5:20
  • $\begingroup$ @Jyrki: ah, I see. $\endgroup$ – Joe Fitzsimons Jul 17 '11 at 11:14
9
$\begingroup$

You may also want to look at Delsarte's linear programming bound, and the Gilbert-Varshamov 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.

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$ – v s Jul 17 '11 at 8:42
  • $\begingroup$ 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. $\endgroup$ – v s Jul 17 '11 at 8:47
  • $\begingroup$ @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. $\endgroup$ – Peter Shor Jul 18 '11 at 0:35
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Shor Jul 17 '11 at 13:24

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.