46.06.03 · information-theory / network-information

Relay Channel: Decode-and-Forward, Compress-and-Forward, and the Cut-Set Bound

shipped3 tiersLean: none

Anchor (Master): Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.7; Cover & El Gamal 1979 Capacity theorems for the relay channel; El Gamal & Kim 2011 Network Information Theory Ch. 9; Gupta & Kumar 2000 The capacity of wireless networks

Intuition Beginner

A radio tower in a valley wants to reach a receiver behind a mountain. The signal cannot go directly — the mountain blocks it. But there is a relay station on the mountain ridge that can hear the tower and retransmit the signal to the receiver behind the mountain.

How much can the relay help? The answer depends on what the relay does with its received signal.

The simplest strategy is decode-and-forward: the relay decodes the full message and re-encodes it for the destination. This works well when the relay has a good channel from the source. The bottleneck is the source-to-relay link: if the relay cannot decode, this strategy fails.

A more robust strategy is compress-and-forward: the relay does not try to decode the message. Instead, it compresses its noisy observation and sends the compressed version to the destination. The destination uses both its own direct observation and the compressed relay observation to decode. This works even when the relay cannot decode, as long as the relay-to-destination link can carry the compressed observation.

The ultimate performance is bounded by the cut-set bound: imagine cutting the network into two halves (source on one side, destination on the other). The information flow across the cut cannot exceed the capacity of the channels crossing it. The minimum cut gives the tightest bound, and for some relay channels, decode-and-forward achieves this bound.

The relay channel combines a broadcast sub-problem (source transmits to both relay and destination) with a MAC sub-problem (source and relay transmit to destination). The capacity is known only for special cases but remains open in general.

Visual Beginner

Figure: a relay network diagram. Source node (S) transmits $X_{1}$ . Relay node (R) receives $Y_{2}$ and transmits $X_{2}$ . Destination node (D) receives $Y_{3}$ . The direct link S-to-D and the relay link S-to-R-to-D are shown.

Strategy	Relay action	Bottleneck	Advantage
Decode-and-forward	Full decode, re-encode	Source-to-relay link	Cooperates perfectly with source
Compress-and-forward	Compress observation, forward	Relay-to-destination link	Works even if relay cannot decode
Cut-set bound	N/A (upper bound)	Minimum cut	Tight for degraded relay

Worked example Beginner

A Gaussian relay channel: source transmits $X_{1}$ with power $P_{1} = 10$ . Relay receives $Y_{2} = X_{1} + Z_{2}$ where $Z_{2} \sim N (0, 1)$ . Relay transmits $X_{2}$ with power $P_{2} = 5$ . Destination receives $Y_{3} = X_{1} + X_{2} + Z_{3}$ where $Z_{3} \sim N (0, 1)$ .

Direct channel (no relay): capacity $= \frac{1}{2} lo g (1 + 10/1) \approx 1.73$ bits/use.

With relay (decode-and-forward): the relay decodes the message (requires $R \leq \frac{1}{2} lo g (1 + P_{1} / N_{2}) = \frac{1}{2} lo g (1 + 10/1) \approx 1.73$ bits/use). Then relay and source cooperate: the MAC from $(X_{1}, X_{2})$ to $Y_{3}$ has sum-rate $\frac{1}{2} lo g (1 + (P_{1} + P_{2}) / N_{3}) = \frac{1}{2} lo g (1 + 15) \approx 1.99$ bits/use.

The decode-and-forward rate is $min (1.73, 1.99) = 1.73$ bits/use — the source-to-relay link is the bottleneck, and the relay does not help in this specific configuration because the direct link is already at the relay decode limit.

With a weaker direct link (say $Y_{3} = 0.5 X_{1} + X_{2} + Z_{3}$ ), the relay would provide significant gain.

Check your understanding Beginner

Formal definition Intermediate+

A three-node relay channel has source input $X_{1}$ , relay input $X_{2}$ , relay output $Y_{2}$ , and destination output $Y_{3}$ , with transition probabilities $p (y_{2}, y_{3} ∣ x_{1}, x_{2})$ .

Definition (Relay code). A $(2^{n R}, n)$ relay code consists of encoding functions at the source $f_{i} : {1, \dots, 2^{n R}} \to X_{1, i}$ and relay encoding functions $x_{2, i} = f_{r, i} (y_{2, 1}, \dots, y_{2, i - 1})$ , plus a decoder $g : Y_{3}^{n} \to {1, \dots, 2^{n R}}$ .

Definition (Cut-set bound). The cut-set upper bound on the capacity of the relay channel is:

C \leq p (x_{1}, x_{2}) max min (I (X_{1}; Y_{2}, Y_{3} ∣ X_{2}), I (X_{1}, X_{2}; Y_{3})) .

The first term is the broadcast cut (source to relay-and-destination). The second is the MAC cut (source-and-relay to destination).

Key theorem with proof Intermediate+

Theorem (Cover-El Gamal 1979). The decode-and-forward achievable rate is:

R_{D F} = p (x_{1}) p (x_{2}) max min (I (X_{1}; Y_{2} ∣ X_{2}), I (X_{1}, X_{2}; Y_{3})) .

The compress-and-forward achievable rate is:

R_{C F} = p (x_{1}) p (\overset{y}{^}_{2} ∣ y_{2}) p (x_{2}) max min (I (X_{1}; \hat{Y}_{2}, Y_{3} ∣ X_{2}), I (X_{1}, X_{2}; Y_{3}) - I (Y_{2}; \hat{Y}_{2} ∣ X_{1}, X_{2}, Y_{3})) .

Proof sketch (decode-and-forward). The relay uses $B$ blocks of length $n$ . In block $b$ , the source sends message $w_{b}$ . The relay, having decoded $w_{b - 1}$ in the previous block, sends a codeword $X_{2}^{n} (w_{b - 1})$ that helps the destination decode $w_{b - 1}$ .

Broadcast cut: The relay decodes $w_{b}$ from $(Y_{2}^{n}, X_{2}^{n} (w_{b - 1}))$ . This succeeds if $R < I (X_{1}; Y_{2} ∣ X_{2})$ .

MAC cut: The destination decodes $(w_{b - 1}, w_{b})$ from $(Y_{3}^{n}, X_{2}^{n} (w_{b - 1}))$ . The sum-rate constraint gives $R < I (X_{1}, X_{2}; Y_{3})$ .

The achievable rate is the minimum of these two constraints. $□$

Bridge. The relay channel builds toward all multi-hop network models by combining the broadcast channel 46.06.02 (source to relay-and-destination) with the MAC 46.06.01 (source-and-relay to destination). This is exactly the structure that makes the cut-set bound a natural outer bound: any cut of the network separates source from destination, and the capacity across the cut bounds the end-to-end rate. The result appears again in the interference channel 46.06.04 where relay-like cooperation between transmitters can improve performance. The foundational reason the relay channel capacity remains open is that decode-and-forward and compress-and-forward optimize different aspects: DF maximizes cooperation at the cost of requiring the relay to decode, while CF maximizes information flow at the cost of quantization noise. Neither dominates the other, and no single strategy achieves the cut-set bound for all channels. Putting these together, the relay channel is the simplest multi-hop network and the central insight is that cooperation (DF) and compression (CF) represent two fundamental modes of relaying that cannot be unified into a single optimal strategy for the general case.

Exercises Intermediate+

Exercise (medium, short answer).

Derive the cut-set bound for the relay channel. Why are there two terms?

Hint

Consider two cuts: one separating the source from everything else, and one separating source-plus-relay from the destination.

Answer

The cut-set bound considers all ways to partition the network into $S$ (containing the source) and $S^{c}$ (containing the destination).

Cut 1: $S = {source}$ , $S^{c} = {relay, destination}$ . The capacity across this cut is the maximum rate the source can communicate to the relay and destination jointly: $I (X_{1}; Y_{2}, Y_{3} ∣ X_{2})$ (conditioning on the relay's input since it is in $S^{c}$ ).

Cut 2: $S = {source, relay}$ , $S^{c} = {destination}$ . The capacity across this cut is the MAC from source-and-relay to destination: $I (X_{1}, X_{2}; Y_{3})$ .

The cut-set bound is the minimum of these two cuts, optimized over the input distribution. The minimum arises because the information flow is limited by the tightest bottleneck.

Exercise (medium, short answer).

Explain the compress-and-forward strategy. What is the role of Wyner-Ziv coding?

Hint

The relay compresses its observation. The destination uses this as side information.

Answer

In compress-and-forward, the relay does not decode the message. Instead, it compresses its observation $Y_{2}^{n}$ into a quantized version $\hat{Y}_{2}^{n}$ using Wyner-Ziv coding. The compression rate is $I (Y_{2}; \hat{Y}_{2} ∣ X_{1}, X_{2}, Y_{3})$ — the conditional rate-distortion function given that the destination has its own observation $Y_{3}^{n}$ as side information. The relay forwards the compressed index to the destination. The destination uses both $Y_{3}^{n}$ (direct observation) and $\hat{Y}_{2}^{n}$ (compressed relay observation) to decode the source message. The achievable rate is $I (X_{1}; \hat{Y}_{2}, Y_{3} ∣ X_{2})$ subject to the relay forwarding constraint $I (Y_{2}; \hat{Y}_{2} ∣ X_{1}, X_{2}, Y_{3}) \leq I (X_{2}; Y_{3} ∣ X_{1})$ .

Exercise (medium, short answer).

Show that for the degraded relay channel ( $Y_{3}$ is a degraded version of $Y_{2}$ ), decode-and-forward achieves the cut-set bound.

Hint

In the degraded case, the relay is stronger than the destination. The broadcast cut equals the MAC cut.

Answer

For the degraded relay channel $X_{1}, X_{2} \to Y_{2} \to Y_{3}$ , the relay sees a less noisy version of the signal than the destination. The broadcast cut is $I (X_{1}; Y_{2} ∣ X_{2})$ and the MAC cut is $I (X_{1}, X_{2}; Y_{3})$ . Since $Y_{3}$ is a degraded version of $Y_{2}$ , the data-processing inequality gives $I (X_{1}; Y_{2} ∣ X_{2}) \geq I (X_{1}; Y_{3} ∣ X_{2})$ . For the degraded relay channel, Cover and El Gamal showed that the broadcast cut is the binding constraint, and decode-and-forward achieves it: the relay decodes (it has a better channel), then cooperates with the source to achieve the MAC cut. The resulting rate $min (I (X_{1}; Y_{2} ∣ X_{2}), I (X_{1}, X_{2}; Y_{3}))$ equals the cut-set bound.

Exercise (hard, short answer).

Prove the cut-set upper bound for the relay channel.

Hint

Use Fano's inequality and the max-flow min-cut argument.

Answer

By Fano's inequality, $n R \leq I (W; Y_{3}^{n}) + n ϵ_{n}$ where $W$ is the message. By the data-processing inequality, the information flow from source to destination is bounded by the capacity of any cut separating them.

Cut ${1} ∣ {2, 3}$ : $n R \leq I (X_{1}^{n}; Y_{2}^{n}, Y_{3}^{n} ∣ X_{2}^{n}) + n ϵ_{n}$ . By the memoryless channel: $\leq \sum_{i} I (X_{1, i}; Y_{2, i}, Y_{3, i} ∣ X_{2, i}) + n ϵ_{n}$ , giving $R \leq I (X_{1}; Y_{2}, Y_{3} ∣ X_{2})$ .

Cut ${1, 2} ∣ {3}$ : $n R \leq I (X_{1}^{n}, X_{2}^{n}; Y_{3}^{n}) + n ϵ_{n}$ . By the memoryless property: $\leq \sum_{i} I (X_{1, i}, X_{2, i}; Y_{3, i}) + n ϵ_{n}$ , giving $R \leq I (X_{1}, X_{2}; Y_{3})$ .

The cut-set bound is $C \leq max_{p (x_{1}, x_{2})} min (I (X_{1}; Y_{2}, Y_{3} ∣ X_{2}), I (X_{1}, X_{2}; Y_{3}))$ .

Exercise (hard, short answer).

For the Gaussian relay channel, find the optimal power split between source and relay that maximizes the decode-and-forward rate.

Hint

Maximize $min (\frac{1}{2} lo g (1 + P_{1} / N_{2}), \frac{1}{2} lo g (1 + (P_{1} + P_{2} + 2 P_{1} P_{2}) / N_{3}))$ with coherent combining.

Answer

For the Gaussian relay channel with coherent combining at the destination, the source and relay can cooperate (since the relay knows the message after decoding). The broadcast cut gives $R \leq \frac{1}{2} lo g (1 + P_{1} / N_{2})$ . The MAC cut with full cooperation gives $R \leq \frac{1}{2} lo g (1 + (P_{1} + P_{2})^{2} / N_{3}) = \frac{1}{2} lo g (1 + (P_{1} + P_{2} + 2 P_{1} P_{2}) / N_{3})$ .

The DF rate is the minimum of these two. The optimal strategy is to allocate power so that both cuts are equal: $\frac{1}{2} lo g (1 + P_{1} / N_{2}) = \frac{1}{2} lo g (1 + (P_{1} + P_{2} + 2 P_{1} P_{2}) / N_{3})$ , i.e., $P_{1} / N_{2} = (P_{1} + P_{2} + 2 P_{1} P_{2}) / N_{3}$ . If $N_{2} < N_{3}$ (relay is closer to source), the broadcast cut is larger and the MAC cut binds, meaning cooperation at the destination is the bottleneck. If $N_{2} > N_{3}$ , the relay cannot decode and DF fails.

Exercise (hard, short answer).

Describe noisy network coding (Lim, Kim, El Gamal, Chung 2011) as a generalization of compress-and-forward for relay networks.

Hint

Noisy network coding applies CF simultaneously at all relays and uses simultaneous nonunique decoding at the destination.

Answer

Noisy network coding generalizes CF to arbitrary relay networks by having each relay independently compress its observation (using Wyner-Ziv-like quantization) and broadcast the compressed index. The destination performs simultaneous nonunique decoding: it searches for a message and a set of relay compression indices that are consistent with all received signals. The achievable rate is $R \leq min_{cuts} [I (X_{S}; \hat{Y}_{S^{c}}, Y_{d} ∣ X_{S^{c}}) - I (Y_{S}; \hat{Y}_{S} ∣ X_{N}, Y_{d})]$ where the minimum is over all cuts and the compression noise is controlled by the quantization. This achieves rates within a constant gap of the cut-set bound for Gaussian networks, regardless of network size.

Lean formalization Intermediate+

Mathlib does not define relay channels, decode-and-forward, compress-and-forward, or cut-set bounds. The relay channel combines MAC and broadcast sub-channels, requiring a multi-user code structure. The cut-set bound involves max-flow min-cut arguments over network graphs. DF requires sequential block coding with relay decoding. CF requires Wyner-Ziv compression at the relay. None of this is formalized. This unit ships without formalization.

Advanced results Master

The partial decode-and-forward strategy

A generalization of decode-and-forward is partial decode-and-forward, where the relay decodes only part of the message. The source splits its message into two parts: $W_{1}$ (decoded by the relay) and $W_{2}$ (not decoded by the relay). The achievable rate is:

R_{P D F} = max [min (I (X_{1}; Y_{2} ∣ U, X_{2}) + I (U; Y_{3} ∣ X_{2}), I (X_{1}, X_{2}; Y_{3}))],

where $U$ is an auxiliary variable carrying the relay-decoded part. This interpolates between DF ( $U = X_{1}$ , full decode) and direct transmission ( $U = \emptyset$ , no decode).

Noisy network coding

Noisy network coding (Lim, Kim, El Gamal, Chung 2011) is a powerful generalization of compress-and-forward to arbitrary networks. Each relay independently compresses its observation and forwards the compressed bits. The destination uses simultaneous nonunique decoding. The key advantage: no coordination between relays is needed, and the scheme achieves rates within a constant gap of the cut-set bound for Gaussian networks.

The Gaussian relay channel: within a constant gap

For the Gaussian relay channel, the gap between the best known inner bound (partial DF or CF) and the cut-set outer bound is at most 0.5 bits, regardless of the channel parameters. This "constant gap" result means that while the exact capacity is unknown, the achievable strategies are within a fixed number of bits of optimal.

Synthesis. The relay channel is the simplest multi-hop network, combining the broadcast channel 46.06.02 (source to relay-and-destination) with the MAC 46.06.01 (source-and-relay to destination). The central insight is that relay cooperation can be achieved through two fundamental modes: decode-and-forward (cooperation through full decoding and re-encoding) and compress-and-forward (cooperation through Wyner-Ziv compression of the relay observation). Neither strategy dominates the other, and the foundational reason the general capacity remains open is that these two modes cannot be combined into a single strategy that achieves the cut-set bound for all relay channels. The result builds toward the interference channel 46.06.04 where relay-like cooperation strategies appear, and noisy network coding extends CF to arbitrary networks with constant-gap optimality guarantees. Putting these together, the relay channel is the prototype for cooperative communication, and the interplay between DF and CF illustrates the fundamental trade-off between decoding accuracy and information preservation in relay networks.

Full proof set Master

Proposition (Cut-set bound). For the relay channel $p (y_{2}, y_{3} ∣ x_{1}, x_{2})$ , the capacity satisfies:

C \leq p (x_{1}, x_{2}) max min (I (X_{1}; Y_{2}, Y_{3} ∣ X_{2}), I (X_{1}, X_{2}; Y_{3})) .

Proof. By Fano's inequality, $H (W ∣ Y_{3}^{n}) \leq n ϵ_{n}$ . Consider two cuts:

Cut ${1} ∣ {2, 3}$ : $I (W; Y_{2}^{n}, Y_{3}^{n} ∣ X_{2}^{n}) \geq H (W) - H (W ∣ Y_{2}^{n}, Y_{3}^{n}) \geq n R - n ϵ_{n}$ . Since $X_{2}^{n}$ depends on $Y_{2}^{n}$ (causal relay), and $W \to X_{1}^{n} \to (Y_{2}^{n}, Y_{3}^{n})$ : $I (W; Y_{2}^{n}, Y_{3}^{n} ∣ X_{2}^{n}) \leq I (X_{1}^{n}; Y_{2}^{n}, Y_{3}^{n} ∣ X_{2}^{n}) = \sum_{i} I (X_{1, i}; Y_{2, i}, Y_{3, i} ∣ X_{2, i})$ by the memoryless property. Single-letterize: $R \leq I (X_{1}; Y_{2}, Y_{3} ∣ X_{2})$ .

Cut ${1, 2} ∣ {3}$ : $I (W; Y_{3}^{n}) \leq I (X_{1}^{n}, X_{2}^{n}; Y_{3}^{n}) = \sum_{i} I (X_{1, i}, X_{2, i}; Y_{3, i})$ . Single-letterize: $R \leq I (X_{1}, X_{2}; Y_{3})$ .

The capacity is bounded by the minimum over all cuts, maximized over the input distribution. $□$

Connections Master

46.06.01 — The MAC capacity region provides the ${1, 2} ∣ {3}$ cut of the relay channel: source-and-relay cooperate as a two-user MAC to the destination.
46.06.02 — The broadcast capacity region provides the ${1} ∣ {2, 3}$ cut: the source broadcasts to relay and destination simultaneously.
46.03.01 — Point-to-point capacity is the relay channel without a relay ( $P_{2} = 0$ ); the cut-set bound reduces to $I (X_{1}; Y_{3})$ .
46.05.02 — Compress-and-forward uses Wyner-Ziv coding at the relay: the relay compresses its observation with the destination's signal as decoder side information.
46.06.04 — The interference channel can be analyzed as two relay channels, where each transmitter acts as a relay for the other's message.

Historical & philosophical context Master

Cover and El Gamal established the foundations of the relay channel in "Capacity Theorems for the Relay Channel" (IEEE Trans. IT-25, 1979, 572-584). The paper introduced decode-and-forward, compress-and-forward, and the cut-set bound, and proved that the cut-set bound is tight for the degraded relay channel. The paper remains one of the most cited in information theory.

The Gaussian relay channel was studied extensively in the 2000s, driven by the practical importance of relay networks in wireless communication. Gupta and Kumar's 2000 paper "The Capacity of Wireless Networks" (IEEE Trans. IT-46) showed that relay-based architectures can achieve significant scaling gains in large networks.

Noisy network coding, introduced by Lim, Kim, El Gamal, and Chung in 2011 ("Noisy Network Coding," IEEE Trans. IT-57), unified and generalized compress-and-forward to arbitrary networks, achieving constant-gap optimality.

Despite decades of effort, the general relay channel capacity remains one of the most important open problems in network information theory. The gap between the best known inner bound (partial DF combined with CF) and the cut-set outer bound is at most 0.5 bits for Gaussian channels, but whether this gap can be closed is unknown.

Bibliography Master

@article{cover-elgamal1979,
  author  = {Cover, T. M. and El Gamal, A. A.},
  title   = {Capacity Theorems for the Relay Channel},
  journal = {IEEE Transactions on Information Theory},
  volume  = {IT-25},
  pages   = {572--584},
  year    = {1979},
}
@article{gupta-kumar2000,
  author  = {Gupta, P. and Kumar, P. R.},
  title   = {The Capacity of Wireless Networks},
  journal = {IEEE Transactions on Information Theory},
  volume  = {IT-46},
  pages   = {388--404},
  year    = {2000},
}
@article{lim-kim-elgamal-chung2011,
  author  = {Lim, S. H. and Kim, Y.-H. and El Gamal, A. and Chung, S.-Y.},
  title   = {Noisy Network Coding},
  journal = {IEEE Transactions on Information Theory},
  volume  = {57},
  pages   = {3132--3152},
  year    = {2011},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@book{elgamal-kim2011,
  author    = {El Gamal, A. and Kim, Y.-H.},
  title     = {Network Information Theory},
  publisher = {Cambridge University Press},
  year      = {2011},
}

Prerequisites

46.06.01
46.03.01

Tier anchors

beginner: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.7 (a relay node helps the source reach the destination, decode-and-forward and compress-and-forward strategies)
intermediate: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.7 (the relay channel model, cut-set outer bound, decode-and-forward achievability, compress-and-forward achievability)
master: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.7; Cover & El Gamal 1979 Capacity theorems for the relay channel; El Gamal & Kim 2011 Network Information Theory Ch. 9; Gupta & Kumar 2000 The capacity of wireless networks

References

Cover, T. M. & El Gamal, A. A. — Capacity Theorems for the Relay Channel · IEEE Transactions on Information Theory IT-25(5) (1979) 572-584; the foundational paper on the relay channel, establishing the cut-set upper bound, the decode-and-forward achievable rate $R \leq min (I (X_{1}; Y_{2} ∣ X_{2}), I (X_{1}, X_{2}; Y_{3}))$ , the compress-and-forward achievable rate using Wyner-Ziv binning at the relay, and showing that the cut-set bound is tight for the degraded relay channel. The paper introduced both main strategies that remain the building blocks for all relay network analysis.
Cover, T. M. & Thomas, J. A. — Elements of Information Theory (2nd ed.) · Wiley (2006). Section 15.7: the relay channel model with source $X_{1}$ , relay input $X_{2}$ , relay output $Y_{2}$ , and destination output $Y_{3}$ . The cut-set bound: $C \leq max_{p (x_{1}, x_{2})} min (I (X_{1}; Y_{2}, Y_{3} ∣ X_{2}), I (X_{1}, X_{2}; Y_{3}))$ . Decode-and-forward: the relay fully decodes the message and re-encodes. Compress-and-forward: the relay compresses its observation and forwards the compressed version.
El Gamal, A. & Kim, Y.-H. — Network Information Theory · Cambridge University Press (2011). Chapter 9: comprehensive treatment of the relay channel, including the partial decode-and-forward, hash-and-forward, and noisy network coding strategies that generalize Cover-El Gamal. The chapter establishes that the capacity is unknown for the general relay channel but known for several special cases (degraded, reversely degraded, deterministic, semideterministic).

Estimated time

beginner: 20m
intermediate: 50m
master: 100m