Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 30 / 3 / b

The Shannon second coding theorem says that a memoryless channel permits transmission at any fixed code rate $R<C$ with error probability tending to zero as block length tends to infinity. Conversely, a sequence of codes with error probability tending to zero cannot have a limiting rate above $C$. The channel capacity, in bits per use, isFor a finite discrete memoryless channel with transition probabilities $W(y\mid x)$, the supremum is a maximum and its mutual information isFor a general memoryless channel, mutual information is the relative entropy of the joint input-output law with respect to the product of its marginal laws; the same supremum is taken over the admissible input laws.

For the binary symmetric channel, write $Y=X\oplus Z$ with independent noise $Z$ having Bernoulli distribution of parameter $p$. Given either input bit, the output conditional entropy is $h_2(p)$. ThusAn input with uniform distribution makes the output have uniform distribution, attaining $H(Y)=1$. The binary symmetric channel capacity is therefore