Ferkans — Interactive Telecom Tutor

The Canonical CF Application

The simplest setting that exposes what compute-and-forward actually buys is the two-way relay channel (TWRC): two users $A$ and $B$ want to exchange messages via a single relay $R$ , with no direct link between $A$ and $B$ . This captures everything from a cellular uplink-downlink pair via a base station through a satellite-mediated terrestrial link to two nodes communicating through an amplifier in a sensor network. Three strategies compete: classical routing (four orthogonal time slots), amplify- or-decode-forward (two slots with a MAC-then-broadcast split), and compute-and-forward (two slots, relay decodes the XOR or sum).

The punchline (Nam-Chung-Lee 2010): on a symmetric TWRC, CF achieves the capacity region within $\tfrac{1}{2}$ bit per user, matching the best-known upper bound up to a constant gap. Neither AF nor DF does this — AF loses the full MAC gain to noise amplification; DF spends one slot decoding two messages it will immediately combine anyway. CF bypasses both failures by never decoding the individual users in the MAC phase. Zhang-Liew-Lam's 2006 physical-layer network coding (PNC) was the intuitive precursor; the Nazer-Gastpar framework is the rigorous generalisation. This section derives the TWRC rate region, compares strategies quantitatively, and sets up §4's identification of PNC as the integer-coefficient $\mathbf{a} = (1, 1)^T$ case.

,

Definition:
Two-Way Relay Channel

The Gaussian two-way relay channel (TWRC) consists of three nodes:

Two users $A$ and $B$ , each with a message $\mathbf{u}_A$ or $\mathbf{u}_B$ to send to the other.
A relay $R$ with no message of its own.

Communication proceeds over two time slots:

Slot 1 (multiple-access phase). Both users transmit simultaneously: $\mathbf{y}_R \;=\; h_A \mathbf{x}_A + h_B \mathbf{x}_B + \mathbf{w}_R,$ with per-user power $P$ and $\mathbf{w}_R \sim \mathcal{N}( \mathbf{0}, \mathbf{I})$ . The relay computes some function of $(\mathbf{u}_A, \mathbf{u}_B)$ .

Slot 2 (broadcast phase). The relay transmits $\mathbf{x}_R$ at power $P_R$ to both users: $\mathbf{y}_A = g_A \mathbf{x}_R + \mathbf{w}_A, \qquad \mathbf{y}_B = g_B \mathbf{x}_R + \mathbf{w}_B.$ Each user then recovers the other's message using its own self-knowledge (e.g., $\mathbf{u}_A$ XOR $\mathbf{u}_B$ XOR $\mathbf{u}_A$ = $\mathbf{u}_B$ ). A rate pair $(R_A, R_B)$ is achievable if both users eventually decode their target message with vanishing error.

,

TWRC Strategies: Symmetric Sum-Rate at $\text{SNR} = 20\,\text{dB}$

Strategy	Slots	Relay function	Sum-rate (bits/ch. use)	Gap to cap.
Routing (4 slots)	4 orthogonal	Relay decodes each user separately	$\tfrac{1}{2} \log_2(1+\text{SNR}) / 2 \approx 1.66$	Huge
Amplify-and-forward	2 (MA+BC)	Relay scales $\mathbf{y}_R$ and rebroadcasts	$\tfrac{1}{2} \log_2(1 + \text{SNR}^{2}/(2\text{SNR}+1)) \approx 3.20$	Medium
Decode-and-forward	2 (MA+BC)	Relay decodes both messages and XORs	$\min\{\tfrac{1}{2}\log_2(1+\text{SNR}), \tfrac{1}{4}\log_2(1+2\text{SNR})\} \approx 3.33$	Medium
Compute-and-forward	2 (MA+BC)	Relay decodes $\mathbf{u}_A + \mathbf{u}_B \bmod \Lambda$	$2 \cdot R(\mathbf{h}, (1,1)) \approx 2 \cdot 3.16 = 6.32$	$\le 1/2$ bit/user
Capacity upper bound	2	(cut-set)	$\log_2(1 + \text{SNR}) \approx 6.66$	–

Theorem: Nam-Chung-Lee: CF Is Within 1/2 Bit of TWRC Capacity

Consider the symmetric Gaussian TWRC with $h_A = h_B = 1$ , $g_A = g_B = 1$ , and common user power $P$ and relay power $P_R$ . Let $\text{SNR} = \min(P, P_R)$ . The capacity region of this channel satisfies $\mathcal{C}_{\rm TWRC}(\text{SNR}) \;\subseteq\; \{(R_A, R_B) : R_A \le \tfrac{1}{2} \log_2(1 + \text{SNR}), \; R_B \le \tfrac{1} {2} \log_2(1 + \text{SNR})\}$ (the cut-set bound), and the compute-and-forward strategy with integer coefficient $\mathbf{a} = (1, 1)^T$ in the MA phase achieves the rate pair $\left( \tfrac{1}{2} \log_2^+\!\left(\tfrac{1}{2} + \text{SNR}\right), \tfrac{1}{2} \log_2^+\!\left(\tfrac{1}{2} + \text{SNR}\right)\right),$ in each direction — within $\tfrac{1}{2}$ bit per user of the cut-set bound for all $\text{SNR} \ge 0$ .

At high $\text{SNR}$ , the cut-set bound grows like $\tfrac{1}{2} \log_2(\text{SNR})$ ; the CF rate grows like $\tfrac{1}{2} \log_2 (\text{SNR})$ as well. The gap $\tfrac{1}{2} \log_2(1+\text{SNR}) - \tfrac{1}{2} \log_2(\tfrac{1}{2} + \text{SNR})$ is bounded above by $\tfrac{1}{2} \log_2(2) = \tfrac{1}{2}$ bit, achieved as $\text{SNR} \to 0$ and asymptotically vanishing as $\text{SNR} \to \infty$ . So CF is not only within a constant gap of capacity — at high SNR it is essentially tight.

Proof

MA phase: apply the Nazer-Gastpar rate with $\mathbf{a} = (1,1)$

With $\mathbf{h} = (1, 1)^T$ and $\mathbf{a} = (1, 1)^T$ : $\|\mathbf{a}\|^2 = 2$ , $\mathbf{h}^T \mathbf{a} = 2$ , $\|\mathbf{h}\|^2 = 2$ . Hence $N_{\rm eff} = 2 - \text{SNR} \cdot 4 / (1 + 2\text{SNR}) = (2 + 4 \text{SNR} - 4 \text{SNR})/(1 + 2 \text{SNR}) = 2/(1 + 2\text{SNR})$ , and by Thm. TNazer-Gastpar Computation Rate, $R_{\rm MA} = \tfrac{1}{2} \log_2\!\left(\tfrac{1 + 2\text{SNR}}{2} \right) = \tfrac{1}{2} \log_2^+\!\left(\tfrac{1}{2} + \text{SNR} \right).$ Each user can transmit at rate $R_{\rm MA}$ and the relay decodes $\mathbf{u}_A + \mathbf{u}_B \bmod \Lambda_s$ reliably.

BC phase: broadcast the decoded sum

The relay has $\mathbf{v} = \mathbf{u}_A + \mathbf{u}_B \bmod \Lambda_s$ , a lattice point of rate $R_{\rm MA}$ . In the BC phase the relay transmits $\mathbf{x}_R = \mathbf{v}$ (suitably scaled to power $P_R$ ). Each user $k \in \{A, B\}$ receives $\mathbf{y}_k = \mathbf{x}_R + \mathbf{w}_k$ at SNR $P_R = \text{SNR}$ , decodes $\mathbf{v}$ at rate $\tfrac{1}{2} \log_2(1 + \text{SNR})$ , and subtracts its own message: $\mathbf{u}_B = \mathbf{v} - \mathbf{u}_A \bmod \Lambda_s$ at user $A$ , and similarly at user $B$ . The BC rate is the single-user cap and does not bottleneck.

Rate is $\min(R_{\rm MA}, R_{\rm BC}) = R_{\rm MA}$ at moderate SNR

At balanced power $P = P_R = \text{SNR}$ , the BC rate $\tfrac{1} {2} \log_2(1 + \text{SNR})$ always exceeds the MA CF rate $\tfrac{1}{2} \log_2(1/2 + \text{SNR})$ . So the two-slot CF rate per user is $R_{\rm TWRC}^{\rm CF} = \tfrac{1}{2} \log_2^+ (1/2 + \text{SNR})$ .

Cut-set upper bound

Standard cut-set (Cover-Thomas Thm. 15.10.1): for any point-to- point message from $A$ to $B$ through relay $R$ , the rate is upper-bounded by $\tfrac{1}{2} \log_2 (1 + \text{SNR})$ — the single-user MA-to-relay capacity. The same bound holds for $B \to A$ .

Gap computation

$\Delta = \tfrac{1}{2} \log_2 (1 + \text{SNR}) - \tfrac{1}{2} \log_2 (1/2 + \text{SNR}) = \tfrac{1}{2} \log_2 \big(\tfrac{1 + \text{SNR}}{1/2 + \text{SNR}}\big) \le \tfrac{1}{2} \log_2(2) = \tfrac{1}{2}$ bit, with equality at $\text{SNR} = 0$ and asymptotically $\to 0$ as $\text{SNR} \to \infty$ . $\blacksquare$

,

Two-Way Relay: CF vs. Amplify/Decode-Forward Sum-Rate

Sum-rate of the symmetric two-way relay channel versus SNR, comparing four strategies: (i) routing (4 orthogonal slots), (ii) amplify-and-forward (2 slots), (iii) decode-and-forward (2 slots, relay decodes both messages and XORs), (iv) compute- and-forward with $\mathbf{a} = (1, 1)^T$ . At moderate-to-high SNR the CF curve is the highest, and approaches the cut-set bound $\log_2(1 + \text{SNR})$ as $\text{SNR} \to \infty$ — the "within 1/2 bit" Nam-Chung-Lee guarantee (Thm. TNam-Chung-Lee: CF Is Within 1/2 Bit of TWRC Capacity). At low SNR, DF can marginally outperform CF because the $\tfrac{1}{2}$ bit gap matters proportionally more.

Parameters

Example: TWRC Rates at Symmetric $\text{SNR} = 20\,\text{dB}$

Compare the per-user sum-rate of the symmetric Gaussian TWRC at $\text{SNR} = 20\,\text{dB} = 100$ under routing, AF, DF, and CF. Which strategy is closest to the cut-set upper bound?

Solution

Routing (4 slots)

Four orthogonal slots: $A \to R$ , $R \to B$ , $B \to R$ , $R \to A$ . Each link: rate $\tfrac{1}{2} \log_2(1 + 100) = 3.33$ bits. But each message uses 2 slots out of 4, so per- user rate is $3.33 / 2 = 1.66$ bits. Sum-rate: $2 \cdot 1.66 = 3.33$ bits/ch. use.

Amplify-and-forward

Relay receives $\mathbf{y}_R = \mathbf{x}_A + \mathbf{x}_B + \mathbf{w}_R$ , rescales to power $P_R$ , broadcasts. Each user's end-to-end SNR is $\text{SNR}^{2}/(2\text{SNR} + 1) \approx \text{SNR}/2 = 50$ after interference cancellation. Per-user rate: $\tfrac{1}{2} \log_2(1 + 50) \approx 2.84$ bits. Sum-rate: $5.68$ .

Decode-and-forward

MA cut limits decoding both messages: $\tfrac{1}{4} \log_2(1 + 200) \approx 1.91$ bits/user. BC limit: $\tfrac{1}{2} \log_2(1 + 100) = 3.33$ . Bottleneck: MA. Per-user rate: $1.91$ . Sum-rate: $3.82$ . Better than routing, worse than CF.

Compute-and-forward

With $\mathbf{a} = (1,1)^T$ : $R_{\rm CF} = \tfrac{1}{2} \log_2(1/2 + 100) \approx \tfrac{1}{2} \log_2(100.5) = 3.32$ bits/user. Sum-rate: $6.65$ .

Cut-set upper bound and conclusion

Cut-set: $\tfrac{1}{2} \log_2(1 + 100) = 3.33$ bits/user, sum-rate $6.66$ . CF achieves $3.32 / 3.33 = 99.7\%$ of cut-set per user. The $\tfrac{1}{2}$ -bit gap in the Nam- Chung-Lee theorem has shrunk to $0.01$ bit at $\text{SNR} = 20\,\text{dB}$ — essentially tight. CF wins decisively. $\blacksquare$

,

What About Asymmetric TWRC?

The $\tfrac{1}{2}$ -bit gap of Thm. TNam-Chung-Lee: CF Is Within 1/2 Bit of TWRC Capacity assumes a symmetric TWRC: $h_A = h_B$ and $g_A = g_B$ . For asymmetric channels ( $h_A \neq h_B$ ), the integer coefficient $\mathbf{a} = (1, 1)^T$ is not necessarily optimal. With $\mathbf{h} = (1, 2)^T$ , $\mathbf{a} = (1, 2)^T$ is exact and CF achieves nearly the full MAC sum-rate; with $\mathbf{h} = (1, \sqrt{2})^T$ , no integer vector is exact and CF pays a Diophantine-approximation penalty.

Wilson-Narayanan-Pfister-Sprintson (2010) and Nam-Chung-Lee (2011) extended the constant-gap result to asymmetric TWRCs using optimised $\mathbf{a}^*$ chosen from the channel; the gap grows to $\log_2(1 + \text{SNR} \kappa^2)$ where $\kappa$ is a Diophantine-mismatch parameter, but remains bounded over bounded SNR. For the curriculum we focus on the symmetric case; asymmetric refinements are deferred to exercises.

,

Historical Note: The TWRC in Theory: From Shannon 1961 to Nam-Chung-Lee 2010

1961-2011

The two-way channel was introduced by Shannon in his 1961 "Two-way communication channels" paper — one of the first studies of network information theory. Shannon asked: what rate pairs can two users exchange over a shared medium? For the general two-way channel (direct links, no relay), Shannon gave an inner bound that is still not known to be tight 60 years later — one of the longest-standing open problems in information theory.

The relay-mediated two-way channel admits a cleaner answer. Wu-Chou-Chan (2005) first proposed a two-slot network-coded protocol using digital XOR at the relay. Popovski-Yomo (2006) extended it to wireless with analog superposition. Zhang-Liew-Lam (2006) — in the MobiCom paper that coined "physical-layer network coding" — showed that the XOR can be extracted from the analog sum itself, doubling the slot efficiency. Katti-Gollakota- Katabi (2007) demonstrated this experimentally in a MIT testbed called ANC (Analog Network Coding).

The information-theoretic characterisation came later. Oechtering and colleagues (2008–2009) computed the exact achievable region. Nam-Chung-Lee (2010) — the paper that sits at the heart of this section — proved the $\tfrac{1}{2}$ -bit constant-gap via lattice codes. Nazer-Gastpar (2011) then framed all of this as the $K = 2$ specialisation of compute-and-forward, making the TWRC the pedagogical gateway to the general CF framework. The lineage is Shannon $\to$ network coding $\to$ PNC $\to$ lattice CF — forty years of convergence on a two-slot lattice protocol that is nearly optimal.

,

Two-Slot Compute-and-Forward TWRC Protocol

Complexity: Encoding:

O(n)

lattice lookups per user. MMSE decoding at relay:

O(n \log n)

per block with standard lattice decoders. Total latency:

2

channel blocks of

n

symbols each.

# Two-way relay channel: users A, B exchange messages via relay R

# Nested lattices: Lambda_c subset Lambda_s, shared by both users

# Channel: y_R = h_A * x_A + h_B * x_B + w_R (slot 1)

# y_A = g_A * x_R + w_A, y_B = g_B * x_R + w_B (slot 2)

# ----- Encoding (at each user k in {A, B}) -----

Pick message u_k in Lambda_c intersect V(Lambda_s)

Generate dither d_k ~ Uniform(V(Lambda_s)) # shared with R

Transmit x_k = (u_k - d_k) mod Lambda_s # power P

# ----- Slot 1: MAC phase, relay decodes v = u_A + u_B mod Lambda_s -----

Relay receives y_R = h_A * x_A + h_B * x_B + w_R

Choose integer a = (1, 1) [symmetric TWRC]

Compute alpha = SNR * (h^T a) / (1 + SNR * ||h||^2)

Compute y_R_eff = alpha * y_R + d_A + d_B

Decode v_hat = argmin over v_lat in Lambda_c of

|| (y_R_eff - v_lat) mod Lambda_s ||^2

# ----- Slot 2: BC phase, relay transmits v_hat, users recover -----

Relay transmits x_R ~ v_hat (scaled to power P_R)

User A receives y_A = g_A * x_R + w_A

User A decodes v_hat from y_A (single-user Lambda_c decoder)

User A recovers u_B = (v_hat - u_A) mod Lambda_s # A knows u_A

User B recovers u_A = (v_hat - u_B) mod Lambda_s # B knows u_B

return u_A (to B), u_B (to A)

The protocol's elegance lies in two moves. In slot 1 the relay decodes only the sum, not the individual messages — avoiding the MAC cut that limits DF. In slot 2 each user subtracts its own message from the decoded sum, turning the XOR broadcast into a point-to-point code.

Common Mistake: Both Users Need Their Dithers at the Relay

Mistake:

Forgetting that in the nested-lattice CF protocol the dithers $\mathbf{d}_A, \mathbf{d}_B$ at each user are shared with the relay — not broadcast in the air. If the dithers are unknown to the relay, the relay cannot form $\mathbf{y}_R' = \alpha \mathbf{y}_R + \mathbf{d}_A + \mathbf{d}_B$ and the crypto-lemma argument breaks: the effective noise no longer has mean zero.

Correction:

In practice the dithers are generated from a pseudo-random seed shared in advance between each user and the relay (e.g., via a common pilot sequence or a key-exchange phase). This is inexpensive: a 128-bit seed regenerates an infinite dither sequence. It is not secret data — the dither exists to make the crypto-lemma uniformity hold, nothing more. The PNC protocol (§4) achieves a similar effect without dithers by using a finite-alphabet structured codebook; for asymptotic AWGN-capacity achievability, nested lattices with shared dithers are the standard construction.

Why This Matters: TWRC in Modern Wireless: Integrated Access and Backhaul

5G NR introduced Integrated Access and Backhaul (IAB) in Release 16: a hub gNB serves user equipments through wireless relay gNBs that also backhaul their traffic over the same spectrum. Architecturally, the IAB-relay plays the role of " $R$ " in a multi-user TWRC: users send uplink data, the relay forwards to the hub, the hub sends downlink data, the relay forwards to users — four logical traffic flows over shared spectrum.

5G NR does not implement compute-and-forward — it uses orthogonal time-frequency splitting for the four flows. But the information-theoretic analysis of this section predicts that a CF-based IAB relay could double the throughput of the backhaul link at high SNR. Chapter 20 discusses massive-MIMO coded modulation, where the role of lattice codes extends to precoded uplink-downlink combinations — a spiritual continuation of TWRC CF in higher dimensions.

See full treatment in Chapter 20

Quick Check

Why does compute-and-forward outperform decode-and-forward on the symmetric Gaussian TWRC at high SNR?

CF uses a single codebook while DF uses two; one codebook is cheaper.

The MA decode in DF is limited by $\tfrac{1}{2} \log(1 + 2\text{SNR})/2$ , while CF's MA rate is $\tfrac{1}{2} \log(1/2 + \text{SNR})$ per user — asymptotically identical but CF is tighter at finite SNR.

DF must decode both messages at the relay — limited by the MAC-sum capacity $\tfrac{1}{2} \log_2(1+2\text{SNR})$ — while CF only decodes the sum, limited by the single-user effective rate $\tfrac{1}{2} \log_2(1/2 + \text{SNR})$ which is $\log_2 \text{SNR}/2$ worth larger at high SNR.

CF never requires synchronisation, while DF does.

Correction:

DF must decode both messages at the relay — limited by the MAC-sum capacity

\tfrac{1}{2} \log_2(1+2\text{SNR})

— while CF only decodes the sum, limited by the single-user effective rate

\tfrac{1}{2} \log_2(1/2 + \text{SNR})

which is

\log_2 \text{SNR}/2

worth larger at high SNR.

Correct. DF's relay bottleneck is the MAC sum-capacity $\tfrac{1}{2} \log_2(1 + 2\text{SNR})$ , which splits into $\tfrac{1}{4} \log_2(1 + 2\text{SNR})$ per user. CF only needs to decode the sum $\mathbf{u}_A + \mathbf{u}_B \bmod \Lambda$ , bypassing the per-user split — so its per-user rate scales with the full channel capacity.

Two-way relay channel (TWRC)

A three-node network in which two users $A$ and $B$ exchange messages via a single relay $R$ . No direct $A \leftrightarrow B$ link exists. The canonical CF application, operating in two time slots (multiple-access + broadcast); Nam-Chung-Lee proved CF achieves capacity within $\tfrac{1}{2}$ bit per user.

Key Takeaway

On the symmetric Gaussian two-way relay channel, compute-and- forward with integer coefficient $\mathbf{a} = (1, 1)^T$ achieves a per-user rate of $\tfrac{1}{2} \log_2^+ (1/2 + \text{SNR})$ , within $\tfrac{1}{2}$ bit per user of the cut-set capacity bound for all SNR (Nam-Chung-Lee 2010). Over two slots (MA + BC), this doubles the classical routing throughput and strictly outperforms both AF and DF at moderate-to-high SNR. The key move: the relay decodes $\mathbf{u}_A + \mathbf{u}_B \bmod \Lambda_s$ — a single lattice point — and each user recovers the other's message by subtracting its own.

Application: The Two-Way Relay Channel