Exercises

(a) $\text{SNR}_{SD} = 10^{0.5} = 3.16$. $C_{\text{direct}} = \log_2(4.16) = 2.06$ bits/s/Hz.

(b) $\text{SNR}_{SR} = 100$, $\text{SNR}_{RD} = 31.62$. $C_{\text{DF}} = \frac{1}{2}\min\{\log_2(101), \log_2(1+3.16+31.62)\}$ $= \frac{1}{2}\min\{6.66, 5.16\} = 2.58$ bits/s/Hz.

(c) $C_{\text{AF}} = \frac{1}{2}\log_2(1+3.16 +\frac{100 \times 31.62}{1+100+31.62})$ $= \frac{1}{2}\log_2(1+3.16+23.83)$ $= \frac{1}{2}\log_2(28.0) = 2.41$ bits/s/Hz.

(d) DF: $2.58/2.06 = 25\%$ gain. AF: $2.41/2.06 = 17\%$ gain. DF provides the larger gain because the $S \to R$ link is strong enough for reliable decoding. $\blacksquare$

(a) Cut 1: $0.5\log_2(101) + 0.5\log_2(4.16) = 3.33 + 1.03 = 4.36$. Cut 2: $0.5\log_2(4.16) + 0.5\log_2(35.78) = 1.03 + 2.58 = 3.61$.

$C_{\text{cut}} = \min\{4.36, 3.61\} = 3.61$ bits/s/Hz.

(b) $C_{\text{cut}} - C_{\text{DF}} = 3.61 - 2.58 = 1.03$ bits/s/Hz.

This is above the theoretical 0.5-bit gap for the optimal time-sharing; the gap here is larger because we fixed $t = 1/2$.

(c) Strong relay requires $\text{SNR}_{SR} \geq \text{SNR}_{SD} + \text{SNR}_{RD}$: $100 \geq 3.16 + 31.62 = 34.78$. Yes, the relay is in the strong regime. $\blacksquare$

(a) Relay receives: $y_R = h_{SR}\sqrt{P_S}x + n_R$. Relay transmits: $x_R = G y_R$ with $G = \sqrt{P_R/(P_S|h_{SR}|^2 + \sigma^2)}$.

(b) Phase 1: $y_D^{(1)} = h_{SD}\sqrt{P_S}x + n_D^{(1)}$. Phase 2: $y_D^{(2)} = h_{RD}G(h_{SR}\sqrt{P_S}x + n_R) + n_D^{(2)}$.

$= h_{RD}Gh_{SR}\sqrt{P_S}x + h_{RD}Gn_R + n_D^{(2)}$.

(c) MRC combining yields: $\text{SINR}_{\text{MRC}} = \text{SNR}_{SD} + \text{SINR}_{\text{relay}}$

where $\text{SINR}_{\text{relay}} = \frac{|h_{RD}|^2 G^2 |h_{SR}|^2 P_S} {|h_{RD}|^2 G^2 \sigma^2 + \sigma^2} = \frac{\text{SNR}_{SR}\cdot\text{SNR}_{RD}} {1 + \text{SNR}_{SR} + \text{SNR}_{RD}}$.

Therefore: $C_{\text{AF}} = \frac{1}{2}\log_2(1 + \text{SNR}_{SD} + \frac{\text{SNR}_{SR}\text{SNR}_{RD}}{1+\text{SNR}_{SR}+\text{SNR}_{RD}})$. $\blacksquare$

(a) The relay channel is physically degraded if $p(y_R \mid x_S, x_R) = p(y_R \mid y_D)$, i.e., $Y_R$ is obtained from $Y_D$ through a memoryless channel.

More precisely: $X_S \to Y_D \to Y_R$ forms a Markov chain (given $X_R$). This means the relay receives a noisier version of the destination's signal.

(b) The cut-set bound (broadcast cut) is: $C \leq I(X_S; Y_R, Y_D \mid X_R) = I(X_S; Y_D \mid X_R) + I(X_S; Y_R \mid Y_D, X_R)$.

By the degradedness: $I(X_S; Y_R \mid Y_D, X_R) = 0$ (Markov chain). So Cut 2 $= I(X_S; Y_D \mid X_R)$.

DF achieves $\min\{I(X_S; Y_R \mid X_R), I(X_S, X_R; Y_D)\}$. Since $I(X_S; Y_R \mid X_R) \geq I(X_S; Y_D \mid X_R)$ (data processing inequality, reversed because degradedness is $X \to Y_D \to Y_R$... wait, the degraded direction means $Y_D$ is better than $Y_R$).

Actually: for the degraded relay channel where the relay has a weaker observation, DF with block Markov encoding achieves $C = \max \min\{I(X_S; Y_R \mid X_R), I(X_S, X_R; Y_D)\}$. Since $I(X_S; Y_R \mid X_R) \leq I(X_S; Y_D \mid X_R)$, the broadcast cut $I(X_S; Y_D \mid X_R)$ is not the binding cut.

(c) For the degraded relay channel: $C = \max_{p(x_S, x_R)} \min\{I(X_S; Y_R \mid X_R), I(X_S, X_R; Y_D)\}$

The degradedness ensures that the relay's decoding constraint is the tighter of the two cuts, and DF with superposition coding at the source achieves this. This was Cover and El Gamal's original 1979 result. $\blacksquare$

(a) $\text{SNR} = 10^{1.5} = 31.62$. $p_{\text{out}} = 1 - \exp(-3/31.62) = 1 - e^{-0.0949} = 0.0906$ (9.1%).

(b) Half-duplex effective rate: $2R = 4$ bits/s/Hz. Threshold: $2^4 - 1 = 15$.

$p_{\text{out}}^{\text{coop}} \approx (15/31.62)^2/2 = (0.474)^2/2 = 0.112$.

Wait — this is worse than direct! The half-duplex penalty doubles the effective rate requirement. With effective threshold $\tau = 2^{2R} - 1 = 15$:

$p_{\text{out}} \approx \binom{2}{2}\tau^2/\text{SNR}^{2} = 15^2/31.62^2 = 225/1000 = 0.225$.

At $R = 2$ bits/s/Hz and SNR = 15 dB, the half-duplex penalty outweighs the diversity gain. Cooperation is beneficial at higher SNR or lower rate.

(c) For $R = 1$ bit/s/Hz instead: Direct: $p_{\text{out}} = 1 - e^{-1/31.62} = 0.031$. Coop: $\tau = 2^2 - 1 = 3$, $p_{\text{out}} \approx 9/1000 = 0.009$.

Cooperation gain: direct needs SNR $= 1/0.009 \approx$ 20.5 dB for 0.9% outage; coop achieves it at 15 dB. Gain $\approx$ 5.5 dB. $\blacksquare$

(a) In repetition-coded cooperation, $L+1$ phases transmit the same codeword. The effective rate is $R/(L+1)$. The multiplexing gain $r = R/\log(\text{SNR})$, so the effective multiplexing gain is $r/(L+1)$. Maximum: $r_{\max} = 1/(L+1)$ (since the per-phase $r \leq 1$).

(b) At $r = 0$: all $L+1$ paths contribute diversity independently. Each Rayleigh link provides diversity 1. $d(0) = (L+1) \times 1 = L+1$.

(c) The DMT is linear: $d(r) = (L+1)(1-(L+1)r)$ for $0 \leq r \leq 1/(L+1)$.

$L=1$: $d(r) = 2(1-2r)$, $r_{\max} = 0.5$. $L=2$: $d(r) = 3(1-3r)$, $r_{\max} = 0.333$. $L=3$: $d(r) = 4(1-4r)$, $r_{\max} = 0.25$.

(d) DDF: $d(r) = (L+1)(1-r)$ for $0 \leq r \leq 1$.

DDF achieves the same maximum diversity $d(0) = L+1$ but with multiplexing gain up to $r = 1$ (the full MISO DMT). The repetition-coded DMT is strictly worse for all $r > 0$. $\blacksquare$

(a) Source transmits a codeword of block length $n$. Relay $\ell$ listens until time $f_\ell n$ where:

$f_\ell = \inf\{t : t\log_2(1+\text{SNR}|h_{SR_\ell}|^2) \geq nR\}$

$= R/\log_2(1+\text{SNR}|h_{SR_\ell}|^2)$.

After decoding, relay transmits a distributed space-time code with the source for the remaining $(1-f_\ell)n$ symbols.

(b) With $R = r\log_2(\text{SNR})$ and Rayleigh fading: $f_\ell = r\log(\text{SNR})/\log(1+\text{SNR}|h_{SR_\ell}|^2)$.

For $|h_{SR_\ell}|^2 = \text{SNR}^{-v}$ (exponential parameterisation): $f_\ell = r/(1-v)$ when $v < 1$.

If $v > r/(1+\epsilon)$: $f_\ell > 1$ and relay cannot decode. Probability: $\Pr[v > 1-r] \doteq \text{SNR}^{-(1-r)}$.

(c) With $(L+1)$ paths (direct + $L$ relays), each independently faded, and relay $\ell$ contributing for fraction $(1-f_\ell)$:

The outage exponent is $(L+1)(1-r)$, matching the $(L+1) \times 1$ MISO DMT. The dynamic listening ensures that the relay contributes whenever possible, and the diversity order is not penalised by the variable listening time. $\blacksquare$

(a) $\text{SNR}_{SD} = 10$. $\text{SNR}_{SR} = 10 \times 0.3^{-4} = 10/0.0081 = 1235$. $\text{SNR}_{RD} = 10 \times 0.7^{-4} = 10/0.2401 = 41.6$.

(b) $C_{\text{DF}} = 0.5\min\{\log_2(1236), \log_2(1+10+41.6)\}$ $= 0.5\min\{10.27, 5.72\} = 2.86$ bits/s/Hz.

(c) $f = 0.5$: $\text{SNR}_{SR} = 160$, $\text{SNR}_{RD} = 160$. $C = 0.5\min\{7.33, 7.42\} = 3.67$.

$f = 0.7$: $\text{SNR}_{SR} = 41.6$, $\text{SNR}_{RD} = 1235$. $C = 0.5\min\{5.41, 10.28\} = 2.71$.

$f = 0.5$ gives the highest rate (3.67 bits/s/Hz). $\blacksquare$

(a) | $\alpha$ | $f^{\star}$ | |----------|-------------| | 2 | 0.382 | | 3 | 0.414 | | 4 | 0.435 | | 5 | 0.447 | | 6 | 0.456 |

(b) As $\alpha \to \infty$: for $f < 0.5$, $f^{-\alpha} \gg 1$ and $(1-f)^{-\alpha} \ll f^{-\alpha}$. The equation $f^{-\alpha} = 1 + (1-f)^{-\alpha}$ requires both sides to be nearly equal, which forces $f \to 0.5$.

(c) For $\alpha = 1$: $1/f = 1 + 1/(1-f) = (2-f)/(1-f)$. Cross-multiplying: $(1-f) = f(2-f)$, $1-f = 2f - f^2$, $f^2 - 3f + 1 = 0$, $f = (3-\sqrt{5})/2 = 0.382$. As $\alpha \to 1$, $f \to 0.382$.

(d) $f^{\star}$ varies from 0.382 to 0.456 as $\alpha$ goes from 2 to 6 — a range of only 7.4% of $d_{SD}$. The optimal position is remarkably insensitive to the path-loss exponent, so $f \approx 0.4$--$0.45$ is a robust choice for most environments. $\blacksquare$

(a) $(m_A, m_B)$: $(0,0) \to y = -2+n$; $(0,1) \to y = 0+n$; $(1,0) \to y = 0+n$; $(1,1) \to y = +2+n$.

Three distinct levels: $\{-2, 0, +2\}$.

(b) $m_A \oplus m_B = 0$ when $y \approx \pm 2$ (same bits). $m_A \oplus m_B = 1$ when $y \approx 0$ (different bits).

Threshold detector: if $|y| > 1$, decode XOR = 0; if $|y| < 1$, decode XOR = 1.

(c) When $|h_A| \neq |h_B|$, the constellation points are $h_A + h_B$, $h_A - h_B$, $-h_A + h_B$, $-h_A - h_B$. The middle two points ($h_A - h_B$ and $-h_A + h_B$) are no longer coincident, creating a 4-point constellation.

Solution: the relay uses a mapping that accounts for the known channel gains, or it uses lattice codes that are designed to be robust to asymmetric channels. $\blacksquare$

(a) Phase 1 is a Gaussian MAC: $R_A \leq \log_2(1+|h_A|^2\gamma)$ $R_B \leq \log_2(1+|h_B|^2\gamma)$ $R_A + R_B \leq \log_2(1+|h_A|^2\gamma+|h_B|^2\gamma)$

(b) For the relay to decode $m_A \oplus m_B$, it suffices to decode the lattice point $m_A + m_B \bmod p$ for some prime $p$. The rate of the XOR function is bounded by the computation rate:

$R_{\text{comp}} \leq \log_2(1 + |h_A|^2\gamma + |h_B|^2\gamma) - \log_2(1 + |h_A - h_B|^2\gamma)$ (for lattice codes).

For equal channels: $R_{\text{comp}} \leq \log_2(1+2\gamma)$.

(c) Phase 2: relay broadcasts at rate $R_{\text{BC}} = \min\{\log_2(1+|h_{RA}|^2\gamma), \log_2(1+|h_{RB}|^2\gamma)\}$.

Sum rate: $R_{\Sigma} = \min\{R_{\text{comp}}, R_{\text{BC}}\}$.

With equal channels: $R_{\Sigma} = \log_2(1+\gamma)$ per phase, so sum rate $= \log_2(1+\gamma)$ bits/s/Hz.

(d) The cut-set bound for the TWRC is $R_{\Sigma} \leq \log_2(1+2\gamma)$. The PNC achievable rate is $\log_2(1+\gamma)$.

Gap: $\log_2(1+2\gamma) - \log_2(1+\gamma) = \log_2((1+2\gamma)/(1+\gamma))$.

At high SNR: gap $\to \log_2(2) = 1$ bit. $\blacksquare$

(a) $T(50) = 1/\sqrt{50 \times 3.91} = 1/\sqrt{195.6} = 0.0715$. (b) $T(500) = 1/\sqrt{500 \times 6.21} = 1/\sqrt{3107} = 0.0179$. (c) $T(5000) = 1/\sqrt{5000 \times 8.52} = 1/\sqrt{42{,}600} = 0.00485$.

(d) $T(50)/T(5000) = 0.0715/0.00485 = 14.7\times$.

A 100$\times$ increase in nodes reduces per-node throughput by 14.7$\times$. The sub-linear scaling $1/\sqrt{n\log n}$ is better than $1/n$ (direct transmission) but still approaches zero. $\blacksquare$

(a) $\bar{d}_{SD} = \Theta(1)$ (random pairs in unit square). Hop length: $r = c\sqrt{\log n/n}$. Hops per route: $\bar{d}_{SD}/r = \Theta(\sqrt{n/\log n})$.

(b) Each route passes through $\Theta(\sqrt{n/\log n})$ nodes. There are $n$ routes total (one per source). Each node's neighbourhood (area $\sim r^2 = c^2\log n/n$) is crossed by routes from sources that lie on a strip of width $r$ through the neighbourhood.

Number of routes through a typical node: $\Theta(n \times r \times 1) = \Theta(\sqrt{n\log n})$.

(c) Each node can transmit at rate $W$ per time slot. With spatial reuse, each node gets $\Theta(1)$ fraction of time. It must relay for $\Theta(\sqrt{n\log n})$ flows.

Per-flow throughput: $T(n) = \Theta(1/\sqrt{n\log n})$. $\blacksquare$

(a) Phase I (local exchange): Nodes within a cluster of size $M$ exchange their data using the protocol of the previous hierarchical level. After this phase, every node in the cluster knows all $M$ messages.

Phase II (long-range MIMO): The cluster acts as a virtual $M$-antenna array and performs distributed MIMO transmission to another cluster (also with $M$ virtual antennas), achieving multiplexing gain $M$.

Phase III (local distribution): The receiving cluster distributes the decoded messages to individual nodes.

(b) Phase I requires $M$ messages to be exchanged within a cluster of $M$ nodes. Using the previous level's protocol with per-node throughput $T_{\text{prev}}$: time $\sim M/T_{\text{prev}}$.

The MIMO phase delivers $M$ streams in one "super-slot." The ratio of overhead to useful data is $M/(M \cdot T_{\text{prev}}) = 1/T_{\text{prev}}$, which is $o(1)$ if $T_{\text{prev}} \to \infty$ (in the appropriate scaling).

(c) Starting with $M_0 = 1$ (individual nodes): $M_1 = n^{1/2}$ (first level clusters). $M_2 = n^{3/4}$... More precisely, at each level the cluster size grows as $M_{k+1} = M_k^2$: $M_k = M_1^{2^{k-1}}$. After $L$ levels: $M_L = M_1^{2^{L-1}} = n$. $L = 1 + \log_2(\log_{M_1} n) = O(\log\log n)$.

(d) Key challenges:

1. CSI overhead: Each node needs CSI for all $M$ intra-cluster links.
2. Synchronisation: Distributed space-time coding requires tight timing across the cluster.
3. Backhaul for CSI exchange: The intra-cluster exchange of channel estimates consumes overhead.
4. Latency: $O(\log\log n)$ levels of recursion introduce delay. $\blacksquare$

(a) $\text{SNR}_{SR}/\text{SNR}_{SD} = (1/0.5)^3 = 8$. $\text{SNR}_{RD}/\text{SNR}_{SD} = (1/0.5)^3 = 8$.

(b) $1 = \log_2(1+\text{SNR}_{SD})$ requires $\text{SNR}_{SD} = 1$. $\gamma_0 = \text{SNR}_{SD} \times d_{SD}^3 = 1 \times 8 = 8$ (9 dB).

(c) $\text{SNR}_{SR} = 8$, $\text{SNR}_{RD} = 8$. $C_{\text{DF}} = 0.5\min\{\log_2(9), \log_2(1+1+8)\}$ $= 0.5\min\{3.17, 3.32\} = 1.58$ bits/s/Hz.

Gain: $1.58/1.0 = 58\%$. $\blacksquare$

(a) $\text{SNR}_{SR} = 16\gamma_{SD}$, $\text{SNR}_{RD} = 16\gamma_{SD}$.

$C_{\text{AF}} = \frac{1}{2}\log_2\!\left(1 + \gamma_{SD} + \frac{256\gamma_{SD}^2}{1+32\gamma_{SD}}\right)$

(b) At the crossover: $\log_2(1+\gamma) = \frac{1}{2}\log_2(1+\gamma+256\gamma^2/(1+32\gamma))$.

$(1+\gamma)^2 = 1 + \gamma + \frac{256\gamma^2}{1+32\gamma}$

$\gamma + \gamma^2 = \frac{256\gamma^2}{1+32\gamma}$

$(1+\gamma)(1+32\gamma) = 256\gamma$

$32\gamma^2 + 33\gamma + 1 = 256\gamma$

$32\gamma^2 - 223\gamma + 1 = 0$

$\gamma = (223 \pm \sqrt{223^2 - 128})/64 = (223 \pm 222.7)/64$.

$\gamma^{\star} \approx 445.7/64 = 6.96$ (8.4 dB).

(c) AF crossover: 8.4 dB. DF crossover: 23.5 dB. AF ceases to be beneficial at much lower SNR than DF because it amplifies noise, providing less SNR gain per relay hop. $\blacksquare$

(a) $C_{\text{FD-DF}} = \min\{ \log_2(1+\gamma f^{-\alpha}/(1+\beta)), \log_2(1+\gamma+\gamma(1-f)^{-\alpha})\}$

No 1/2 pre-factor since the relay transmits and receives simultaneously.

(b) With $\beta = 0$: $C_{\text{FD-DF}} = \min\{\log_2(1+\gamma f^{-\alpha}), \log_2(1+\gamma+\gamma(1-f)^{-\alpha})\}$

Both terms $\geq \log_2(1+\gamma) = C_{\text{direct}}$ since $f^{-\alpha} > 1$ and $\gamma(1-f)^{-\alpha} > 0$.

Therefore $C_{\text{FD-DF}} > C_{\text{direct}}$ always.

(c) At $f = 0.5$, $\alpha = 4$, SNR = 20 dB ($\gamma = 100$):

HD-DF: $C = 0.5\log_2(1+1600) = 5.33$ bits/s/Hz.

FD-DF $> 5.33$ requires: $\log_2(1+1600/(1+\beta)) > 5.33$ $1600/(1+\beta) > 2^{5.33} - 1 = 39.3$ $1+\beta < 40.7$ $\beta < 39.7$ (16 dB).

Full-duplex needs only 16 dB of SI cancellation to beat half-duplex DF at 20 dB SNR. Modern prototypes achieve 80+ dB cancellation — far exceeding this requirement. $\blacksquare$

(a) Each hop spans distance $d = d_{SD}/(L+1)$. $\text{SNR}_{\text{hop}} = \gamma_0 \cdot (d_{SD}/(L+1))^{-\alpha} = \gamma_0 (L+1)^{\alpha}/d_{SD}^{\alpha}$.

End-to-end rate (bottleneck = per-hop rate / time fraction): $C_L = \frac{1}{L+1}\log_2(1+\gamma_0(L+1)^{\alpha}/d_{SD}^{\alpha})$.

(b) Taking derivative of $C_L$ and setting to zero: $\frac{\partial C_L}{\partial L} = 0$ gives $\alpha \gamma_{\text{hop}}/(1+\gamma_{\text{hop}}) = \ln(1+\gamma_{\text{hop}})$.

For large $\gamma_{\text{hop}}$: $\alpha \approx \ln(\gamma_{\text{hop}})$, so $\gamma_{\text{hop}} \approx e^{\alpha}$, giving $(L+1)^{\alpha} \approx e^{\alpha} d_{SD}^{\alpha}/\gamma_0$, $L+1 \approx e \cdot d_{SD}/\gamma_0^{1/\alpha}$.

(c) $\gamma_0 = 1000$, $d_{SD} = 4$, $\alpha = 4$. $\gamma_{SD} = 1000/256 = 3.91$.

$L = 0$: $C = \log_2(4.91) = 2.30$. $L = 1$: $C = 0.5\log_2(1+1000\times4/256) = 0.5\log_2(16.6) = 2.03$. $L = 3$: $C = 0.25\log_2(1+1000\times256/256) = 0.25\log_2(1001) = 2.49$.

Multi-hop with 3 relays gives the best rate (2.49 bits/s/Hz).

(d) Multi-hop introduces: (i) latency of $L$ hop delays, (ii) synchronisation overhead for TDMA scheduling, (iii) CSI acquisition for each hop, (iv) reliability concerns (one failed hop drops the connection). The optimal $L$ balances rate gain against these overheads. $\blacksquare$