Back to the on-screen lesson · Print

Channel capacity

C = max over inputs of I(X; Y); noiseless and useless channels; units of bits per use.

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 describe a discrete memoryless channel by its transition matrix, compute output distributions and noise entropies for a given input, explain what memorylessness means for blocks of uses, and recognise the binary symmetric, binary erasure and Z channels. You will define channel capacity as the maximum mutual information over input distributions, compute it for noiseless, useless and binary symmetric channels, explain why the uniform input is optimal when the noise entropy is fixed, and state the bounds that any capacity must satisfy, ready for the coding theorem that gives the definition its operational meaning.

2. Capacity

The capacity of a DMC is $$C = \max_{p(x)} I(X; Y)$$ bits per channel use: the most information any input distribution can push through one use. It depends on the channel only, satisfies $0 \le C \le \min(\log_2 |\mathcal{X}|, \log_2 |\mathcal{Y}|)$, and the maximum exists because $I$ is a continuous concave function of $p(x)$ on a compact set. A noiseless channel with $m$ inputs has $C = \log_2 m$; a channel whose output ignores the input has $C = 0$. For the BSC, $I = H(Y) - h(\varepsilon)$ with the noise term fixed, so the uniform input, which makes $H(Y) = 1$, is optimal and $C = 1 - h(\varepsilon)$; at $\varepsilon = 0$ this is $1$, at $\varepsilon = \tfrac{1}{2}$ it is $0$, and at $\varepsilon = 1$ it is $1$ again, since a channel that always flips is perfectly informative. The definition earns its name in the channel coding theorem: $C$ is exactly the largest rate at which arbitrarily reliable communication is possible.

3. Maximising over the input

Capacity is $C = \max_{p(x)} I(X; Y)$: the channel is given, the input distribution is yours to choose, and $C$ is the best you can do per use. The maximum exists because $I$ is continuous and concave in $p(x)$ over a compact set, and it obeys $$0 \le C \le \min\big(\log_2 |\mathcal{X}|, \log_2 |\mathcal{Y}|\big)$$ because $I \le H(X)$ and $I \le H(Y)$. The recipe that solves most channels in one line: if $H(Y \mid X)$ does not depend on the input — every row of the matrix has the same entropy — then maximising $I = H(Y) - H(Y \mid X)$ means maximising $H(Y)$ alone, and a uniform input usually makes the output uniform.

4. Solving the practice problems

1. Noiseless channel with $2^k$ symbols: $C = \log_2 2^k = k$ bits per use.
2. BSC with crossover $p$, uniform input: $1 - h(p)$, from the table above.
3. Output independent of the input: $I = 0$ for every input, so $C = 0$ — the alphabet sizes are a distraction.
4. The definition: the maximum of $I(X; Y)$ over input distributions — not the mutual information at a particular input, and not a maximum over channels.

Common mistakes

• Answering $2^k$ for the noiseless channel: capacity is measured in bits, so take the logarithm.
• Maximising $H(Y)$ when the row entropies differ (the Z-channel): then the best input is not uniform.
• Confusing $C$ with $I$ at some input: $I$ depends on the input, $C$ does not.

5. Capacity of the BSC

1. $I(X; Y) = H(Y) - H(Y \mid X) = H(Y) - h(\varepsilon)$, and $H(Y) \le 1$ with equality when $Y$ is uniform, which the uniform input achieves.

   Noise term fixed, output entropy maximised.

2. $C = 1 - h(\varepsilon)$: $0.531$ at $\varepsilon = 0.1$, $0.278$ at $\varepsilon = 0.2$, $0$ at $\varepsilon = 0.5$.

6. Two bounds on capacity

1. $I(X; Y) \le H(X) \le \log_2 |\mathcal{X}|$ and $I(X; Y) \le H(Y) \le \log_2 |\mathcal{Y}|$.

   Mutual information never exceeds either entropy.

2. So a channel with $4$ inputs and $8$ outputs has $C \le 2$ bits per use, however the outputs are arranged.

7. Capacity from the two bounds

1. A channel has $8$ inputs and $4$ outputs.

2. $I \le H(X) \le \log_2 8 = 3$ and $I \le H(Y) \le \log_2 4 = 2$.

3. $C \le 2$ bits per use, however clean the channel: you cannot learn more than the output can express.

8. Why the uniform input is optimal for the BSC

1. $I(X; Y) = H(Y) - H(Y \mid X) = H(Y) - h(\varepsilon)$ for every input distribution.

   The subtracted term is a constant of the channel.

2. $Y$ is binary, so $H(Y) \le 1$, with equality when $P(Y = 1) = \tfrac{1}{2}$.

3. A uniform input gives $P(Y = 1) = \tfrac{1}{2}(1 - \varepsilon) + \tfrac{1}{2}\varepsilon = \tfrac{1}{2}$, so $C = 1 - h(\varepsilon)$.

9. Your turn: capacity of a BSC with $\varepsilon = 0.9$

1. $C = 1 - h(0.9) = 1 - h(0.1)$ by symmetry of $h$.

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

   $0.531$ bits: the receiver simply flips every bit back.

10. Guided practice

A noiseless channel delivers each of its $16$ input symbols exactly. What is its capacity in bits per use?

Computed value: _answer

11. Guided practice

A binary symmetric channel has crossover probability $0.35$. Compute $I(X; Y)$ for the uniform input, in bits to three decimal places; this is the channel's capacity.

Computed value: _answer

12. Practice

A channel with $4$ inputs and $8$ outputs produces its output uniformly at random, independently of the input. What is its capacity?

Computed value: _answer

13. Practice

A noiseless channel delivers each of its $8$ input symbols exactly. What is its capacity in bits per use?

Computed value: _answer

14. Somewhere new

Which is the definition of the capacity of a discrete memoryless channel?

• $C = \max_{p(x)} I(X; Y)$, the largest mutual information over input distributions
• $C = H(Y)$, the entropy of the output
• $C = \log_2 |\mathcal{X}|$, the number of input bits
• $C = \min_{p(x)} I(X; Y)$, the worst-case mutual information

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 has crossover probability $0.4$. Compute $I(X; Y)$ for the uniform input, in bits to three decimal places; this is the channel's capacity.

Computed value: _answer

17. What you can do now

You can model a noisy channel and compute how much information one use can carry at best. Next: the two workhorse channels, binary symmetric and binary erasure, in detail.

Working for the steps left to you

9. Your turn: capacity of a BSC with $\varepsilon = 0.9$, step 2