The Channel Coding Theorem — Achievability

Fix an input distribution $P_X$ and $\epsilon > 0$.

Generate a random codebook: draw $2^{nR}$ codewords $X^n(1), X^n(2), \ldots, X^n(2^{nR})$ independently, each with i.i.d. entries $X_i(m) \sim P_X$.

The codebook is revealed to both the encoder and the decoder before communication begins. The message $M$ is uniform on $\mathcal{M} = [1 : 2^{nR}]$.

The decoder, upon receiving $y^n$, looks for a unique message $\hat{m}$ such that $(x^n(\hat{m}), y^n) \in \mathcal{T}_\epsilon^{(n)}(X, Y)$.

$$g(y^n) = \begin{cases} \hat{m} & \text{if } \hat{m} \text{ is the unique index with } (x^n(\hat{m}), y^n) \in \mathcal{T}_\epsilon^{(n)} \\ \text{error} & \text{otherwise (no match or multiple matches)} \end{cases}$$

By the symmetry of the random codebook (all codewords drawn from the same distribution), the ensemble average error probability satisfies:

$$\overline{P}_e^{(n)} = \mathbb{E}_{\mathcal{C}}[P_e(\mathcal{C})] = \Pr(g(Y^n) \neq 1 \mid M = 1)$$

We condition on $M = 1$ (WLOG by symmetry) and define error events:

• $\mathcal{E}_1 = \{(X^n(1), Y^n) \notin \mathcal{T}_\epsilon^{(n)}(X,Y)\}$: the true pair is not jointly typical.
• $\mathcal{E}_2 = \{\exists\, m \neq 1 : (X^n(m), Y^n) \in \mathcal{T}_\epsilon^{(n)}(X,Y)\}$: a wrong codeword is jointly typical with $Y^n$.

By the union bound: $\Pr(\text{error} \mid M=1) \leq \Pr(\mathcal{E}_1) + \Pr(\mathcal{E}_2)$.

Since $M = 1$ was sent, $(X^n(1), Y^n)$ are jointly distributed as $\prod_{i=1}^n P_X(x_i) P_{Y|X}(y_i|x_i) = \prod_{i=1}^n P_{XY}(x_i, y_i)$.

By the law of large numbers (AEP property of typical sequences): $$\Pr(\mathcal{E}_1) = \Pr((X^n(1), Y^n) \notin \mathcal{T}_\epsilon^{(n)}) \to 0 \text{ as } n \to \infty$$

For $m \neq 1$, the codeword $X^n(m)$ is independent of $Y^n$ (since $Y^n$ depends only on $X^n(1)$, and the codewords are drawn independently). So $(X^n(m), Y^n) \sim \prod_{i=1}^n P_X(x_i) P_Y(y_i)$ — the product distribution.

By the Packing Lemma (Chapter 3, Lemma 18): $$\Pr((X^n(m), Y^n) \in \mathcal{T}_\epsilon^{(n)}) \leq 2^{-n(I(X;Y) - \delta(\epsilon))}$$

By the union bound over the $2^{nR} - 1$ wrong codewords: $$\Pr(\mathcal{E}_2) \leq (2^{nR} - 1) \cdot 2^{-n(I(X;Y) - \delta(\epsilon))} \leq 2^{-n(I(X;Y) - R - \delta(\epsilon))}$$

This vanishes as $n \to \infty$ provided $R < I(X; Y) - \delta(\epsilon)$.

We have shown $\overline{P}_e^{(n)} \leq \epsilon + 2^{-n(I(X;Y) - R - \delta(\epsilon))} \leq 2\epsilon$ for large $n$.

Since this is the average over random codebooks, there exists at least one deterministic codebook $\mathcal{C}_n^*$ with $P_e(\mathcal{C}_n^*) \leq 2\epsilon$.

Choose $P_X = P_X^*$ (the capacity-achieving distribution) to get $R < C - \delta(\epsilon)$, and let $\epsilon \to 0$ (which makes $\delta(\epsilon) \to 0$).

The code $\mathcal{C}_n^*$ has $P_e(\mathcal{C}_n^*) \leq 2\epsilon$ (average error). Sort codewords by their individual error probabilities: $P_{e,1} \leq P_{e,2} \leq \cdots \leq P_{e,2^{nR}}$.

The expurgated code $\widetilde{\mathcal{C}}_n^*$ keeps only the best half: codewords $1, \ldots, 2^{nR - 1}$.

Since the average error is $\leq 2\epsilon$, the worst codeword in the best half satisfies $P_{e,\max}(\widetilde{\mathcal{C}}_n^*) \leq 4\epsilon$.

The new rate is $R' = R - 1/n$, which is still below $C$ for large $n$. So $P_{e,\max} \to 0$.