= Shannon's rate-distortion theorem
{c}
= Shannon rate-distortion theorem
{c}
{synonym}
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 $\varepsilon>0$, sufficiently long <block codes> exist with rate at most $R(D)+\varepsilon$ and <expected distortion> at most $D+\varepsilon$. Every such $n$-symbol code obeys $R_n\geq R(D_n)$, where $D_n$ is its actual <expected distortion>.<6.441 Information Theory (Spring 2016 lecture notes) by Yury Polyanskiy and others/Chapter 24: Rate Distortion: Achievability Bounds>[§24.1, Theorem 24.1, printed pp. 246–247; §24.2, Theorem 24.2, printed p. 247]{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.
Back to article page
