2
$\begingroup$

Under the Binary Symmetric Channel, the Shannon limit can be stated as:

$R \le 1-H(p)$

where $R$ is the rate of a code that can be decoded with high probability, $p$ is the probability of bit-flips on the channel, and $H$ is the binary entropy function. (I believe all of this applies in general, but I'm stating it in terms of binary alphabets for simplicity.) This is suspiciously similar to the Hamming bound:

$R \le 1-H(\delta/2)$

where $\delta$ is the relative distance of the code. And indeed, when $\delta \ge 2p$ then obviously the code will be able to correct all errors with high probability. Naively, the converse feels like it should also be true: That to correct all errors with high probability, $p \le \delta / 2$. And indeed, this is claimed in these lecture notes:

Proposition 2.1. Let $0 ≤ p < \frac{1}{2}$ and $0 < ε ≤ \frac{1}{2} − p$. If an algorithm $A$ can handle $p + ε$ fraction of worst case errors, then it can be used for reliable communication over $BSC_p$.

... proof snipped ...

Remark 2.2. The converse of Proposition 2.1 is also true. More precisely, if the decoding error probability is exponentially small for the BSC, then the corresponding code must have constant relative distance. The proof of this claim is left as an exercise.

However, that leads to a contradiction: The Shannon limit is tight, but there are better upper bounds than the Hamming bound, such as the Elias-Bassalygo bound and the MRRW bound. These bounds rule out the existence of codes that, by Remark 2.2 would be required to achieve the tightness of the Shannon limit.

I know I'm missing something important here, but what is it?

$\endgroup$
2
  • 1
    $\begingroup$ I don't know much information theory at all. For me coding theory has always been applied algebra :-). Anyway, I guess the answer is in the difference "high probability", and "exponentially small error probability". IIRC Shannon's theorem uses a random code that is "long enough", and does not care about $\delta$ at all. OTOH LDPC-codes are withing a fraction of a dB of the Shannon bound (in AWGN channel though), and don't care much about $\delta$ either. I'm ashamed to admit I don't know where Polar codes lie in here. In my sims I have never gone below BERS at roughly $10^{-9}$, so :-) $\endgroup$ Jan 27, 2021 at 19:32
  • $\begingroup$ Your comment that "LDPC-codes ... don't care much about δ either" strikes to the heart of what I think is weak in my argument. Practical near-Shannon codes (and the codes in the proof of the bound) aren't concerned about δ, yet work well. I think Remark 2.2 is suspect, and it is not actually required to have p <= δ/2. I haven't found a good counterexample yet, though. $\endgroup$
    – D0SBoots
    Jan 27, 2021 at 21:41

1 Answer 1

2
$\begingroup$

This might help. The Shannon limit places no constraints on computational complexity, nor on the type of coding/decoding. And it is proved by using random coding ideas, which I am sure you know.

Codes are traditionally used for unique decoding while it is possible to do list decoding, i.e., let the decoder output a small list where the correct codeword belongs to one element of the list. See the notes below in the course by Madhu Sudan, for example.

http://people.seas.harvard.edu/~madhusudan/courses/Spring2020/scribe/lect05.pdf

There it is explained how the Elias-Bassalygo bound applies if one allows "small list decoding".

$\endgroup$
2
  • 1
    $\begingroup$ Thanks! But I don't think this is it. The Plotkin bound, for instance, doesn't have any limitations (that I am aware of) and also dominates the Hamming bound over a large interval (as you can see in the graph in the notes you linked). Particularly in the range where \delta > 1/2, most bounds agree that R -> 0 except the Hamming bound. So if my logic above held, for 1/4 < p < 1/2 there would have to be only rate 0 codes, which again contradicts the tightness of the Shannon limit. $\endgroup$
    – D0SBoots
    Jan 26, 2021 at 2:21
  • $\begingroup$ I'll have another think about this--you're correct I believe. $\endgroup$
    – kodlu
    Jan 26, 2021 at 23:33

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.