Back to the on-screen lesson ·
Cascades, parallel channels, product channels, and capacity per second.
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 recognise symmetric and weakly symmetric channels from their transition matrices, prove that the uniform input is optimal for them and compute their capacity as $\log_2 |\mathcal{Y}|$ minus a row entropy, and explain through the noisy typewriter how non-overlapping output sets give error-free communication at capacity. You will combine capacities correctly for channels used in parallel, in cascade and over time, using data processing to bound cascades and independence to add parallel channels, and you will reduce two symmetric channels in series to a single equivalent channel.
Real systems combine channels, and capacity combines with them in three standard ways. Parallel (product) channels used independently, one symbol through each per joint use, have capacity $C_1 + C_2$: independent inputs make the mutual informations add, and $I(X_1 X_2; Y_1 Y_2) \le I(X_1; Y_1) + I(X_2; Y_2)$ shows nothing better is possible. Cascaded channels, the output of the first feeding the second, form a Markov chain $X \to Y_1 \to Y_2$, so by data processing $C \le \min(C_1, C_2)$, usually with strict inequality; two BSCs in cascade are one BSC with crossover $\varepsilon_1 + \varepsilon_2 - 2\varepsilon_1 \varepsilon_2$. Capacity per second is capacity per use times uses per second, which is how bits per use become a data rate; for a sum channel that offers a choice of one of two channels per use, $C = \log_2(2^{C_1} + 2^{C_2})$. These rules, with the symmetric-channel formula and the definition, cover most capacities one meets.
Another way: picture
Two diagrams: side by side, two boxes fed by two arrows and read by two arrows, capacities adding; in series, one box feeding the next, where the second box can only lose what the first passed on.
Another way: steps
| combination | capacity | why | example |
|---|---|---|---|
| parallel (one symbol each) | $C_1 + C_2$ | independent inputs make the informations add | $0.4 + 0.7 = 1.1$ |
| cascade (output feeds the next) | $\le \min(C_1, C_2)$ | data processing on $X \to Y_1 \to Y_2$ | usually strictly less |
| per second | $C \times$ uses per second | a unit conversion, nothing more | $0.75 \times 4000 = 3000$ bit/s |
Parallel channels add because independent inputs make the mutual informations add, and $I(X_1 X_2; Y_1 Y_2) \le I(X_1; Y_1) + I(X_2; Y_2)$ shows nothing better is possible. Cascades are governed by the data processing inequality: $X \to Y_1 \to Y_2$ is a Markov chain, so $C \le \min(C_1, C_2)$, and the inequality is usually strict — noise accumulates.
| $p$ | $s$ | $e = p + s - 2ps$ | $h(e)$ | $1 - h(e)$ | $1 - h(p)$ |
|---|---|---|---|---|---|
| $0.1$ | $0.1$ | $0.18$ | $0.680$ | $0.320$ | $0.531$ |
| $0.1$ | $0.2$ | $0.26$ | $0.827$ | $0.173$ | $0.531$ |
| $0.2$ | $0.2$ | $0.32$ | $0.904$ | $0.096$ | $0.278$ |
| $0.05$ | $0.1$ | $0.14$ | $0.584$ | $0.416$ | $0.714$ |
| $0.1$ | $0.3$ | $0.34$ | $0.925$ | $0.075$ | $0.531$ |
Read the last two columns: a cascade of two $\text{BSC}(0.1)$ has capacity $1 - h(0.18) = 0.320$, well under the $0.531$ of a single stage. Decoding between the stages — correcting after the first channel and re-encoding for the second — avoids the accumulation, which is exactly why long links use repeaters rather than one end-to-end code.
Common mistakes
$\text{BSC}(0.1)$ then $\text{BSC}(0.1)$: a bit is wrong at the end when exactly one stage flips, probability $2 \cdot 0.1 \cdot 0.9 = 0.18$.
Combine the stages.
$C = 1 - h(0.18) = 0.320$, well below the single-stage $0.531$; decoding between the stages would keep $0.531$.
Relays that decode and re-encode beat raw cascades.
A channel with $C = 0.75$ bits per use, signalling at $4000$ symbols per second.
$0.75 \times 4000 = 3000$ bits per second is the reliable limit, whatever modulation and code are used.
A channel with $C = 0.75$ bits per use, signalling $4000$ times per second.
$0.75 \times 4000 = 3000$ bits per second.
Bits per use times uses per second; the units cancel.
No modulation, code or protocol beats $3000$ bit/s on that channel; only more bandwidth or more power moves the ceiling.
Two channels with capacities $0.4$ and $0.7$ bits per use.
Side by side: $0.4 + 0.7 = 1.1$ bits per joint use.
In cascade: at most $\min(0.4, 0.7) = 0.4$, and in general less — the same two devices, arranged differently, differ by more than a factor of two.
Parallel: $0.4 + 0.7 = 1.1$ bits per joint use.
Cascade: at most $0.4$, and less unless the $0.7$ channel is noiseless.
Two independent channels with capacities $3/4$ and $5/4$ bits per use are used side by side, once each. What is the capacity of the combined (product) channel per joint use?
Computed value: answer
A $\text{BSC}(0.1)$ is followed by a $\text{BSC}(0.1)$, output of the first feeding the second. What is the capacity of the cascade, in bits per use to three decimal places?
Computed value: answer
A channel has capacity $5/8$ bits per use and is used $1 \times 10^{4}$ times per second. What is its capacity in bits per second?
Computed value: answer
Two independent channels with capacities $4/4$ and $2/4$ bits per use are used side by side, once each. What is the capacity of the combined (product) channel per joint use?
Computed value: answer
Channel 1 has capacity $4/10$ and channel 2 has capacity $8/10$ bits per use. They are connected in cascade, the output of channel 1 feeding channel 2 directly. Which is true of the cascade's capacity $C$?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A $\text{BSC}(0.2)$ is followed by a $\text{BSC}(0.2)$, output of the first feeding the second. What is the capacity of the cascade, in bits per use to three decimal places?
Computed value: answer
You can compute the capacity of any symmetric channel and of combinations of channels. Next: the theorem that makes capacity the true speed limit of reliable communication.
9. Your turn: capacities $0.4$ and $0.7$ used in parallel, then in cascade, step 2