Prerequisites & Notation

Before You Begin

This chapter takes the lattice machinery of Chapters 15-16 — point- group lattices with their generator matrices and fundamental regions, nested codebooks $\Lambda_c \supset \Lambda_s$ on the AWGN channel, the Erez-Zamir mod- $\Lambda$ scheme with MMSE scaling that attains the Gaussian capacity — and shows that the same primitives give a dramatic gain in network settings. The Nazer-Gastpar compute-and-forward framework (2011) is the flagship application: instead of decoding individual users at a relay, the relay decodes a linear combination $\sum_k a_k \mathbf{u}_k$ directly from the analog superposition $y = \sum_k h_k \mathbf{x}_k + \mathbf{w}$ . Lattice codes make this possible because $\Lambda$ is closed under integer linear combinations. Readers need the Chapter 15 definition of a lattice and its fundamental region, the Chapter 16 construction of nested Erez-Zamir codebooks and the MMSE-scaling achievability of $C_{\rm AWGN}$ , and a working knowledge of $K$ -user Gaussian multiple-access channels. Familiarity with network coding (the XOR of packets in routing) helps contextualise §4 but is not required; the lattice derivation is self-contained.

Lattices, generator matrices, and fundamental regions(Review ch15)
Self-check: Can you state that a lattice $\Lambda \subset \mathbb{R}^n$ is a discrete additive subgroup of full rank, write it as $\Lambda = \{\mathbf{G} \mathbf{z} : \mathbf{z} \in \mathbb{Z}^n\}$ for some invertible generator matrix $\mathbf{G}$ , and identify the fundamental Voronoi region $\mathcal{V}(\Lambda)$ as the nearest- neighbour cell around $\mathbf{0}$ ?
Nested lattices and Erez-Zamir mod- $\Lambda$ coding(Review ch16)
Self-check: Can you describe the nested construction $\Lambda_s \subset \Lambda_c$ where $\Lambda_c$ is the fine (coding) lattice and $\Lambda_s$ is the coarse (shaping) lattice, define the coset codebook $\mathcal{C} = \Lambda_c \cap \mathcal{V}(\Lambda_s)$ , and explain why its rate is $R = \tfrac{1}{n} \log_2 |\mathcal{C}| = \tfrac{1}{n} \log_2 (V(\Lambda_s)/V(\Lambda_c))$ ?
MMSE-scaled mod- $\Lambda$ and AWGN capacity(Review ch16)
Self-check: Can you reproduce the Erez-Zamir-Zamir-Shamai achievability of $\tfrac{1}{2} \log_2 (1 + \text{SNR})$ : at the receiver, form $\alpha^* y \bmod \Lambda_s$ with $\alpha^* = \text{SNR}/(1 + \text{SNR})$ , decode to the nearest $\Lambda_c$ point in $\mathcal{V}(\Lambda_s)$ , and bound the effective noise variance by $\text{SNR}/(1 + \text{SNR})$ ?
$K$ -user Gaussian MAC and its capacity region(Review ch07)
Self-check: Can you state that the capacity region of the $K$ -user scalar Gaussian MAC $y = \sum_{k=1}^K h_k x_k + w$ with per-user power $P$ is the polytope $\sum_{k \in S} R_k \le \tfrac{1}{2} \log_2 (1 + P \sum_{k \in S} h_k^2)$ for every $S \subseteq \{1, \ldots, K\}$ , and recall that the sum-rate corner is achieved by successive interference cancellation?
Relay channels and cut-set bounds
Self-check: Can you state the three basic relay strategies — amplify-and- forward (relay retransmits a scaled $y$ ), decode-and-forward (relay decodes the message and re-encodes), and compress-and- forward (relay quantises $y$ and forwards the description) — and recall that the cut-set bound on the relay channel is tight for the degraded case (Cover-El Gamal 1979)?
Integer lattices $\mathbb{Z}^n$ and Gaussian integers $\mathbb{Z}[j]$ (Review ch15)
Self-check: Can you recognise $\mathbb{Z}^n$ as the simplest lattice, state that its fundamental region is the unit cube, and identify $\mathbb{Z}[j] = \mathbb{Z} + j\mathbb{Z}$ as the Gaussian integers — the natural "integer" lattice in $\mathbb{C} \cong \mathbb{R}^2$ where complex-valued integer coefficients $a_k \in \mathbb{Z}[j]$ live in the Nazer-Gastpar framework?
Shortest-vector problem and lattice reduction(Review ch15)
Self-check: Can you state the Shortest-Vector Problem (SVP): given a lattice $\Lambda$ via its generator matrix, find $\mathbf{v}^* = \arg\min_ {\mathbf{v} \in \Lambda \setminus \{0\}} \|\mathbf{v}\|$ ? And recall that SVP is NP-hard in general but is approximated in polynomial time by the LLL algorithm (Lenstra-Lenstra-Lovász 1982)?

Notation for This Chapter

Symbols specific to compute-and-forward and its network-coding applications. The Chapter 15-16 lattice notation (lattice $\Lambda$ , generator matrix $\mathbf{G}$ , fundamental region $\mathcal{V}(\Lambda)$ , nested codebook $\Lambda_c \supset \Lambda_s$ , MMSE coefficient $\alpha^*$ ) continues to apply and is not repeated here. The Chapter 1-7 single-user/MAC notation ( $\text{SNR}$ , noise $\mathbf{w}$ , Gaussian noise variance $\sigma^2$ ) also carries over.

Symbol	Meaning	Introduced
$K$	Number of users (transmitters) sharing the channel to a single relay	s01
$\mathbf{h} \in \mathbb{R}^K$	Channel vector from the $K$ transmitters to the relay; entry $h_k$ is the gain from user $k$ to the relay. Assumed real and known at the relay; complex extension is straightforward	s01
$\mathbf{x}_k \in \mathbb{R}^n$	Lattice codeword transmitted by user $k$ ; drawn from a nested Erez-Zamir codebook $\Lambda_c \cap \mathcal{V}(\Lambda_s)$ and satisfying the power constraint $\mathbb{E}[\\|\mathbf{x}_k\\|^2] \le n P$	s01
$\mathbf{u}_k \in \Lambda_c$	Lattice point (message) of user $k$ ; related to the transmitted codeword by dithering: $\mathbf{x}_k = [\mathbf{u}_k - \mathbf{d}_k] \bmod \Lambda_s$	s01
$\mathbf{a} \in \mathbb{Z}^K$	Integer coefficient vector that defines the linear combination the relay wants to decode: $\sum_{k=1}^K a_k \mathbf{u}_k \bmod \Lambda_s$	s01
$R(\mathbf{h}, \mathbf{a})$	Nazer-Gastpar computation rate: the rate at which the relay can reliably decode $\sum_k a_k \mathbf{u}_k \bmod \Lambda_s$ for channel $\mathbf{h}$ and integer coefficient vector $\mathbf{a}$	s02
$\alpha^*(\mathbf{h}, \mathbf{a})$	MMSE scaling coefficient at the relay: $\alpha^* = \text{SNR} \, \mathbf{h}^T \mathbf{a} / (1 + \text{SNR} \\|\mathbf{h}\\|^2)$ ; minimises the effective noise variance of $\alpha y - \sum_k a_k \mathbf{x}_k$	s02
$\log_2^+(x)$	Truncated logarithm: $\log_2^+(x) = \max(\log_2 x, 0)$ ; the Nazer-Gastpar rate is $0$ when the argument of the $\log$ falls below $1$	s02
$PNC$	Physical-layer network coding (Zhang-Liew-Lam 2006): the integer-coefficient- $(1,1)$ special case of the Nazer-Gastpar framework applied to the two-way relay channel	s04
$TWRC$	Two-way relay channel: two users $A, B$ exchange messages via a single relay $R$ ; the canonical $K = 2$ application of compute-and-forward	s03
$\mathbf{a}^*(\mathbf{h})$	Integer-coefficient optimiser: $\mathbf{a}^(\mathbf{h}) = \arg\max_{\mathbf{a} \in \mathbb{Z}^K \setminus \{0\}} R(\mathbf{h}, \mathbf{a})$ ; formulated as a shortest-vector problem on an $\alpha^$ -scaled channel lattice	s05
$N_{\rm eff}$	Effective noise variance at the relay after MMSE scaling and subtraction: $N_{\rm eff} = \\|\mathbf{a}\\|^2 - \text{SNR} (\mathbf{h}^T \mathbf{a})^2 / (1 + \text{SNR} \\|\mathbf{h}\\|^2)$ ; controls the computation rate via $R = \tfrac{1}{2} \log_2^+(1/N_{\rm eff})$	s02

← Ch 17 The Nazer-Gastpar Framework