Ferkans — Interactive Telecom Tutor

The Relay Channel: Cooperation Without Shared Messages

The relay channel is a three-terminal network where a source communicates with a destination, assisted by a relay that has no message of its own. This models cooperative communication in cellular networks (relay-assisted transmission), mesh networks, and satellite systems. The relay channel, first studied by van der Meulen (1971) and developed by Cover and El Gamal (1979), remains one of the most important open problems in information theory: the capacity is unknown even for the simple Gaussian case. What we have are tight upper bounds (cut-set) and lower bounds (decode-forward, compress-forward) that match in special cases but not in general.

Three-Node Relay Channel — The relay channel consists of a source, relay, and destination. The source communicates to the destination via a direct link ( $h_{\text{SD}}$ ) and a two-hop relay path ( $h_{\text{SR}}$ , $h_{\text{RD}}$ ). The relay has no message of its own — it assists the source-destination communication.

Definition:
Gaussian Relay Channel

The Gaussian relay channel consists of a source ( $X_1$ ), relay ( $X_2$ ), and destination ( $Y$ ):

$Y_R = g_{SR} X_1 + Z_R \quad \text{(source-to-relay)}$ $Y = g_{SD} X_1 + g_{RD} X_2 + Z \quad \text{(to destination)}$

where $g_{SR}, g_{SD}, g_{RD}$ are channel gains, $X_1$ has power $P_1$ , $X_2$ has power $P_2$ , and $Z_R, Z \sim \mathcal{N}(0, 1)$ .

The relay operates causally: $X_{2,i}$ can depend on $(Y_{R,1}, \ldots, Y_{R,i-1})$ but not on $Y_{R,i}$ (full-duplex with causal processing).

Key channel parameters:

$\text{SNR}_{D} = g_{SD}^2 P_1$ : direct link SNR
$\text{SNR}_{R} = g_{SR}^2 P_1$ : source-to-relay SNR
$\text{SNR}_{RD} = g_{RD}^2 P_2$ : relay-to-destination SNR

The relay channel is fundamentally different from the MAC and BC because the relay does not have its own message — it must help the source. This cooperation constraint makes the channel harder to analyse than the MAC or BC.

,

Theorem: Cut-Set Upper Bound

For any relay channel, the capacity is upper bounded by:

$C \leq \max_{p(x_1, x_2)} \min\{I(X_1, X_2; Y), \; I(X_1; Y, Y_R | X_2)\}$

For the Gaussian relay channel with coherent combining:

$C \leq \min\left\{ \frac{1}{2}\log_2\!\left(1 + (g_{SD}\sqrt{P_1} + g_{RD}\sqrt{P_2})^2\right), \; \frac{1}{2}\log_2\!\left(1 + g_{SD}^2 P_1 + g_{SR}^2 P_1\right) \right\}$

The first term is the broadcast cut (maximum rate at which information can flow from $\{$ source, relay $\}$ to destination). The second term is the cooperation cut (maximum rate at which information can flow from the source to $\{$ relay, destination $\}$ ).

The cut-set bound captures two bottlenecks: (1) the source must convey information to the relay (limited by $I(X_1; Y_R | X_2)$ which appears in the cooperation cut), and (2) both source and relay must convey information to the destination (limited by $I(X_1, X_2; Y)$ ). The capacity cannot exceed either bottleneck.

Proof

Information flow across cuts

Consider any partition of the three terminals into two sets $(\mathcal{S}, \mathcal{S}^c)$ where the source is in $\mathcal{S}$ and the destination is in $\mathcal{S}^c$ .

There are two non-trivial cuts:

Cut 1: $\mathcal{S} = \{S, R\}$ , $\mathcal{S}^c = \{D\}$ : $nR \leq I(X_1^n, X_2^n; Y^n) + n\epsilon_n$
Cut 2: $\mathcal{S} = \{S\}$ , $\mathcal{S}^c = \{R, D\}$ : $nR \leq I(X_1^n; Y^n, Y_R^n | X_2^n) + n\epsilon_n$

Single-letterisation

By the memoryless property and the chain rule: $I(X_1^n, X_2^n; Y^n) \leq \sum_{i=1}^n I(X_{1,i}, X_{2,i}; Y_i)$

The maximum over joint distributions $p(x_1, x_2)$ gives: $C \leq \max_{p(x_1, x_2)} \min\{I(X_1, X_2; Y), I(X_1; Y, Y_R | X_2)\}$

For the Gaussian case, the optimal $p(x_1, x_2)$ is jointly Gaussian with correlation $\rho$ (coherent transmission). $\blacksquare$

,

Theorem: Decode-Forward Lower Bound

The decode-forward (DF) strategy achieves:

$R_{\mathrm{DF}} = \max_{0 \leq \rho \leq 1} \min\left\{ \frac{1}{2}\log_2\!\left(1 + (1-\rho^2) g_{SR}^2 P_1\right), \; \frac{1}{2}\log_2\!\left(1 + g_{SD}^2 P_1 + g_{RD}^2 P_2 + 2\rho g_{SD} g_{RD} \sqrt{P_1 P_2}\right) \right\}$

where $\rho$ is the correlation between the source and relay signals (coherent combining).

Protocol:

The source encodes message $W$ using block Markov encoding across $B$ blocks of length $n$ .
In block $b$ , the source sends new information at rate $R$ plus a known cooperation signal correlated with the relay.
The relay fully decodes the source's message from block $b$ and re-encodes it in block $b+1$ .
The destination uses backward decoding across all $B$ blocks.

DF matches the cut-set bound when the source-relay link is sufficiently strong ( $g_{SR}^2 P_1 \gg g_{SD}^2 P_1$ ).

Decode-forward is optimal when the relay is close to the source (strong source-relay link): the relay can decode the source's message perfectly and then cooperate with the source to create a virtual MIMO system to the destination. The parameter $\rho$ controls how much the source and relay signals are correlated (higher $\rho$ = more beamforming gain, less independent information).

Proof

Block Markov encoding

Divide the total $nB$ channel uses into $B$ blocks of $n$ . In block $b$ , the source transmits $\mathbf{x}_1(w_b, w_{b-1})$ — encoding the new message $w_b$ along with the previous message $w_{b-1}$ (for cooperation).

The relay, having decoded $w_{b-1}$ in the previous block, transmits $\mathbf{x}_2(w_{b-1})$ — a codeword correlated with the source's cooperation component.

Relay decoding and rates

The relay decodes $w_b$ from $Y_R^n$ in block $b$ by treating the cooperation signal as known side information. Reliable if: $R < \frac{1}{2}\log_2(1 + (1-\rho^2) g_{SR}^2 P_1)$ .

The destination uses backward decoding: knowing $w_B$ , decode $w_{B-1}$ from block $B$ using $(Y^n, \mathbf{x}_2(w_{B-1}))$ , and so on. Reliable if: $R < \frac{1}{2}\log_2(1 + g_{SD}^2 P_1 + g_{RD}^2 P_2 + 2\rho g_{SD} g_{RD}\sqrt{P_1 P_2})$ .

Taking the minimum gives the DF rate. $\blacksquare$

,

Definition:
Compress-Forward Strategy

Compress-forward (CF) is an alternative relay strategy where the relay does not decode the source's message but instead quantises (compresses) its received signal $Y_R$ and forwards the compressed version $\hat{Y}_R$ to the destination:

$R_{\mathrm{CF}} = \frac{1}{2}\log_2\!\left(1 + g_{SD}^2 P_1 + \frac{g_{SR}^2 P_1}{1 + \sigma_Q^2}\right)$

where $\sigma_Q^2$ is the quantisation noise variance, chosen to satisfy the relay-destination link capacity:

$\frac{1}{2}\log_2\!\left(\frac{1 + g_{SR}^2 P_1}{\sigma_Q^2}\right) \leq \frac{1}{2}\log_2(1 + g_{RD}^2 P_2)$

CF is optimal when the relay-destination link is strong but the source-relay link is weak (the relay cannot decode, but its observation provides useful side information).

CF and DF are complementary strategies: DF excels when the source-relay link is strong (close relay), while CF excels when the relay-destination link is strong (close to destination). The capacity of the Gaussian relay channel lies between DF and CF rates for most parameter values, but neither is always optimal.

,

Definition:
Noisy Network Coding

Noisy network coding (NNC) (Lim, Kim, El Gamal, Chung, 2011) generalises compress-forward to arbitrary multi-relay networks:

Each relay $k$ quantises its received signal and maps the quantised version to a channel input using a random hash. The destination jointly decodes the source message and all quantised relay signals simultaneously.

Key properties:

Achieves the cut-set bound to within a constant gap ( $\log(|V|)$ bits per cut, where $|V|$ is the number of nodes) for Gaussian networks.
Does not require relays to decode — each relay simply compress-and-forwards.
Subsumes CF for the single-relay channel.
Extended to the diamond network (source $\to$ $K$ relays $\to$ destination, no direct link), achieving rates within $O(\log K)$ of the cut-set bound.

The NNC rate for the single-relay channel is: $R_{\mathrm{NNC}} = \max_{\hat{Y}_R} \min\{I(X_1; Y, \hat{Y}_R | X_2) - I(Y_R; \hat{Y}_R | X_1, X_2, Y), \; I(X_1, X_2; Y)\}$

Noisy network coding is one of the most general and powerful achievability tools in network information theory. It unifies many previously separate results (CF, quantize-map-forward) and provides constant-gap capacity approximations for large classes of networks.

Definition:
Diamond Network

The diamond network is a two-hop relay network with $K$ relays and no direct source-destination link:

$Y_{R_k} = g_{SR_k} X + Z_{R_k}, \quad k = 1, \ldots, K$ $Y = \sum_{k=1}^K g_{R_kD} X_{R_k} + Z$

Each relay $k$ observes a noisy version of the source signal and transmits to the destination under power constraint $P_k$ .

Cut-set bound: $C \leq \min\{C_{\mathrm{MAC}}, C_{\mathrm{BC}}\}$ where $C_{\mathrm{MAC}}$ is the MAC capacity from relays to destination and $C_{\mathrm{BC}}$ is the total rate at which the source can convey information to all relays.

For $K$ symmetric relays with equal gains, the capacity scales as $\Theta(\log K)$ : each additional relay provides a beamforming gain that increases the rate logarithmically.

The diamond network is the simplest multi-relay topology and serves as a testbed for network coding strategies. The gap between DF, CF, NNC, and the cut-set bound has been extensively studied for this topology.

Example: Comparing DF and CF for the Gaussian Relay Channel

A relay channel has $g_{SD} = 1$ , $g_{RD} = 2$ , $P_1 = P_2 = 10$ . Compare the rates for:

(a) Direct transmission (no relay). (b) Decode-forward with $g_{SR} = 3$ (relay near source). (c) Compress-forward with $g_{SR} = 0.5$ (relay near destination). (d) Cut-set bound for each case.

Solution

Direct transmission

(a) $R_{\mathrm{direct}} = \frac{1}{2}\log_2(1 + 10) = 1.73$ bits/c.u.

Decode-forward

(b) $g_{SR} = 3$ , $\text{SNR}_{R} = 9 \times 10 = 90$ . Optimising $\rho$ : $R_{\mathrm{DF}} = \min\{\frac{1}{2}\log_2(1 + (1-\rho^2) \cdot 90), \; \frac{1}{2}\log_2(1 + 10 + 40 + 2\rho\sqrt{10 \cdot 40})\}$ .

At $\rho = 0.5$ : $\min\{3.06, 3.14\} = 3.06$ bits. At $\rho = 0.6$ : $\min\{2.84, 3.25\} = 2.84$ bits. Optimal $\rho^* \approx 0.45$ : $R_{\mathrm{DF}} \approx 3.10$ bits.

DF gain over direct: $3.10 / 1.73 = 1.79\times$ .

Compress-forward

(c) $g_{SR} = 0.5$ , $\text{SNR}_{R} = 0.25 \times 10 = 2.5$ . Relay-to-destination: $C_{RD} = \frac{1}{2}\log_2(1 + 40) = 2.70$ bits. Quantisation: $\sigma_Q^2 = (1 + 2.5)/2^{2 \times 2.70} - 1 \approx 0.079$ .

$R_{\mathrm{CF}} = \frac{1}{2}\log_2(1 + 10 + 2.5/1.079) = \frac{1}{2}\log_2(13.32) = 1.87$ bits.

Modest improvement over direct (relay too far from source).

Cut-set bounds

(d) Case (b): $C_{\mathrm{cut}} = \min\{3.42, 3.32\} = 3.32$ bits. DF achieves $3.10/3.32 = 93$ % of the cut-set bound.

Case (c): $C_{\mathrm{cut}} = \min\{3.42, 1.95\} = 1.95$ bits. CF achieves $1.87/1.95 = 96$ % of the cut-set bound.

Both strategies are near-optimal in their respective regimes. $\blacksquare$

Quick Check

Under what condition does decode-forward (DF) match the cut-set upper bound for the Gaussian relay channel?

When the relay-to-destination link is very strong

When the source-to-relay link is very strong (relay close to source)

When the direct source-to-destination link is very weak

DF never matches the cut-set bound

Correction:

When the source-to-relay link is very strong (relay close to source)

When the source-to-relay link is strong ( $g_{SR}^2 P_1 \to \infty$ ), the relay can decode the source's message perfectly, and the cooperation cut $I(X_1; Y_R | X_2) \to \infty$ becomes non-binding. The DF rate then equals the broadcast cut $I(X_1, X_2; Y)$ , which matches the cut-set bound. The relay effectively acts as a second transmit antenna, forming a virtual MISO system to the destination.

Cut-Set Bound

An upper bound on the capacity of any relay network, obtained by considering all possible partitions of the network nodes into two sets and bounding the information flow across each cut. Tight for some channels (degraded relay) but not in general.

Decode-Forward (DF)

A relay strategy where the relay fully decodes the source's message and re-encodes it for the destination. Uses block Markov encoding for cooperation. Optimal when the source-relay link is strong.

Compress-Forward (CF)

A relay strategy where the relay quantises its received signal and forwards the compressed version to the destination without decoding the source's message. Optimal when the relay-destination link is strong but the source-relay link is weak.

Relay and Diamond Networks