Ferkans — Interactive Telecom Tutor

From QAM to Nested Lattices: Replacing Truncation with Modulo

A 16-QAM constellation is a $4 \times 4$ patch of $\mathbb{Z}^2$ . How do we pick the patch? Traditionally, we truncate — keep the lattice points inside a square and discard the rest. Truncation is crude: the square has more "real estate" than a random Gaussian codeword would typically need, and the constellation boundary radiates bits of outer information that the decoder must somehow handle.

Nested lattice codes replace truncation with a much cleaner operation: reduction modulo a coarser lattice. We pick a fine lattice $\Lambda_c$ (the "coding lattice") to hold the codewords, and a coarse lattice $\Lambda_s \subset \Lambda_c$ (the "shaping lattice") whose Voronoi region $\mathcal{V}(\Lambda_s)$ defines the power-constrained transmit region. The codebook is all fine-lattice points that fall inside this Voronoi cell: $\mathcal{C} \;=\; \Lambda_c \cap \mathcal{V}(\Lambda_s).$

The point is that this "modulo shaping" is algebraic. The constellation boundary is no longer a square or a cube; it is the Voronoi region of $\Lambda_s$ , which can be made as round as desired by choosing $\Lambda_s$ appropriately. The transmitter reduces its codeword mod $\Lambda_s$ ; the receiver undoes the modulo at the end of decoding. No outer information is radiated because no information is encoded in the boundary — the boundary is a lattice operation, not a pattern of bits. This is the single idea that will carry us to the AWGN capacity in s02.

,

Definition:
Nested Lattice Pair

A pair $(\Lambda_c, \Lambda_s)$ of lattices in $\mathbb{R}^n$ is called nested if $\Lambda_s \subset \Lambda_c$ : every shaping-lattice point is also a coding-lattice point. We call $\Lambda_c$ the fine (coding) lattice and $\Lambda_s$ the coarse (shaping) lattice.

The nesting index is $|\Lambda_c / \Lambda_s| \;=\; \frac{V(\Lambda_s)}{V(\Lambda_c)},$ which counts the number of distinct cosets of $\Lambda_s$ inside $\Lambda_c$ . The cosets are the equivalence classes of the relation $\mathbf{x} \sim \mathbf{x}'$ if $\mathbf{x} - \mathbf{x}' \in \Lambda_s$ .

Every lattice chain $\mathbb{Z}^n \supset 2 \mathbb{Z}^n \supset 4 \mathbb{Z}^n \supset \cdots$ is an example; the classic 4-PAM/16-QAM constellations are $\mathbb{Z} \cap \mathcal{V}(4 \mathbb{Z})$ and $\mathbb{Z}^2 \cap \mathcal{V}(4 \mathbb{Z}^2)$ respectively. Choosing $\Lambda_s$ other than scaled integers is where shaping gain enters.

,

Definition:
Modulo-Lattice Operation and Nearest-Neighbour Quantiser

For a lattice $\Lambda \subset \mathbb{R}^n$ , the nearest-neighbour quantiser is $Q_\Lambda(\mathbf{y}) \;=\; \arg \min_{\boldsymbol{\lambda} \in \Lambda} \|\mathbf{y} - \boldsymbol{\lambda}\|,$ defined (uniquely) for $\mathbf{y}$ outside the (measure-zero) boundary of the Voronoi tessellation.

The modulo-lattice reduction is $[\mathbf{y}] \bmod \Lambda \;=\; \mathbf{y} - Q_\Lambda(\mathbf{y}) \;\in\; \mathcal{V}(\Lambda),$ i.e., the unique representative of the coset $\mathbf{y} + \Lambda$ inside the Voronoi region. The operation is a group homomorphism from $(\mathbb{R}^n, +)$ to $(\mathcal{V}(\Lambda), \oplus)$ , where $\oplus$ denotes addition followed by mod- $\Lambda$ reduction.

Computing $Q_\Lambda$ is the closest-lattice-point problem — NP-hard in the worst case and the topic of s05. For $\Lambda = \mathbb{Z}^n$ it reduces to scalar rounding ( $O(n)$ ); for $\mathbb{Z}$ -dilates of $E_8$ or $\Lambda_{24}$ there are fast decoding algorithms (Forney's). For a generic integer lattice, one resorts to the sphere decoder.

,

Definition:
Nested Lattice Code

Given a nested lattice pair $\Lambda_s \subset \Lambda_c$ , the associated nested lattice code is $\mathcal{C} \;=\; \Lambda_c \cap \mathcal{V}(\Lambda_s).$ That is, $\mathcal{C}$ consists of all fine-lattice points that lie inside the Voronoi region of the coarse lattice around the origin. The code has $|\mathcal{C}| = |\Lambda_c / \Lambda_s|$ codewords, and we encode a message $u \in \{0, 1, \ldots, |\mathcal{C}| - 1\}$ by a fixed enumeration $u \mapsto \mathbf{x}_u \in \mathcal{C}$ .

The rate (bits per real dimension) is $R \;=\; R \;=\; \frac{1}{n} \log_2 |\mathcal{C}| \;=\; \frac{1}{n} \log_2 \frac{V(\Lambda_s)}{V(\Lambda_c)}.$

The codebook size is the nesting index. The rate — whose units are bits per real dimension — directly compares against the per-dimension AWGN capacity $\tfrac12 \log_2(1 + \text{SNR})$ . Chapter 15's coding-gain vocabulary ( $\gamma_c(\Lambda_c)$ , $\gamma_s(\Lambda_s)$ ) will re-enter in s03 as the two independent knobs controlling how close this $R$ gets to $\tfrac12 \log_2(1 + \text{SNR})$ .

,

Theorem: Codebook Size Equals Volume Ratio

For any nested lattice pair $\Lambda_s \subset \Lambda_c \subset \mathbb{R}^n$ , the number of fine-lattice points inside a Voronoi region of the coarse lattice is exactly the index: $|\Lambda_c \cap \mathcal{V}(\Lambda_s)| \;=\; |\Lambda_c / \Lambda_s| \;=\; \frac{V(\Lambda_s)}{V(\Lambda_c)}.$

Each coset of $\Lambda_s$ in $\Lambda_c$ has exactly one representative inside any fundamental region of $\Lambda_s$ — this is just the statement that a fundamental region tiles $\mathbb{R}^n$ under translations by $\Lambda_s$ . The Voronoi region is one such fundamental region, so each coset contributes exactly one point to $\Lambda_c \cap \mathcal{V}(\Lambda_s)$ .

Show Hint

Show that each coset of $\Lambda_s$ in $\Lambda_c$ has exactly one representative in $\mathcal{V}(\Lambda_s)$ .

Use the fact that the Voronoi region $\mathcal{V}(\Lambda_s)$ is a fundamental region (tiles $\mathbb{R}^n$ under $\Lambda_s$ -translations up to a measure-zero boundary).

Count cosets: $|\Lambda_c / \Lambda_s| = V(\Lambda_s) / V(\Lambda_c)$ from Ch. 4.

Proof

One representative per coset

Let $\mathbf{x} \in \Lambda_c$ . The translates $\{\mathbf{x} + \boldsymbol{\lambda}_s : \boldsymbol{\lambda}_s \in \Lambda_s\}$ form the coset $\mathbf{x} + \Lambda_s$ . Since $\mathcal{V}( \Lambda_s)$ is a fundamental region, exactly one of these translates lies in $\mathcal{V}(\Lambda_s)$ (ignoring the measure-zero boundary). Hence the map $\Lambda_c \cap \mathcal{V}(\Lambda_s) \;\to\; \Lambda_c / \Lambda_s$ sending a lattice point to its coset is a bijection.

Cosets count by volume

From Ch. 4 (or Ch. 15), the index $|\Lambda_c / \Lambda_s|$ of a sublattice in a lattice equals the ratio of fundamental volumes. Since $\Lambda_s \subset \Lambda_c$ , we have $V(\Lambda_s) \ge V(\Lambda_c)$ and $|\Lambda_c / \Lambda_s| \;=\; \frac{V(\Lambda_s)}{V(\Lambda_c)}.$

Conclude

Combining: $|\Lambda_c \cap \mathcal{V}(\Lambda_s)| = |\Lambda_c / \Lambda_s| = V(\Lambda_s) / V(\Lambda_c)$ . $\blacksquare$

,

Nested Lattice Pair $\Lambda_c \supset \Lambda_s$ in 2D

Visualisation of a 2D nested lattice pair: the fine coding lattice $\Lambda_c = \mathbb{Z}^2$ and a scaled shaping sublattice $\Lambda_s = N \mathbb{Z}^2$ (hexagonal-rotated for realism). The Voronoi cell $\mathcal{V}(\Lambda_s)$ is outlined; the codeword set $\mathcal{C} = \Lambda_c \cap \mathcal{V}(\Lambda_s)$ is highlighted; the other $\Lambda_c$ -points are shown faintly to emphasise the periodic lattice outside. Increasing the nesting ratio $N$ grows both $|\mathcal{C}|$ and the rate $R = \log_2 N^2 / 2 = \log_2 N$ bits per real dimension.

Parameters

Nesting ratio

|\Lambda_c/\Lambda_s|^{1/n}

5

Example: 16-QAM as a Nested Lattice Code

Express the 16-QAM constellation $\{\pm 1, \pm 3\}^2$ as a nested lattice code $\Lambda_c \cap \mathcal{V}(\Lambda_s)$ for some fine and coarse lattices. Compute the codebook size and the rate.

Solution

Fine lattice

The constellation points are $(\pm 1, \pm 3)^2$ — odd integers in both coordinates. They are the $\Lambda_c$ -lattice points $2 \mathbb{Z}^2 + (1, 1)^T$ . For the purposes of identifying $\Lambda_c$ we can shift: $\Lambda_c = 2 \mathbb{Z}^2$ with a coset offset $(1, 1)^T$ . (We absorb the offset into the dither in s02.)

Equivalently, set $\Lambda_c = 2 \mathbb{Z}^2$ ; the constellation lives on a coset of $\Lambda_c$ , not on $\Lambda_c$ itself, but this is a notational quibble.

Coarse lattice and Voronoi region

The constellation is bounded by the square $[-4, 4]^2$ , which is the Voronoi region of $\Lambda_s = 8 \mathbb{Z}^2$ . Hence $\mathcal{V}(\Lambda_s) = [-4, 4]^2$ with $V(\Lambda_s) = 64$ .

Verify the count

$|\Lambda_c / \Lambda_s| = V(\Lambda_s) / V(\Lambda_c) = 64 / 4 = 16$ , matching the $16$ QAM constellation points.

Rate

$R = \tfrac{1}{n} \log_2 |\mathcal{C}| = \tfrac{1}{2} \log_2 16 = 2$ bits per real dimension (i.e., $4$ bits per complex QAM symbol). This matches the nominal 16-QAM rate, as expected. $\blacksquare$

Why this is still a weak nested-lattice code

Both $\Lambda_c$ and $\Lambda_s$ are scaled cubes $\mathbb{Z}^n$ . Hence there is no coding gain relative to $\mathbb{Z}^n$ ( $\gamma_c = 1$ ) and no shaping gain relative to a cube ( $\gamma_s = 1$ ). 16-QAM sits at the reference point from which all lattice codes are measured. In s03 we will replace the cubic shaping by a Voronoi-shaped $\Lambda_s$ to harvest up to $1.53$ dB of shaping gain, and in Ch. 17 we will replace the cubic $\Lambda_c$ by a DMT-optimal LAST code.

,

Encoder and Decoder, in One Picture

With the definitions in place, the nested-lattice coding system is: $\underbrace{u \in \{0, \ldots, 2^{nR} - 1\}}_{\text{message}} \;\xrightarrow{\text{enumerator}}\; \underbrace{\mathbf{x} \in \mathcal{C}}_{\text{codeword in } \mathcal{V}(\Lambda_s)} \;\xrightarrow{\text{AWGN}}\; \mathbf{y} = \mathbf{x} + \mathbf{w} \;\xrightarrow{\text{decoder}}\; \hat{\mathbf{x}} \in \mathcal{C} \;\xrightarrow{\text{un-enumerator}}\; \hat{u}.$ The two "trivial" steps — the enumerator and its inverse — are implementation-level and will be treated in s05. The interesting content is in what the decoder does, and whether the choice of $(\Lambda_c, \Lambda_s)$ plus a small amount of additional processing (MMSE scaling + dither, in s02) is enough to achieve the AWGN capacity. Erez and Zamir (2004) proved the answer is yes — with a single algebraic scheme, no random codebook required.

Common Mistake: Nesting Must Be Strict for a Nontrivial Code

Mistake:

Taking $\Lambda_c = \Lambda_s$ and expecting a nontrivial code. If the two lattices coincide, then $|\Lambda_c / \Lambda_s| = 1$ and the code has exactly one "codeword" (the origin) — a zero-rate code that transmits no information. Similarly, using $\Lambda_s \supsetneq \Lambda_c$ violates the nesting ordering.

Correction:

Always check: $\Lambda_s \subsetneq \Lambda_c$ , i.e., the coarse lattice is a proper sublattice of the fine lattice. For positive rate we need $V(\Lambda_s) > V(\Lambda_c)$ . The standard language is " $\Lambda_c$ is a refinement of $\Lambda_s$ ," or equivalently " $\Lambda_s$ is a sublattice of $\Lambda_c$ ."

Historical Note: Forney, 1989: Lattice Shaping Is Coding

1988–1989

The coset-code framework of Forney (1988) explicitly separated the coding lattice (which provides asymptotic coding gain) from the shaping lattice (which provides asymptotic shaping gain). In the 1989 follow-up, Forney showed that Voronoi-constellation shaping of $\Lambda_s$ can achieve up to $1.53$ dB of shaping gain — a number that earned a proper name in the modulation community. What neither Forney's paper nor the Ungerboeck–Forney 1998 survey proved was that this "fine + coarse lattice" architecture could close the remaining capacity gap entirely. That took another $15$ years: Erez and Zamir (2004) showed that a careful choice of $\Lambda_c$ (a random lattice via Loeliger's averaging), a coarse $\Lambda_s$ (any lattice with $G(\Lambda_s) \to 1/(2\pi e)$ ), an MMSE scalar $\alpha$ , and a dither $\mathbf{d}$ , achieve $\tfrac12 \log_2(1 + \text{SNR})$ — the AWGN capacity, exactly.

,

Nested lattice code

A codebook $\mathcal{C} = \Lambda_c \cap \mathcal{V}(\Lambda_s)$ defined by a fine lattice $\Lambda_c$ and a coarse lattice $\Lambda_s \subset \Lambda_c$ . The number of codewords equals the index $|\Lambda_c / \Lambda_s| = V(\Lambda_s) / V(\Lambda_c)$ , and the rate is $R = (1/n) \log_2 |\Lambda_c / \Lambda_s|$ .

Fine (coding) lattice

The lattice $\Lambda_c$ in a nested pair; carries the individual codewords and provides the coding gain $\gamma_c(\Lambda_c)$ . Typically $\Lambda_c$ is chosen to be dense in the packing sense (e.g., $E_8$ , $\Lambda_{24}$ , or random lattices via Loeliger).

Coarse (shaping) lattice

The sublattice $\Lambda_s \subset \Lambda_c$ in a nested pair; its Voronoi region $\mathcal{V}(\Lambda_s)$ defines the power-constrained transmit region and provides the shaping gain $\gamma_s(\Lambda_s)$ , bounded by $\pi e / 6 \approx 1.53$ dB.

Modulo-lattice reduction

The operation $[\mathbf{y}] \bmod \Lambda = \mathbf{y} - Q_\Lambda( \mathbf{y})$ , which returns the unique representative of the coset $\mathbf{y} + \Lambda$ inside the Voronoi region $\mathcal{V}(\Lambda)$ . A group homomorphism from $\mathbb{R}^n$ onto $\mathcal{V}(\Lambda)$ .

Quick Check

A nested lattice code uses $\Lambda_c = \mathbb{Z}^2$ and $\Lambda_s = 5 \mathbb{Z}^2$ . How many codewords does it have, and what is its rate $R$ (bits per real dimension)?

$|\mathcal{C}| = 5$ , $R = \log_2 5 / 2 \approx 1.16$

$|\mathcal{C}| = 25$ , $R = \log_2 25 / 2 \approx 2.32$

$|\mathcal{C}| = 10$ , $R = \log_2 10 / 2 \approx 1.66$

$|\mathcal{C}| = 25$ , $R = \log_2 25 \approx 4.64$

Correction:

|\mathcal{C}| = 25

,

R = \log_2 25 / 2 \approx 2.32

Correct. $V(\Lambda_s) = 25$ , $V(\Lambda_c) = 1$ , so $|\mathcal{C}| = 25$ . Rate $R = (1/2) \log_2 25 \approx 2.32$ bits per real dimension (i.e., $4.64$ bits per complex symbol).

Key Takeaway

A nested lattice code is a fine lattice intersected with the Voronoi region of a coarse sublattice: $\mathcal{C} = \Lambda_c \cap \mathcal{V}(\Lambda_s)$ , with $|\mathcal{C}| = V(\Lambda_s) / V(\Lambda_c)$ codewords and rate $R = (1/n) \log_2 V(\Lambda_s)/ V(\Lambda_c)$ . The construction decouples the "coding" job (done by $\Lambda_c$ ) from the "shaping" job (done by $\Lambda_s$ ), and the key operation — reduction modulo $\Lambda_s$ — is algebraic. s02 shows that a careful choice of $\Lambda_c$ , $\Lambda_s$ , an MMSE scalar, and a uniform dither yields the AWGN capacity $\tfrac12 \log_2(1 + \text{SNR})$ exactly.

Nested Lattice Codes

From QAM to Nested Lattices: Replacing Truncation with Modulo

Definition: Nested Lattice Pair

Definition: Modulo-Lattice Operation and Nearest-Neighbour Quantiser

Definition: Nested Lattice Code

Theorem: Codebook Size Equals Volume Ratio

One representative per coset

Cosets count by volume

Conclude

Nested Lattice Pair Λc⊃Λs\Lambda_c \supset \Lambda_sΛc​⊃Λs​ in 2D

Parameters

Example: 16-QAM as a Nested Lattice Code

Fine lattice

Coarse lattice and Voronoi region

Verify the count

Rate

Why this is still a weak nested-lattice code

Encoder and Decoder, in One Picture

Common Mistake: Nesting Must Be Strict for a Nontrivial Code

Historical Note: Forney, 1989: Lattice Shaping Is Coding

Nested lattice code

Fine (coding) lattice

Coarse (shaping) lattice

Modulo-lattice reduction

Quick Check

Key Takeaway

Definition:
Nested Lattice Pair

Definition:
Modulo-Lattice Operation and Nearest-Neighbour Quantiser

Definition:
Nested Lattice Code

Nested Lattice Pair $\Lambda_c \supset \Lambda_s$ in 2D