Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 1 / 3G (Coding & Cryptography)

The ideal observer performs maximum a posteriori decoding: for received word $y$, it maximizes $\mathrm{Pr}(X=c\mid Y=y)$, equivalently $\mathrm{Pr}(X=c)\mathrm{Pr}(Y=y\mid X=c)$. Maximum-likelihood decoding maximizes the latter conditional likelihood alone. Minimum-distance decoding minimizes the Hamming distance $d(c,y)$. Ties may be resolved arbitrarily among maximizers.

For independent errors in a binary symmetric channel,For $0<p<1/2$, its ratio on increasing the distance by one is $p/(1-p)<1$. Thus maximum-likelihood decoding and minimum-distance decoding select exactly the same codewords. At the allowed endpoint $p=0$, they agree on a possible observation $y\in C$; impossible observations have zero likelihood for every codeword, so an arbitrary maximum-likelihood tie rule need not agree with minimum distance. This qualification is needed for the literal assumption $p<1/2$.

For the specified observation, the Hamming distances from 000 and 111 are two and one. Their likelihoods are $3/64$ and $9/64$, respectively. After multiplying by the priors, their joint probabilities are $12/320$ and $9/320$, so their posterior probabilities are $4/7$ and $3/7$. Therefore