The direct part of Shannon’s channel theorem shows that random codebooks achieve every rate below capacity. The proof is a packing theorem for typical sets.
Channel code
Definition. An \((n,M)\) channel code chooses codewords \(x^n(m)\), sends one through \(W^n\), and decodes the received \(Y^n\) to \(\widehat M\). The average error is \(P_e=P(\widehat M\ne M)\) for a uniform message.
Achievability theorem
Theorem. For a discrete memoryless channel with capacity \(C\), every rate \(R<C\) is achievable: there exist \((n,M_n)\) codes with \(n^{-1}\log M_n\to R\) and average error probability tending to zero.
Random coding argument
Proof. Choose codewords independently from a capacity-approaching input distribution. Decode by joint typicality. The transmitted codeword and output are jointly typical with high probability. A wrong codeword is jointly typical with the output with probability about \(\exp[-nI(X;Y)]\). A union bound over \(\exp(nR)\) wrong messages tends to zero when \(R<I(X;Y)\).
Packing interpretation
Remark. The theorem is a high-dimensional packing statement: output typical sets generated by different messages can be made almost disjoint as long as their exponential count is below the mutual-information exponent.
Codes and average error
Definition. An \((n,M)\) channel code has codewords \(x^n(m)\), \(m=1,\ldots,M\), and decoder \(\widehat m(y^n)\). With uniform message, average error is \[ P_e^{(n)}=\frac1M\sum_{m=1}^M W^n\{\widehat m(Y^n)\ne m\mid x^n(m)\}. \]
Random coding with joint typicality
Theorem. For every input law \(P_X\) and rate \(R<I(X;Y)\), there exist DMC codes with \[ \frac1n\log M_n\to R,\qquad P_e^{(n)}\to0. \]
Proof. Draw \(M=e^{nR}\) codewords iid from \(P_X^n\). Send message \(1\). Decode to the unique codeword jointly typical with \(Y^n\). Error occurs if the true pair is not jointly typical or if another codeword is jointly typical with the output. Conditional typicality makes the first probability vanish. Each independent competing codeword is jointly typical with probability at most \(e^{-n(I-\delta)}\), so the union bound gives \[ P_e\le o(1)+e^{nR}e^{-n(I-\delta)}\to0 \] when \(R<I-\delta\). Average over random codebooks; at least one deterministic codebook performs no worse than the ensemble average.
Information-density threshold decoding
Dependence-testing bound. For every input law \(P_{X^n}\) and threshold \(\gamma>0\), there exists an \(M\)-code with \[ P_e\le P\{\imath_{X^n;Y^n}(X^n;Y^n)\le\log\gamma\} +\frac{M-1}{\gamma}. \]
Proof outline. Generate codewords independently from \(P_{X^n}\) and accept a candidate when its information density with the output exceeds \(\log\gamma\). The transmitted pair fails the threshold with the first probability. For an independent wrong codeword \(\bar X^n\), \[ P\{\imath_{\bar X^n;Y^n}>\log\gamma\} \le\gamma^{-1} \] by change of measure or Markov's inequality. Union over \(M-1\) competitors and average over the ensemble.
Expurgation from average to maximal error
Lemma. If a code has average error at most \(\epsilon\), then at least half its codewords have conditional error at most \(2\epsilon\). Removing the others yields a code of size at least \(M/2\) and maximal error at most \(2\epsilon\).
Proof. Markov's inequality applied to the \(M\) conditional error probabilities shows that fewer than \(M/2\) can exceed twice their average.
The rate loss \((\log2)/n\) vanishes. For multiuser channels, average and maximal error capacities can differ, so this simple expurgation is not always enough.
Constant-composition random codes
Choosing every codeword from one type class fixes input cost exactly and sharpens type-enumeration exponents. The probability that a wrong codeword and output have joint type \(Q_{XY}\) is controlled by \(e^{-nI_Q(X;Y)}\), making the method of types a direct achievability proof.
Random-coding exponent
Theorem. For a DMC and input law \(P_X\), random coding achieves \[ P_e^{(n)}\lesssim e^{-nE_r(R,P_X)}, \] where \[ E_r(R,P_X)= \max_{0\le\rho\le1}\{E_0(\rho,P_X)-\rho R\} \] and \[ E_0(\rho,P_X)= -\log\sum_y \left[\sum_xP_X(x)W(y\mid x)^{1/(1+\rho)} \right]^{1+\rho}. \]
Proof outline. Gallager's inequality bounds the indicator that a competitor beats the transmitted codeword by a fractional power of the likelihood sum. Average over independently generated codewords and the channel, use concavity for \(0\le\rho\le1\), and factor the memoryless product. Optimization in \(\rho\) yields the exponent.
Capacity achievability
Corollary. Maximizing over \(P_X\), every rate \[ R<C=\max_{P_X}I(X;Y) \] is achievable.
Finite-blocklength normal approximation
Theorem. For many regular memoryless channels, \[ \log M^*(n,\epsilon) = nC-\sqrt{nV}\,\Phi^{-1}(1-\epsilon) +O(\log n), \] where \(V\) is channel dispersion, the variance of information density under a capacity-achieving input with the appropriate optimization convention.
Capacity is only the first-order slope. Dispersion determines the blocklength penalty for a prescribed nonzero error probability.