Chapter Summary

Chapter Summary

Key Points

• 1.

  The lossy compression problem. When lossless compression is too expensive (continuous sources, large alphabets), we allow controlled distortion $D$ and ask: what is the minimum rate? The distortion measure $d(x, \hat{x})$ quantifies reconstruction quality, and the rate-distortion pair $(R, D)$ parametrizes the fundamental tradeoff.

• 2.

  The rate-distortion function. $R = \min_{P_{\hat{X}|X}: \mathbb{E}[d] \leq D} I(X;\hat{X})$ is the information-theoretic minimum rate for distortion $D$. It is convex and non-increasing, ranging from $H(X)$ (lossless) to 0 ($D = D_{\max}$). For binary sources with Hamming distortion: $R = H(p) - H(D)$.

• 3.

  The rate-distortion theorem: covering as the dual of packing. The achievability proof generates a random codebook and uses the covering lemma to show that $2^{nR}$ codewords suffice to cover the typical set when $R > R$. The converse uses data processing and convexity. Shannon's separation theorem unifies source and channel coding: a source is transmissible iff $R < C$.

• 4.

  Gaussian rate-distortion: the 6 dB rule. For $X \sim \mathcal{N}(0, \sigma^2)$: $R = \frac{1}{2}\log(\sigma^2/D)$, equivalently $D(R) = \sigma^2 2^{-2R}$. Each bit halves the distortion (6 dB). For parallel Gaussian sources, reverse waterfilling allocates more distortion to weak components — the dual of channel waterfilling.

• 5.

  Wyner-Ziv: side information at the decoder. When the decoder has correlated side information $Y$, binning reduces the required rate to $R_{WZ}(D) = \min_U [I(X;U) - I(U;Y)]$. For Gaussian sources, this equals $R_{XY}(D)$ — side information at the encoder is worthless. For general sources, there is a strict loss.

• 6.

  Successive refinement and scalable coding. A source is successively refinable if layered encoding achieves $R$ at every quality level. Gaussian sources are always successively refinable; this is the theoretical basis for scalable video coding (SVC, HEVC scalability).

• 7.

  Transform coding: theory meets practice. The pipeline of transform (DCT/wavelet) + quantize + entropy code approaches $R$ for Gaussian sources. ECSQ operates within 1.53 dB of the bound. Modern codecs (HEVC, VVC) close much of this gap through prediction, variable-size transforms, and context-adaptive arithmetic coding.