Chapter Summary

Chapter Summary

Key Points

• 1.

  The Nazer-Gastpar framework: decode functions, not messages. On a $K$-user Gaussian MAC-relay channel $\mathbf{y} = \sum_k h_k \mathbf{x}_k + \mathbf{w}$, the relay can decode the modulo-lattice linear combination $\sum_k a_k \mathbf{u}_k \bmod \Lambda_s$ for any integer vector $\mathbf{a} \in \mathbb{Z}^K$, without ever decoding individual messages. Lattices are the natural primitive because they are closed under integer linear combinations: if $\mathbf{u}_1, \mathbf{u}_2 \in \Lambda_c$ then $a_1 \mathbf{u}_1 + a_2 \mathbf{u}_2 \in \Lambda_c$ automatically. The framework unifies physical-layer network coding, integer-forcing, and distributed source coding under a single coding principle.

• 2.

  The Nazer-Gastpar computation rate. The central theorem (Thm. TNazer-Gastpar Computation Rate) gives $R(\mathbf{h}, \mathbf{a}) = \tfrac{1}{2} \log_2^+ \big( 1 / (\|\mathbf{a}\|^2 - \text{SNR}(\mathbf{h}^T \mathbf{a})^2 / (1 + \text{SNR}\|\mathbf{h}\|^2)) \big)$, achieved by a shared nested Erez-Zamir codebook $\Lambda_c \supset \Lambda_s$, MMSE scaling $\alpha^* = \text{SNR} (\mathbf{h}^T \mathbf{a})/(1 + \text{SNR}\|\mathbf{h}\|^2)$ at the relay, and modulo-$\Lambda_s$ decoding to the nearest $\Lambda_c$ point. The rate is high when $\mathbf{a}$ is a close integer approximation to $\mathbf{h}$ (Diophantine alignment); it degenerates to the single-user AWGN capacity in the $K = 1$ case.

• 3.

  Two-way relay: within 1/2 bit of capacity. On the symmetric Gaussian TWRC, Nam-Chung-Lee (Thm. TNam-Chung-Lee: CF Is Within 1/2 Bit of TWRC Capacity) proved that 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})$, which is within $\tfrac{1}{2}$ bit of the cut-set upper bound for all SNR. This doubles the throughput of the classical four-slot routing protocol (two slots for MA + BC instead of four for sequential uplink- downlink) and strictly outperforms amplify-and-forward and decode-and-forward at moderate-to-high SNR. The key move: the relay decodes $\mathbf{u}_A + \mathbf{u}_B \bmod \Lambda_s$ in one slot, then broadcasts it, and each user subtracts its own message to recover the other's.

• 4.

  Physical-layer network coding is CF with $\\mathbf{a} = (1,1)$ and BPSK. Zhang-Liew-Lam's 2006 MobiCom PNC protocol — relay extracts the XOR $u_A \oplus u_B$ directly from the analog BPSK superposition — is the $\Lambda_s = 2\mathbb{Z}$ / binary special case of the Nazer-Gastpar framework (Thm. $\mathbf{a} = (1, 1)^T$ Special Case of CF" data-ref-type="theorem">TPNC Is the $\mathbf{a} = (1, 1)^T$ Special Case of CF). PNC is rate-capped at $1$ bit per channel use per user by its BPSK codebook; lattice- CF with higher-dimensional nested lattices breaks this cap and approaches Gaussian capacity. PNC was the conceptual breakthrough — "the wireless medium is a computational resource" — and lattice-CF is its rigorous generalisation.

• 5.

  Integer-forcing: CF as a MIMO receiver. Ordentlich-Erez- Nazer (2014) showed that CF applied row-by-row to a $K \times K$ MIMO channel — decode $K$ linearly independent integer combinations and invert the integer matrix $\mathbf{A} \in \mathbb{Z}^{K \times K}$ — achieves the MIMO sum-capacity within a constant gap (Thm. TInteger-Forcing Achieves a Constant Gap to MIMO Sum-Capacity). Integer-forcing strictly dominates zero-forcing on ill- conditioned channels because the integer inverse $\mathbf{A}^ {-1}$ is exact (no noise enhancement), unlike $\mathbf{H}^{-1}$. The main cost is the integer-coefficient search, which is an SVP instance.

• 6.

  The integer-coefficient search is NP-hard. Finding $\mathbf{a}^*(\mathbf{h}) = \arg\max_{\mathbf{a} \in \mathbb{Z}^K} R(\mathbf{h}, \mathbf{a})$ reduces to the shortest-vector problem (SVP) on an integer lattice with Gram matrix $\mathbf{G}_ {\rm ch}(\mathbf{h}) = \mathbf{I} - \text{SNR}\, \mathbf{h} \mathbf{h}^T/(1 + \text{SNR}\|\mathbf{h}\|^2)$. SVP is NP-hard in general (Ajtai 1996), but LLL reduction (Lenstra-Lenstra- Lovász 1982) gives a polynomial-time approximation good enough for $K \le 20$. Beyond that, heuristic SVP solvers or reduced-search CF (restrict $\|\mathbf{a}\|_\infty \le A_{\max}$) are used. Practical CF deployment has stayed at small $K$ as a result.

• 7.

  CF requires quasi-static channels and sample-level sync. The integer vector $\mathbf{a}$ is channel-dependent, so $\mathbf{h}$ must be constant over the coding block (coherence time $\ge n T_s$ — roughly $10$ ms at 30 kmh, $3$ GHz). Transmitters must be sample-aligned to within $T_s/10$ (roughly $3\,\mu$s for 5G NR 30-kHz SCS) for the analog superposition to land on a lattice point; frequency offsets must be below $1/(nT_s)$. These requirements are stringent enough that no major commercial standard (LTE, 5G NR, Wi-Fi 7) implements CF. Research prototypes (satellite relay, IAB test-beds) rely on GPS-disciplined clocks. 5G NR's integrated access and backhaul (Release 16) is a structural fit for CF but uses orthogonal multiplexing instead.

• 8.

  CF extends to interference, source coding, and beyond. Nazer-Gastpar's main application was the $K$-user Gaussian interference channel: each receiver treats the $K$ transmitters as a MAC and applies CF with a receiver-specific integer vector, achieving within-constant-gap of the Etkin-Tse-Wang sum-capacity bound — a lattice alternative to Cadambe-Jafar interference alignment. The Körner-Marton distributed source coding problem admits a lattice-CF interpretation with sensor-network applications. Integer-forcing on massive MIMO (Ch. 20) inherits the framework for high-dimensional receive beamforming. The compute-and-forward viewpoint — treat the wireless medium as a computational resource, not an interference source — is Nazer-Gastpar's most lasting legacy.