Exercises

$\Lambda_c = 2\mathbb{Z}^2$ (odd-integer coset absorbed into the dither). $V(\Lambda_c) = 4$.

$\Lambda_s = 16 \mathbb{Z}^2$ with $V(\Lambda_s) = 256$. $|\mathcal{C}| = V(\Lambda_s)/V(\Lambda_c) = 256/4 = 64$. Matches 64-QAM.

$R = (1/2) \log_2 64 = 3$ bits per real dimension (i.e., $6$ bits per complex symbol). $\blacksquare$

Let $\mathbf{x}' = [\mathbf{x}] \bmod \Lambda = \mathbf{x} - \mathbf{q}_x$ with $\mathbf{q}_x \in \Lambda$, and similarly $\mathbf{y}' = \mathbf{y} - \mathbf{q}_y$ with $\mathbf{q}_y \in \Lambda$.

$[\mathbf{x}' + \mathbf{y}'] \bmod \Lambda = \mathbf{x}' + \mathbf{y}' - Q_\Lambda(\mathbf{x}' + \mathbf{y}')$. Also $\mathbf{x} + \mathbf{y} = \mathbf{x}' + \mathbf{y}' + \mathbf{q}_x + \mathbf{q}_y$, so $[\mathbf{x} + \mathbf{y}] \bmod \Lambda = \mathbf{x}' + \mathbf{y}' + (\mathbf{q}_x + \mathbf{q}_y) - Q_\Lambda( \mathbf{x}' + \mathbf{y}' + \mathbf{q}_x + \mathbf{q}_y)$.

Since $\mathbf{q}_x + \mathbf{q}_y \in \Lambda$, translating a point by a lattice vector and then quantising to the nearest lattice point shifts the quantiser output by the same lattice vector: $Q_\Lambda(\mathbf{z} + \boldsymbol{\lambda}) = Q_\Lambda(\mathbf{z}) + \boldsymbol{\lambda}$. Therefore $[\mathbf{x} + \mathbf{y}] \bmod \Lambda = \mathbf{x}' + \mathbf{y}' - Q_\Lambda(\mathbf{x}' + \mathbf{y}')$, which equals $[\mathbf{x}' + \mathbf{y}'] \bmod \Lambda$. $\blacksquare$

$\mathbb{E}[(X - \alpha Y)^2] = \mathbb{E}[X^2] - 2\alpha \mathbb{E}[XY] + \alpha^2 \mathbb{E}[Y^2] = P - 2 \alpha P + \alpha^2(P + \sigma^2)$.

$d/d\alpha = -2 P + 2 \alpha(P + \sigma^2) = 0 \Rightarrow \alpha = P/(P + \sigma^2)$.

Plugging back: $\mathbb{E}[(X - \alpha Y)^2] = P - 2 \alpha P + \alpha^2 (P + \sigma^2) = P - \alpha P (2 - \alpha (1 + \sigma^2/P))$. Simplifying: $P(1 - 2 \alpha + \alpha (\alpha + \alpha \sigma^2/P)) = P(1 - \alpha) = P \cdot \sigma^2/(P + \sigma^2) = \alpha \sigma^2$. $\blacksquare$

$\alpha = 100/(101) \approx 0.990$.

$C = \tfrac12 \log_2(1 + 100) = \tfrac12 \log_2 101 \approx 3.33$ bits per real dimension.

Uncoded 16-QAM has $R = 2$ bits per real dimension (fixed by the constellation). The SNR required for $P_b = 10^{-5}$ is $\text{SNR} \approx 14$ dB, not $20$. At $20$ dB, $P_b$ for 16-QAM is $\sim 10^{-10}$, so well below target. Gap to Shannon at $R = 2$: $\tfrac12 \log_2 5 = 1.16$ dB for the Shannon $\text{SNR}$ of $\text{SNR} = 15 = 11.76$ dB, so uncoded 16-QAM at $R = 2$ operates $20 - 11.76 = 8.24$ dB above the Shannon limit. Erez–Zamir mod-$\Lambda$ closes this $8.24$ dB gap. $\blacksquare$

Condition on $\mathbf{x} = \mathbf{x}_0$. The conditional density of $\mathbf{x}_0 + \mathbf{d}$ is the uniform density on $\mathbf{x}_0 + \mathcal{V}(\Lambda)$: $f_{\mathbf{x}_0 + \mathbf{d}}(\mathbf{z}) = 1/V(\Lambda)$ for $\mathbf{z} \in \mathbf{x}_0 + \mathcal{V}(\Lambda)$ and $0$ elsewhere.

The set $\mathbf{x}_0 + \mathcal{V}(\Lambda)$ is a translated Voronoi region, hence a fundamental region of $\Lambda$ (any translate of a fundamental region is a fundamental region). It tiles $\mathbb{R}^n$ under $\Lambda$-translation.

The map $\mathbf{z} \mapsto [\mathbf{z}] \bmod \Lambda$ is a bijection from any fundamental region to $\mathcal{V}(\Lambda)$ that preserves Lebesgue measure. So the conditional density of $[\mathbf{x}_0 + \mathbf{d}] \bmod \Lambda$ is $1/V(\Lambda)$ on $\mathcal{V}(\Lambda)$, i.e., uniform.

The conditional distribution is the same uniform distribution for every $\mathbf{x}_0$, so $[\mathbf{x} + \mathbf{d}] \bmod \Lambda$ is independent of $\mathbf{x}$. $\blacksquare$

$\mathbb{E}[\|\mathbf{z}\|^2]/n = (1 - \alpha)^2 \mathbb{E}[\| \mathbf{d}\|^2]/n + \alpha^2 \mathbb{E}[\|\mathbf{w}\|^2]/n = (1-\alpha)^2 P + \alpha^2 \sigma^2$.

$(1 - \alpha) = \sigma^2/(P + \sigma^2)$, so $(1-\alpha)^2 P = P {\sigma^2}^{2} / (P + \sigma^2)^2$. $\alpha^2 \sigma^2 = P^2 \sigma^2/(P+\sigma^2)^2$. Sum: $P \sigma^2/(P + \sigma^2)^2 \cdot(\sigma^2 + P) = P \sigma^2/(P + \sigma^2) = \alpha \sigma^2$. $\blacksquare$

Per-dimension second moment of $\mathbf{u}$ uniform on $[-1/2, 1/2]^n$ is $\mathbb{E}[u_i^2] = \int_{-1/2}^{1/2} u^2 du = 1/12$.

$V(\mathbb{Z}^n) = 1$, so $G(\mathbb{Z}^n) = P/V^{2/n} = (1/12)/1 = 1/12$ for every $n$.

$\gamma_s(\mathbb{Z}^n) = G(\mathbb{Z}^n)/G(\mathbb{Z}^n) = 1$, i.e., $0$ dB. The cube is the reference. $\blacksquare$

$\pi e / 6 \approx 1.5330$, so $10 \log_{10}(1.533) = 1.853$ dB. Wait — this is closer to $\approx 1.85$, not the often- quoted $1.53$ dB. The $1.53$ figure is the natural-log equivalent $\ln(\pi e/6) \cdot 10/\ln 10 \cdot 1/2 = 1.533/2 \cdot 4.343 \approx 3.33$ — hmm.

Let me redo: the standard $1.53$ dB is the factor $\pi e/6$ expressed as $10 \log_{10}(\pi e / 6)$ where $\pi e / 6 = 2.71828 \cdot 3.14159/6 = 1.4234$... actually $\pi e = 8.5397$, $\pi e / 6 = 1.4233$, $10 \log_{10}(1.4233) = 1.533$ dB.

The key: $\pi e = 8.5397$, so $\pi e / 6 = 1.4233$ and $10 \log_{10}(1.4233) = 1.533$ dB. This is the shaping gain ceiling.

Shannon: $\tfrac12 \log_2(101) = 3.326$ bits/real dim. Poltyrev: $\tfrac12 \log_2(100/(1.4233)) = \tfrac12 \log_2 (70.26) = 3.068$ bits/real dim. Gap: $3.326 - 3.068 = 0.258$ bits/real dim.

At $20$ dB, $\tfrac12 \log_2(1.4233) = 0.258$ bits/real dim = $1.533$ dB of SNR gap at the same rate. This is the shaping gap — the exact dB by which a cubic-shaped (Poltyrev-optimal) lattice falls short of Shannon.

The gap between Shannon and Poltyrev capacities is exactly $1.53$ dB for any SNR $> 0$ (take the limit: Shannon $-$ Poltyrev $= \tfrac12 \log_2((1 + \text{SNR})/\text{SNR} \cdot (1.4233)) \to \tfrac12 \log_2(1.4233) = 0.258$ bits as $\text{SNR} \to \infty$, which is $1.533$ dB). The Erez–Zamir scheme closes this $1.53$ dB by using a shaping lattice $\Lambda_s$ with $G(\Lambda_s) \to 1/(2\pi e)$ — reducing the normalised second moment from the cube's $1/12$ to the ball's limit. $\blacksquare$

$R_{\text{naïve}} = \tfrac12 \log_2(1 + P/(10 + 0.1)) = \tfrac12 \log_2(1 + 0.099) \approx 0.0682$ bits/real dim.

$R_{\text{DPC}} = \tfrac12 \log_2(1 + 1/0.1) = \tfrac12 \log_2 11 \approx 1.731$ bits/real dim.

Rate gap: $1.731 - 0.068 = 1.663$ bits/real dim ≈ $96\%$ loss. The DPC advantage is massive in this regime. As $\|\mathbf{s}\|^2 \to \infty$, the naïve rate tends to $0$ while DPC remains at the clean-channel $1.731$. The non-causal knowledge of $\mathbf{s}$ at the transmitter is worth arbitrarily many bits when interference dominates. $\blacksquare$

$\mathbf{G} = \mathbf{Q} \mathbf{R}$. Since $\mathbf{G}$'s columns have equal norm $1$, $\mathbf{Q}$ is orthogonal and $\mathbf{R}$ is upper-triangular. A direct computation gives $\mathbf{Q} = \mathbf{G}$ (already orthogonal here after normalisation), $\mathbf{R} = \mathbf{I}$.

Apply QR-rotated received: $\mathbf{y}' = \mathbf{Q}^T \mathbf{y} = (0.6/\sqrt{2} - 0.8/\sqrt{2}, 0.6/\sqrt{2} + 0.8/\sqrt{2}) \cdot \sqrt{2} \approx (-0.14, 0.99)$ (after normalisation).

Babai: $\hat{u}_2 = \mathrm{round}(0.99) = 1$, $d_2 = 0.0001$. Then $\hat{u}_1 = \mathrm{round}(-0.14) = 0$, $d_1 = 0.02$. Total: $T = 0.02$. Closest $D_2$ point: $\mathbf{G} (0,1)^T = (1, 1)/\sqrt{2}$. Verify: $(0.6,-0.8) - (1/\sqrt{2}, 1/ \sqrt{2}) \approx (-0.11, -1.51)$, norm $\approx 1.51$. Hmm — might not be optimal. Try $\mathbf{G}(0,0)^T = (0,0)$: distance $\sqrt{0.6^2 + 0.8^2} = 1.0$ — smaller!

Revise: $\mathbf{G}(0,0)^T = (0,0)$ at distance $1.0$ is closer than $\mathbf{G}(0,1)^T$ at $1.51$. The correct closest $D_2$ point is $(0, 0)^T$.

Sphere decoder: $\approx 4$ norm evaluations + QR overhead = $\sim 10$ operations. Brute force: $5 \times 5 = 25$ candidates to check, each requiring a norm evaluation — $\sim 50$ operations. The sphere decoder is faster even at this tiny dimension; the advantage grows exponentially with $n$. $\blacksquare$

$\mathbf{z} = \mathbf{z}_{\text{d}} + \mathbf{z}_{\text{g}}$ where $\mathbf{z}_{\text{d}} = (1-\alpha)(-\mathbf{d})$ has bounded norm ($\|\mathbf{z}_{\text{d}}\| \le (1-\alpha) R(\Lambda_s)$ where $R$ is the covering radius of $\Lambda_s$), and $\mathbf{z}_{\text{g}} = \alpha \mathbf{w}$ is Gaussian with per-dim variance $\alpha^2 \sigma^2$.

For the error event to occur, $\mathbf{z}$ must leave the Voronoi region of $\Lambda_c$. The Gaussian component alone has the tightest tails (Gaussian > bounded for a given variance), so the error probability is dominated by the Gaussian part: $\Pr[\mathbf{z} \notin \mathcal{V}(\Lambda_c)] \le \Pr[\mathbf{z}_{\text{g}} \notin \mathcal{V}(\Lambda_c) - \mathbf{z}_{\text{d}}]$ uniformly over $\mathbf{z}_{\text{d}}$.

Erez–Zamir Lemma 6: the cumulant-generating function of $\mathbf{z}$ is dominated (componentwise) by that of a Gaussian of per-dim variance $\alpha \sigma^2 = (1- \alpha)^2 P + \alpha^2 \sigma^2$. Hence $$P_e(\Lambda_c, \mathbf{z}\text{-noise}) \;\le\; P_e(\Lambda_c, \mathcal{N}(0, \alpha \sigma^2 \mathbf{I})).$$ The right-hand side vanishes exponentially for any rate below the Poltyrev capacity at effective noise variance $\alpha \sigma^2$. $\blacksquare$

Two-user degraded Gaussian BC. User 1 (strong) sees $\text{SNR}_{1} = 1/0.01 = 100$; User 2 (weak) sees $\text{SNR}_{2} = 1/1 = 1$.

Allocate $P_2$ power to user 2's signal $\mathbf{x}_2$. Rate: $R_2 = \tfrac12 \log_2(1 + P_2/(P_1 + \sigma_2^2))$ — the user 2 signal treats user 1's signal plus noise as interference.

User 1's signal $\mathbf{x}_1$ is encoded via DPC against the (already-encoded) $\mathbf{x}_2$. By the DPC theorem, $R_1 = \tfrac12 \log_2(1 + P_1/\sigma_1^2)$ — no interference penalty from $\mathbf{x}_2$.

Sum-rate: $R_1 + R_2 = \tfrac12 \log_2(1 + P_1/\sigma_1^2) + \tfrac12 \log_2(1 + P_2/(P_1 + \sigma_2^2))$. Maximise over $P_1 + P_2 = 1$. The two-user BC sum-capacity is $\tfrac12 \log_2(1 + 1/\sigma_1^2) = \tfrac12 \log_2(101) \approx 3.33$ bits/real dim — achieved by $P_1 = 1, P_2 = 0$ (all power to the stronger user).

More interestingly, for general power allocations, the achievable rate region is $R_1 \le \tfrac12 \log_2(1 + \beta P/\sigma_1^2)$, $R_2 \le \tfrac12 \log_2(1 + (1-\beta) P/(\beta P + \sigma_2^2))$ for $\beta \in [0, 1]$. This is the full BC capacity region (Cover–van der Meulen).

The DPC allows the base station to support weak users without harming strong users — the weak-user interference is pre-cancelled via DPC for the strong user. This is exactly the principle behind MU-MIMO vector precoding (Weingarten–Steinberg–Shamai 2006). $\blacksquare$

At layer $i$, the partial-sum cost is $T + (y'_i - \sum_{j>i} R_{ij} u_j - R_{ii} u_i)^2 = T + (R_{ii})^2 (u_i - \hat{u}_i)^2$ — increasing in $|u_i - \hat{u}_i|$.

The zigzag $\hat{u}_i, \hat{u}_i + 1, \hat{u}_i - 1, \hat{u}_i + 2, \hat{u}_i - 2, \ldots$ visits candidates in strictly increasing order of $|u_i - \hat{u}_i|$, hence in increasing order of layer cost.

Branch-and-bound prunes when the partial sum exceeds the current best. Since costs are visited in increasing order, once a cost exceeds the best, all subsequent costs also do (they are monotonically larger). Hence the zigzag termination is the earliest possible: any other order visits some candidates out of cost order, wasting evaluations on costs larger than the eventual prune threshold.

The optimality here is layer-local; global tree pruning depends on the initial sphere radius $r$ and on interactions across layers. Schnorr–Euchner's order is locally optimal but not globally optimal (exact global optimality would require an oracle for the optimal codeword's cost). In practice, initializing $r$ via the Babai estimate gets within a small constant of the optimal pruning. $\blacksquare$

At $R = 2$: $\text{SNR}_{\text{Shannon}} = 2^{2R} - 1 = 15 = 11.76$ dB.

With $\Lambda_{24}$ shaping (gain $1.03$ dB vs cube's $0$ dB), the shaping gap is $1.53 - 1.03 = 0.50$ dB. An ideal Erez–Zamir scheme with $\Lambda_{24}$ shaping achieves $R = 2$ at $\text{SNR} = 11.76 + 0.50 = 12.26$ dB — $0.50$ dB above Shannon, due to the finite-dim shaping limit.

A Poltyrev-optimal $\Lambda_c$ in dimension $24$ achieves the Poltyrev capacity, meaning it has zero coding-gap asymptotically. In practice, a dimension-$24$ lattice can be within $\sim 0.5$ dB of Poltyrev capacity. Total SNR gap: $0.50 + 0.5 = 1.00$ dB vs Shannon.

In the limit $n \to \infty$, both coding and shaping gaps close to zero; in finite dimension $24$, roughly half of the $1.53$ dB shaping gap is recovered, and most of the coding gap is recovered, giving a total of $\sim 1$ dB from Shannon. This matches the published numerics for LDPC-lattice constructions in dimension $24$–$1000$ (Sommer–Feder–Shalvi 2008). $\blacksquare$

Suppose the transmitter uses dither $\mathbf{d}$ and the receiver uses $\mathbf{d}' = \mathbf{d} + \boldsymbol{\delta}$. The decoder's mod reduction is $[\alpha \mathbf{y} + \mathbf{d}'] \bmod \Lambda_s$ instead of the correct $[\alpha \mathbf{y} + \mathbf{d}] \bmod \Lambda_s$.

The effective noise $\mathbf{z}' = \mathbf{z} + \boldsymbol{\delta}$, where $\mathbf{z}$ is the original effective noise. Assuming $\boldsymbol{\delta}$ independent of $\mathbf{z}$: $\mathbb{E}[\|\mathbf{z}'\|^2]/n = \alpha \sigma^2 + \|\boldsymbol{\delta}\|^2/n$.

Rate loss $\approx -\tfrac12 \log_2(1 + \|\boldsymbol{\delta}\|^2/ (n \alpha \sigma^2))$ bits/real dim. For small errors (typical synchronisation), this is negligible. For catastrophic errors ($\boldsymbol{\delta}$ on the scale of the constellation), the scheme breaks down entirely — error probability $\to 1/2$.

Dither synchronisation is a real concern in practice. It is typically handled via a shared seed (as in 3GPP scrambling codes) or via a pilot preamble that the receiver uses to lock onto the pseudo-random dither sequence. A $0.1$ dB synchronisation budget is typical in LAST-code implementations (Ch. 17). $\blacksquare$

$R = 4$: $\text{SNR}_{\text{Shannon}} = 255 = 24.1$ dB.

At BER $10^{-5}$: $\text{SNR} \approx 28$ dB. Gap: $28 - 24.1 = 3.9$ dB. But: this is with no coding. With a rate-1 FEC code (no error correction), uncoded 256-QAM is bounded by its own constellation; to reach the Shannon limit we'd need infinite modulation order or perfect coding.

Cubic shaping: $\Lambda_s = M\mathbb{Z}^n$, $\gamma_s = 0$ dB. Erez–Zamir with perfect $\Lambda_c$: $\text{SNR} = \text{SNR}_{\text{Shannon}} + 1.53$ dB $= 25.6$ dB. Gap to Shannon: $1.53$ dB (the unresolved shaping gap).

$E_8$ shaping: $\gamma_s = 0.66$ dB. Erez–Zamir with perfect $\Lambda_c$: $\text{SNR} = 24.1 + 1.53 - 0.66 = 24.97$ dB. Gap to Shannon: $0.87$ dB.

Moving from uncoded 256-QAM to cubic-shaping Erez–Zamir saves ~$2.4$ dB; moving to $E_8$-shaping saves another $0.66$ dB, for total ~$3$ dB improvement. The remaining $0.87$ dB requires Ch. 15's Leech-lattice shaping and asymptotic-dimension arguments — the Rogers/Poltyrev limit. $\blacksquare$

The lattice decoder finds $\hat{\mathbf{c}} = \arg \min_{\boldsymbol{\lambda} \in \Lambda_c} \|\mathbf{r} - \boldsymbol{\lambda}\|^2$ with $\mathbf{r} \in \mathcal{V}(\Lambda_s)$. The closest point in $\Lambda_c$ to a point in $\mathcal{V}(\Lambda_s)$ is typically in $\mathcal{V}(\Lambda_s)$ itself — i.e., in $\mathcal{C}$.

Only when the effective noise $\|\mathbf{z}\|$ exceeds the covering radius $R(\Lambda_s)$, in which case the closest $\Lambda_c$ point may lie outside $\mathcal{V}(\Lambda_s)$. Probability of this: $\Pr[\|\mathbf{z}\| > R(\Lambda_s)]$.

At any rate $R < R^*_{\text{EZ}} = \tfrac12 \log_2(1 + \text{SNR})$, $\Pr[\|\mathbf{z}\| > R(\Lambda_s)]$ vanishes exponentially in $n$ (by the Erez–Zamir MMSE inflation lemma). Hence lattice decoder and message-set decoder agree with high probability; their rates are the same.

At the capacity, the two decoders diverge in their asymptotic error probability — the lattice decoder's error probability does not quite match the message-set decoder's. The gap, however, is sub-exponentially small. Erez–Litsyn–Zamir (2005) showed the lattice decoder achieves the capacity of the unconstrained AWGN (Poltyrev) channel, which coincides with the message-set capacity of the mod-$\Lambda_s$ channel. $\blacksquare$

The capacity-achieving power allocation is $P_i^* = (1/\lambda - \sigma_i^2)^+$ where $\lambda$ is chosen to meet the total power constraint $\sum_i P_i = N P$. The capacity is $\sum_i \tfrac12 \log_2(1 + P_i^*/\sigma_i^2)$.

Apply the Erez–Zamir scheme to each sub-channel $i$ independently: nested lattices $(\Lambda_{c,i}, \Lambda_{s,i})$ with second moment $P_i^*$, MMSE coefficient $\alpha_i = P_i^*/(P_i^* + \sigma_i^2)$, dither $\mathbf{d}_i$ uniform on $\mathcal{V}(\Lambda_{s,i})$.

Each sub-channel achieves $\tfrac12 \log_2(1 + P_i^*/ \sigma_i^2)$ bits/real dim (Erez–Zamir). Summing: total rate = $\sum_i \tfrac12 \log_2(1 + P_i^*/\sigma_i^2) =$ water-filling capacity. $\blacksquare$

A single $N$-dimensional lattice with Voronoi region anisotropically scaled (second-moment profile matching the water-filling profile) also works. In practice, the per-sub-channel scheme is simpler; the joint scheme can give marginal shaping-gain improvements. This construction is the lattice-code version of OFDM's adaptive bit-loading — see Ch. 9 of this book for BICM-OFDM, or Ch. 17 of the MIMO book for the MIMO- parallel-stream equivalent.

Step 1: $u \mapsto \mathbf{c}(u) \in \mathcal{C}$: $O(n)$ lookup via the enumeration (typically via a finite-state machine). Step 2: $[\mathbf{c}(u) - \mathbf{d}] \bmod \Lambda_s$: requires $Q_{\Lambda_s}$. For $\Lambda_s = E_8$ or $E_8^k$, the quantiser is $O(n)$ (Forney 1989). Total encoder: $O(n)$.

Step 1: $\alpha \mathbf{y}$: $O(n)$. Step 2: $[\alpha \mathbf{y} + \mathbf{d}] \bmod \Lambda_s$: $O(n)$ via $E_8$ quantiser. Step 3: $\hat{\mathbf{c}} = Q_{\Lambda_c}(\mathbf{r})$: This is the CLP problem, dominated by QR ($O(n^3)$) + Schnorr- Euchner zigzag ($O(n^2)$ at high SNR on average). Total decoder: $O(n^3)$.

For poorly-conditioned $\Lambda_c$, pre-process once with LLL: $O(n^6)$ one-time cost. Per-symbol amortised cost: unchanged $O(n^3)$.

Random Gaussian codebook decoding: $O(2^{nR})$ per symbol — exponential. Erez–Zamir: $O(n^3)$ per symbol — polynomial. The lattice-code formulation provides an exponential speedup, and this is the practical reason the entire theory exists. $\blacksquare$