Back to the on-screen lesson · Print

The converse and feedback

Fano proves no rate above C is reliable; feedback does not raise DMC capacity.

Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.

1. What you will learn

By the end of this lesson you will be able to prove the converse to the channel coding theorem by chaining Fano's inequality, the data processing inequality and the memoryless bound $I(X^n; Y^n) \le nC$, compute the error floor that any code above capacity must suffer, and explain why noiseless feedback leaves the capacity of a memoryless channel unchanged while simplifying good codes. You will state the source-channel separation theorem, decide whether a source can be carried by a channel from its entropy rate and the capacity, compute the channel uses per symbol required, and say when practical systems have reason to depart from separation.

2. The converse

The converse to the channel coding theorem says that at any rate $R > C$ the error probability stays bounded away from $0$, however long the code. Let $W$ be uniform on $2^{nR}$ messages, so $H(W) = nR$. Then $$nR = H(W) = H(W \mid Y^n) + I(W; Y^n) \le \big(1 + P_e nR\big) + I(X^n; Y^n) \le 1 + P_e nR + nC,$$ using Fano's inequality for the first term, data processing ($W \to X^n \to Y^n$) for the second, and for the last step the memoryless property: $I(X^n; Y^n) = H(Y^n) - \sum_i H(Y_i \mid X_i) \le \sum_i \big(H(Y_i) - H(Y_i \mid X_i)\big) \le nC$. Rearranged, $P_e \ge 1 - \dfrac{C}{R} - \dfrac{1}{nR}$, a positive floor whenever $R > C$. The same chain survives feedback, since $Y_i$ given $X_i$ is still independent of everything else, so feedback cannot increase the capacity of a discrete memoryless channel, although it can make simple schemes optimal, as retransmitting erased symbols on the erasure channel shows.

3. The chain, one line at a time

The converse is a budget argument: the message carries $nR$ bits of uncertainty, the channel can deliver at most $nC$ bits about it, and Fano's inequality says the leftover must show up as errors.

Step 5 is the one that uses the channel's structure. Memorylessness gives $H(Y^n \mid X^n) = \sum_i H(Y_i \mid X_i)$, and subadditivity gives $H(Y^n) \le \sum_i H(Y_i)$, so $$I(X^n; Y^n) = H(Y^n) - H(Y^n \mid X^n) \le \sum_i \big(H(Y_i) - H(Y_i \mid X_i)\big) = \sum_i I(X_i; Y_i) \le nC.$$ Nothing about the code enters — which is why the bound holds for every code, and why the same chain survives noiseless feedback: with feedback $X_i$ may depend on past outputs, but $Y_i$ still depends only on $X_i$, so step 5 is unchanged and $C$ does not grow.

Feedback still helps in practice: on an erasure channel, resending each erased bit until it arrives needs $1/(1 - \alpha)$ uses per bit on average — exactly the capacity — with a decoder of one line and no block code at all. It bought simplicity, not capacity.

4. Solving the practice problems

1. Asymptotic floor from $C$ and $R$: $1 - C/R$, as a fraction. Both are given over the same denominator, so the ratio is a ratio of the numerators.
2. Finite-$n$ bound $P_e \ge 1 - \dfrac{nC + 1}{nR}$: substitute $n$, $C$ and $R = 1$ and simplify to a fraction.
3. Which chain proves the converse: Fano on $H(W \mid Y^n)$, data processing for $I(W; Y^n) \le I(X^n; Y^n)$, and memorylessness for $I(X^n; Y^n) \le nC$.
4. What feedback does to capacity: nothing. It can simplify coding, but $C$ is unchanged for a discrete memoryless channel.

Common mistakes

• Writing $C/R$ for the floor instead of $1 - C/R$.
• Believing feedback raises capacity because it clearly helps; it raises convenience.
• Reading the floor as the actual error probability: it is a lower bound that every code must exceed.

5. Why $I(X^n; Y^n) \le nC$

1. $I(X^n; Y^n) = H(Y^n) - H(Y^n \mid X^n)$ and memorylessness gives $H(Y^n \mid X^n) = \sum_i H(Y_i \mid X_i)$.

   The noise acts symbol by symbol.

2. $H(Y^n) \le \sum_i H(Y_i)$ by subadditivity, so $I(X^n; Y^n) \le \sum_i I(X_i; Y_i) \le nC$.

   Each use is worth at most $C$.

6. Feedback on the erasure channel

1. With feedback, resend each erased bit until it gets through: the expected uses per bit are $1/(1 - \alpha)$, rate $1 - \alpha = C$.

   A trivial scheme reaches capacity.

2. But capacity is still $1 - \alpha$: feedback simplified the code, it did not enlarge the limit.

7. The floor at rate $0.8$ on a channel with $C = 0.5$

1. $1 - C/R = 1 - 0.5/0.8 = 1 - 0.625$.

2. $P_e \ge 0.375$ as $n$ grows.

   The $1/(nR)$ term vanishes with $n$.

3. More than a third of the messages are decoded wrongly, however long and clever the code.

8. A finite block at rate $1$

1. $C = \tfrac{1}{4}$, $n = 20$, $R = 1$, so $nC = 5$ and $nR = 20$.

2. $P_e \ge 1 - \dfrac{5 + 1}{20} = 1 - \dfrac{3}{10}$.

3. $P_e \ge \tfrac{7}{10}$: seven messages in ten arrive wrong, at best.

9. Your turn: rate $0.8$ on a channel with $C = 0.5$; the asymptotic error floor?

1. $P_e \ge 1 - C/R = 1 - 0.5/0.8$.

2. Your turn: work this step out. Its working is at the end of the packet.

   $P_e \ge 0.375$: at least three messages in eight are decoded wrongly, for every code.

10. Guided practice

A channel has capacity $4/7$ bits per use and a code runs at rate $6/7$. As the block length grows, the converse gives a lower bound on the error probability. What is it, as a fraction?

Computed value: _answer

11. Guided practice

A channel has capacity $4/9$ bits per use; a code of length $n = 45$ carries $45$ message bits (rate $1$). Using $P_e \ge 1 - \dfrac{nC + 1}{nR}$, what is the lower bound on its error probability, as a fraction?

Computed value: _answer

12. Practice

Which chain of inequalities proves the converse to the channel coding theorem for a uniformly chosen message $W$ sent as $X^n$ and decoded from $Y^n$?

• $nR = H(W) \le 1 + P_e nR + I(X^n; Y^n) \le 1 + P_e nR + nC$, so $P_e \to 0$ forces $R \le C$
• $nR \ge I(X^n; Y^n) \ge nC$, so $R \ge C$ for every code
• $H(W \mid Y^n) = 0$ for every decoder, so $R = C$

13. Practice

A channel has capacity $2/9$ bits per use and a code runs at rate $7/9$. As the block length grows, the converse gives a lower bound on the error probability. What is it, as a fraction?

Computed value: _answer

14. Somewhere new

The receiver of a discrete memoryless channel can tell the sender every received symbol before the next is sent (noiseless feedback). What happens to the capacity?

• It stays the same: feedback cannot raise the capacity of a memoryless channel, but it can simplify codes
• It doubles, since information flows both ways
• It becomes $\log_2 |\mathcal{X}|$, since every error can be corrected by resending

15. Lesson test

Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.

16. Test question

A channel has capacity $6/8$ bits per use; a code of length $n = 40$ carries $40$ message bits (rate $1$). Using $P_e \ge 1 - \dfrac{nC + 1}{nR}$, what is the lower bound on its error probability, as a fraction?

Computed value: _answer

17. What you can do now

You can prove both directions of the coding theorem and connect sources to channels through $H < C$. Next: the Gaussian channel, where signals are real numbers and power is the constraint.

Working for the steps left to you

9. Your turn: rate $0.8$ on a channel with $C = 0.5$; the asymptotic error floor?, step 2