Noisy-channel coding theorem

The noisy-channel coding theorem is a fundamental result in information theory establishing the maximum rate at which information can be transmitted reliably through a noisy communication channel. For a discrete memoryless channel, every rate strictly below its channel capacity permits codes whose decoding error probability tends to zero as block length increases; rates strictly above capacity do not. Claude Shannon introduced the result in his 1948 paper A Mathematical Theory of Communication. It establishes the possibility of reliable communication despite noise, without requiring the noise itself to disappear. (web.njit.edu)

Channel model and coding

The standard formulation concerns a discrete memoryless channel with finite input and output alphabets $\mathcal X$ and $\mathcal Y$ . Its behavior is specified by the conditional probabilities $W(y\mid x)$ . “Memoryless” means that, conditional on the transmitted sequence, successive outputs are independent and each depends only on the corresponding input:

W^n(y^n\mid x^n)=\prod_{i=1}^{n}W(y_i\mid x_i).

The same transition law applies at every use. This assumption does not require the symbols within a codeword to be independent. (ocw.mit.edu)

An $(n,M)$ code consists of an encoder assigning each of $M$ messages a length- $n$ input sequence, called a codeword, and a decoder assigning an estimated message to each received sequence. Its rate is

R_n=\frac{\log_2 M}{n},

measured in bits per channel use. With a uniformly selected message $U$ , the average block error probability is $P_e^{(n)}=\Pr(\widehat U\ne U)$ . Block error concerns the entire decoded message, rather than the proportion of incorrectly decoded bits. An error-correcting code sacrifices some potential message rate to make different messages distinguishable after transmission. (ocw.mit.edu)

Mathematical statement

For the finite-alphabet channel described above, capacity is

C=\max_{P_X} I(X;Y),

where the maximization ranges over input probability distributions, and the input and output random variables have joint law $P_X(x)W(y\mid x)$ . Their mutual information is

I(X;Y)= \sum_{x,y}P_X(x)W(y\mid x) \log_2 \frac{W(y\mid x)} {\sum_{x'}P_X(x')W(y\mid x')}.

Equivalently, $I(X;Y)=H(X)-H(X\mid Y)$ : the input’s entropy minus the conditional entropy remaining after the output is observed. (ocw.mit.edu)

The theorem has two parts:

Achievability: For every $0<R<C$ , there is a sequence of codes with limiting rate at least $R$ and $P_e^{(n)}\to0$ .
Converse: Any sequence of codes with vanishing error probability must have $\limsup_{n\to\infty}R_n\le C$ .

Thus capacity is a supremum of reliably achievable rates. The basic statement does not assert that a fixed positive-length code is error-free, nor that operation at exactly $C$ always has vanishing error. For finite-alphabet discrete memoryless channels, the stronger converse states that error tends to one when rates remain bounded strictly above capacity. (ocw.mit.edu)

Proof principles

Achievability can be established through random coding. Choose an input distribution with $I(X;Y)>R$ , then independently generate approximately $2^{nR}$ codewords according to its product distribution. A decoder seeks the unique codeword statistically compatible with the received sequence. The law of large numbers makes the transmitted input-output pair typically compatible, while the chance of an unrelated codeword appearing compatible decreases approximately as $2^{-nI(X;Y)}$ . Because $R<I(X;Y)$ , the ensemble-average error tends to zero. Consequently, at least one deterministic codebook has small error; fresh random codebooks need not be generated during operation. (ocw.mit.edu)

The converse uses Fano’s inequality and the data-processing inequality. For a uniformly distributed message,

H(U\mid Y^n)\le 1+P_e^{(n)}\log_2 M.

Processing through the encoder and channel gives $I(U;Y^n)\le I(X^n;Y^n)\le nC$ . Combining these bounds yields

(1-P_e^{(n)})R_n\le C+\frac1n.

If error vanishes, the limiting rate cannot exceed capacity. This argument proves the weak converse, not the strong converse by itself. (ocw.mit.edu)

Representative channels

A binary symmetric channel flips each transmitted bit independently with probability $p$ . Its capacity is

C=1-h_2(p),\qquad h_2(p)=-p\log_2p-(1-p)\log_2(1-p).

At $p=1/2$ , output is independent of input and capacity is zero. At $p=0$ , capacity is one bit per use. A binary erasure channel, which replaces each bit by a recognizable erasure with probability $\epsilon$ , has capacity $1-\epsilon$ . Unlike an unknown bit flip, an erasure reveals where information was lost. (ocw.mit.edu)

For an ideal band-limited additive white Gaussian noise channel, the related Shannon–Hartley theorem gives

C=B\log_2(1+P/N)

bits per second, where $B$ is bandwidth, $P$ is average signal power, and $N$ is noise power within that bandwidth. Its continuous-channel assumptions and power constraint distinguish it from the finite-alphabet formulation. (web.njit.edu)

Scope and limitations

The theorem is an asymptotic existence result, not an efficient encoding or decoding algorithm. It does not specify the block length needed for a target error probability, decoding cost, or acceptable delay. Finite-blocklength theory studies these additional rate–reliability trade-offs; channel dispersion quantifies an important second-order departure from capacity. (ocw.mit.edu)

Together with the source coding theorem, channel coding supports source–channel separation under standard point-to-point memoryless assumptions: lossless compression removes source redundancy, while channel coding introduces redundancy for protection. When source entropy per channel use is strictly below capacity, the two stages can provide asymptotically reliable transmission. This separation need not be optimal under short-delay constraints or in general multiuser settings. (ocw.mit.edu)

References

A Mathematical Theory of Communicationweb.njit.edu
Lecture Notes — Information Theory, Spring 2016ocw.mit.edu
Information Theory Reviewweb.mit.edu