Ferkans — Interactive Telecom Tutor

A Universal Strategy for Relay Networks

We have seen that compress-and-forward achieves within 0.5 bits of the cut-set bound for the single-relay Gaussian channel. But what about general networks with multiple relays? Can we find a single strategy that works well for any network topology?

Noisy network coding (NNC), introduced by Lim, Kim, El Gamal, and Chung (2011), answers this affirmatively. NNC generalizes compress-and-forward to arbitrary networks: every relay compresses its observation and maps it to a channel input, and the destination jointly decodes using all received signals. The key result is that NNC achieves within a constant gap of the cut-set bound for any Gaussian relay network — and the gap depends only on the number of nodes, not on the channel parameters.

Definition:
Noisy Network Coding (NNC)

Consider a network with $K$ nodes, a source node $1$ , and a destination node $K$ . Nodes $2, \ldots, K-1$ are relays. The noisy network coding scheme operates as follows:

Compression: Each relay $k$ quantizes its received signal $Y_k^n$ to a compressed version $\hat{Y}_k^n$ using a random codebook at rate $\hat{R}_k$ .
Random mapping: Each relay maps its compression index to a channel input codeword $X_k^n$ drawn from an i.i.d. Gaussian codebook.
Joint decoding: The destination jointly decodes the source message $W$ and all compression indices from its own observation $Y_K^n$ .

The scheme uses long blocks and the compression codebooks are generated independently. Unlike standard CF (which uses Wyner-Ziv binning and sequential decoding), NNC uses joint decoding of all compression indices simultaneously.

Noisy Network Coding

A generalization of compress-and-forward to arbitrary relay networks where each relay quantizes its observation and maps it to a channel input via random coding. The destination jointly decodes the source message and all compression indices. Achieves within a constant gap of the cut-set bound for Gaussian networks.

Related: Compress-and-Forward

Theorem: Noisy Network Coding Achievable Rate

For a general discrete memoryless relay network with source node 1, destination node $K$ , and relay nodes $\mathcal{N} = \{2, \ldots, K-1\}$ , noisy network coding achieves all rates $R < \min_{\mathcal{S} \subseteq \mathcal{N}} \left[I(X_1, X_{\mathcal{S}}; \hat{Y}_{\mathcal{S}^c}, Y_K \mid X_{\mathcal{S}^c}) - \sum_{k \in \mathcal{S}^c \setminus \{K\}} I(Y_k; \hat{Y}_k \mid X_k, \hat{Y}_{\mathcal{S}}, Y_K)\right]$ where the minimum is over all subsets $\mathcal{S}$ of relay nodes, and the mutual informations are evaluated under the product distribution $\prod_k p(x_k) p(\hat{y}_k | y_k, x_k)$ .

The rate expression has a "cut-set-like" structure: for each subset $\mathcal{S}$ of relays that "cooperate" with the source, the achievable rate is bounded by the mutual information across the cut minus the cost of describing the compression indices of the relays on the destination side. The scheme is universal in the sense that it does not require the relays to know the network topology or the other relays' codebooks.

Proof

Codebook generation

For each node $k$ , generate $2^{n\hat{R}_k}$ compression codewords i.i.d. $\sim \prod_i p(\hat{y}_{k,i} | x_{k,i})$ and $2^{nR_k}$ transmission codewords i.i.d. $\sim \prod_i p(x_{k,i})$ (for source) or random mapping (for relays).

Relay operation

In each block, relay $k$ finds $\hat{y}_k^n$ jointly typical with $(y_k^n, x_k^n)$ . The compression index is mapped to the next block's transmission codeword via a deterministic function (random hash).

Joint decoding at destination

The destination looks for the unique message $\hat{w}$ and compression indices $(\hat{l}_2, \ldots, \hat{l}_{K-1})$ such that all sequences are jointly typical. Error analysis via the multivariate packing lemma gives the rate constraint for each cut $\mathcal{S}$ .

🎓CommIT Contribution(2011)

Noisy Network Coding

S. H. Lim, Y.-H. Kim, A. El Gamal, S.-Y. Chung, G. Caire — IEEE Transactions on Information Theory

Lim, Kim, El Gamal, and Chung introduced noisy network coding as a universal relay strategy for general networks. The scheme generalizes compress-and-forward by replacing Wyner-Ziv binning with joint decoding of all compression indices at the destination. This simplification enables a single scheme to achieve within a constant gap of the cut-set bound for any Gaussian network — a landmark result in network information theory.

noisy-network-codingrelay-networkconstant-gapView Paper →

Theorem: NNC Constant-Gap Result for Gaussian Networks

For any Gaussian relay network with $K$ nodes, noisy network coding with Gaussian quantization at the noise level achieves within $\text{gap} \leq \frac{K-1}{2} \text{ bits per channel use}$ of the cut-set bound. The gap depends only on the number of nodes $K$ , not on the channel gains, powers, or SNRs.

Each relay introduces at most 0.5 bits of loss (from using independent inputs instead of correlated, similar to the single-relay case). With $K - 1$ relays, the total gap is at most $(K-1)/2$ bits. While this grows with the network size, it is independent of SNR — a universal approximation.

The point is that noisy network coding reduces the capacity approximation problem for any Gaussian network to within a constant that depends only on the network size. For a network with 5 nodes, the gap is at most 2 bits — quite useful in practice.

Proof

Quantize at the noise level

Each relay $k$ sets its quantization distortion $\Delta_k = N_k$ (the noise variance at relay $k$ ). This choice ensures that the compression index can be forwarded at a rate not exceeding the relay-to-downstream link capacity, while capturing all the useful information in $Y_k$ beyond the noise floor.

Gap analysis per cut

For each cut $\mathcal{S}$ , the NNC rate with Gaussian quantization is $I(X_1, X_{\mathcal{S}}; \hat{Y}_{\mathcal{S}^c}, Y_K | X_{\mathcal{S}^c}) - \text{compression overhead}$ . The compression overhead for each relay in $\mathcal{S}^c$ is at most $\frac{1}{2}\log 2 = 0.5$ bits (since quantizing at the noise level loses at most one bit of precision). The total gap across the cut is $|\mathcal{S}^c \setminus \{K\}| \cdot 0.5 \leq (K-2) \cdot 0.5$ .

Independence loss

An additional 0.5 bits is lost from using independent inputs (no beamforming gain), giving a total gap of at most $(K-1)/2$ .

Example: NNC Applied to the Diamond Network

Apply noisy network coding to the Gaussian diamond network from Section 22.6: $Y_{r_k} = h_k X + Z_{r_k}$ ( $k = 1,2$ ), $Y = g_1 X_{r_1} + g_2 X_{r_2} + Z$ . With $h_1 = h_2 = 1$ , $g_1 = g_2 = 1$ , $P = P_{r_1} = P_{r_2} = 10$ , $N = N_{r_1} = N_{r_2} = 1$ . Compute the NNC rate and the cut-set bound.

Solution

Cut-set bound

Broadcast cut: $I(X; Y_{r_1}, Y_{r_2}) = \frac{1}{2}\log(1 + 2P/N) = \frac{1}{2}\log(21) \approx 2.18$ bits. MAC cut: $I(X_{r_1}, X_{r_2}; Y) = \frac{1}{2}\log(1 + 2P_r) = \frac{1}{2}\log(21) \approx 2.18$ bits. Cut-set bound: $\min\{2.18, 2.18\} = 2.18$ bits.

NNC rate

Each relay quantizes at the noise level: $\Delta_1 = \Delta_2 = 1$ . The NNC rate accounts for the compression overhead. With $K = 4$ nodes, the gap is at most $(4-1)/2 = 1.5$ bits. Explicit computation: the NNC rate is approximately $2.18 - 1.0 \approx 1.18$ bits (the actual gap is typically much smaller than the worst-case bound).

Interpretation

NNC achieves a rate within about 1 bit of the cut-set bound for this 4-node network, without any coordination between relays. Each relay simply compresses and forwards independently. The gap would shrink further with optimized compression parameters.

Example: NNC for a Serial Relay Chain

Consider a chain of relays: source → relay 1 → relay 2 → destination, with Gaussian links $Y_{r_1} = X + Z_1$ , $Y_{r_2} = X_{r_1} + Z_2$ , $Y = X_{r_2} + Z$ , all with noise variance $N = 1$ and powers $P = P_{r_1} = P_{r_2} = 10$ . Compare DF (decode at each hop) with NNC.

Solution

DF rate (decode at each hop)

The DF rate is limited by the weakest hop: $R_{\text{DF}} = \min\{\frac{1}{2}\log(1+10), \frac{1}{2}\log(1+10), \frac{1}{2}\log(1+10)\} = \frac{1}{2}\log(11) \approx 1.73$ bits.

NNC rate

With NNC, each relay compresses and forwards. The cut-set bound gives $C \leq \frac{1}{2}\log(11) \approx 1.73$ bits (the bottleneck is any single hop). NNC with Gaussian quantization achieves approximately $1.73 - 1.0 = 0.73$ bits.

Comparison

For a serial chain, DF is clearly superior: each relay can fully decode (the observation contains only one upstream signal), so there is no loss from decoding. NNC is suboptimal here because it does not exploit the sequential structure. NNC shines in non-serial topologies (diamond, mesh) where decoding at relays may not be optimal.

NNC Gap to Cut-Set Bound vs. Network Size

Visualize how the worst-case gap between NNC and the cut-set bound grows with the number of relay nodes. Compare with the actual gap for specific network topologies.

Parameters

Number of Nodes

K

5

Per-Link SNR (dB)10

Network Topology

Noisy Network Coding: Universal Relay Strategy

Animated walkthrough of the noisy network coding scheme for a multi-relay network: each relay independently compresses its observation, forwards it, and the destination jointly decodes the source message and all compression indices.

Common Mistake: NNC Is Not Always Better Than DF

Mistake:

Assuming NNC is universally superior because it has a "constant gap" guarantee.

Correction:

NNC's constant gap is a worst-case result. For specific topologies like serial relay chains or degraded relay channels, decode-and-forward can achieve the exact capacity while NNC falls short. The value of NNC is its universality: it works well for any topology without requiring topology-specific optimization. In practice, the best approach is to compare DF, CF, NNC, and hybrid schemes for the specific network at hand.

Historical Note: The Quest for a Universal Relay Strategy

2005-2011

The development of noisy network coding was the culmination of a decade-long quest for a universal relay strategy. Cover and El Gamal (1979) provided DF and CF for the single relay. Kramer, Gastpar, and Gupta (2005) extended these to networks but found that the gap could grow unboundedly. Avestimehr, Diggavi, and Tse (2011) showed, via the deterministic approach, that a constant-gap approximation exists for Gaussian networks — but their QMF scheme was complex and not based on standard information-theoretic tools.

Lim, Kim, El Gamal, and Chung (2011) achieved the same constant-gap result using a surprisingly simple modification of compress-and-forward: replace Wyner-Ziv binning with joint decoding. This insight — that joint decoding of compression indices is the key to universality — was unexpected and elegant.

⚠️Engineering Note

Practical Implications of NNC

Noisy network coding has significant implications for practical relay network design:

Simplicity: each relay compresses independently — no coordination between relays is needed. This maps naturally to distributed systems.
Robustness: the scheme works for any topology and channel parameters. No topology-specific optimization is required.
Scalability: adding a new relay can only improve performance (it provides additional compressed observations).

The main practical challenge is the joint decoding at the destination, which has complexity exponential in the number of relays. For small networks ( $K \leq 5$ ), this is feasible; for large networks, iterative decoding approximations are needed.

Practical Constraints

•
Joint decoding complexity grows exponentially with number of relays
•
Each relay needs to estimate its noise level for optimal quantization
•
Synchronization across relays required for coherent reception

Quick Check

What is the key difference between standard compress-and-forward (Chapter 22) and noisy network coding?

NNC uses better compression codebooks

NNC replaces Wyner-Ziv binning with joint decoding of all compression indices at the destination

NNC allows relays to cooperate with each other

NNC uses structured (lattice) codes instead of random codes

Correction:

NNC replaces Wyner-Ziv binning with joint decoding of all compression indices at the destination

Correct. In standard CF, the relay uses Wyner-Ziv binning and the destination decodes sequentially. In NNC, there is no binning — the destination jointly decodes the source message and all compression indices simultaneously. This removes the need for the Wyner-Ziv rate constraint to hold for each relay individually.

Key Takeaway

Noisy network coding provides a universal relay strategy: each relay compresses independently, and the destination jointly decodes everything. For any Gaussian relay network with $K$ nodes, NNC achieves within $(K-1)/2$ bits of the cut-set bound — a constant gap independent of channel parameters. This makes NNC the default strategy when the network topology is complex or unknown.

Noisy Network Coding

A Universal Strategy for Relay Networks

Definition: Noisy Network Coding (NNC)

Noisy Network Coding

Theorem: Noisy Network Coding Achievable Rate

Codebook generation

Relay operation

Joint decoding at destination

Noisy Network Coding

Theorem: NNC Constant-Gap Result for Gaussian Networks

Quantize at the noise level

Gap analysis per cut

Independence loss

Example: NNC Applied to the Diamond Network

Cut-set bound

NNC rate

Interpretation

Example: NNC for a Serial Relay Chain

DF rate (decode at each hop)

NNC rate

Comparison

NNC Gap to Cut-Set Bound vs. Network Size

Parameters

Noisy Network Coding: Universal Relay Strategy

Common Mistake: NNC Is Not Always Better Than DF

Historical Note: The Quest for a Universal Relay Strategy

Practical Implications of NNC

Quick Check

Key Takeaway

Definition:
Noisy Network Coding (NNC)