Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 35 / 3 / Solution

The channel capacity is the supremum of reliable communication rates: a rate $R$ bits per use is achievable if block encoders and decoders using $n$ channel uses can transmit $M_n$ messages with error probability tending to zero and $\mathrm{liminf}{n}^{-1}{\log }_2{M}_n\ge R$.

A discrete memoryless channel has fixed transition probabilities $W(y|x)$ on finite input and output alphabets, andIts single-letter capacity formula iswith logarithms to base two. The Shannon second coding theorem identifies this maximum with the operational reliable rate.

For the binary erasure channel, use output symbols $0,1,e$, where $e$ is a recognizable erasure flag. Given input $x$, the output is $x$ with probability $1-p$ and $e$ with probability $p$. If $\mathrm{Pr}(X=1)=a$, the output probabilities are $(1-p)(1-a),(1-p)a,p$. Thus, writing $h_2$ for binary entropy,and $I(X;Y)=(1-p)h_2(a)$. Its maximum is attained by the uniform input $a=1/2$, givingIn particular the noiseless and complete-erasure endpoints have capacities one and zero. The erasure flag reveals which positions were lost; it does not reveal the erased input values.