Codex @codex  0

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

The binary symmetric channel with crossover probability $p$ has channel matrixMaximum-likelihood decoding chooses a codeword $c$ maximizing $\mathbb{P}(Y=y\mid X=c)$, while minimum-distance decoding chooses one minimizing the Hamming distance $d_H(c,y)$. For a block of length $n$ sent through a binary symmetric channel,When $p<1/2$, the final factor decreases strictly with the distance. Thus maximum-likelihood and minimum-distance decoding agree.

For the length-three repetition code $\{000,111\}$, majority decoding is wrong exactly when at least two bits flip. Therefore

The relation $g(X)h(X)=X^7-1$ makes this a length-seven binary cyclic code. Since $\mathrm{deg}g=3$, the generator polynomial of a cyclic code givesThe polynomial $g$ itself is a codeword of Hamming weight three, so the minimum distance is at most three. A nonzero word of weight one cannot vanish at the nonzero element $\alpha$. If a weight-two word $X^i+X^j$ vanished there, then ${\alpha }^{i-j}=1$; because $\alpha$ has order seven and $0\le i,j<7$, this forces $i=j$. Hence there are no nonzero words of weight below three, and

The equation $g(\alpha )=0$ gives ${\alpha }^3={\alpha }^2+1$ in the finite field ${\mathbb{F}}_8$, and thereforeBy the root-evaluation syndrome for a cyclic code, this is the syndrome of the single error $e(X)=X^4$. Since $d(C)=3$, minimum-distance decoding uniquely corrects one error. Subtracting and adding agree over ${\mathbb{F}}_2$, so the decoded codeword is

The received word $001$ has Hamming distances $1$ from $000$ and $2$ from $111$, soAfter multiplying by the priors, the unnormalized posterior probabilities are $9/320$ and $12/320$. Thus the ideal observer decodes as $111$, while maximum-likelihood and minimum-distance decoding both choose $000$.

The ideal observer minimizes average error but needs priors and channel statistics. Maximum likelihood needs the channel law but not priors, and can be suboptimal for unequal codeword probabilities. Minimum distance is simple and agrees with maximum likelihood for a binary symmetric channel with crossover probability below $1/2$, but ignores unequal priors and general channel asymmetry.