Ferkans — Interactive Telecom Tutor

From Zhang-Liew-Lam's MobiCom to Nazer-Gastpar's Theorem

Five years before Nazer-Gastpar, Zhang, Liew, and Lam published a MobiCom paper with a provocative thesis: the analog superposition of two users' BPSK symbols at a relay's antenna already computes the XOR of their bits. Call this Physical- Layer Network Coding (PNC). It doubles the two-way relay throughput from four slots to two — not by clever digital processing but by reading the physics of the channel differently.

PNC was the intuitive spark, Nazer-Gastpar is the rigorous framework. This section identifies PNC as the $\mathbf{a} = (1, 1)^T$ special case of compute-and-forward, proves this correspondence formally, and honestly catalogues PNC's limits — the asymmetric-channel failure mode, the finite-alphabet constraint, and the alignment sensitivity. The takeaway: PNC gave wireless its first "computation over the channel" primitive; lattice CF extended it to every integer combination at arbitrary rates.

,

Definition:
Physical-Layer Network Coding (PNC)

Consider the symmetric two-way relay channel with users $A, B$ each transmitting a binary message $u_k \in \{0, 1\}$ via BPSK: $x_k = 1 - 2 u_k \in \{-1, +1\}$ . The relay receives $y_R = x_A + x_B + w_R = (1 - 2 u_A) + (1 - 2 u_B) + w_R = 2 - 2(u_A + u_B) + w_R.$ Physical-layer network coding is the following relay decoding rule:

If $y_R > \phantom{-}1$ : decode $u_A \oplus u_B = 0$ (both zeros)
If $|y_R| \le 1$ : decode $u_A \oplus u_B = 1$ (mixed)
If $y_R < -1$ : decode $u_A \oplus u_B = 0$ (both ones)

That is, PNC maps the analog sum $y_R$ directly to the XOR $u_A \oplus u_B$ — skipping the intermediate step of decoding $u_A, u_B$ separately. The relay then broadcasts $u_A \oplus u_B$ ; each user XORs with its own bit to recover the other's.

Note the three-level decision boundary corresponds to the sum $u_A + u_B \in \{0, 1, 2\}$ (the cardinality-3 set), with $\{0, 2\} \mapsto 0$ and $\{1\} \mapsto 1$ — the XOR is $u_A + u_B \bmod 2$ . The analog superposition gives the sum over the reals; the final mod-2 reduction is the binary XOR. This is the lattice insight in miniature: $\{0, 1\}$ is a piece of $\mathbb{Z}$ , BPSK is a piece of $\mathbb{R}$ , the channel superposes integers by adding reals.

,

Theorem: PNC Is the $\mathbf{a} = (1, 1)^T$ Special Case of CF

Physical-layer network coding on the symmetric Gaussian TWRC — with the relay decoding $u_A \oplus u_B$ from the analog sum $y_R = x_A + x_B + w_R$ — is equivalent to compute-and-forward with integer coefficient vector $\mathbf{a} = (1, 1)^T$ using a binary nested lattice $\Lambda_c / \Lambda_s = \mathbb{Z} / 2\mathbb{Z}$ . The PNC throughput (at $\text{SNR} \to \infty$ ) approaches $1$ bit per channel use per user — matching the $K = 1$ binary cap but not the Nazer-Gastpar Gaussian bound of Thm. TNazer-Gastpar Computation Rate.

PNC uses the binary quotient lattice $\mathbb{Z}/2\mathbb{Z}$ , which forces $R \le 1$ bit at any SNR. The lattice-CF version uses the continuous quotient $\Lambda_c/\Lambda_s$ with large- $V(\Lambda_s)/V(\Lambda_c)$ , unlocking the full Gaussian capacity. PNC is CF with a BPSK-quality codebook; lattice-CF is CF with a capacity-achieving codebook. The correspondence is the reason PNC works at all — and the reason lattice-CF beats it at moderate-to-high SNR.

Proof

Lattice framing of BPSK

BPSK $x_k \in \{-1, +1\}$ is a coset representative of $\mathbb{Z}/2\mathbb{Z}$ : $u_k = 0 \leftrightarrow x_k = +1$ is the coset $2\mathbb{Z}$ ; $u_k = 1 \leftrightarrow x_k = -1$ is the coset $1 + 2\mathbb{Z}$ . The coarse lattice is $\Lambda_s = 2\mathbb{Z}$ and the fine lattice is $\Lambda_c = \mathbb{Z}$ ; the codebook is $\mathbb{Z} \cap [-1, 1) = \{-1, 0\}$ — except BPSK is shifted to $\{-1, +1\}$ by convention. The point is: BPSK is a nested-lattice codebook with $|\Lambda_c \cap \mathcal{V}(\Lambda_s)| = 2$ elements.

Analog sum at the relay

The relay receives $y_R = x_A + x_B + w_R$ . Taking $y_R \bmod \Lambda_s = y_R \bmod 2$ : if we quantise to the nearest element of $\mathbb{Z}$ within $[-1, 1)$ , we recover $(x_A + x_B) \bmod 2$ . In BPSK values, $(-1 + -1) \bmod 2 = -2 \bmod 2 = 0 \leftrightarrow u_A \oplus u_B = 0$ ; $(-1 + 1) \bmod 2 = 0 \leftrightarrow u_A \oplus u_B = 1$ ; etc. — the PNC decision rule.

MMSE coefficient for binary lattice

Plugging $\mathbf{h} = (1, 1)^T$ , $\mathbf{a} = (1, 1)^T$ into the Nazer-Gastpar MMSE: $\alpha^* = \text{SNR} \cdot 2 / (1 + 2\text{SNR}) \to 1$ as $\text{SNR} \to \infty$ . The MMSE coefficient approaches $1$ — exactly what PNC uses (it reads $y_R$ directly, no scaling). At low SNR, $\alpha^* \to 0$ and PNC's hard-decision rule is provably suboptimal (a soft PNC or lattice-CF version wins).

Rate comparison

PNC rate is $1 - H(p_e)$ where $p_e$ is the BPSK XOR error probability — bounded by $1$ bit per channel use. Lattice-CF rate is $\tfrac{1}{2} \log_2(1/2 + \text{SNR}) \to \infty$ at high SNR. For $\text{SNR} > 3\,\text{dB}$ , lattice-CF beats PNC. For $\text{SNR} < 0\,\text{dB}$ , PNC (with BPSK discrete codebook) is comparable because the rate cap of $1$ bit is non-binding.

Conclusion: PNC as the degenerate CF case

PNC is compute-and-forward with: (i) integer coefficient $\mathbf{a} = (1, 1)^T$ , fixed by symmetric channel assumption; (ii) codebook $\Lambda_c / \Lambda_s = \mathbb{Z}/2\mathbb{Z}$ , limiting rate to $1$ bit per channel use; (iii) hard-decision decoding (no MMSE scaling, no iterative refinement), simplifying implementation. Relaxing (ii) gives lattice-CF. Relaxing (i) gives asymmetric CF. Relaxing (iii) gives MMSE-aware CF. PNC is the first, simplest, most-pedagogically-essential version of the full framework. $\blacksquare$

,

Historical Note: PNC at MobiCom 2006: A 4-Page Wake-Up Call

2006

In September 2006, Shengli Zhang, Soung Chang Liew, and Patrick P. Lam presented a 4-page "Hot topic" paper at the ACM MobiCom conference titled simply "Hot topic: physical-layer network coding." The paper's core idea — that the relay's antenna performs network coding in hardware by summing analog signals — was so simple and so radical that it launched an entire subfield overnight.

Independently and in parallel, Popovski and Yomo (2006) published a similar result in an IEEE paper ("The Anti-Packets Can Increase the Achievable Throughput of a Wireless Multi-Hop Network") with the same two-slot analog-XOR protocol. Katti, Gollakota, and Katabi followed in 2007 with the ANC (Analog Network Coding) testbed at MIT — the first hardware demonstration of PNC on commodity radios. The 2007 paper became the most-cited PNC reference, ahead of the original 2006 papers, because it gave experimentalists a clear implementation target.

The Zhang-Liew-Lam paper has been cited over 2000 times. Its enduring contribution was conceptual: that the wireless medium is a computational resource, not just an interference source to be orthogonalised. This view — that interference can be harnessed through structured codes rather than avoided through orthogonalisation — is the ideological seed of Chapter 18 and much of modern wireless information theory.

,

Two-Way Relay Throughput: Routing vs. Digital NC vs. PNC

Throughput comparison on the symmetric Gaussian TWRC across three protocols. Routing (4 slots) uses orthogonal access: $A \to R$ , $R \to B$ , $B \to R$ , $R \to A$ . Sum rate grows as $\tfrac{1}{2} \log_2(1 + \text{SNR}) / 2$ . Digital NC (3 slots) has the relay decode both messages in one shared MA slot, XOR them, and broadcast in one BC slot — saving one slot over routing. PNC (2 slots) uses the analog XOR of Zhang-Liew-Lam: two slots total, relay decodes XOR from the analog sum directly. At $\text{SNR} > 10\,\text{dB}$ PNC achieves $\approx 2\times$ the routing throughput; at very low SNR PNC is limited by its BPSK-rate ceiling of $1$ bit per channel use.

Parameters

Example: PNC BPSK Error Probability

Compute the PNC decision error probability at $\text{SNR} = 5\, \text{dB}$ on the symmetric TWRC ( $h_A = h_B = 1$ , BPSK). Compare to the corresponding lattice-CF rate with $\mathbf{a} = (1, 1)^T$ at the same SNR.

Solution

PNC decision rule at the relay

Noise variance $\sigma_w^2 = 1/\text{SNR}$ . The relay's analog sum $y_R \in \{-2, 0, +2\} + \mathcal{N}(0, \sigma_w^2)$ . Decision: XOR = 0 if $|y_R| \ge 1$ , XOR = 1 if $|y_R| < 1$ . Error event: either both signals are zeros $(y_R$ mean $+2)$ and noise drives $y_R < 1$ ; or mixed $(y_R$ mean $0)$ and noise drives $|y_R| \ge 1$ ; or both ones $(y_R$ mean $-2)$ and noise drives $y_R > -1$ .

Error probability by Q-function

By symmetry, the three cases have equal marginal probabilities up to small corrections. At $\text{SNR} = 5\,\text{dB} = 3.16$ , $\sigma_w = 1/\sqrt{3.16} = 0.562$ . Threshold: $1$ from means $\pm 2$ is $1/\sigma_w = 1.78$ , so $Q(1.78) \approx 0.0375$ . Overall XOR error probability: $p_e \approx 2 Q(1/\sigma_w) \approx 0.075$ .

PNC rate

$R_{\rm PNC} = 1 - H_2(p_e) = 1 - H_2(0.075) \approx 1 - 0.38 = 0.62$ bits per channel use per user.

Lattice-CF rate at same SNR

$N_{\rm eff} = 2 - 3.16 \cdot 4 / (1 + 6.32) = 2 - 1.727 = 0.273$ . $R_{\rm CF} = \tfrac{1}{2} \log_2(1/0.273) = \tfrac{1} {2} \log_2(3.66) \approx 0.94$ bits per channel use per user.

Comparison

Lattice-CF beats PNC by $0.32$ bits ( $\sim 50\%$ ) at $\text{SNR} = 5\,\text{dB}$ . The advantage grows with SNR because lattice-CF has no rate ceiling. The advantage shrinks at very low SNR because both approach the same $1$ -bit-per-use ceiling. PNC wins only on simplicity: no lattice decoder, no dithers, no MMSE scaling. $\blacksquare$

Where PNC Fails: Asymmetric Channels and Large Constellations

PNC works cleanly for symmetric BPSK TWRC. Three failure modes limit its scope:

(1) Asymmetric channels. When $h_A \neq h_B$ , the analog sum $h_A x_A + h_B x_B$ does not land on the $\{-2, 0, +2\}$ BPSK- XOR grid. For instance $h_A = 1, h_B = 1.5$ gives possible values $\{-2.5, -0.5, 0.5, 2.5\}$ — the XOR = 1 case splits into two subclusters separated by $1$ , increasing the error probability dramatically. Remedies: use $\mathbf{a} = (1, 2)$ or a different integer vector (i.e., the general CF framework), or force amplitude alignment at the transmitters (power control).

(2) Higher-order constellations. For QPSK, 16-QAM, etc., the number of XOR-compatible output symbols grows and the decision boundaries become a complex Voronoi diagram in the complex plane. Still tractable, but loses the "read the XOR directly" simplicity of BPSK-PNC.

(3) Alignment sensitivity. Phase and timing misalignment between $A$ and $B$ cause the analog sum to rotate or smear across the decision boundaries. A $30^\circ$ phase mismatch can raise the XOR error probability by an order of magnitude at $\text{SNR} = 10\,\text{dB}$ .

Lattice-CF (via shared nested lattices with pseudo-random dithers) resolves (1) and (2) elegantly — different integer vectors and large codebooks. It still demands (3); that constraint is intrinsic to any scheme that harnesses the analog superposition.

,

Common Mistake: XOR $\neq$ Sum in General

Mistake:

Assuming that PNC's "relay decodes $u_A \oplus u_B$ " generalises to "relay decodes $u_A + u_B$ " for higher-order constellations. This confuses the binary-field XOR with the integer-ring sum.

Correction:

In binary: $u_A \oplus u_B = (u_A + u_B) \bmod 2$ . For binary messages, XOR and mod-2 sum are the same. For general integer messages, the relay decodes $(u_A + u_B) \bmod \Lambda_s$ — not XOR. The user-downstream subtraction rule becomes $u_B = ((u_A + u_B) - u_A) \bmod \Lambda_s$ , the modular inverse of addition, not XOR. For QPSK: XOR bit-by-bit gives correct decoding only if Gray coding and specific modulation mappings align — otherwise one must track the integer sum. For lattice-CF over $\Lambda_c$ with fundamental region $\mathcal{V}(\Lambda_s)$ , the correct operation is always modulo-lattice sum, which specialises to XOR only for $\Lambda_s = 2\mathbb{Z}$ .

Quick Check

What is the theoretical rate limit of PNC with BPSK signalling on the symmetric Gaussian TWRC, regardless of SNR?

$\tfrac{1}{2} \log_2(1 + \text{SNR})$ per user — the single-user AWGN capacity.

$1$ bit per channel use per user — the BPSK entropy cap.

$2$ bits per channel use per user — the MAC sum-rate cap.

There is no rate limit; PNC matches lattice-CF at all SNRs.

Correction:

1

bit per channel use per user — the BPSK entropy cap.

Correct. BPSK carries at most $\log_2(2) = 1$ bit per symbol. PNC decodes the XOR of two BPSK symbols, which is also binary. So PNC-BPSK is rate-limited to $1$ bit per channel use per user — even at infinite SNR.

Physical-layer network coding (PNC)

A two-slot two-way relay protocol (Zhang-Liew-Lam 2006) in which the relay decodes $u_A \oplus u_B$ directly from the analog superposition $x_A + x_B + w$ — without separating the individual messages. Formally the BPSK / $\Lambda_s = 2\mathbb{Z}$ special case of Nazer-Gastpar compute-and-forward with integer coefficient $\mathbf{a} = (1, 1)^T$ . Rate-capped at $1$ bit per channel use per user.

Key Takeaway

Physical-layer network coding (Zhang-Liew-Lam 2006) is the BPSK / binary-lattice instance of Nazer-Gastpar compute-and- forward with integer coefficient $\mathbf{a} = (1, 1)^T$ . It achieves the same two-slot TWRC throughput advantage as lattice- CF, with the simplification of discrete hard-decision decoding — at the cost of a $1$ -bit-per-channel-use rate ceiling. PNC's enduring insight is that the analog superposition is a computational resource: the wireless medium performs network coding for free, if the code is chosen to align with the channel's additive structure.

Physical-Layer Network Coding

From Zhang-Liew-Lam's MobiCom to Nazer-Gastpar's Theorem

Definition: Physical-Layer Network Coding (PNC)

Theorem: PNC Is the a=(1,1)T\mathbf{a} = (1, 1)^Ta=(1,1)T Special Case of CF

Lattice framing of BPSK

Analog sum at the relay

MMSE coefficient for binary lattice

Rate comparison

Conclusion: PNC as the degenerate CF case

Historical Note: PNC at MobiCom 2006: A 4-Page Wake-Up Call

Two-Way Relay Throughput: Routing vs. Digital NC vs. PNC

Parameters

Example: PNC BPSK Error Probability

PNC decision rule at the relay

Error probability by Q-function

PNC rate

Lattice-CF rate at same SNR

Comparison

Where PNC Fails: Asymmetric Channels and Large Constellations

Common Mistake: XOR ≠\neq= Sum in General

Quick Check

Physical-layer network coding (PNC)

Key Takeaway

Definition:
Physical-Layer Network Coding (PNC)

Theorem: PNC Is the $\mathbf{a} = (1, 1)^T$ Special Case of CF

Common Mistake: XOR $\neq$ Sum in General