# David Mackay's intuitive proof of Shannon's Channel-Coding Theorem

David Mackay, on p. 154 of his textbook, gives an intuitive proof of Shannon's noisy-channel coding theorem.

Imagine making an input sequence $$x$$ for the extended channel by drawing it from an ensemble $$X^N$$ , where $$X$$ is an arbitrary ensemble over the input alphabet. Recall the source coding theorem of Chapter 4, and consider the number of probable output sequences y. The total number of typical output sequences y is $$2^{NH(Y)}$$, all having similar probability. For any particular typical input sequence $$x$$, there are about $$2^{NH(Y|X)}$$ probable sequences.

We now imagine restricting ourselves to a subset of the typical inputs x such that the corresponding typical output sets do not overlap. We can then bound the number of non-confusable inputs by dividing the size of the typical $$y$$ set, $$2^{NH(Y)}$$, by the size of each typical-y-given-typical-x set, $$2^{NH(Y|X)}$$. So the number of non-confusable inputs, if they are selected from the set of typical inputs $$x ∼ X^N$$ , is $$\leq 2^{NH(Y)−NH(Y|X)} = 2^{NI(X;Y)}$$.

The maximum value of this bound is achieved if $$X$$ is the ensemble that maximizes $$I(X;Y)$$, in which case the number of non-confusable inputs is $$\leq 2^{NC}$$ . Thus asymptotically up to $$C$$ bits per cycle, and no more, can be communicated with vanishing error probability.

My question concerns the passage in bold. In the proof of the source coding theorem, the size of the typical set is $$2^{NH(X)}$$ only because the bits of $$x$$ are iid, and so the information content of a typical string is an unbiased estimator for $$NH(X)$$ (see p.80 in the book).

In channel coding however, we make a choice of code, and so the bits of $$y$$ are not iid (for example, if all of the chosen codewords $$x$$ have $$0$$ as first bit).

Note that given the channel input, the $$Y$$s are independent (not identically distributed, though, of course). This comes from the memorylessness property of the channel. Below I'll keep the precise notion of typicality (strong, weak, robust...) unspecified, because this is only a heuristic and I'm not tracking the epsilons. I'll assume that $$X$$ has a finite alphabet, letter of which are denoted $$a$$.

For a given $$x = (x_i)_{i = 1}^n$$, $$n$$ large, let $$\mathcal{I}(a,x) := \{ i : x_i = a\}$$ and let $$n_a(x):= |\mathcal{I}(a,x)|.$$ Then fixing any $$x$$ as the input, the set of $$y$$ that are typical of the output are those such that $$y|_{\mathcal{I}(a,x)}$$ are each typical w.r.t. $$P_{Y|X}(\cdot |a)$$. There are about $$2^{n_a(x) H(Y|X = a)}$$ such sequences. This means that the total number of typical outputs for an input $$x$$ are about $$\prod_a 2^{n_a(x) H(Y|X = a)} = 2^{\sum n_a(x) H(Y|X = a)}.$$ At this point we can take into account that $$x$$ is typical itself, so $$n_a(x) \approx nP_X(a),$$ which gives that the above is about $$2^{n \sum P_X(a) H(Y|X = a)} = 2^{n H(Y|X)}.$$

In the proof of the source coding theorem, the size of the typical set is 2𝑁𝐻(𝑋) only because the bits of 𝑥 are iid, and so the information content of a typical string is an unbiased estimator for 𝑁𝐻(𝑋) (see p.80 in the book).

If the random variables $$X_1, X_2, ..., X_n$$ are not iid then the entropy of the $$n$$ bit sample is $$H(X_1, X_2, ..., X_n)$$ and thus the typical set is of size $$2^{H(X_1, X_2, ..., X_n)}$$.

If the limit

$$H(\mathcal{X}) = \lim _{n \rightarrow \infty} \frac{1}{n} H(X_1, X_2, ..., X_n)$$

exists then it is called the entropy of the stochastic process and the size of the typical set is then usually denoted as $$2^{nH(\mathcal{X})}$$.

The total number of typical output sequences y is 2𝑁𝐻(𝑌), all having similar probability. For any particular typical input sequence 𝑥, there are about 2𝑁𝐻(𝑌|𝑋) probable sequences.

Over the communication channel we have $$Y = X + Z$$. It then follows that for a constant $$X$$ (i.e $$X$$ is just a constant $$k$$). If $$X$$ is just a constant, then the total number of possible values of $$Y$$ is at most equal to the number of different values the random variable $$Z$$ can take (because $$X$$ is just a constant).

The number of sequences in the typical set of $$Z$$ is approximately $$2^{nH(Z)}$$ and thus the number in the typical set of $$(k + Z)$$ is also $$2^{nH(Z)}$$. Note that $$H(Y | X = k) = H(k + Z) = H(Z)$$.

In order to have error free communication, we need each possible output sequence to be associated with a unique input sequence. It should not be possible for two input sequences to produce the same output sequence. In order to achieve this, we can restrict the number of allowed input sequences so we can achieve this goal.

Let $$M$$ be the number of input sequences we restrict ourselves to. Because we know each of these input sequences yield $$2^{nH(X)}$$ unique output sequences each and we know there are a maximum of $$2^{nH(Y)}$$ output sequences then we can easily deduce that

$$M \times 2^{nH(Y | X)} \leq 2^{nH(Y)}$$

$$M \leq \frac{2^{nH(Y)}}{2^{nH(Y | X)}} = 2^{nI(X;Y)} = 2^{nC}$$

The above constitutes half the proof for the channel capacity and is called the converse proof of capacity.

The main part of the proof involves proving that $$M > 2^{nI(X;Y) - \epsilon}$$ for every $$\epsilon > 0$$. After proving this it will then follow that $$2^{nI(X;Y) - \epsilon} < M \leq 2^{nI(X;Y)}$$ for every $$\epsilon > 0$$. Implying that the capacity is indeed $$I(X;Y)$$ per sample.

The key contribution that Shannon made was to show that if random coding is used at the transmitter and typical set decoding is used at the receiver then transmission at a rate $$I(X;Y) - \epsilon$$ can be achieved whilst also upper bounding the maximum bit error rate to $$\epsilon$$.