Rate–distortion theory and test channels

Start with an iid finite-alphabet source, a finite reconstruction alphabet and a bounded nonnegative distortion d(x,x-hat). A length-n code selects one of M reconstructions, and its rate is log₂M/n. The distortion criterion is the expected average of the n symbol distortions. The information formula minimizes I(X;X-hat) over stochastic conditional reconstruction laws whose expected distortion is at most D. A deterministic one-symbol map is only one restricted candidate in that minimization.

For distortion levels above the minimum attainable value, rates strictly above this function permit block codes with expected distortion at most D plus any fixed positive slack for sufficiently large lengths. Taking limits or closures gives the operational rate–distortion tradeoff, including boundaries. The finite-alphabet bounded-distortion theorem does not itself prove every continuous-source formula. Those require their own integrability and coding arguments, such as the separate Gaussian squared-error result used below.

For fair binary symbols and Hamming distortion up to one half, a binary symmetric test channel with mismatch probability D attains the lower bound one minus h₂(D). One way to write the same joint law is backward: choose a fair reconstruction bit and add an independent Bernoulli-D error to obtain X. Conditional uncertainty is then h₂(D). A covering argument constructs a long codebook whose selected reconstruction has approximately this joint behavior with the source.

The function R(D) is nonincreasing and convex: allowing more distortion cannot increase the required rate, and time sharing between block codes gives the convex tradeoff. A zero-rate reconstruction minimizes distortion among constant reproduction symbols. Zero rate therefore does not mean zero distortion. Conversely, an average distortion bound does not prevent some blocks or coordinates from having much larger errors; a worst-case or excess-distortion requirement needs an explicitly different operational statement.

In the Gaussian construction, the independent error is added to the reconstruction to produce the source. Reversing the arrow while keeping the same independence assumption changes the joint distribution. The forward optimal reconstruction has conditional mean (1−D/σ²)X and independent Gaussian residual variance D(1−D/σ²). Simply setting the reconstruction equal to X plus independent variance-D noise achieves the desired distortion but generally uses more mutual information than necessary.

These formulas compare population source distributions and asymptotic block-coding rates. A learned compressor may have quantization constraints, limited codebook size or a mismatched source law, so matching a Gaussian mean-square error alone does not certify operation at the rate–distortion optimum. A practical comparison should record actual description length, the distortion criterion and any excess-distortion probability, rather than treating a test-channel mutual information as a measured file size.