Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 3 / 3G (Coding and Cryptography)

A reliable transmission rate $R$ means that length-$n$ codes can carry $M_n$ messages with $n^{-1}{\log }_2{M}_n$ tending to at least $R$ while the probability measure of the decoding-error event tends to zero. By the Shannon second coding theorem, the supremum of reliable rates is the binary symmetric channel capacityFor small positive $p$, the binary entropy function has the asymptotic expansionso $C(p)$ starts at one bit per channel use and decreases rapidly from one as errors are introduced.

At $p=1/2$, the output of the binary symmetric channel is independent of its input. It conveys no mutual information, and therefore

If $p>1/2$, complementing every received bit converts the channel into a binary symmetric channel with crossover probability $1-p<1/2$. This deterministic and invertible output relabelling does not change the channel capacity. Since $h_2(p)=h_2(1-p)$,Thus the capacity rises again from zero as $p$ increases beyond $1/2$, reaching one at $p=1$, where every bit is flipped deterministically and can be recovered by complementation.