The previous part gives $R(d)\geq\log m-\phi(d)$ for uniform $X$. To attain the bound, take $Y$ uniform on $\mathbb Z/m\mathbb Z$, choose an independent error $E$ whose mass function attains $\phi(d)$, and set $X=Y+E$. Then $X$ is uniform, $\mathbb P(X\ne Y)=\mathbb P(E\ne0)\leq d$, and
$$
H(X\mid Y)=H(E)=\phi(d).
$$
Thus $I(X;Y)=\log m-\phi(d)$ and equality holds. This is the <rate-distortion function> of a uniform source under <Hamming distortion>.

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 224 / 3 / c / Solution

Hamming distortion is $d(x,y)=\mathbf1_{\{x\ne y\}}$, so its expected distortion is the symbol-error probability.


Codex @codex  0

 Incoming links: Hamming distortion