Ferkans — Interactive Telecom Tutor

What a Fundamental Region Is

Having defined a lattice, we now need to describe the space between the points. Every AWGN-decoding calculation — what is the minimum distance, how often do two lattice points get confused, how much energy does the nearest neighbour carry — is really a calculation about the geometry around a lattice point. The fundamental region, Voronoi region, packing and covering radii are the four objects that make those calculations clean. By the end of this section we will have stated, proved, and illustrated the fact that all fundamental regions have the same volume $V(\Lambda)$ , and we will have introduced the packing radius $\rho$ , covering radius $R$ , kissing number $K$ , and packing density $\Delta$ — the full vocabulary that Ch. 16 and Ch. 17 will draw on.

Definition:
Fundamental Region

A fundamental region $\mathcal{R}(\Lambda)$ of a lattice $\Lambda$ is any measurable subset of $\mathbb{R}^n$ such that its translates $\{\mathcal{R}(\Lambda) + \lambda : \lambda \in \Lambda\}$ tile $\mathbb{R}^n$ — i.e., they cover $\mathbb{R}^n$ and pairwise overlaps have Lebesgue measure zero.

The two canonical choices are:

The fundamental parallelepiped $\mathcal{P}(\mathbf{G}) = \{\mathbf{G} \mathbf{u} : \mathbf{u} \in [0, 1)^n\}$ , spanned by the basis vectors.
The Voronoi region $\mathcal{V}(\Lambda)$ , defined below — the set of points strictly closer to the origin than to any nonzero lattice point.

Both have the same volume; indeed so does every fundamental region, as the next theorem shows.

Fundamental regions are highly non-unique: any measurable set that contains exactly one representative of each coset $\mathbb{R}^n / \Lambda$ qualifies. The parallelepiped is the simplest; the Voronoi region is the most symmetric and is what gets used in decoding and quantization.

,

Theorem: All Fundamental Regions Have the Same Volume

Let $\mathcal{R}_1(\Lambda), \mathcal{R}_2(\Lambda)$ be any two fundamental regions of the same lattice $\Lambda$ . Then $\mathrm{vol}(\mathcal{R}_1) \;=\; \mathrm{vol}(\mathcal{R}_2) \;=\; V(\Lambda) \;=\; |\det \mathbf{G}|.$ In particular, the volume of the Voronoi region $\mathcal{V}(\Lambda)$ equals the volume of the fundamental parallelepiped $\mathcal{P}(\mathbf{G})$ , and both equal $|\det \mathbf{G}|$ .

A fundamental region is a complete set of coset representatives for $\mathbb{R}^n / \Lambda$ . Its volume is a measure of the size of that coset space, which is an intrinsic property of the quotient — not of which "shape" we chose for the representatives.

Show Hint

Use the indicator function $\mathbf{1}_\mathcal{R}$ and the tiling property.

Write $\int_{\mathbb{R}^n} \mathbf{1}_\mathcal{R}(\mathbf{x}) \, d\mathbf{x}$ in two ways, or compare it to the parallelepiped.

Proof

Tiling identity

For a fundamental region $\mathcal{R}$ , the tiling property says $\sum_{\lambda \in \Lambda} \mathbf{1}_\mathcal{R}(\mathbf{x} - \lambda) \;=\; 1 \qquad \text{for almost every } \mathbf{x} \in \mathbb{R}^n.$ In particular, integrating this identity against the characteristic function of any bounded measurable set $B$ yields $\mathrm{vol}(B) = \sum_\lambda \int_B \mathbf{1}_\mathcal{R} (\mathbf{x} - \lambda) d\mathbf{x}$ .

Take $B = \mathcal{P}(\mathbf{G})$

Apply the identity with $B = \mathcal{P}(\mathbf{G})$ , the parallelepiped. Each integrand $\int_\mathcal{P} \mathbf{1}_\mathcal{R} (\mathbf{x} - \lambda) d\mathbf{x} = \mathrm{vol}(\mathcal{R} \cap (\mathcal{P} + \lambda))$ measures the overlap of the translate $\mathcal{R}$ with the shifted parallelepiped. Summing over $\lambda \in \Lambda$ and using the tiling gives $\mathrm{vol}(\mathcal{P}) = \sum_\lambda \mathrm{vol}(\mathcal{R} \cap (\mathcal{P} + \lambda)) = \mathrm{vol}(\mathcal{R})$ — the last step uses that $\{\mathcal{P} + \lambda\}$ tiles $\mathbb{R}^n$ and the total overlap of $\mathcal{R}$ with that tiling is just $\mathrm{vol}(\mathcal{R})$ .

Conclude

Thus $\mathrm{vol}(\mathcal{R}) = \mathrm{vol}(\mathcal{P}) = |\det \mathbf{G}|$ for every fundamental region $\mathcal{R}$ . $\blacksquare$

,

Definition:
Voronoi Region

The Voronoi region of $\Lambda$ around the origin is $\mathcal{V}(\Lambda) \;=\; \bigl\{\mathbf{x} \in \mathbb{R}^n : \|\mathbf{x}\| \le \|\mathbf{x} - \lambda\| \text{ for all } \lambda \in \Lambda\bigr\}.$ Equivalently, $\mathcal{V}(\Lambda)$ is the intersection of the half-spaces $\{\mathbf{x} : \langle \mathbf{x}, \lambda \rangle \le \tfrac12 \|\lambda\|^2\}$ indexed by $\lambda \in \Lambda \setminus \{\mathbf{0}\}$ .

The Voronoi region of a lattice point $\lambda_0 \in \Lambda$ is the translate $\mathcal{V}(\Lambda) + \lambda_0$ . These regions are convex polytopes (since intersections of half-spaces are), symmetric under $\mathbf{x} \mapsto -\mathbf{x}$ , and tile $\mathbb{R}^n$ .

The boundary of $\mathcal{V}(\Lambda)$ is a union of faces, each perpendicular to a vector from the origin to a relevant lattice point. In 2D, $\mathcal{V}(\mathbb{Z}^2)$ is the unit square and $\mathcal{V}(A_2)$ is a regular hexagon. In higher dimensions the combinatorics becomes rich — $\mathcal{V}(E_8)$ has 240 relevant vectors (the minimum-norm vectors), and $\mathcal{V}(\Lambda_{24})$ has at least 196560.

,

Definition:
Packing Radius

The packing radius of $\Lambda$ is the largest $r$ such that the balls $B(\lambda, r)$ around distinct lattice points are disjoint: $\rho(\Lambda) \;=\; \frac{1}{2} \, \min_{\mathbf{x} \in \Lambda \setminus \{\mathbf{0}\}} \|\mathbf{x}\| \;=\; \frac{1}{2} \, d_{\min}(\Lambda).$ Geometrically, $\rho(\Lambda)$ is the radius of the largest ball inscribed in the Voronoi region: $B(\mathbf{0}, \rho) \subset \mathcal{V}(\Lambda)$ .

The factor of $\tfrac12$ is the "balls meet halfway" geometry: if two balls of radius $r$ sit at centres $\lambda_1, \lambda_2$ , they are disjoint iff $\|\lambda_1 - \lambda_2\| \ge 2 r$ , so the extremal case is $r = d_{\min} / 2$ .

,

Definition:
Covering Radius

The covering radius of $\Lambda$ is the smallest $R$ such that the closed balls $B(\lambda, R)$ around all lattice points cover $\mathbb{R}^n$ : $R(\Lambda) \;=\; \max_{\mathbf{y} \in \mathbb{R}^n} \, \min_{\mathbf{x} \in \Lambda} \|\mathbf{y} - \mathbf{x}\|.$ Geometrically, $R(\Lambda)$ is the circumradius of the Voronoi region (the distance from the origin to the farthest vertex of $\mathcal{V}(\Lambda)$ ).

$R(\Lambda)$ is the "worst-case quantization error": if a lattice decoder rounds any received signal $\mathbf{y} \in \mathbb{R}^n$ to the nearest lattice point, the worst-case rounding error has magnitude $R(\Lambda)$ . The ratio $R / \rho$ is therefore a measure of how "round" the Voronoi region is — it equals $1$ iff $\mathcal{V}(\Lambda)$ is a ball, which happens only in the nonexistent limit of a continuous point set.

,

Definition:
Kissing Number

The kissing number of $\Lambda$ is the number of minimum-norm nonzero vectors: $K(\Lambda) \;=\; \bigl| \{\mathbf{x} \in \Lambda : \|\mathbf{x}\| = d_{\min}(\Lambda)\} \bigr|.$ It is also written $\tau(\Lambda)$ in the sphere-packing literature. At high SNR, the union-bound error probability for lattice ML decoding satisfies $P_e \;\lesssim\; K(\Lambda) \cdot Q\!\left(\frac{d_{\min} (\Lambda)}{2 \sqrt{\sigma^2}}\right),$ so the kissing number is the multiplicative prefactor of the error floor.

A large kissing number is a mixed blessing: it is a sign that the lattice has many short vectors (good, because it means the lattice could be dense), but it multiplies the union-bound error count (bad). The effective coding gain is often quoted as $\gamma_c(\Lambda) / K(\Lambda)^{1/n}$ , which penalises large $K$ .

Definition:
Packing Density and Center Density

The packing density of $\Lambda$ is the fraction of $\mathbb{R}^n$ covered by disjoint balls of radius $\rho(\Lambda)$ centred at the lattice points: $\Delta(\Lambda) \;=\; \frac{\rho^n V_n}{V(\Lambda)},$ where $V_n = \pi^{n/2} / \Gamma(n/2 + 1)$ is the volume of the unit $n$ -ball.

The center density strips off the ball factor: $\delta(\Lambda) \;=\; \frac{\rho^n}{V(\Lambda)} \;=\; \frac{\Delta(\Lambda)}{V_n}.$ Both are basis invariants and both are $\le 1$ . The center density is more convenient for comparing lattices across dimensions because the ball factor $V_n$ collapses to zero as $n \to \infty$ .

Do not confuse $\Delta(\Lambda)$ (the packing density, $\le 1$ ) with $\delta(\Lambda)$ (the center density, which can exceed $1$ in high dimensions because $V_n \to 0$ faster than $\rho^n / V$ grows). The Conway–Sloane tables list $\delta$ ; papers often quote $\Delta$ .

Example: Voronoi Volume, Packing and Covering Radii for $\mathbb{Z}^2$ and $A_2$

Compute the Voronoi volume, packing radius, covering radius, kissing number, and packing density for (a) $\mathbb{Z}^2$ and (b) $A_2$ . Verify that $A_2$ is denser than $\mathbb{Z}^2$ in 2D.

Solution

Part (a): $\mathbb{Z}^2$

The Voronoi region is the unit square $[-1/2, 1/2]^2$ , with volume $V(\mathbb{Z}^2) = 1$ . The minimum-norm vectors are the four unit vectors $\pm \mathbf{e}_1, \pm \mathbf{e}_2$ , giving $K = 4$ and $d_{\min} = 1$ . So $\rho = 1/2$ and $R = \sqrt{2}/2$ (the half-diagonal of the unit square). Packing density $\Delta(\mathbb{Z}^2) = \pi (1/2)^2 / 1 = \pi/4 \approx 0.7854$ .

Part (b): $A_2$

The minimum-norm vectors of $A_2$ have length $d_{\min} = 1$ (we picked the basis $(1, 0), (1/2, \sqrt{3}/2)$ ), and there are $K = 6$ of them (three basis-like vectors and their negatives). $V(A_2) = \sqrt{3}/2$ , $\rho = 1/2$ , $R = 1/\sqrt{3} \approx 0.577$ (the distance to the hexagon's vertex). Packing density $\Delta(A_2) = \pi (1/2)^2 / (\sqrt{3}/2) = \pi / (2 \sqrt{3}) \approx 0.9069$ .

Comparison

$\Delta(A_2) / \Delta(\mathbb{Z}^2) = 2 / \sqrt{3} \approx 1.155$ , so $A_2$ is $\approx 15.5\%$ denser. In coded-modulation language, the fundamental coding gain of $A_2$ over $\mathbb{Z}^2$ is $10 \log_{10}(2/\sqrt{3}) \approx 0.625$ dB. Note also that the $R/\rho$ ratio is $\sqrt{2} \approx 1.414$ for $\mathbb{Z}^2$ and only $2/\sqrt{3} \approx 1.155$ for $A_2$ — the hexagonal Voronoi cell is "rounder" than the square one. $\blacksquare$

Theorem: $A_2$ is the Densest 2D Lattice (Gauss, 1831)

Among all 2D lattices $\Lambda \subset \mathbb{R}^2$ , the hexagonal lattice $A_2$ achieves the maximum packing density: $\Delta_2 \;=\; \Delta(A_2) \;=\; \frac{\pi}{2 \sqrt{3}} \;\approx\; 0.9069.$ Equivalently, the Hermite constant in dimension 2 is $\gamma_2 = 2/\sqrt{3}$ .

In 2D, every lattice has a reduced basis $\mathbf{b}_1, \mathbf{b}_2$ with $|\mathbf{b}_1| \le |\mathbf{b}_2|$ and $|\langle \mathbf{b}_1, \mathbf{b}_2\rangle| \le \tfrac12 |\mathbf{b}_1|^2$ . The packing density is optimized when $|\mathbf{b}_2| = |\mathbf{b}_1|$ and the angle is $60°$ — exactly the hexagonal geometry.

Show Hint

Reduce to the case $d_{\min}(\Lambda) = 1$ and minimize $V(\Lambda)$ over all lattices with that property.

Use a Lagrange-reduced basis: $|\mathbf{b}_1| \le |\mathbf{b}_2|$ , $|\langle \mathbf{b}_1, \mathbf{b}_2\rangle / \mathbf{b}_1^2| \le 1/2$ .

Proof

Lagrange reduction

Any 2D lattice admits a basis $\mathbf{b}_1, \mathbf{b}_2$ with $|\mathbf{b}_1| \le |\mathbf{b}_2|$ and $|\langle \mathbf{b}_1, \mathbf{b}_2 \rangle| \le \tfrac12 |\mathbf{b}_1|^2$ . Scale so that $|\mathbf{b}_1| = 1$ ; then $d_{\min}(\Lambda) = 1$ (the vector $\mathbf{b}_1$ realizes the minimum since $|\mathbf{b}_2| \ge 1$ and all other vectors $u_1 \mathbf{b}_1 + u_2 \mathbf{b}_2$ with $(u_1, u_2) \ne \pm (1, 0)$ are at least as long).

Volume lower bound

Write $\mathbf{b}_2 = t \mathbf{b}_1 + s \mathbf{b}_1^\perp$ with $|t| \le 1/2$ and $s > 0$ . Then $|\mathbf{b}_2|^2 = t^2 + s^2 \ge 1$ , so $s^2 \ge 1 - t^2 \ge 3/4$ , and $V(\Lambda) = |\det(\mathbf{b}_1, \mathbf{b}_2)| = s \ge \sqrt{3}/2$ , with equality iff $|t| = 1/2$ and $|\mathbf{b}_2| = 1$ .

Density bound and extremiser

Since $\rho = 1/2$ (always) when $d_{\min} = 1$ , we have $\Delta(\Lambda) = \pi \rho^2 / V(\Lambda) = \pi/(4 V(\Lambda)) \le \pi / (4 \cdot \sqrt{3}/2) = \pi / (2 \sqrt{3})$ . Equality holds iff $t = 1/2, s = \sqrt{3}/2$ — the hexagonal basis. $\blacksquare$

,

Packing vs Covering Radius Across Classical Lattices

A bar chart comparing the packing radius $\rho$ , the covering radius $R$ , and the ratio $R/\rho$ (a measure of Voronoi-cell "roundness") for classical lattices in dimensions 2 through 24. Rounder is better: a ball-shaped Voronoi region minimizes both the worst-case quantization error and the maximum union-bound term. The hexagonal $A_2$ , the exceptional $E_8$ , and the Leech lattice $\Lambda_{24}$ stand out as unusually round.

Parameters

$A_2$ Hexagonal Lattice: Voronoi Tessellation, Packing and Covering

Animated construction of the

A_2

hexagonal lattice and its Voronoi tessellation. We start with a single point, add the six minimum-norm neighbours (kissing number

K = 6

), draw the Voronoi cell (a regular hexagon), highlight the inscribed packing circle of radius

\rho = 1/2

, and the circumscribed covering circle of radius

R = 1/\sqrt{3}

. The entire plane tiles with congruent hexagons — the densest 2D packing.

🔧Engineering Note

Every QAM Constellation is a Finite Piece of $\mathbb{Z}^2$

The square 16-QAM, 64-QAM, 256-QAM constellations used in Wi-Fi, LTE, and 5G NR are finite subsets of $\mathbb{Z}^2$ (scaled and centred). The 32-QAM "cross" constellation used in V.32 modems is a finite subset of $\mathbb{Z}^2$ intersected with a non-square shaping region. Circular APSK constellations (DVB-S2) step outside the lattice framework slightly by placing points on concentric rings rather than on a grid. Hexagonal constellations — slices of $A_2$ — are never standardised in consumer equipment because the asymmetric row/column addressing is inconvenient for I/Q DACs, even though $A_2$ is $0.625$ dB more efficient than $\mathbb{Z}^2$ . This is a case where fabrication convenience beats theoretical optimality.

Practical Constraints

•
QAM I/Q DACs sample a rectangular grid, naturally aligned with $\mathbb{Z}^2$ .
•
Hexagonal constellations require trigonometric DAC spacing, rarely justified for the $0.6$ dB gain.
•
Gray labelling is easier on $\mathbb{Z}^2$ than on $A_2$ .

,

Common Mistake: Packing Density vs Center Density — Don't Mix Them Up

Mistake:

Comparing $\Delta$ and $\delta$ values across references without realising they differ by the ball factor $V_n = \pi^{n/2} / \Gamma(n/2 + 1)$ . In high dimensions $V_n$ is exponentially small (e.g., $V_{24} \approx 0.0019$ ), so the two quantities scale very differently.

Correction:

Decide once — are you quoting packing density $\Delta$ (fraction of space covered, always $\le 1$ ) or center density $\delta = \Delta / V_n$ (which removes the ball factor and is convenient across dimensions)? The Conway–Sloane tables quote $\delta$ . When comparing to a paper, always check which one is meant: $\delta(\Lambda_{24}) = 1$ but $\Delta(\Lambda_{24}) = V_{24} \approx 0.0019$ .

Fundamental region

A measurable subset $\mathcal{R} \subset \mathbb{R}^n$ whose translates by $\Lambda$ tile $\mathbb{R}^n$ . Volume equals $V(\Lambda) = |\det \mathbf{G}|$ .

Voronoi region

The set of points in $\mathbb{R}^n$ closer to the origin than to any nonzero lattice point. A convex polytope, centrally symmetric, and the canonical fundamental region.

Packing radius

$\rho(\Lambda) = d_{\min}(\Lambda) / 2$ , the largest radius of disjoint balls centred at the lattice points; equivalently the inradius of the Voronoi region.

Covering radius

$R(\Lambda) = \max_\mathbf{y} \min_\mathbf{x} \|\mathbf{y} - \mathbf{x}\|$ , the smallest radius of balls at the lattice points that cover $\mathbb{R}^n$ ; equivalently the circumradius of the Voronoi region.

Related: Packing Radius, Voronoi Region

Kissing number

$K(\Lambda)$ : the number of minimum-norm nonzero lattice vectors. The multiplicative prefactor in the union-bound error probability.

Packing density

$\Delta(\Lambda) = \rho^n V_n / V(\Lambda)$ : the fraction of $\mathbb{R}^n$ covered by disjoint balls of radius $\rho$ centred on lattice points. Always $\le 1$ ; measures how "full" the lattice packing is.

Quick Check

A lattice $\Lambda$ has $\rho = R$ . What can we conclude about the Voronoi region of $\Lambda$ ?

The Voronoi region is a ball, which is impossible.

The lattice has infinitely many minimum-norm vectors.

The lattice is self-dual.

The covering radius is zero.

Correction:

The Voronoi region is a ball, which is impossible.

$\rho$ is the inradius and $R$ is the circumradius of $\mathcal{V}(\Lambda)$ . They coincide only if every point on the Voronoi boundary is at the same distance from the origin, i.e., the boundary is a sphere. But a tiling region cannot be a ball except in the trivial sense of a single point. So no lattice achieves $\rho = R$ ; the Conway–Sloane quotient $R / \rho > 1$ is a strict inequality, with the Leech lattice holding the record for 24D ( $R/\rho = \sqrt{2}$ ).

Quick Check

True or false: the volume of the Voronoi region $\mathcal{V}(\Lambda)$ always equals $|\det \mathbf{G}|$ for any generator matrix $\mathbf{G}$ of $\Lambda$ .

True.

False — the Voronoi region is smaller because it is convex.

Only if $\mathbf{G}$ is a reduced basis (LLL-reduced).

Only in dimension $\le 2$ .

Correction:

True.

This is the content of Theorem 'thm-volume-invariance': any two fundamental regions (and the Voronoi region is one) have the same volume $V(\Lambda) = |\det \mathbf{G}|$ . The proof is a tiling argument: the integral of the indicator of the region over all translates is 1 almost everywhere, so the total mass matches the parallelepiped's volume.

Key Takeaway

The lattice has one volume $V(\Lambda) = |\det \mathbf{G}|$ , two radii $\rho$ and $R$ , and a kissing number $K$ — and these four numbers dictate its error-correction performance. The packing radius $\rho$ is half the minimum distance and controls how far apart codewords sit; the covering radius $R$ is the worst-case quantization error and controls MMSE shaping; the kissing number multiplies the union-bound error prefactor; the volume $V(\Lambda)$ sets the rate per dimension. Every subsequent calculation — coding gain, density, Hermite constant — is a ratio of these four basic quantities.

Fundamental Regions, Packing, and Covering

What a Fundamental Region Is

Definition: Fundamental Region

Theorem: All Fundamental Regions Have the Same Volume

Tiling identity

Take $B = \mathcal{P}(\mathbf{G})$

Conclude

Definition: Voronoi Region

Definition: Packing Radius

Definition: Covering Radius

Definition: Kissing Number

Definition: Packing Density and Center Density

Example: Voronoi Volume, Packing and Covering Radii for Z2\mathbb{Z}^2Z2 and A2A_2A2​

Part (a): $\mathbb{Z}^2$

Part (b): $A_2$

Comparison

Theorem: A2A_2A2​ is the Densest 2D Lattice (Gauss, 1831)

Lagrange reduction

Volume lower bound

Density bound and extremiser

Packing vs Covering Radius Across Classical Lattices

Parameters

A2A_2A2​ Hexagonal Lattice: Voronoi Tessellation, Packing and Covering

Every QAM Constellation is a Finite Piece of Z2\mathbb{Z}^2Z2

Common Mistake: Packing Density vs Center Density — Don't Mix Them Up

Fundamental region

Voronoi region

Packing radius

Covering radius

Kissing number

Packing density

Quick Check

Quick Check

Key Takeaway

Definition:
Fundamental Region

Definition:
Voronoi Region

Definition:
Packing Radius

Definition:
Covering Radius

Definition:
Kissing Number

Definition:
Packing Density and Center Density

Example: Voronoi Volume, Packing and Covering Radii for $\mathbb{Z}^2$ and $A_2$

Theorem: $A_2$ is the Densest 2D Lattice (Gauss, 1831)

$A_2$ Hexagonal Lattice: Voronoi Tessellation, Packing and Covering

Every QAM Constellation is a Finite Piece of $\mathbb{Z}^2$