Shannon's noisy-channel coding theorem

**Converse ($R > C \Rightarrow P_e \not\to 0$).** Fano's inequality bounds the receiver's remaining uncertainty about the message given the noisy output: $H(X\mid Y) \le 1 + P_e \log_2(n-1)$, where $n$ is the number of possible messages. Meanwhile, the data-processing structure of the channel forces $I(X;Y) \le C$ for every use, so over a block of $N$ channel uses the total information the receiver can extract is at most $NC$ bits. If the true rate is $R > C$ bits per use, the message carries $NR$ bits of entropy but the channel supplies only about $NC < NR$ bits about it; Fano's inequality then forces $P_e$ to stay bounded away from $0$ as $N$ grows, since the leftover uncertainty $H(X\mid Y)$ cannot be made to vanish.

**Achievability sketch ($R < C \Rightarrow P_e \to 0$).** Fix an input distribution $p(x)$ achieving the capacity and generate a codebook of $2^{NR}$ codewords of length $N$ independently at random from $p(x)^N$. To decode, the receiver looks for the unique codeword that is jointly typical with the received sequence (i.e. behaves, in its statistical patterns, like a genuine input–output pair). Because $R < C$, the number of candidate codewords ($2^{NR}$) is far smaller than the number of statistically distinguishable channel outputs ($\approx 2^{NC}$), so as $N \to \infty$ the chance that some other, unsent codeword accidentally looks jointly typical with the received sequence shrinks to $0$, and so does the decoding error probability, averaged over the random choice of codebook — hence at least one codebook must achieve arbitrarily small $P_e$.