Back to the on-screen lesson ·
A source is transmissible iff H < C; compression and error correction can be designed apart.
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.
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.
The source-channel separation theorem joins the two halves of the course. A stationary ergodic source with entropy rate $H$ can be sent over a discrete memoryless channel of capacity $C$, one channel use per source symbol, with error probability tending to $0$ if $H < C$, and cannot if $H > C$. Achievability is a two-stage design: compress the source to about $H$ bits per symbol (typical-set or arithmetic coding), then protect those bits with a channel code at a rate between $H$ and $C$. The converse combines Fano's inequality with the converse for channels and the AEP for the source. With $\rho$ channel uses per source symbol the condition becomes $H < \rho C$, so at least $H/C$ uses per symbol are needed. The theorem says a bit is a bit: the compressor need not know the channel and the channel coder need not know the source, which is why layered communication systems work. Its assumptions matter, though: with strict delay limits, short blocks, or several users sharing a channel, joint source-channel designs can do better.
Another way: picture
A pipeline: source $\to$ compressor ($H$ bits per symbol) $\to$ channel encoder (rate below $C$) $\to$ channel $\to$ channel decoder $\to$ decompressor $\to$ reconstruction. The only number that has to line up across the dashed boundary between the two halves is $H < C$.
Another way: steps
The separation theorem joins the two halves of the course. A stationary ergodic source of entropy rate $H$ can be sent over a channel of capacity $C$, one use per symbol, with error tending to $0$ if $H < C$, and cannot if $H > C$. Achievability is the obvious two-stage design: compress to about $H$ bits per symbol (typical sets or arithmetic coding, lessons 10 and 11), then protect those bits with a channel code at a rate between $H$ and $C$ (lesson 15). The converse combines Fano for the source with the channel converse.
With $\rho$ channel uses per source symbol the condition becomes $H < \rho C$, so at least $H/C$ uses per symbol are needed:
| source rate $H$ | capacity $C$ | uses per symbol $\rho$ | $\rho C$ | transmissible? |
|---|---|---|---|---|
| $0.4$ | $0.5$ | $1$ | $0.5$ | yes |
| $0.6$ | $0.5$ | $1$ | $0.5$ | no |
| $0.6$ | $0.5$ | $2$ | $1.0$ | yes |
| $1.3$ | $0.531$ | $3$ | $1.59$ | yes |
| $0.6$ | $0.25$ | $2.4$ | $0.6$ | borderline |
What the theorem buys is modularity: a compression team and a coding team may work separately and lose nothing asymptotically, which is why formats and modems are designed by different people. What it hides is that the promise is asymptotic. At short block lengths, or with a delay budget, or when the channel varies, joint source-channel schemes do better — which is why video over a mobile link is not simply a compressor bolted to a channel code.
Common mistakes
English text at about $1.3$ bits per letter over a $\text{BSC}(0.1)$ with $C = 0.531$, one use per letter: $1.3 > 0.531$, impossible.
Compare $H$ with $C$.
With $\rho = 3$ uses per letter, $\rho C = 1.59 > 1.3$: compress to $1.3$ bits per letter, then a rate-$0.45$ channel code, and it works.
Separate stages, one condition.
Any scheme, joint or not, maps source blocks to channel inputs; Fano on the source block gives $H(V^n \mid \hat{V}^n) \le 1 + P_e n \log_2 |\mathcal{V}|$.
Then $nH \approx H(V^n) \le 1 + P_e n \log_2 |\mathcal{V}| + I(V^n; \hat{V}^n) \le 1 + P_e n \log_2 |\mathcal{V}| + nC$, so $P_e \to 0$ forces $H \le C$.
The same chain as the channel converse.
English at about $1.3$ bits per letter over a $\text{BSC}(0.1)$ with $C = 0.531$, one use per letter.
$1.3 > 0.531$: impossible at one use per letter.
With $\rho = 3$ uses per letter, $\rho C = 1.59 > 1.3$: compress to $1.3$ bits per letter, then code those bits at a rate under $0.531$.
$\rho \ge H/C = 2.45$, so three uses suffice and two do not.
A source has $H = \tfrac{7}{4}$ bits per symbol; the channel has $C = \tfrac{3}{4}$ bits per use.
$\rho \ge H/C = \tfrac{7/4}{3/4} = \tfrac{7}{3}$.
The quarters cancel: divide the numerators.
At least $\tfrac{7}{3} \approx 2.33$ channel uses per source symbol; in practice, three.
Need $\rho C > H$, so $\rho > 0.6 / 0.25$.
$\rho > 2.4$: at least $2.4$ channel uses per source symbol, in the limit.
A source has entropy rate $4/8$ bits per symbol and a channel has capacity $6/8$ bits per use, with one channel use per source symbol. Can the source be transmitted with vanishing error probability?
A source has entropy rate $3/4$ bits per symbol and the channel has capacity $2/4$ bits per use. At least how many channel uses per source symbol are needed for reliable transmission? Give a fraction.
Computed value: answer
What does the source-channel separation theorem say about designing a communication system?
A source has entropy rate $1/8$ bits per symbol and a channel has capacity $4/8$ bits per use, with one channel use per source symbol. Can the source be transmitted with vanishing error probability?
When might a practical system deliberately not separate source coding from channel coding?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A source has entropy rate $4/4$ bits per symbol and the channel has capacity $1/4$ bits per use. At least how many channel uses per source symbol are needed for reliable transmission? Give a fraction.
Computed value: answer
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.
9. Your turn: $H = 0.6$, $C = 0.25$; uses per symbol?, step 2