Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 1 / 11K (Coding and Cryptography)

For a received word $y$, the ideal-observer rule chooses a message $i$ maximizing the posterior probabilityMaximum-likelihood decoding chooses $i$ maximizingand minimum-distance decoding chooses a codeword minimizing its Hamming distance from $y$.

Bayes' formula givesEqual message priors therefore make ideal-observer and maximum-likelihood decoding identical. On a binary symmetric channel, if $d=d_H(y,c_i)$, thenFor $p<1/2$, this strictly decreases with $d$, so maximum likelihood and minimum distance agree.

Choose $\delta$ withA greedy packing construction gives binary length-$n$ codes of minimum distance greater than $2\delta n$ and size at leastTheir asymptotic rate is at leastwhere $h_2$ is binary Binary entropy. Minimum-distance decoding corrects every error pattern of weight at most $\delta n$. Since a channel error count is $\mathrm{Bin}(n,p)$, the law of large numbers givesThus a fixed positive rate is achievable with error tending to zero, proving that the operational capacity is nonzero. This is the positive-rate coding bound below one-quarter crossover.

Shannon second coding theorem states that the operational capacity of a discrete memoryless channel equalsevery rate below $C$ is achievable with error probability tending to zero, while rates above $C$ are not.

Put $d=b-a$. If $d=0$, then $Y=X+a$, so $X$ is recovered exactly and $C=1$ bit. If $|d|\ge 2$, the two output supportsare disjoint, so again $Y$ determines $X$ and $C=1$.

If $|d|=1$, one output value is common to both inputs and occurs with probability $1/2$ independently of the input, while either of the other two values reveals the input. The channel is therefore a binary erasure channel with erasure probability $1/2$, whose capacity is $1/2$ bit. Hence