Rate-distortion function ($R(D)$)

Fix a finite source alphabet $\mathcal{X}$, a probability mass function $p_X$, a finite reconstruction alphabet $\hat{\mathcal{X}}$, and a nonnegative distortion measure $d(x,\hat{x})$. The information rate-distortion function isThe source probability distribution stays fixed; the conditional distribution of the reconstruction is what we optimize. Each feasible test channel must keep expected distortion at most $D$. The objective is mutual information, measured in bits when the logarithms have base two. If no test channel satisfies the constraint, the infimum is $+\infty$.^[ref]

Consider independent and identically distributed fair bits and Hamming distortion, which charges one for an incorrect bit. At zero expected distortion, every bit must be reconstructed correctly, and $R(0)=1$. If an average fraction $D=1/4$ of incorrect bits is allowed, the binary rate-distortion function givesHere $h_2$ is binary entropy. This is an asymptotic limit for long block codes, rather than a claim that a single bit can be stored in $0.18872$ physical bits. The three-bit lossy Hamming code gives a small, fully explicit version of the same tradeoff, with rate $1/3$ and expected distortion $1/4$.

Rate-distortion theory separates the question of what is possible from the design of a practical encoder and decoder. It also forces the fidelity criterion to be explicit. Hamming distortion treats all symbol mismatches alike; mean squared error instead penalizes larger numerical errors more strongly. Those objectives can favor different reconstructions of the same data. An average error criterion does not by itself control the error on every individual input.

Claude Shannon's Coding Theorems for a Discrete Source With a Fidelity Criterion by Claude Shannon was published in 1959. Its formulation fixes a cost for replacing one source letter by another and studies the communication rate compatible with the allowed average cost. The important shift is to quantify which distinctions may be discarded, rather than requiring exact recovery of every letter.^[ref]

A distortion measure assigns a nonnegative cost to replacing a source symbol $x$ by a reconstruction $\hat{x}$. It need not be a metric: the two alphabets may differ, and neither symmetry nor the triangle inequality is required. Choosing the cost is part of the model. For numerical symbols, $d(x,\hat{x})=(x-\hat{x}{)}^2$ gives mean squared error after averaging; for exact symbol agreement, use Hamming distortion.

The reconstruction alphabet is the set of values that the decoder may output. It need not equal the source alphabet. A restricted reconstruction alphabet can prevent zero expected distortion, even if the representation is allowed arbitrarily many bits.

Expected distortion is the expectation of the reconstruction cost under the joint probability distribution of $X$ and $\hat{X}$. It weights common source outcomes more strongly than rare ones. A bound on expected distortion is therefore different from a bound on the cost for every input, or on the probability of exceeding a specified cost.

For a block code, separable distortion is the average of the individual symbol costs. With Hamming distortion it is the fraction of incorrectly reconstructed symbols, rather than the unnormalized number of mismatches. This normalization makes expected distortion comparable across different block lengths.^[ref]

A test channel is a proposed conditional distribution of a reconstruction given the source symbol. It describes a candidate joint probability distribution for evaluating mutual information and expected distortion. It need not be a physical transmission channel, or an implementable one-symbol encoder; the Shannon rate-distortion theorem relates this optimization to long block codes.

Hamming distortion is zero for a correctly reconstructed symbol and one for a mismatch. Its expected distortion is the symbol-error probability:For strings of length $n$, separable distortion divides their Hamming distance by $n$. Thus $001$ reconstructed as $000$ has Hamming distance one and average Hamming distortion $1/3$. Counting only whether the whole string is correct would give a different criterion.

Let $X_1,X_2,X_3$ be independent fair bits. The encoder sends their majority bit: zero when at least two inputs are zero, and one otherwise. The decoder reconstructs $000$ or $111$ by repeating that received bit three times. This is lossy compression: different original strings deliberately share a reconstruction.

There are eight equally likely inputs. The strings $000$ and $111$ have zero Hamming distance from their reconstructions; each of the other six has Hamming distance one. One transmitted bit represents three source symbols, soEvery input has average Hamming distortion at most $1/3$, whereas the population average is $1/4$. The actual block code therefore obeys $R\ge R(D)\approx 0.18872$, but does not reach the optimal long-block rate.

This construction uses the same reconstruction strings as the threefold binary repetition code, but the tasks differ. An error-correcting encoder expands one source bit into three transmitted bits; this lossy compression example compresses three source bits into one transmitted bit. The source distribution and the direction of the mapping matter.

For a stationary source of independent and identically distributed fair bits, with Hamming distortion and binary reconstruction alphabet,The binary entropy convention is $0{\log }_{2}0=0$. Once $D\ge 1/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.^[ref]

The short argument identifies both sides of the optimum. For any feasible binary reconstruction, put $E=X\oplus \hat{X}$, using exclusive or. Knowing $\hat{X}$ makes $X$ and $E$ determine one another, so the conditional entropy obeyswhen $0\le D\le 1/2$. The last step uses the increase of binary entropy on that interval. Hence $I(X;\hat{X})=1-H(X\mid \hat{X})\ge 1-h_2(D)$. Conversely, choose $\hat{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.

A fixed-length lossy code maps a block of $n$ source symbols to one of $M_n$ messages, then maps that message to a reconstruction block. The encoder and decoder together define the reconstruction. Its rate is ${\log }_2{M}_n/n$ bits per source symbol; an implementation using a fixed binary message needs $\lceil {\log }_2{M}_n\rceil$ transmitted bits per block. Its performance also depends on expected distortion, block length, and the chosen distortion measure.

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.

For the finite alphabets considered here, the zero-rate distortion threshold is the smallest expected distortion obtainable by always outputting one fixed reconstruction. Such a reconstruction is independent of the source, so its mutual information is zero. A randomized output that is independent of the source averages the costs of fixed reconstructions and cannot improve their minimum. Thus $R(D)=0$ exactly when $D\ge D_{\mathrm{zero}}$. For a fair bit under Hamming distortion, $D_{\mathrm{zero}}=1/2$; for a Bernoulli random variable of parameter $p$, it is $\min \{p,1-p\}$. The threshold depends on the source probability distribution, rather than only the alphabet.