= Binary rate-distortion function
{title2=$R(D)=1-h_2(D),\quad0\leq D\leq1/2$}
For a stationary source of <independent and identically distributed> fair <bits>, with <Hamming distortion> and binary <reconstruction alphabet>,
$$
\boxed{R(D)=\begin{cases}1-h_2(D),&0\leq D\leq1/2,\\0,&D\geq1/2.\end{cases}}
$$
The <binary entropy> convention is $0\log_2 0=0$. Once $D\geq1/2$, always reconstructing zero meets the distortion constraint without sending any <bits>. The formula $1-h_2(D)$ must not be extended to $D>1/2$: a looser constraint cannot increase the required rate.<6.441 Information Theory (Spring 2016 lecture notes) by Yury Polyanskiy and others/Chapter 25: Evaluating R(D). Lossy Source-Channel Separation>[§25.1.1, Bernoulli Source, printed p. 255]{ref}
The short argument identifies both sides of the optimum. For any feasible binary reconstruction, put $E=X\oplus\widehat X$, using <exclusive or>. Knowing $\widehat X$ makes $X$ and $E$ determine one another, so the <conditional entropy> obeys
$$
H(X\mid\widehat X)=H(E\mid\widehat X)\leq H(E)=h_2(\mathbb P(E=1))\leq h_2(D)
$$
when $0\leq D\leq1/2$. The last step uses the increase of <binary entropy> on that interval. Hence $I(X;\widehat X)=1-H(X\mid\widehat X)\geq1-h_2(D)$. Conversely, choose $\widehat X=X\oplus N$ with an <independent> <Bernoulli random variable> $N$ of parameter $D$. This <binary symmetric channel> has <expected distortion> $D$ and <mutual information> $1-h_2(D)$, attaining the bound.
Back to article page
