# Shannon limit vs Hamming bound

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?

• 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 :-) Jan 27, 2021 at 19:32
• 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. Jan 27, 2021 at 21:41