Back to the on-screen lesson ·
C = 1 − α, why erasures cost less than errors, and uses needed per bit.
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 derive the capacity $1 - h(\varepsilon)$ of the binary symmetric channel, explain why the uniform input achieves it and why the curve is symmetric about one half, and convert a capacity into a payload for a given number of uses or a number of uses for a given message. You will derive the capacity $1 - \alpha$ of the binary erasure channel in two ways, from the mutual information and from the genie argument, compare erasures with errors at the same probability, and recognise where each channel models a real system.
The binary erasure channel $\text{BEC}(\alpha)$ delivers each bit intact with probability $1 - \alpha$ and replaces it by an erasure symbol $?$ with probability $\alpha$; it never delivers a wrong bit. Use $I(X; Y) = H(X) - H(X \mid Y)$: when $Y = ?$ all of $H(X)$ remains, otherwise nothing, so $H(X \mid Y) = \alpha H(X)$ and $I = (1 - \alpha) H(X) \le 1 - \alpha$, with equality for the uniform input: $$C_{\text{BEC}} = 1 - \alpha.$$ An upper-bound argument makes this intuitive: a receiver told in advance which uses will be erased could still learn at most one bit from each surviving use, and advance knowledge can only help. Compared with a BSC at the same probability, the erasure channel is better, $1 - \alpha > 1 - h(\alpha)$ on $(0, 1)$: an erasure is a known loss, an error is a hidden one. The BEC models packet loss on the internet, where a missing packet is detected by its sequence number, and it is the channel on which capacity-achieving codes such as LDPC and fountain codes are simplest to analyse.
Another way: picture
Two capacity curves on the same axes: $1 - \alpha$, a straight line from $1$ down to $0$, and $1 - h(\alpha)$, the valley below it. At every probability strictly between $0$ and $1$ the erasure line lies above.
Another way: steps
Take $I = H(X) - H(X \mid Y)$ this time, because the erasure channel is easiest to read backwards. If $Y \ne \,?$ the input is known exactly, so nothing of $X$ remains; if $Y = \,?$ nothing was learned, so all of $H(X)$ remains. Averaging, $H(X \mid Y) = \alpha H(X)$ and $$I(X; Y) = (1 - \alpha) H(X) \le 1 - \alpha,$$ with equality for the uniform input: $C_{\text{BEC}} = 1 - \alpha$. An intuition that makes the answer obvious: imagine the receiver were told in advance which uses will be erased. It would then face $(1 - \alpha) n$ clean binary uses, worth $1$ bit each, and advance knowledge can only help — so $1 - \alpha$ is an upper bound, and the calculation shows it is achieved.
| probability | BEC capacity $1 - \alpha$ | BSC capacity $1 - h(\varepsilon)$ | ratio |
|---|---|---|---|
| $0.05$ | $0.95$ | $0.714$ | $1.33$ |
| $0.1$ | $0.9$ | $0.531$ | $1.69$ |
| $0.2$ | $0.8$ | $0.278$ | $2.88$ |
| $0.3$ | $0.7$ | $0.119$ | $5.88$ |
| $0.5$ | $0.5$ | $0$ | $\infty$ |
At every probability strictly between $0$ and $1$ the erasure channel is better, and the gap widens as the channel worsens. The reason is one word: location. An erasure says where the damage is; a flip does not, and the receiver must spend information finding out.
Common mistakes
$P(X = 1) = q$: $H(X) = h(q)$ and $H(X \mid Y) = P(Y = ?) H(X \mid Y = ?) + P(Y \ne ?) \cdot 0 = \alpha h(q)$.
Condition on whether an erasure happened.
$I = (1 - \alpha) h(q)$, maximised at $q = \tfrac{1}{2}$: $C = 1 - \alpha$.
A link loses $30\%$ of packets, each loss detected: a $\text{BEC}(0.3)$ at the packet level with $C = 0.7$.
To deliver $700$ packets of data reliably you must send about $1000$: fountain codes achieve this without retransmission requests.
Uses per bit $= 1/(1 - \alpha)$.
A link loses $30\%$ of packets and the loss is always detected: a $\text{BEC}(0.3)$ at the packet level.
Capacity $1 - 0.3 = 0.7$ packets of data per packet sent.
To deliver $700$ packets of data you must send about $1000$; fountain codes come within a few per cent of that limit.
$\text{BEC}(0.3)$ has $C = 0.7$, so rate $0.6$ is below capacity: achievable.
$\text{BEC}(0.5)$ has $C = 0.5$, so rate $0.6$ is above capacity: not achievable at any block length.
The comparison is always rate against capacity; the block length changes how close you get, never whether you can.
Capacities $0.7$ and $0.5$.
$0.6 < 0.7$: yes; $0.6 > 0.5$: no.
What is the capacity of a binary erasure channel with erasure probability $3/8$? Give a fraction.
Computed value: answer
A binary erasure channel with erasure probability $2/6$ is used $102$ times. At most how many information bits can be carried reliably?
Computed value: answer
Which has the larger capacity: a binary erasure channel with erasure probability $0.3$, or a binary symmetric channel with crossover probability $0.3$?
What is the capacity of a binary erasure channel with erasure probability $1/8$? Give a fraction.
Computed value: answer
Why is the capacity of the binary erasure channel exactly $1 - \alpha$ and not more?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A binary erasure channel with erasure probability $3/7$ is used $119$ times. At most how many information bits can be carried reliably?
Computed value: answer
You know the two textbook channels by heart and can size a transmission against their capacities. Next: symmetric channels in general and the tricks for computing capacity.
9. Your turn: is rate $0.6$ achievable on $\text{BEC}(0.3)$? On $\text{BEC}(0.5)$?, step 2