Ferkans — Interactive Telecom Tutor

Why Cut-Set Bounds?

Before we develop coding strategies for the relay channel, we need an upper bound on capacity — a benchmark against which to measure our achievable rates. The cut-set bound is the most powerful general upper bound in network information theory. The idea is beautifully simple: any information flow from source to destination must cross every "cut" that separates them, and the flow across each cut is limited by the mutual information across that cut.

For the relay channel, there are exactly two non-trivial cuts, and the capacity cannot exceed the minimum of the two. The remarkable fact is that for certain channel models (the degraded relay channel), this bound is tight — achieved by decode-and-forward.

Theorem: Cut-Set Bound for the Relay Channel

For the discrete memoryless relay channel $p(y, y_r | x, x_r)$ , the capacity satisfies $C \leq \max_{p(x, x_r)} \min\bigl\{I(X, X_r; Y),\; I(X; Y, Y_r \mid X_r)\bigr\}.$

The two terms correspond to:

Broadcast cut: $\{S\} \to \{R, D\}$ . The source and relay cooperate to send to the destination, giving $I(X, X_r; Y)$ .
Multiple-access cut: $\{S, R\} \setminus \{R\} \to \{D\}$ . The source sends to both relay and destination, with relay input $X_r$ as known side information at the destination, giving $I(X; Y, Y_r \mid X_r)$ .

Think of it as two bottlenecks. The broadcast cut limits how fast the source can "broadcast" to the relay-destination pair. The multiple-access cut limits how fast the source can communicate to the destination even when the destination has the relay's observation as side information. The capacity cannot exceed either bottleneck, so it is bounded by the minimum.

Proof

Setup and Fano's inequality

Suppose $W$ is uniform on $\{1, \ldots, 2^{nR}\}$ and is decoded with vanishing error probability. By Fano's inequality: $nR \leq I(W; Y^n) + n\epsilon_n$ where $\epsilon_n \to 0$ .

Broadcast cut

We bound $I(W; Y^n)$ by treating source and relay as a single "super-transmitter": $I(W; Y^n) \leq I(X^n, X_r^n; Y^n) = \sum_{i=1}^n I(X_i, X_{r,i}; Y_i \mid Y^{i-1}).$ Since the channel is memoryless, $Y_i$ depends on $(X_i, X_{r,i})$ only, and conditioning reduces entropy: $\leq \sum_{i=1}^n I(X_i, X_{r,i}; Y_i).$

Multiple-access cut

We write $I(W; Y^n)$ as: $I(W; Y^n) = I(W; Y^n, Y_r^n) - I(W; Y_r^n \mid Y^n)$ $\leq I(W; Y^n, Y_r^n) = I(X^n; Y^n, Y_r^n \mid X_r^n)$ where the last step uses the fact that $W \to X^n \to (Y^n, Y_r^n, X_r^n)$ and that $X_r^n$ is a function of $Y_r^{n-1}$ (strictly causal). Expanding: $= \sum_{i=1}^n I(X_i; Y_i, Y_{r,i} \mid X_{r,i}, Y^{i-1}, Y_r^{i-1}).$ By memorylessness and the fact that conditioning reduces mutual information: $\leq \sum_{i=1}^n I(X_i; Y_i, Y_{r,i} \mid X_{r,i}).$

Combining via time-sharing

Taking the minimum of the two bounds and introducing a time-sharing random variable $Q$ uniform on $\{1, \ldots, n\}$ : $R \leq \min\bigl\{I(X_Q, X_{r,Q}; Y_Q \mid Q),\; I(X_Q; Y_Q, Y_{r,Q} \mid X_{r,Q}, Q)\bigr\} + \epsilon_n.$ Maximizing over all input distributions $p(x, x_r)$ and letting $n \to \infty$ yields the cut-set bound.

,

Example: Cut-Set Bound for the Degraded Relay Channel

Consider a degraded relay channel where $X \to (Y_r, X_r) \to Y$ , i.e., the destination's observation is a degraded version of the relay's. Show that the cut-set bound simplifies and that the broadcast cut is always the binding constraint.

Solution

Simplify the multiple-access cut

Since $X \to (Y_r, X_r) \to Y$ forms a Markov chain, we have $I(X; Y, Y_r \mid X_r) = I(X; Y_r \mid X_r) + I(X; Y \mid Y_r, X_r)$ . But $I(X; Y \mid Y_r, X_r) = 0$ by the Markov chain, so the multiple-access cut becomes $I(X; Y_r \mid X_r)$ .

Compare the two cuts

The broadcast cut is $I(X, X_r; Y)$ . For the degraded channel, this is at most $I(X, X_r; Y_r)$ (by data processing), which equals $I(X_r; Y_r) + I(X; Y_r \mid X_r)$ . Since $I(X_r; Y_r) \geq 0$ , the broadcast cut $I(X, X_r; Y) \leq I(X; Y_r \mid X_r)$ is the tighter constraint. The cut-set bound becomes $C \leq \max_{p(x, x_r)} I(X, X_r; Y)$ .

Tightness

We will show in Section 22.3 that decode-and-forward achieves exactly this bound for the degraded relay channel, establishing the capacity: $C = \max_{p(x, x_r)} \min\bigl\{I(X; Y_r \mid X_r),\; I(X, X_r; Y)\bigr\} = \max_{p(x, x_r)} I(X, X_r; Y).$

Cut-Set Bound: Broadcast vs. Multiple-Access Cut

Visualize how the two cuts of the cut-set bound trade off as the relay link quality varies. The relay channel is Gaussian with adjustable source-relay and relay-destination SNRs.

Parameters

Source-Relay SNR (dB)10

SNR of the source-to-relay link

Relay-Destination SNR (dB)15

SNR of the relay-to-destination link

Source-Destination SNR (dB)5

SNR of the direct source-to-destination link

Common Mistake: The Cut-Set Bound Is Not Always Tight

Mistake:

Assuming that the cut-set bound gives the exact capacity of any relay channel.

Correction:

The cut-set bound is tight for the degraded relay channel (achieved by DF) and within a constant gap for the Gaussian relay channel (Chapter 23). However, it is not tight in general. Counterexamples exist where the cut-set bound strictly exceeds the capacity. The cut-set bound is an outer bound — it tells us what rates are impossible, but achieving it requires a specific coding scheme.

🔧Engineering Note

Cut-Set Bound as a System Design Benchmark

In practice, the cut-set bound serves as the gold standard for evaluating relay protocols. When a proposed relay scheme achieves a rate within a few bits of the cut-set bound, we consider it "near-optimal" even if exact capacity is unknown. For the Gaussian relay channel, the gap between the best known achievable rate (a combination of DF and CF) and the cut-set bound is at most 0.5 bits per channel use — a remarkably small gap that makes the cut-set bound operationally useful for system design.

Cut-Set Bound

An upper bound on the capacity of a network channel obtained by considering all possible partitions (cuts) of the network nodes into source-side and destination-side sets. The capacity cannot exceed the mutual information across any cut.

Related: Relay Channel

Quick Check

In the cut-set bound for the relay channel, what does the term $I(X; Y, Y_r \mid X_r)$ represent?

The broadcast cut: how fast the source can broadcast to both relay and destination

The multiple-access cut: the source's rate to the destination when the relay observation is available as side information

The direct-link capacity without the relay

The relay's decoding rate

Correction:

The multiple-access cut: the source's rate to the destination when the relay observation is available as side information

Correct. This term represents the maximum rate at which the source can communicate to the destination, given that the destination also has access to the relay's observation $Y_r$ and knows the relay's transmission $X_r$ .

Key Takeaway

The cut-set bound provides the tightest known upper bound on relay channel capacity by considering two bottlenecks: the broadcast cut (source to relay+destination) and the multiple-access cut (source to destination with relay side information). The capacity cannot exceed the minimum of these two cuts, optimized over the joint input distribution.