Past exam of the mathematics course of the University of Cambridge / 2005 / ii / Paper 4 / 4J / Solution

Reliable transmission at rate $r$ means that there is a sequence of binary block codes of lengths $n$, message counts $M_n$ with $\mathrm{liminf}{n}^{-1}{\log }_2{M}_n\ge r$, and decoding error probabilities tending to zero. The Shannon second coding theorem identifies the supremum of reliable rates with the channel capacity.

For a binary symmetric channel, the conditional entropy of the output given any input bit is $h_2(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$. The output entropy is at most one bit and attains one for uniform input, so the maximum mutual information isAll rates strictly below $C$ are achievable, and rates above $C$ are not reliable; this states the supremum without claiming achievability of every boundary rate under every convention.

For very small $p$, the capacity is close to one, with $h_2(p)=p{\log }_2(1/p)+p/\log 2+O(p^2)$. At $p=1/2$, the output is independent of the input and capacity is zero. For $p>1/2$, flipping every received bit converts the channel to crossover probability $1-p<1/2$; its capacity is unchanged because $h_2(p)=h_2(1-p)$. At $p=1$ the deterministic bit flip is perfectly reversible.