Exercises

$H(0.3) \approx 0.881$ bits.

• $R(0) = H(0.3) - H(0) = 0.881 - 0 = 0.881$ bits
• $R(0.1) = 0.881 - H(0.1) = 0.881 - 0.469 = 0.412$ bits
• $R(0.2) = 0.881 - H(0.2) = 0.881 - 0.722 = 0.159$ bits
• $R(0.3) = 0.881 - H(0.3) = 0.881 - 0.881 = 0$ bits

The curve is convex, decreasing from $H(p)$ to 0.

SNR = 30 dB $= 10^{30/10} = 1000$. So $D = \sigma^2/\text{SNR} = 4/1000 = 0.004$. $R = \frac{1}{2}\log_2(\sigma^2/D) = \frac{1}{2}\log_2(1000) \approx \frac{1}{2}(9.97) = 4.98$ bits/sample.

Alternatively: $R = \frac{1}{2} \cdot \text{SNR(dB)} / (20\log_{10}2) \cdot 2 = \text{SNR(dB)} / 6.02 = 30/6.02 = 4.98$ bits.

At rate $R = 0$, the codebook has $2^0 = 1$ codeword. The best single reconstruction is $\hat{x}^* = \arg\min_{\hat{x}} \mathbb{E}[d(X, \hat{x})]$, achieving distortion $D_{\max}$. Since $I(X;\hat{X}) = 0$ when $\hat{X}$ is constant (independent of $X$), we have $R(D_{\max}) = 0$.

For Hamming distortion on Bernoulli($p$): $D_{\max} = \min(p, 1-p) = p$ (always output the more likely symbol). For Gaussian squared error: $D_{\max} = \sigma^2$ (always output the mean, zero).

$D = 2^{-16} \approx 1.5 \times 10^{-5}$. SNR $= 1/D = 2^{16} = 65536 \approx 48.2$ dB.

For a uniform quantizer with $M = 2^8 = 256$ levels: SNR $\approx 6.02 \times 8 - 7.27 = 40.9$ dB (using the standard formula for uniform quantization of Gaussian). The gap from R-D is about 7.3 dB — this includes both the shaping loss (1.53 dB) and the overload loss.

For $\lambda \in [0,1]$, given a code $C_1$ achieving $(R_1, D_1)$ and $C_2$ achieving $(R_2, D_2)$: use $C_1$ on a $\lambda$-fraction of the source blocks and $C_2$ on the rest. The average rate is $\lambda R_1 + (1-\lambda)R_2$ and the average distortion is $\lambda D_1 + (1-\lambda)D_2$. Since this pair is achievable: $$R(\lambda D_1 + (1-\lambda)D_2) \leq \lambda R_1 + (1-\lambda)R_2.$$ Setting $R_i = R(D_i)$: $R(\lambda D_1 + (1-\lambda)D_2) \leq \lambda R(D_1) + (1-\lambda)R(D_2)$. This is the definition of convexity.

By symmetry (uniform source, symmetric distortion), the optimal test channel is a ternary symmetric channel: $P(\hat{x}|x) = 1 - D$ if $\hat{x} = x$, and $D/(|\mathcal{X}|-1) = D/2$ otherwise. The marginal $\hat{X}$ is also uniform.

$H(\hat{X}) = \log_2 3$ (uniform). $H(\hat{X}|X) = -(1-D)\log(1-D) - D\log(D/2) = -(1-D)\log(1-D) - D\log D + D\log 2$ $= H(D) + D\log 2 = H(D) + D$ (in bits, where $H$ is the binary entropy).

Wait — more carefully: $H(\hat{X}|X=x) = -(1-D)\log_2(1-D) - 2 \cdot \frac{D}{2}\log_2\frac{D}{2}$ $= -(1-D)\log_2(1-D) - D\log_2(D/2)$ $= -(1-D)\log_2(1-D) - D\log_2 D + D$.

So $R = \log_2 3 - [-(1-D)\log_2(1-D) - D\log_2 D + D]$ $= \log_2 3 + (1-D)\log_2(1-D) + D\log_2 D - D$ $= \log_2 3 - H(D, (1-D)) - D\log_2 2 + D\log_2 D + D\log_2 D$...

Let me redo this cleanly. With the ternary symmetric channel: $H(\hat{X}|X) = H_3(1-D, D/2, D/2) = -(1-D)\log(1-D) - 2 \cdot \frac{D}{2}\log\frac{D}{2}$ $= -(1-D)\log(1-D) - D\log\frac{D}{2} = -(1-D)\log(1-D) - D\log D + D$.

$R = \log 3 + (1-D)\log(1-D) + D\log D - D$ for $0 \leq D \leq 2/3$. At $D = 0$: $R = \log 3 \approx 1.585$ bits. At $D = 2/3$: $R = 0$ (always output any fixed symbol).

If $\gamma \geq \sigma_2^2 = 1$: $D_2^* = \sigma_2^2 = 1$ (shut off, zero bits allocated). Then $D_1^* = D - D_2^* = 2 - 1 = 1$. Check: $D_1^* = 1 < \sigma_1^2 = 4$, so $\gamma = D_1^* = 1 = \sigma_2^2$. This is the boundary case — the waterfilling level equals $\sigma_2^2$.

$R = \frac{1}{2}\log_2\frac{\sigma_1^2}{D_1^*} + 0 = \frac{1}{2}\log_2\frac{4}{1} = 1$ bit. Only the first (stronger) component gets any bits. The second component contributes its full variance $\sigma_2^2 = 1$ to the distortion budget.

Equal allocation: $D_1 = D_2 = 1$. Same result! But for $D = 1.5$: reverse waterfilling gives $D_2^* = 1, D_1^* = 0.5$, rate $= \frac{1}{2}\log(4/0.5) = 1.5$ bits. Equal allocation: $D_1 = D_2 = 0.75$, rate $= \frac{1}{2}\log(4/0.75) + \frac{1}{2}\log(1/0.75) = 1.21 + 0.21 = 1.42$ bits. Equal allocation is better here because it doesn't waste bits on the weak component. Wait — reverse waterfilling gives 1.5 bits while equal gives 1.42. Let me recheck: at $D = 1.5$, $\gamma$ satisfies $\min(\gamma, 4) + \min(\gamma, 1) = 1.5$. If $\gamma < 1$: $\gamma + \gamma = 1.5$, so $\gamma = 0.75$. Rate $= \frac{1}{2}\log(4/0.75) + \frac{1}{2}\log(1/0.75) = 1.21 + 0.21 = 1.42$ bits. So reverse waterfilling gives 1.42 bits — same as equal allocation! This makes sense: $\gamma = 0.75 < 1$, so both components are active with $D_i^* = 0.75$.

SNR $= \sigma^2/D = 2^{2R}$. In dB: $$\text{SNR(dB)} = 10\log_{10}(2^{2R}) = 20R\log_{10}(2) = 20R \times 0.3010 = 6.02R.$$ Each bit of rate adds 6.02 dB of SNR — this is the fundamental resolution of digital representation. A 16-bit audio sample (CD quality) achieves $6.02 \times 16 = 96.3$ dB SNR.

$P(\hat{x}|x) \propto q(\hat{x}) e^{-\lambda d(x,\hat{x})}$. For $x = 0$: $P(0|0) \propto 0.5 \cdot e^0 = 0.5$, $P(1|0) \propto 0.5 \cdot e^{-2} \approx 0.0677$. Normalizing: $P(0|0) = 0.5/0.5677 = 0.881$, $P(1|0) = 0.119$. For $x = 1$: $P(0|1) \propto 0.5 \cdot e^{-2} = 0.0677$, $P(1|1) \propto 0.5 \cdot e^0 = 0.5$. Normalizing: $P(0|1) = 0.119$, $P(1|1) = 0.881$.

$q(0) = 0.7 \times 0.881 + 0.3 \times 0.119 = 0.617 + 0.036 = 0.653$. $q(1) = 0.7 \times 0.119 + 0.3 \times 0.881 = 0.083 + 0.264 = 0.347$.

$D = 0.7 \times 0.119 + 0.3 \times 0.119 = 0.119$. $R = \sum_{x,\hat{x}} P(x) P(\hat{x}|x) \log\frac{P(\hat{x}|x)}{q(\hat{x})}$. This requires more computation; after convergence (a few more iterations), the algorithm produces the point $(R, D)$ on the R-D curve corresponding to $\lambda = 2$.

The encoder output $W = f(\mathbf{X})$ takes $2^{nR}$ values: $nR \geq H(W) \geq I(\mathbf{X}; W) \geq I(\mathbf{X}; \hat{\mathbf{X}})$ where the last step uses data processing ($\hat{\mathbf{X}} = g(W)$).

$I(\mathbf{X}; \hat{\mathbf{X}}) \geq \sum_{i=1}^n I(X_i; \hat{X}_i)$ by the chain rule and dropping conditioning (conditioning reduces mutual information for independent $X_i$'s). Each $I(X_i; \hat{X}_i) \geq R(D_i)$ by definition of $R(\cdot)$, where $D_i = \mathbb{E}[d(X_i, \hat{X}_i)]$.

$nR \geq \sum_{i=1}^n R(D_i) \geq n R\!\left(\frac{1}{n}\sum_{i=1}^n D_i\right) \geq n R(D)$ by convexity (Jensen's inequality applied to convex $R(\cdot)$) and $\frac{1}{n}\sum D_i \leq D$.

With side information at both encoder and decoder, the problem reduces to compressing $X$ given $Y$. Since $X|Y \sim \text{Bern}(p)$ (the BSC flips with probability $p$): $$R_{XY}(D) = R_{X|Y}(D) = H(p) - H(D) \text{ for } 0 \leq D \leq p.$$

Without side information at the encoder, the Wyner-Ziv rate for this binary case is: $$R_{WZ}(D) = H(p * D) - H(D)$$ where $p * D = p(1-D) + (1-p)D$ (BSC convolution). This can be shown using the auxiliary $U$ in the Wyner-Ziv theorem with $U = X \oplus Z$, $Z \sim \text{Bern}(D)$.

The gap $R_{WZ}(D) - R_{XY}(D) = H(p * D) - H(p)$. Since $H(p * D) \geq H(p)$ (BSC convolution increases entropy for $D > 0$), $R_{WZ} \geq R_{XY}$ with strict inequality for $D > 0$ and $p \notin \{0, 1/2\}$. The gap is zero only when $p = 1/2$ (useless side information) or $D = 0$ (lossless).

For example, with $p = 0.1$, $D = 0.05$: $R_{XY}(0.05) = H(0.1) - H(0.05) = 0.469 - 0.286 = 0.183$ bits. $R_{WZ}(0.05) = H(0.1 \cdot 0.95 + 0.9 \cdot 0.05) - H(0.05)$ $= H(0.14) - 0.286 = 0.588 - 0.286 = 0.302$ bits. Gap: 0.119 bits (65% overhead for not knowing $Y$ at the encoder).

Choose $R$ with $R < R < C$. This is possible since $R < C$. Use a lossy source code at rate $R$ achieving distortion $\leq D + \epsilon$ (by the R-D theorem). The encoder output is $2^{nR}$ indices — transmit these over the channel using a channel code at rate $R < C$ with $P_e \to 0$ (by the channel coding theorem). The overall distortion is $\leq D + \epsilon + \delta$ where $\delta$ accounts for the (vanishing) channel error.

Any joint source-channel code maps $\mathbf{X}$ to $\hat{\mathbf{X}}$ via the channel. By data processing: $I(\mathbf{X}; \hat{\mathbf{X}}) \leq I(\mathbf{X}; \mathbf{Y}) \leq nC$. By the R-D converse: $I(\mathbf{X}; \hat{\mathbf{X}}) \geq nR(D)$. Combining: $R(D) \leq C$, so $R \leq C$ is necessary.

The achievability proof uses separate source and channel codes, while the converse applies to any coding scheme (including joint). Since both give the same condition $R < C$, separation is optimal. No joint scheme can do better.

For any source with differential entropy $h(X)$ and squared-error distortion: $$R(D) \geq h(X) - \frac{1}{2}\log(2\pi e D) = \frac{1}{2}\log\frac{2^{2h(X)}}{2\pi e D}.$$ The "entropy power" is $N_X = \frac{1}{2\pi e} 2^{2h(X)}$. The Gaussian with the same entropy has variance $N_X$, and the bound says $R(D) \geq R_{\text{Gauss}}(D)$ with $\sigma^2 = N_X$.

$h(X) = 1 + \ln(1/\lambda)$ nats $= (1 + \ln(1/\lambda))/\ln 2$ bits. Entropy power: $N_X = \frac{1}{2\pi e}2^{2h} = \frac{1}{2\pi e} \cdot (e/\lambda)^2 \cdot 4 = \frac{2e}{\pi\lambda^2}$. Hmm, this doesn't simplify to $1/\lambda^2$.

Actually, for the exponential source, the exact $R(D)$ is not available in simple closed form. The Shannon lower bound gives $R(D) \geq \frac{1}{2}\log_2\frac{e^2/(2\pi e \lambda^2)}{D} = \frac{1}{2}\log_2\frac{e}{2\pi\lambda^2 D}$. The actual $R(D)$ for the exponential source lies strictly above the Gaussian $R(D)$ at the same variance — this is because the Gaussian has the maximum entropy for a given variance, making it the "hardest" source to compress.

The Gaussian $R(D)$ at variance $\sigma^2 = 1/\lambda^2$ is $\frac{1}{2}\log(\sigma^2/D) = \frac{1}{2}\log(1/(\lambda^2 D))$. The exponential source has $R_{exp}(D) > R_{gauss}(D)$ for all $D > 0$, because the Gaussian is the hardest source to compress at a given variance. The gap measures the "non-Gaussianity" penalty and can be computed numerically via Blahut-Arimoto.

For successive refinement, we need $\hat{X}_1 = \hat{X}_2 \oplus N'$ where $N' \sim \text{Bern}(\delta)$. If $\hat{X}_2 = X \oplus N_2$ with $N_2 \sim \text{Bern}(D_2)$, then $\hat{X}_1 = X \oplus N_2 \oplus N' = X \oplus N_1$ where $N_1 \sim \text{Bern}(D_2 * \delta)$. For this to give $\mathbb{E}[d(X, \hat{X}_1)] = D_1$, we need $D_2 * \delta = D_1$.

The rate for $\hat{X}_2$ is $R(D_2)$. The incremental rate for $\hat{X}_1 \to \hat{X}_2$ in the successive scheme is $I(X; \hat{X}_2 | \hat{X}_1) = R(D_2) - I_{\text{base}}$. The total rate $R(D_2)$ must be achievable, and the base rate must be $R(D_1)$. The constraint is: can we find a joint distribution achieving both $R(D_1)$ at $D_1$ and $R(D_2)$ at $D_2$ with the degradation structure?

For $p \neq 1/2$, the optimal test channel at distortion $D$ is BSC($D$), but the optimal marginal $P_{\hat{X}}$ depends on $D$. At $D_1$: $P(\hat{X} = 0) = p * (1-D_1) + (1-p)D_1$. At $D_2 < D_1$: $P(\hat{X} = 0)$ is different. The degradation $\hat{X}_1 = \hat{X}_2 \oplus N'$ fixes the relationship between marginals, and for $p \neq 1/2$, this constraint prevents both layers from being individually optimal. The gap is small but nonzero.

With dithering: $Y = Q(X + U) - U$ where $Q$ is the uniform quantizer. The quantization noise is $Z = Y - X = Q(X + U) - U - X$. Schuchman's theorem states that $Z$ is uniformly distributed on $[-\Delta/2, \Delta/2]$ and independent of $X$. Therefore $D = \mathbb{E}[Z^2] = \Delta^2/12$, regardless of the distribution of $X$.

The quantized output $Q(X+U)$ takes integer values. Its entropy satisfies: $H(Q(X+U)) \leq h(X+U) - \log \Delta + 1$ (by the entropy bound for integer RVs). Since $h(X+U) \leq \frac{1}{2}\log(2^{2h(X)} + \Delta^2/12) \cdot 2\pi e$... More directly: $H(Q(X+U)) \leq h(X) + \frac{1}{2}\log(2\pi e \Delta^2/12)/\Delta$...

The clean result (Zamir and Feder, 1996) is: $R = H(Q(X+U)) \leq h(X) - \log\Delta + D_{KL}(f_Z \| f_{Gauss}) \leq h(X) - \log\Delta + 0.254$ nats. Converting: $0.254$ nats $\approx 0.366$ bits... The 0.754 bit figure comes from the full analysis including the entropy of the uniform distribution vs. Gaussian: $\frac{1}{2}\log(2\pi e/12) = 0.254$ nats $= 0.366$ bits is the shaping loss in entropy.

The total gap to $R(D)$: rate $\leq R(D) + \frac{1}{2}\log_2(\pi e/6) + 1 \approx R(D) + 0.754$ bits.