Ferkans — Interactive Telecom Tutor

Why Lattice Codes?

Shannon's random coding argument proves existence but gives no structure — a random Gaussian codebook is hopelessly complex to store and decode. We need structured codes that are efficiently encodable and decodable while still approaching capacity.

Lattice codes provide exactly this structure. A lattice is a regular grid of points in $\mathbb{R}^n$ , and a lattice code is a finite subset of lattice points. The regularity of the lattice enables efficient nearest-neighbor decoding (lattice decoding), while the high-dimensional geometry allows the code to approach capacity. The point is that lattices provide the right balance between structure (for efficient implementation) and richness (for approaching the Shannon limit).

Definition:
Lattice

A lattice $\Lambda$ in $\mathbb{R}^n$ is a discrete subgroup of $\mathbb{R}^n$ , equivalently the set of all integer linear combinations of $n$ linearly independent basis vectors $\mathbf{b}_1, \ldots, \mathbf{b}_n$ :

$\Lambda = \left\{\sum_{i=1}^n z_i \mathbf{b}_i : z_i \in \mathbb{Z}\right\} = \mathbf{B}\mathbb{Z}^n,$

where $\mathbf{B} = [\mathbf{b}_1 \cdots \mathbf{b}_n]$ is the generator matrix.

The simplest lattice is $\mathbb{Z}^n$ (the integer lattice). In 2D, the hexagonal lattice $A_2$ is the densest packing; in higher dimensions, lattices like $D_n$ , $E_8$ , and the Leech lattice $\Lambda_{24}$ achieve remarkable packing densities.

Definition:
Voronoi Region and Fundamental Volume

The Voronoi region $\mathcal{V}(\Lambda)$ of a lattice $\Lambda$ is the set of points in $\mathbb{R}^n$ closer to the origin than to any other lattice point:

$\mathcal{V}(\Lambda) = \{\mathbf{x} \in \mathbb{R}^n : \|\mathbf{x}\| \leq \|\mathbf{x} - \boldsymbol{\lambda}\| \text{ for all } \boldsymbol{\lambda} \in \Lambda\}.$

The fundamental volume is $\text{Vol}(\Lambda) = |\det(\mathbf{B})|$ , equal to the volume of the Voronoi region.

Definition:
Normalized Second Moment

The normalized second moment (NSM) of a lattice $\Lambda$ in $\mathbb{R}^n$ is

$G(\Lambda) = \frac{\frac{1}{n}\int_{\mathcal{V}} \|\mathbf{x}\|^2 d\mathbf{x} / \text{Vol}(\mathcal{V})}{\text{Vol}(\mathcal{V})^{2/n}}.$

This measures how efficiently the Voronoi region approximates a sphere. For a sphere, $G = \frac{1}{2\pi e}$ (in the limit $n \to \infty$ ). For the integer lattice $\mathbb{Z}^n$ , $G = 1/12$ . As $n \to \infty$ , good lattices achieve $G(\Lambda) \to \frac{1}{2\pi e}$ .

Lattice

A discrete subgroup of $\mathbb{R}^n$ , or equivalently, all integer linear combinations of $n$ basis vectors. Lattices provide structured codebooks for the Gaussian channel.

Related: Voronoi region, Lattice code

Voronoi region

The set of all points closer to a given lattice point than to any other lattice point. The Voronoi regions tile $\mathbb{R}^n$ and define the nearest-neighbor decoding regions.

Related: Lattice

Lattice code

A finite set of lattice points used as a codebook. Typically formed by intersecting a lattice $\Lambda$ with a shaping region $\mathcal{S}$ : $\mathcal{C} = \Lambda \cap \mathcal{S}$ . Good lattice codes approach AWGN capacity.

Related: Lattice

Definition:
Lattice Code

A lattice code is formed by intersecting a fine lattice $\Lambda$ with a shaping region $\mathcal{S} \subset \mathbb{R}^n$ :

$\mathcal{C} = \Lambda \cap \mathcal{S}.$

The number of codewords is $|\mathcal{C}| \approx \text{Vol}(\mathcal{S})/\text{Vol}(\Lambda)$ . The rate is $R = \frac{1}{n}\log_2 |\mathcal{C}| \approx \frac{1}{n}\log_2\frac{\text{Vol}(\mathcal{S})}{\text{Vol}(\Lambda)}$ .

For the AWGN channel, the shaping region $\mathcal{S}$ should be a sphere (or approximately spherical) to satisfy the power constraint efficiently, and the lattice $\Lambda$ should have small NSM $G(\Lambda)$ for good decoding performance.

Theorem: Lattice Codes Achieve AWGN Capacity

There exist sequences of lattice codes that achieve the capacity of the AWGN channel. Specifically, for any rate $R < C(\text{SNR})$ and any $\epsilon > 0$ , there exists an $n$ -dimensional lattice code with rate at least $R$ and error probability at most $\epsilon$ , for sufficiently large $n$ .

The key insight is that in high dimensions, good lattices become "Gaussian-like" — their Voronoi regions approach spheres, and the distribution of a uniformly random lattice point inside a shaping region approaches Gaussian. The NSM $G(\Lambda) \to 1/(2\pi e)$ as $n \to \infty$ for appropriately chosen lattice families, which is exactly the condition needed for capacity-achieving performance.

Proof

Volume-to-noise ratio

Define the volume-to-noise ratio $\mu(\Lambda, N) = \text{Vol}(\Lambda)^{2/n}/(2\pi e N)$ . Reliable decoding requires $\mu > 1$ , i.e., the lattice cells must be "larger" than the noise.

Rate and volume

The rate of the lattice code is $R = \frac{1}{2}\log_2(\text{Vol}(\mathcal{S})^{2/n}/\text{Vol}(\Lambda)^{2/n})$ . With a spherical shaping region of power $P$ : $R \approx \frac{1}{2}\log_2(2\pi e P/\text{Vol}(\Lambda)^{2/n})$ .

Combining

As $G(\Lambda) \to 1/(2\pi e)$ (good lattice) and the shaping region approaches a sphere, $R \to \frac{1}{2}\log(1 + P/N) = C$ . The existence of such lattice sequences was proved by Erez and Zamir (2004) using lattice Gaussian distributions.

Historical Note: From Sphere Packing to Capacity-Achieving Lattices

The connection between lattices and coding was recognized early — the Hamming code is the binary image of the $D_4$ lattice, and the Golay code relates to the Leech lattice $\Lambda_{24}$ . But proving that lattice codes can achieve AWGN capacity took decades.

De Buda (1975) showed that lattice codes can achieve rates close to capacity. Urbanke and Rimoldi (1998) proved that nested lattice codes achieve the capacity of the modulo-additive Gaussian channel. The breakthrough came with Erez and Zamir (2004), who showed that nested lattice codes with MMSE scaling achieve the full AWGN capacity. This settled a long-standing question in coding theory.

Example: QAM as a Lattice Code

Show that square $M$ -QAM is a 2D lattice code based on $\mathbb{Z}^2$ . For $M = 16$ (16-QAM), compute the rate and the normalized second moment.

Solution

Identify the lattice and shaping region

The 16-QAM constellation is $\{(\pm 1, \pm 1), (\pm 1, \pm 3), (\pm 3, \pm 1), (\pm 3, \pm 3)\}$ (before scaling). This is $\mathbb{Z}^2$ intersected with the square $[-4, 4)^2$ , i.e., $\mathcal{C} = (2\mathbb{Z}+1)^2 \cap [-4, 4)^2 = \Lambda \cap \mathcal{S}$ .

Compute the rate

$|\mathcal{C}| = 16$ , $n = 2$ (two real dimensions per complex symbol). $R = \frac{1}{2}\log_2(16) = 2$ bits per real dimension = 4 bits per complex symbol.

Compute NSM

For a square shaping region, $G = 1/12$ (same as the cubic lattice). This is $\frac{1}{2\pi e} \times 2\pi e/12 \approx 0.0833$ vs. the optimal $1/(2\pi e) \approx 0.0585$ . The ratio $10\log_{10}(1/12 \times 2\pi e) = 1.53$ dB is the shaping loss.

2D Lattice Examples and Their Voronoi Regions — Left: the square lattice $\mathbb{Z}^2$ with square Voronoi regions. Right: the hexagonal lattice $A_2$ with hexagonal Voronoi regions. The hexagonal lattice achieves denser packing and lower NSM ( $G = 0.0802$ vs. $G = 0.0833$ for the square lattice).

Square vs. Hexagonal Lattice Geometry

Comparison of the

\mathbb{Z}^2

(square) and

A_2

(hexagonal) lattices with their Voronoi regions. The hexagonal lattice provides a 0.16 dB improvement in packing efficiency, the basis for the shaping gain discussion.

Lattice Packing Density vs. Dimension

Explore how the best known lattice packing density evolves with dimension. Notable lattices include $A_2$ (hexagonal, $n=2$ ), $D_4$ ( $n=4$ ), $E_8$ ( $n=8$ ), and the Leech lattice ( $n=24$ ). As $n$ grows, the NSM approaches $1/(2\pi e)$ .

Parameters

Maximum dimension

n

24

Quick Check

What is the normalized second moment $G$ of the optimal lattice quantizer in the limit $n \to \infty$ ?

$1/12 \approx 0.0833$

$1/(2\pi e) \approx 0.0585$

$1/(2\pi) \approx 0.159$

0 (perfect quantization)

Correction:

1/(2\pi e) \approx 0.0585

As $n \to \infty$ , the Voronoi region of a good lattice approaches a sphere, and the NSM approaches $1/(2\pi e) \approx 0.0585$ . The value $1/12$ corresponds to the 1D lattice $\mathbb{Z}$ (uniform scalar quantization).

Common Mistake: Lattice Codes Are Not Always Practical

Mistake:

Assuming that since lattice codes achieve AWGN capacity theoretically, they are the best practical choice for all scenarios.