Channel Capacity Theorem

Capacity C = _p(x) I(X;Y) as the limit of reliable rate.

The idea

Shannon's noisy-channel coding theorem identifies the largest rate at which information can cross a noisy channel with vanishing probability of error.

Definition (Channel capacity).

The capacity of a channel with input $X$ and output $Y$ is $C = \max_{p(x)} I(X; Y),$ the mutual information between input and output, maximized over all distributions on the input. With base-$2$ logarithms, $C$ is measured in bits per channel use.

The maximization belongs in the definition: the channel is fixed, but the sender chooses the input distribution, and different choices carry different amounts of information through.

Call a rate $R$ achievable if there are codes of growing block length that transmit $R$ bits per channel use with error probability tending to $0$.

Theorem (Noisy-channel coding theorem).

For a discrete memoryless channel of capacity $C$, every rate $R < C$ is achievable, and no rate $R > C$ is.

Both halves are strong claims. The first says noise does not force errors: below capacity, coding over long enough blocks makes the error rate as small as we like, at no cost in rate. The second says the threshold at $C$ is absolute: no code, of any block length or structure, communicates reliably above it.

Ways to work on it

• Walkthrough. Capacity as maximized mutual information, and the coding theorem's threshold.
• Practice. Capacity of a binary symmetric channel, C = 1 - H(p).
• Hardest. Find the capacity of a binary erasure channel.

Not sure where to start? Take the ten-question placement test.