Back to the on-screen lesson · Print

The binary symmetric channel

C = 1 − h(ε), the optimal input, and what n uses can carry.

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 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.

2. The binary symmetric channel

The binary symmetric channel $\text{BSC}(\varepsilon)$ delivers each bit correctly with probability $1 - \varepsilon$ and flipped with probability $\varepsilon$. Its transition matrix has rows $(1 - \varepsilon, \varepsilon)$ and $(\varepsilon, 1 - \varepsilon)$, each of entropy $h(\varepsilon)$, so $H(Y \mid X) = h(\varepsilon)$ for every input distribution and $I(X; Y) = H(Y) - h(\varepsilon) \le 1 - h(\varepsilon)$, with equality for the uniform input: $$C_{\text{BSC}} = 1 - h(\varepsilon).$$ The curve is symmetric about $\varepsilon = \tfrac{1}{2}$, where it vanishes: $\varepsilon = 0.1$ gives $0.531$, $\varepsilon = 0.11$ about $0.5$, $\varepsilon = 0.9$ again $0.531$ because the receiver can flip everything back. Over $n$ uses the reliable payload is at most $nC$ bits, so sending $k$ bits needs about $k / (1 - h(\varepsilon))$ uses: at $\varepsilon = 0.1$, roughly $1.9$ channel bits per message bit. Repetition coding wastes far more than that; the coding theorem promises codes that approach the bound.

3. From the matrix to the number

The derivation is three lines and worth doing once by hand. Both rows of the transition matrix are $(1 - \varepsilon, \varepsilon)$ up to order, so each has entropy $h(\varepsilon)$ and $H(Y \mid X) = h(\varepsilon)$ for every input distribution. Then $I(X; Y) = H(Y) - h(\varepsilon)$, and since $Y$ is a single bit, $H(Y) \le 1$. A uniform input makes $P(Y = 1) = \tfrac{1}{2}$ and so $H(Y) = 1$. Hence $$C_{\text{BSC}} = 1 - h(\varepsilon),$$ attained at the uniform input.

Two features of the curve matter in practice. It is symmetric: $\varepsilon$ and $1 - \varepsilon$ give the same capacity, because a receiver who knows the channel flips $90\%$ of bits simply inverts every bit it receives. And it is steep near the ends: $1\%$ errors still leave $0.919$ bits per use, while $20\%$ leave only $0.278$.

4. Solving the practice problems

1. Capacity from a crossover $p$: $1 - h(p)$.
2. Crossover above one half: replace $q$ by $1 - q$ first; $h$ is symmetric, so the capacity is $1 - h(1 - q) = 1 - h(q)$ either way.
3. Bits in $n$ uses: $nC$, rounded down to a whole bit. Multiply, then round; rounding $C$ first loses accuracy.
4. Which input achieves capacity: the uniform one, because the noise term is fixed and the uniform input maximises $H(Y)$.

Common mistakes

• Answering $h(\varepsilon)$ instead of $1 - h(\varepsilon)$.
• Treating $\varepsilon = 0.8$ as a worse channel than $\varepsilon = 0.2$: they are the same.
• Answering $1 - \varepsilon$: that is the erasure channel's capacity, and it is always larger.

5. How many uses for $1000$ bits?

1. $\varepsilon = 0.1$: $C = 1 - 0.469 = 0.531$ bits per use.

2. $1000 / 0.531 \approx 1883$ uses at least; $1500$ uses would mean rate $0.667 > C$, impossible.

   Rate must stay below capacity.

6. Repetition versus capacity

1. A $3$-repetition code on $\text{BSC}(0.1)$ has rate $\tfrac{1}{3}$ and still fails with probability $0.028$ per bit.

2. Capacity $0.531$ says codes exist with rate $0.5$ and error probability as small as desired: better rate and better reliability at once.

   The promise of the coding theorem.

7. Payload of $600$ uses at $\varepsilon = 0.2$

1. $h(0.2) = 0.722$, so $C = 0.278$ bits per use.

2. $600 \cdot 0.278 = 166.8$.

   Multiply first; rounding $C$ to $0.28$ would give $168$.

3. About $167$ information bits — and no code, however clever, carries more.

8. A channel that flips most bits

1. $\varepsilon = 0.9$: the channel is wrong nine times out of ten.

2. $h(0.9) = h(0.1) = 0.469$, so $C = 0.531$ bits per use.

   Exactly the capacity of $\varepsilon = 0.1$.

3. A receiver that inverts every received bit sees a channel with crossover $0.1$: consistent lying carries as much information as consistent truth.

9. Your turn: $C$ for $\varepsilon = 0.25$, and the payload of $400$ uses

1. $h(0.25) = 0.811$, so $C = 0.189$ bits per use.

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

   $400 \cdot 0.189 \approx 76$ bits at most.

10. Guided practice

What is the capacity of a binary symmetric channel with crossover probability $0.2$, in bits per use to three decimal places?

Computed value: _answer

11. Guided practice

A binary symmetric channel flips its input with probability $0.6$, more often than not. What is its capacity, to three decimal places?

Computed value: _answer

12. Practice

A binary symmetric channel with crossover $0.3$ is used $800$ times. About how many information bits can be sent reliably at best, to the nearest whole bit?

Computed value: _answer

13. Practice

What is the capacity of a binary symmetric channel with crossover probability $0.05$, in bits per use to three decimal places?

Computed value: _answer

14. Somewhere new

Which input distribution achieves the capacity of a binary symmetric channel, and why?

• The uniform input, because the noise entropy is fixed and the uniform input maximises $H(Y)$
• An input that sends mostly $0$, because $0$ is corrupted less often
• Any input: mutual information does not depend on the input for a symmetric channel

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 binary symmetric channel flips its input with probability $0.65$, more often than not. What is its capacity, to three decimal places?

Computed value: _answer

17. What you can do now

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.

Working for the steps left to you

9. Your turn: $C$ for $\varepsilon = 0.25$, and the payload of $400$ uses, step 2