Exercises

The cut-set bound gives $C \leq \max_{p(x,x_r)} \min\{I(X,X_r;Y), I(X;Y,Y_r|X_r)\}$. Since $Y_r$ is independent of everything, $I(X;Y,Y_r|X_r) = I(X;Y|X_r) \leq I(X;Y)$. Also, $I(X,X_r;Y) \geq I(X;Y)$ (more inputs cannot decrease MI). So the cut-set bound is $\max_{p(x)} I(X;Y)$.

Direct transmission without the relay achieves $\max_{p(x)} I(X;Y)$. This matches the upper bound, so $C = \max_{p(x)} I(X;Y)$.

$I(X; Y, Y_r | X_r) = I(X; Y_r | X_r) + I(X; Y | Y_r, X_r)$.

By the degradedness condition, $X \to (Y_r, X_r) \to Y$, which means $Y$ is conditionally independent of $X$ given $(Y_r, X_r)$. Therefore $I(X; Y | Y_r, X_r) = 0$, and $I(X; Y, Y_r | X_r) = I(X; Y_r | X_r)$.

We need $\frac{B}{B+1} \geq 0.99$, i.e., $B \geq 0.99(B+1) = 0.99B + 0.99$, so $0.01 B \geq 0.99$, giving $B \geq 99$.

With $B = 99$ blocks, the rate loss from block-Markov encoding is only 1%. This is why the rate penalty is negligible in practice — at the cost of a latency of $99n$ channel uses before the first message is decoded.

To decode block $b$, the destination needs the relay's codeword $x_r^n(W_{b-1})$. But $W_{b-1}$ is the message from the previous block — exactly what we want to decode! Forward decoding would require knowing $W_{b-1}$ to find $W_b$, creating a chicken-and-egg problem.

In block $B+1$, a known dummy message is sent. The destination starts there and works backwards: knowing $W_b$ (decoded from block $b+1$), it can determine the relay codeword $x_r^n(W_{b-1})$ and decode $W_{b-1}$ from block $b$. The chain of dependencies runs from block $B+1$ back to block $1$, with each step well-defined.

The Wyner-Ziv constraint is $I(Y_r; \hat{Y}_r | Y, X_r) \leq I(X_r; Y)$. The left side is the Wyner-Ziv compression rate (how many bits are needed to describe $\hat{Y}_r$ given that the destination has $Y$ as side information). The right side is the relay-destination link capacity.

The constraint says the relay-destination link must be strong enough to carry the compressed description. If violated, the relay must use coarser compression (larger distortion), which reduces the quality of $\hat{Y}_r$ and hence the achievable rate. In the extreme, if the relay-destination link has zero capacity, CF reduces to direct transmission — the relay cannot help at all.

The relay can decode the source at rate $R_1 = \frac{1}{2}\log\!\left(1 + \frac{P}{N_r}\right)$.

With the relay having decoded, it can send the message over the noiseless link at rate $C_0$. The destination also receives $Y = X + Z$, providing additional information. In the DF scheme, the destination gets the message from two paths: direct (rate $\frac{1}{2}\log(1+P/N)$) and via relay (rate $C_0$). The effective cooperative rate is bounded by $\frac{1}{2}\log(1+P/N) + C_0$ (the MAC bound with independent inputs).

$R_{\text{DF}} = \min\!\left\{\frac{1}{2}\log\!\left(1 + \frac{P}{N_r}\right),\; \frac{1}{2}\log\!\left(1 + \frac{P}{N}\right) + C_0\right\}.$$ The first term is the source-relay bottleneck; the second is the cooperative link to the destination.

The cut-set bound: $\max_{p(x,x_r)} \min\{I(X,X_r;Y), I(X;Y,Y_r|X_r)\}$. The DF rate: $\max_{p(x,x_r)} \min\{I(X;Y_r|X_r), I(X,X_r;Y)\}$.

The broadcast cut term $I(X,X_r;Y)$ is the same in both. For the second term: $I(X;Y,Y_r|X_r) \geq I(X;Y_r|X_r)$ because conditioning on $Y$ in addition to $Y_r$ can only increase (or maintain) the mutual information.

Since $I(X;Y,Y_r|X_r) \geq I(X;Y_r|X_r)$, the cut-set bound's second term is at least as large as DF's second term. Therefore the cut-set bound is always $\geq$ the DF rate. The gap arises because DF ignores the destination's direct observation $Y$ when determining the relay's decoding rate — the relay must decode on its own.

The natural choice is $\hat{Y}_r = Y_r + Z_q$ where $Z_q \sim \mathcal{N}(0, \Delta)$ is independent quantization noise. This gives the test channel $p(\hat{y}_r | y_r) = \mathcal{N}(\hat{y}_r; y_r, \Delta)$, which is Gaussian and hence optimal for the Gaussian source $Y_r$.

The Wyner-Ziv rate (with side information $Y$) is: $$I(Y_r; \hat{Y}_r | Y) = \frac{1}{2}\log\!\left(1 + \frac{\text{Var}(Y_r | Y)}{\Delta}\right)$$ where $\text{Var}(Y_r | Y)$ is the MMSE of estimating $Y_r$ from $Y$. The compression distortion $\Delta$ is optimized to balance the rate constraint against the achievable rate.

The channel is already integer-valued. Choosing $\mathbf{a} = (2, 1)^T$: the effective noise is minimized because $\mathbf{a}$ is parallel to $\mathbf{h}$. The rate is approximately $\frac{1}{2}\log(\text{SNR}) \approx \frac{1}{2}\log(100) \approx 3.32$ bits.

The best integer approximations are $\mathbf{a} = (2, 1)^T$ or $(1, 1)^T$. For $\mathbf{a} = (2, 1)^T$: the mismatch $\mathbf{a} - \alpha^* \mathbf{h}$ creates additional effective noise, reducing the rate. Computing explicitly: the rate drops by approximately 0.5-1 bit compared to the integer-aligned case.

Even a small deviation of $\mathbf{h}$ from integer values causes a noticeable rate loss in CaF. This sensitivity to channel alignment is the main practical limitation of compute-and-forward.

In the listen phase ($\alpha n$ channel uses), the relay accumulates mutual information $\alpha I(X; Y_r)$ (since $X_r = 0$ during listen). In the transmit phase ($(1-\alpha)n$ channel uses), the source-relay pair achieves $(1-\alpha) I(X, X_r; Y)$. The DF rate is: $$R_{\text{DF}}(\alpha) = \min\{\alpha I(X; Y_r),\; (1-\alpha) I(X, X_r; Y)\}.$$

The optimal $\alpha^*$ balances the two constraints: $\alpha^* I(X; Y_r) = (1-\alpha^*) I(X, X_r; Y)$, giving $$\alpha^* = \frac{I(X, X_r; Y)}{I(X; Y_r) + I(X, X_r; Y)}.$$ The optimized rate is $R_{\text{DF}}^* = \frac{I(X; Y_r) \cdot I(X, X_r; Y)}{I(X; Y_r) + I(X, X_r; Y)}$, the harmonic mean of the two link rates.

$I(X; \hat{Y}_r, Y | X_r) \geq I(X; Y | X_r) \geq I(X; Y)$ where the first inequality follows because conditioning on additional variables ($\hat{Y}_r$) cannot decrease mutual information when $\hat{Y}_r$ carries information about $X$ through $Y_r$. The second holds because $X_r$ is independent of $X$ in the CF scheme.

CF never hurts: the relay's compressed observation is additional side information at the destination. Even if $\hat{Y}_r$ is nearly useless (high distortion), the destination still has its own observation $Y$. The rate is at least the direct-link rate.

$I(X; Y_{r_1}, Y_{r_2}) = \frac{1}{2}\log\!\left(1 + \frac{(|h_1|^2 + |h_2|^2) P}{N}\right)$ assuming independent equal-variance noise.

$I(X_{r_1}, X_{r_2}; Y) = \frac{1}{2}\log\!\left(1 + |g_1|^2 P_{r_1} + |g_2|^2 P_{r_2}\right)$ where $N = 1$ (normalized noise).

$C \leq \min\!\left\{\frac{1}{2}\log\!\left(1 + (|h_1|^2 + |h_2|^2) \frac{P}{N}\right),\; \frac{1}{2}\log(1 + |g_1|^2 P_{r_1} + |g_2|^2 P_{r_2})\right\}.$$ (The two hybrid cuts are omitted here but should also be checked in general.)

$I(X, X_r; Y) \geq I(X; Y)$ since more inputs cannot reduce MI. With reverse degradedness, $Y$ contains all the information about $X$, so: $I(X, X_r; Y) = I(X; Y) + I(X_r; Y | X) \leq I(X; Y) + I(X_r; Y)$.

$I(X; Y, Y_r | X_r) = I(X; Y | X_r) + I(X; Y_r | Y, X_r)$. By the Markov chain $X \to (Y, X_r) \to Y_r$: $I(X; Y_r | Y, X_r) = 0$. So $I(X; Y, Y_r | X_r) = I(X; Y | X_r) \leq I(X; Y)$ (since $X$ and $X_r$ are independent in the maximizing distribution).

The multiple-access cut gives $C \leq \max_{p(x)} I(X; Y)$. Direct transmission achieves this, so $C = \max_{p(x)} I(X; Y)$. The relay is useless because its observation is a degraded version of the destination's.

With $\hat{Y}_r = Y_r + Z_q$: $(X, Y, \hat{Y}_r)$ are jointly Gaussian. $I(X; \hat{Y}_r, Y) = H(X) - H(X | Y, \hat{Y}_r)$. The MMSE of $X$ given $(Y, \hat{Y}_r)$ can be computed via the MMSE formula for jointly Gaussian vectors: $$\text{MMSE} = \left(\frac{1}{P} + \frac{1}{N} + \frac{1}{N_r + \Delta}\right)^{-1} \triangleq D.$$ So $I(X; \hat{Y}_r, Y) = \frac{1}{2}\log(P/D)$.

$I(Y_r; \hat{Y}_r | Y) = \frac{1}{2}\log\!\left(1 + \frac{\text{Var}(Y_r | Y)}{\Delta}\right)$. With $\text{Var}(Y_r | Y) = N_r - \frac{P^2/(P+N)}{1} \cdot \frac{1}{P+N_r} \cdot (\ldots)$... More precisely: $\text{Var}(Y_r | Y) = N_r(1 - \rho^2) + \frac{N_r \rho^2 N}{P + N}$ where $\rho^2 = P^2/((P+N)(P+N_r))$ is the squared correlation. Simplifying: $\text{Var}(Y_r|Y) = \frac{N_r(P+N) + N \cdot P}{(P+N)} = N_r + \frac{P N_r}{P+N} \cdot 0$... Actually: $\text{Var}(Y_r|Y) = N_r + P - \frac{P^2}{P+N} = \frac{PN + N \cdot N_r}{P+N} = \frac{N(P + N_r)}{P+N}$. The constraint is $\frac{1}{2}\log(1 + \frac{N(P+N_r)}{(P+N)\Delta}) \leq C_0$.

From the constraint: $\Delta \geq \frac{N(P+N_r)}{(P+N)(2^{2C_0}-1)}$. The achievable rate is $R_{\text{CF}} = \frac{1}{2}\log\frac{P}{D}$ where $D = (P^{-1} + N^{-1} + (N_r + \Delta)^{-1})^{-1}$, and $\Delta$ is chosen to satisfy the constraint with equality.

With normalized direct-link distance $d = 1$ and relay at $d/2$, the path loss is $1/d^2$. Source-relay distance is $1/2$, so source-relay SNR is $P/(1/2)^2 = 4P = 4\text{SNR}$ (normalizing $N = 1$). Similarly, relay-destination SNR is $4\text{SNR}$ (assuming the relay has the same power $P$).

$R_{\text{DF}} = \min\{\frac{1}{2}\log(1 + 4\text{SNR}),\; \frac{1}{2}\log(1 + \text{SNR} + 4\text{SNR})\}$ $= \min\{\frac{1}{2}\log(1 + 4\text{SNR}),\; \frac{1}{2}\log(1 + 5\text{SNR})\}$ $= \frac{1}{2}\log(1 + 4\text{SNR})$.

Direct: $\frac{1}{2}\log(1 + \text{SNR})$. DF with midpoint relay: $\frac{1}{2}\log(1 + 4\text{SNR})$. At high SNR, the gain approaches 2 bits per channel use — a 6 dB power gain from relaying.

$\mathbf{z}_{\text{eff}} = \alpha \mathbf{y} - (a_1 \mathbf{x}_1 + a_2 \mathbf{x}_2) = (\alpha h_1 - a_1)\mathbf{x}_1 + (\alpha h_2 - a_2)\mathbf{x}_2 + \alpha \mathbf{z}$.

Per-dimension variance: $\sigma_{\text{eff}}^2 = (\alpha h_1 - a_1)^2 P + (\alpha h_2 - a_2)^2 P + \alpha^2 \sigma^2$ $= P\|\alpha \mathbf{h} - \mathbf{a}\|^2 + \alpha^2 \sigma^2$.

Minimize $\sigma_{\text{eff}}^2$ over $\alpha$: $\frac{\partial}{\partial \alpha}\sigma_{\text{eff}}^2 = 2P(\alpha \|\mathbf{h}\|^2 - \mathbf{h}^T\mathbf{a}) + 2\alpha \sigma^2 = 0$, giving $\alpha^* = \frac{P \mathbf{h}^T \mathbf{a}}{P\|\mathbf{h}\|^2 + \sigma^2}$.

Substituting $\alpha^*$: $\sigma_{\text{eff}}^2 = P\|\mathbf{a}\|^2 - \frac{P^2(\mathbf{h}^T\mathbf{a})^2}{P\|\mathbf{h}\|^2 + \sigma^2} + \text{noise terms}$. The computation rate is $R_{\text{CaF}} = \frac{1}{2}\log^+\frac{P}{\sigma_{\text{eff}}^2}$.

At high SNR, the broadcast cut scales as $\frac{1}{2}\log\text{SNR} + O(1)$ and the MAC cut scales as $\frac{1}{2}\log(P_{r_1} + P_{r_2}) + O(1)$.

Each relay quantizes at the noise level: $\Delta_k = N_k$. The relay-destination rates required are $\frac{1}{2}\log(1 + (P+N_k)/N_k)$ per relay. As $\text{SNR} \to \infty$, the quantization overhead is $\frac{1}{2}\log(1 + P/N_k) \approx \frac{1}{2}\log\text{SNR}$ per relay.

The gap between the CF rate and the cut-set bound is bounded by a constant that depends on $N_1, N_2$ but not on $\text{SNR}$. Specifically, quantizing at the noise level introduces at most 1 bit of rate loss per relay, giving a total gap of at most 2 bits. This constant-gap result foreshadows the noisy network coding theorem of Chapter 23.

Split the source message $W$ into $(W_1, W_2)$ at rates $(R_1, R_2)$ with $R_1 + R_2 = R$. Use superposition coding: $X = f(X_1(W_1), X_2(W_2))$.

The relay decodes $W_1$ from $(Y_r^n, X_r^n)$ (requires $R_1 \leq I(X_1; Y_r | X_2, X_r)$). Then, knowing $W_1$, the relay compresses its residual observation of $W_2$: form $\hat{Y}_r$ from $Y_r$ given $X_1(W_1)$ and $X_r$, and forward the compressed version.

The destination decodes $(W_1, W_2)$ using $(Y^n, \hat{Y}_r^n, X_r^n)$. The achievable rate region involves:

• $R_1 \leq I(X_1; Y_r | X_2, X_r)$ (relay decoding of $W_1$),
• $R_1 + R_2 \leq I(X_1, X_2; \hat{Y}_r, Y | X_r)$ (joint destination decoding),
• $I(Y_r; \hat{Y}_r | Y, X_1, X_r) \leq I(X_r; Y | X_2)$ (Wyner-Ziv constraint).

Setting $R_1 = R$ (no compression, relay decodes everything): recovers DF. Setting $R_1 = 0$ (no decoding, relay only compresses): recovers CF. The partial scheme can strictly outperform both when neither the source-relay link nor the relay-destination link dominates.

The relay receives $Y_{r,1}^{\alpha n}$ and the destination receives $Y_1^{\alpha n}$. The relay compresses $Y_{r,1}^{\alpha n}$ to $\hat{Y}_{r,1}^{\alpha n}$.

The relay transmits the compression index plus any DF assistance. The destination receives $Y_2^{(1-\alpha)n}$ from both source and relay.

The hybrid rate is: $$R_{\text{hybrid}}(\alpha) = \alpha I(X; Y_1) + (1-\alpha) I(X, X_r; Y_2) + \text{CF bonus from } \hat{Y}_{r,1}$$ subject to the Wyner-Ziv constraint that the relay-destination link in phase 2 can carry the compression bits. The full derivation involves careful joint optimization of $\alpha$ and the compression quality.

The hybrid protocol can strictly improve over both pure half-duplex DF and CF because it exploits the destination's observation from both phases while also using the relay's compressed observation. The gain is most pronounced at intermediate SNR where neither DF nor CF clearly dominates.

With no memory, $X_{r,i}$ must be a fixed symbol (independent of everything). The relay is equivalent to an additional fixed input, which cannot carry information. The capacity is $\max_{p(x)} I(X; Y | X_r = x_r^*)$ for the best fixed relay input $x_r^*$. This equals the direct-link capacity $\max_{p(x)} I(X; Y)$ when the channel factors appropriately.

The relay has enough memory to store the full decoded message $W$ (which requires $nR$ bits). It can implement block-Markov DF by storing $W_{b-1}$ and encoding $X_r^n(W_{b-1})$ in block $b$. Full DF rate is achieved.

The relay can store partial information about the decoded message. The achievable rate interpolates between the direct-link rate ($M = 0$) and the full DF rate ($M \geq nR$). The relay memory acts as a "bottleneck" that limits the cooperation rate. This is analogous to the fronthaul capacity constraint in Cloud-RAN architectures (Chapter 25).