Channel Coding Theorem — Mathematics Knowledge System

Overview

Shannon's channel coding theorem (noisy channel theorem) is the central result of information theory: reliable communication is possible over a noisy channel at any rate R < C (channel capacity), and impossible at any rate R > C. The theorem is existential -- it guarantees the existence of good codes without constructing them explicitly.

Intuition

A channel has capacity C bits per use. If you try to send R < C bits per use, Shannon guarantees that reliable codes exist (vanishing error probability as block length grows). If R > C, you cannot avoid errors no matter how clever your code. The proof uses random coding: most random codebooks are good. The key insight: at rate R < C, the typical set of outputs for each input is nearly disjoint from typical sets for other inputs.

Formal Definition

Definition

A discrete memoryless channel (DMC) has input X, output Y, transition p(y|x). Channel capacity C = max_{p(x)} I(X;Y). Channel coding theorem: (i) Achievability: for any R < C and epsilon > 0, there exists n sufficiently large and a code of rate R with error probability < epsilon. (ii) Converse: for any R > C, any code has error probability bounded below by a positive constant.

C = \max_{p(x)} I(X; Y)

Channel capacity

R < C \Rightarrow P_e^{(n)} \to 0 \text{ (achievability)}

Achievability

R > C \Rightarrow P_e^{(n)} \geq 1 - \frac{C}{R} - \frac{\log(n+1)}{nR} \text{ (converse, Fano)}

Converse via Fano's inequality

Notation

Notation	Meaning
$C$	Channel capacity in bits per channel use
$R$	Code rate in bits per channel use
$P_e^{(n)}$	Error probability for block length n

Theorems

Theorem 1: Shannon Channel Coding Theorem

For a DMC with capacity C: (i) For R < C, there exist codes with block length n such that max_{m} P(error|m sent) -> 0 as n -> inf. (ii) For R > C, for any sequence of codes, max_{m} P(error|m) >= f(R,C) > 0 for all n sufficiently large.

Worked Examples

1
I(X;Y) is maximized by uniform input: p(x=0)=p(x=1)=1/2.
$C = 1 - H(p) = 1 - H(0.1)$
2
H(0.1) = -0.1*log(0.1) - 0.9*log(0.9) ≈ 0.469 bits.
$C = 1 - 0.469 = 0.531 \text{ bits/use}$

✓ Answer

C = 1 - H(0.1) ≈ 0.531 bits per channel use.

Practice Problems

Hardapplication

A BSC has capacity C = 0.5 bits. Is it possible to send 1000 bits with probability of error < 0.001 using 3000 channel uses?

Common Mistakes

Common Mistake

Thinking Shannon's theorem gives you a specific good code.

The theorem is existential -- it proves codes exist but doesn't construct them. Finding explicit capacity-achieving codes is a major research area (turbo codes, LDPC codes, polar codes).

Quiz

If the channel capacity is C = 2 bits/use and you transmit at rate R = 3 bits/use, then:

Reliable communication is possible with a good codeError probability goes to zero for long codesError probability is bounded away from zero regardless of codeNo information can be transmitted

Historical Background

Shannon announced the channel coding theorem in 1948 in 'A Mathematical Theory of Communication,' shocking the engineering community. Before Shannon, it was believed that reducing error required reducing the transmission rate toward zero. Shannon showed that a nonzero rate C exists below which errors can be driven to zero. The task of finding explicit capacity-achieving codes took decades: turbo codes (1993) and LDPC codes (rediscovered 1993) are practical approaches.

1948
Shannon proves the channel coding theorem
Claude Shannon
1993
Turbo codes and LDPC codes approach Shannon capacity practically
Claude Berrou

Summary

Channel capacity C = max_{p(x)} I(X;Y).
R < C: reliable codes exist (error -> 0 as block length -> inf).
R > C: no code achieves error -> 0 (error bounded below).
BSC with crossover p: C = 1 - H(p). Erasure channel with erasure prob e: C = 1 - e.

References

BookCover, T.M. and Thomas, J.A. Elements of Information Theory. 2nd ed. Wiley, 2006.