Shannon's rate-distortion theorem

For a finite alphabet source with independent and identically distributed symbols, a finite reconstruction alphabet, and a bounded nonnegative separable distortion, the rate-distortion function is the asymptotic limit for fixed-length lossy codes. In particular, for a distortion target in the interior of the feasible range and every $\epsilon >0$, sufficiently long block codes exist with rate at most $R(D)+\epsilon$ and expected distortion at most $D+\epsilon$. Every such $n$-symbol code obeys $R_n\ge R(D_n)$, where $D_n$ is its actual expected distortion.^[ref]

The outline is instructive. The data processing inequality bounds the mutual information in a reconstruction by the information entropy of the transmitted message, which is at most ${\log }_2{M}_n$. Independence and the convexity of the rate-distortion function then give the per-symbol lower bound. For achievability, choose many reconstruction blocks using a suitable probability distribution, so that the source's typical blocks are likely to have an acceptable nearby reconstruction. This is a covering argument; it does not require recovering the original block exactly.