Prerequisites & Notation

Before You Begin

Chapter 16 is the operational payoff of the lattice theory built in Ch. 15. We now use lattices not as geometric curiosities but as coding primitives that actually achieve the AWGN capacity $C = \tfrac12 \log_2(1 + \text{SNR})$ . The mathematical cost is modest beyond Ch. 15: the main addition is a clean understanding of the MMSE estimator and of modulo arithmetic against a lattice. But the payoff is enormous — the mod- $\Lambda$ scheme of Erez and Zamir (2004) closes, with one algebraic construction, a gap Shannon left open in 1948: how to achieve capacity with a structured codebook. If any item below feels shaky, take the cross-reference before starting.

Lattices, generator matrices, fundamental volume, Voronoi region, packing/covering radius(Review ch15)
Self-check: Can you state the definition of a lattice $\Lambda \subset \mathbb{R}^n$ , compute $V(\Lambda) = |\det \mathbf{G}|$ , and describe the Voronoi region $\mathcal{V}(\Lambda)$ ?
Coset codes and the partition $ambda / ambda'$ (Review ch04)
Self-check: Given lattices $\Lambda' \subset \Lambda$ , can you explain the index $|\Lambda / \Lambda'|$ , identify cosets, and relate the fundamental volumes by $V(\Lambda') = |\Lambda/\Lambda'| V(\Lambda)$ ?
AWGN capacity $C = \tfrac12 \log_2(1 + \text{SNR})$ and Shannon's random-coding achievability(Review ch09)
Self-check: Can you state the AWGN capacity formula per real dimension and outline Shannon's random-Gaussian-codebook achievability argument?
MMSE estimation: the orthogonality principle and the scalar MMSE coefficient $\alpha = \mathrm{SNR}/(1+\mathrm{SNR})$ (Review ch03)
Self-check: For $y = x + w$ with $x \sim \mathcal{N}(0, P)$ and $w \sim \mathcal{N}(0, \sigma^2)$ , can you derive the MMSE estimator $\hat{x} = \alpha y$ with $\alpha = P/(P + \sigma^2)$ and explain why it is orthogonal to the error?
Tomlinson–Harashima precoding (ISI precoder via modulo arithmetic)(Review ch10)
Self-check: Can you recall the THP idea for known ISI: at the transmitter, subtract the known interference and reduce mod- $2M$ into a compact box? This is the scalar cousin of Costa's lattice DPC.
Complexity: NP-hardness, average-case polynomial algorithms, sphere-decoder search tree
Self-check: Can you explain the difference between worst-case and average-case complexity and why a branch-and-bound algorithm can beat the exponential worst case in practice?
Uniform distributions on bounded sets, moduli, and the crypto-lemma: if $\mathbf{d}$ is uniform on $\mathcal{V}(\Lambda)$ and independent of $\mathbf{x}$ , then $[\mathbf{x} + \mathbf{d}] \bmod \Lambda$ is uniform on $\mathcal{V}(\Lambda)$ , independent of $\mathbf{x}$ (Review ch04)
Self-check: Can you reproduce the one-line proof of the crypto-lemma via shift-invariance of the uniform distribution on $\mathcal{V}(\Lambda)$ ? This is the single most-used lemma in this chapter.

Notation for This Chapter

Lattice-theoretic symbols from Ch. 4 and Ch. 15 remain in force. The new symbols all circle around the Erez–Zamir construction: a fine coding lattice $\Lambda_c$ , a coarse shaping lattice $\Lambda_s \subset \Lambda_c$ , an MMSE coefficient $\alpha$ , and a dither $\mathbf{d}$ . The book-wide information-theoretic symbols (SNR $\text{SNR}$ , noise variance $\sigma^2$ , capacity $C$ , rate $R$ ) follow the global CM notation.

Symbol	Meaning	Introduced
$\Lambda_c$	Fine (coding) lattice; provides coding gain	s01
$\Lambda_s$	Coarse (shaping) lattice; $\Lambda_s \subset \Lambda_c$ ; provides shaping gain and power constraint	s01
$\Lambda_c / \Lambda_s$	Nesting quotient; the set of cosets of $\Lambda_s$ in $\Lambda_c$ ; indexed by integers $0, 1, \ldots, \|\Lambda_c/\Lambda_s\| - 1$	s01
$\mathcal{V}(\Lambda)$	Voronoi region (fundamental cell) of the lattice $\Lambda$ centred at the origin	s01
$\mathcal{C}$	Nested lattice code: $\mathcal{C} = \Lambda_c \cap \mathcal{V}(\Lambda_s)$	s01
$[\mathbf{y}] \bmod \Lambda$	Modulo-lattice reduction: the unique element of $\mathbf{y} + \Lambda$ inside $\mathcal{V}(\Lambda)$ , i.e., $\mathbf{y} - Q_\Lambda(\mathbf{y})$	s01
$Q_\Lambda(\mathbf{y})$	Nearest-neighbour quantiser to the lattice $\Lambda$ : $Q_\Lambda(\mathbf{y}) = \arg\min_{\boldsymbol{\lambda} \in \Lambda} \\|\mathbf{y} - \boldsymbol{\lambda}\\|$	s01
$R$	Code rate (bits per real dimension): $R = \tfrac{1}{n} \log_2 \|\Lambda_c / \Lambda_s\|$	s01
$P$	Second moment (average energy per dimension) of $\mathcal{V}(\Lambda_s)$ : $P = \tfrac{1}{n V(\Lambda_s)} \int_{\mathcal{V}(\Lambda_s)} \\|\mathbf{x}\\|^2 \, d\mathbf{x}$	s02
$G(\Lambda)$	Normalised second moment of $\Lambda$ : $G(\Lambda) = P(\Lambda) / V(\Lambda)^{2/n}$ ; a dimensionless shape factor with $G(\Lambda) \ge 1/(2 \pi e)$	s03
$\alpha$	MMSE scaling coefficient: $\alpha = \text{SNR} / (1 + \text{SNR}) = P / (P + \sigma^2)$	s02
$\mathbf{d}$	Dither vector, uniform on $\mathcal{V}(\Lambda_s)$ and independent of the message	s02
$\mathbf{s}$	Known interference (state) at the transmitter, in the dirty-paper channel $\mathbf{y} = \mathbf{x} + \mathbf{s} + \mathbf{w}$	s04
$\gamma_s(\Lambda)$	Shaping gain of $\Lambda$ over the cube: $\gamma_s(\Lambda) = G(\mathbb{Z}^n) / G(\Lambda) = (1/12) / G(\Lambda)$ ; upper-bounded by $\pi e / 6 \approx 1.53$ dB	s03
$\gamma_c(\Lambda)$	Coding gain of $\Lambda$ over $\mathbb{Z}^n$ : $d_{\min}^2(\Lambda) / V(\Lambda)^{2/n}$ normalised to $\mathbb{Z}^n$	s03
$P_e^{\mathrm{lat}}$	Lattice-decoding error probability: $\Pr[\hat{\mathbf{x}} \ne \mathbf{x}]$ when $\hat{\mathbf{x}} = Q_{\Lambda}(\mathbf{y})$	s05

← Ch 15 Nested Lattice Codes