gen-define-the-rate-distortion-function-and-give-one-short-worke-f9d2

Define the rate-distortion function and give one short worked example.

# Rate-Distortion Function ## Definition The **rate-distortion function** R(D) is the minimum rate (in bits per symbol) required to encode a source with average distortion at most D. Formally, for a source X with reconstruction X̂: $$R(D) = \min_{p(\hat{x}|x): E[d(X,\hat{X})] \leq D} I(X;\hat{X})$$ where: - I(X;X̂) is the mutual information between source and reconstruction - d(X,X̂) is a distortion measure - The minimization is over all conditional distributions p(x̂|x) satisfying the distortion constraint --- ## Worked Example: Binary Source with Hamming Distortion **Setup:** - Source: X ~ Bernoulli(1/2), so P(X=0) = P(X=1) = 1/2 - Distortion: Hamming distance, d(x,x̂) = 0 if x=x̂, else 1 - Find: R(D) for D ∈ [0, 1/2] **Solution:** The optimal encoding strategy transmits X correctly with probability (1-D) and allows an error with probability D. This gives average distortion = D and requires transmitting: $$R(D) = H(X) - H(D) = 1 - H(D)$$ where H(D) = -D log₂(D) - (1-D)log₂(1-D) is the binary entropy function. **Result:** $$R(D) = \begin{cases} 1 - H(D) & \text{if } 0 \leq D \leq 1/2 \\ 0 & \text{if } D > 1/2 \end{cases}$$ For example: R(0) = 1 bit (perfect reconstruction), R(1/2) = 0 bits (random guessing acceptable).