Ferkans — Interactive Telecom Tutor

The Computational Cost of Capacity

The mod- $\Lambda$ scheme of s02 and the lattice DPC of s04 both rely on the same single primitive: find the closest lattice point to a received vector. This is the closest-lattice-point (CLP) problem, and it is where the theoretical beauty of the Erez–Zamir construction meets computational reality.

Bad news first: CLP is NP-hard in the worst case (Ajtai 1998; Micciancio 2001). There is almost certainly no polynomial-time algorithm for arbitrary lattices. Bad news second: even for the specific lattices we care about (integer-coefficient lattices arising from coding constructions), no polynomial algorithm is known.

Good news: the average case is much better than the worst case. At high SNR, the received vector lies close to a single lattice point, and a carefully designed search algorithm explores only $O(\text{poly}(n))$ candidates rather than the exponential worst-case $O(2^{n R})$ brute force. The workhorse algorithm is the Pohst / Schnorr–Euchner sphere decoder (1981/1994), later refined by Viterbo–Boutros (1999) for communications. Viterbo and Boutros showed empirically that at high SNR the average complexity scales as $O(n^3)$ — cubic in the dimension, as cheap as matrix inversion.

The CommIT group's 2003 paper (Damen, El Gamal, Caire, IEEE Trans. IT, 2003) formally analysed the sphere decoder's average complexity and used the analysis to justify its deployment as the MIMO decoder of the LAST construction of Ch. 17. We cover the basic theory here; Ch. 17 covers the MIMO-specific extensions.

,

Definition:
Closest-Lattice-Point (CLP) Problem

Given a lattice $\Lambda \subset \mathbb{R}^n$ with generator matrix $\mathbf{G}$ and a received vector $\mathbf{y} \in \mathbb{R}^n$ , the closest-lattice-point (CLP) problem is to compute $\hat{\mathbf{x}} \;=\; Q_\Lambda(\mathbf{y}) \;=\; \arg \min_{\boldsymbol{\lambda} \in \Lambda} \|\mathbf{y} - \boldsymbol{\lambda}\|.$ Equivalently, in the integer parametrisation $\boldsymbol{\lambda} = \mathbf{G} \mathbf{u}$ : $\hat{\mathbf{u}} \;=\; \arg \min_{\mathbf{u} \in \mathbb{Z}^n} \|\mathbf{y} - \mathbf{G} \mathbf{u}\|^2.$

A natural relaxation is the lattice-decoding error probability under AWGN: when $\mathbf{y} = \mathbf{x} + \mathbf{w}$ with $\mathbf{x} \in \Lambda$ and $\mathbf{w} \sim \mathcal{N}(0, \sigma^2 \mathbf{I})$ , the probability that the CLP solution is wrong is $P_e^{\mathrm{lat}}(\Lambda) \;=\; \Pr[ Q_\Lambda(\mathbf{y}) \ne \mathbf{x}].$

The related shortest-lattice-vector (SVP) problem is $\min_{\boldsymbol{\lambda} \ne 0} \|\boldsymbol{\lambda}\|$ ; CLP reduces to SVP in the "embedded" lattice (Kannan 1987), so the two are computationally essentially equivalent in terms of NP-hardness.

,

Definition:
Lattice-Decoding Error Probability

For a lattice $\Lambda \subset \mathbb{R}^n$ with packing radius $\rho$ in AWGN at noise variance $\sigma^2$ , the lattice-decoding error probability is $P_e^{\mathrm{lat}}(\Lambda) \;=\; \Pr[\mathbf{w} \notin \mathcal{V}(\Lambda)].$ By the sphere-packing bound ( $\mathcal{V}(\Lambda)$ contains a ball of radius $\rho$ ), $P_e^{\mathrm{lat}}(\Lambda) \;\le\; \Pr[\|\mathbf{w}\| > \rho] \;=\; \Pr[\chi^2_n > \rho^2/\sigma^2],$ which falls as $e^{-n (1 - \eta) / 2}$ with $\eta = 2 \sigma^2/\rho^2$ for $\eta < 1$ — exponential decay in $n$ below the Poltyrev capacity.

The Poltyrev capacity of $\Lambda$ at noise variance $\sigma^2$ is the largest $V(\Lambda)$ (equivalently, the smallest nesting ratio) for which $P_e^{\mathrm{lat}} \to 0$ as $n \to \infty$ . Loeliger's random-lattice averaging shows this capacity is $\tfrac12 \log_2(1/(2 \pi e \sigma^2))$ per normalised volume — the same quantity that appears in the Erez–Zamir s02 proof.

,

Pohst / Schnorr–Euchner Sphere Decoder

Complexity: Worst case:

O((c / \rho)^n)

operations for some constant

c

(Kannan 1983); NP-hard. Average case at high SNR:

O(n^3)

(Viterbo–Boutros 1999, empirical; Damen–El Gamal–Caire 2003, theoretical bound). At SNR near the Poltyrev capacity, the average complexity grows as

O(n^c)

with

c \approx 4

–

5

. For SNR below the Poltyrev cutoff, complexity is exponential.

Input. Generator matrix

\mathbf{G} \in \mathbb{R}^{n \times n}

(upper-triangular after QR), received vector

\mathbf{y} \in \mathbb{R}^n

, initial search radius

r

.

Output.

\hat{\mathbf{u}} = \arg\min_{\mathbf{u} \in \mathbb{Z}^n} \|\mathbf{y} - \mathbf{G} \mathbf{u}\|

.

// QR decomposition:

\mathbf{G} = \mathbf{Q} \mathbf{R}

,

\mathbf{R}

upper-triangular.

\mathbf{y}' \leftarrow \mathbf{Q}^T \mathbf{y}

.

// Now the problem is

\min_\mathbf{u} \|\mathbf{y}' - \mathbf{R} \mathbf{u}\|^2

, and

\mathbf{R}

upper-triangular lets us

decompose as a sum of squares in layers

n, n-1, \ldots, 1

.

procedure

\mathrm{SphereDecode}(i, r^2, \text{partial sum } T)

:

if

i == 0

: return (current

\mathbf{u}

,

\sqrt{T}

) // candidate.

compute the Babai estimate

\hat{u}_i \leftarrow \mathrm{round}( (y'_i - \sum_{j > i} R_{ij} u_j) / R_{ii})

.

for

u_i \in \{\hat{u}_i, \hat{u}_i \pm 1, \hat{u}_i \pm 2, \ldots\}

in Schnorr–Euchner zigzag order:

d_i \leftarrow (y'_i - \sum_{j \ge i} R_{ij} u_j)^2

.

if

T + d_i > r^2

: break the zigzag (all further

u_i

have larger

d_i

).

recurse with

(i - 1, r^2, T + d_i)

; update

r

to the best

candidate norm found.

end procedure

call

\mathrm{SphereDecode}(n, r^2, 0)

.

The key algorithmic ideas are: QR decomposition (reduces CLP to a triangular least-squares problem over $\mathbb{Z}^n$ , layer by layer), branch-and-bound (prune partial sums whose norm already exceeds the current best candidate), and Schnorr–Euchner ordering (explore candidates closest to the Babai estimate first, pruning more aggressively). The same machinery, slightly specialised, is the MIMO detector used in the LAST construction of Ch. 17 — an important CommIT contribution (Damen–El Gamal–Caire 2003) that quantified when this sphere decoder achieves (near-)ML detection at polynomial cost.

, , ,

Theorem: Average Complexity of the Sphere Decoder (Viterbo–Boutros, Damen–El Gamal–Caire)

Let $\Lambda \subset \mathbb{R}^n$ be an integer lattice with generator matrix $\mathbf{G}$ , and consider the AWGN channel $\mathbf{y} = \mathbf{x} + \mathbf{w}$ with $\mathbf{x} \in \Lambda$ and $\mathbf{w} \sim \mathcal{N}(0, \sigma^2 \mathbf{I})$ . For any fixed $\text{SNR}$ strictly less than the Poltyrev capacity of $\Lambda$ (equivalently, $\sigma^2 > c \cdot V(\Lambda)^{2/n}$ for the Poltyrev constant), the expected number of sphere-decoder operations is $\mathbb{E}[T_n] = O(n^3)$ asymptotically. At $\text{SNR}$ near the Poltyrev capacity, $\mathbb{E}[T_n] = O(n^c)$ with $c$ growing to infinity as SNR → Poltyrev capacity from below.

At high SNR, the received $\mathbf{y}$ is very close to the true lattice point $\mathbf{x}$ , so the sphere decoder's initial Babai estimate is usually correct. The subsequent zigzag typically explores only a few nearby candidates before the prune kicks in. At low SNR (near Poltyrev capacity), $\mathbf{y}$ is close to many lattice points, the branch-and-bound search tree has many surviving branches, and complexity grows polynomially but with a higher degree.

Show Hint

For high SNR, use a concentration argument: the Babai estimate equals the true codeword with probability $1 - O(e^{-c/\sigma^2})$ .

Given the Babai estimate is correct, the number of zigzag steps per layer is bounded by a Poisson-like count whose expectation is $O(1)$ .

Combining: total operations = $n$ layers × $O(1)$ per layer × $n^2$ QR/multiplication overhead = $O(n^3)$ .

For low SNR, use the Damen–El Gamal–Caire 'random-walk' argument: the number of surviving partial sums at each depth is a non-homogeneous Markov chain whose growth rate depends on the SNR margin.

Proof

Sketch: high-SNR regime

At high SNR the noise per dimension $\|\mathbf{w}_{i}\| \ll R_{ii}$ (the $i$ -th diagonal of the R factor, which is the per-layer minimum distance scale). The Babai estimate $\mathrm{round}((y'_i - \sum_{j>i} R_{ij} u_j)/R_{ii})$ coincides with the true $u_i$ with probability $1 - O(e^{-c/\sigma^2})$ . In the Schnorr–Euchner zigzag, we explore $u_i = \hat{u}_i$ , $\hat{u}_i \pm 1, \hat{u}_i \pm 2, \ldots$ , each step costing $(R_{ii} \cdot 1)^2 = R_{ii}^2$ of residual-norm contribution. By the pruning rule, only $O(1)$ candidates per layer survive at high SNR — the tree-search is essentially a linear pass.

Per-layer cost: $O(n)$ for the partial-sum update + $O(1)$ for the zigzag. Total over $n$ layers: $O(n^2)$ . Adding the $O(n^3)$ QR preprocessing, the total is $O(n^3)$ .

Sketch: intermediate SNR

As SNR decreases, more zigzag candidates per layer survive. Damen–El Gamal–Caire model the number of survivors at layer $i$ as a random walk whose drift equals the SNR margin. For SNR margin bounded away from zero, the drift is positive and the number of survivors is bounded in probability, giving $\mathbb{E}[T_n] = O(n^c)$ with $c$ determined by the margin.

Near Poltyrev capacity

At the Poltyrev capacity, the random walk becomes recurrent and the number of survivors per layer grows unboundedly. The sphere decoder's complexity tends to exponential — this is unavoidable for any CLP solver near capacity. In practice, one backs off by $0.5$ – $1.0$ dB from capacity to keep the decoder tractable, accepting a small rate loss. $\blacksquare$

,

Sphere Decoder vs Brute Force: Complexity Scaling

Empirical / analytical operation counts (log-scale) of two decoders as a function of lattice dimension $n$ : (i) the sphere decoder with Schnorr–Euchner pruning, exhibiting polynomial average complexity $O(n^3)$ at high SNR; (ii) the brute-force ML search, exponential $O(2^{nR})$ in the nesting ratio. The gap is orders of magnitude at moderate $n \ge 16$ , explaining why the sphere decoder is the default ML/near-ML detector in every published lattice-code implementation since 1999. At low SNR (near Poltyrev capacity), the sphere decoder's advantage narrows — this is the regime where random rounding or the lattice-reduction aided receiver (LLL + ZF, LLL + MMSE) becomes preferable in practice.

Parameters

Max dimension

n

20

Example: Sphere Decoder on $\mathbb{Z}^2$ with a Received Point

Given $\Lambda = \mathbb{Z}^2$ with $\mathbf{G} = \mathbf{I}_2$ (hence $\mathbf{R} = \mathbf{I}_2$ after QR), received vector $\mathbf{y} = (0.4, -1.3)^T$ , and initial radius $r = 0.8$ , run the Schnorr–Euchner sphere decoder and identify the closest lattice point.

Solution

Layer 2: enumerate $u_2$

Babai estimate: $\hat{u}_2 = \mathrm{round}(y_2 / R_{22}) = \mathrm{round}(-1.3/1) = -1$ . Residual contribution: $d_2 = (y_2 - u_2)^2 = (-1.3 - (-1))^2 = 0.09$ . Since $d_2 = 0.09 < r^2 = 0.64$ , we proceed. Zigzag order: $u_2 = -1$ first.

Layer 1: enumerate $u_1$

Given $u_2 = -1$ , Babai estimate: $\hat{u}_1 = \mathrm{round} (y_1/R_{11}) = \mathrm{round}(0.4/1) = 0$ . Residual: $d_1 = (0.4 - 0)^2 = 0.16$ . Total: $T = d_1 + d_2 = 0.16 + 0.09 = 0.25 \le r^2 = 0.64$ . Candidate: $\mathbf{u} = (0, -1)$ with distance $\sqrt{0.25} = 0.5$ . Update $r \leftarrow 0.5$ .

Backtrack

Try $u_2 = 0$ (next in zigzag): $d_2 = 1.69 > r^2 = 0.25$ , pruned. Try $u_2 = -2$ : $d_2 = 0.49 > r^2 = 0.25$ , pruned. All other $u_2$ in zigzag have $d_2 > 0.49 > 0.25$ , so the search terminates.

Result

$\hat{\mathbf{u}} = (0, -1)$ , i.e., $\hat{\mathbf{x}} = \mathbf{G} \hat{\mathbf{u}} = (0, -1)$ . Total operations: QR (trivial here, $\mathbf{G}$ already upper-triangular) + $2$ layer-1 zigzag attempts + $2$ layer-2 zigzag attempts = $4$ actual norm computations. Brute force on a search box $[-2, 2]^2$ would have been $25$ . At moderate dimension the gap amplifies exponentially. $\blacksquare$

Example: CLP Hardness: Worst-Case Lattice That Defeats the Sphere Decoder

Describe a lattice $\Lambda_{\text{bad}}$ for which the sphere decoder requires exponential time even at high SNR, and explain why the Babai estimate fails in this case.

Solution

Construction

Consider the lattice generated by $\mathbf{G} = \begin{pmatrix} 1 & \varepsilon & \varepsilon^2 & \cdots & \varepsilon^{n-1} \\ 0 & 1 & \varepsilon & \cdots & \varepsilon^{n-2} \\ \vdots & & \ddots & & \vdots \\ 0 & 0 & \cdots & 0 & 1 \end{pmatrix},$ where $\varepsilon = 0.99$ . The diagonal is all ones, but the matrix is nearly singular (columns nearly parallel). The Babai estimate rounds each layer to the nearest integer, but the near-singularity means small noise can flip the decision in many layers simultaneously.

Why sphere decoder fails

The diagonals $R_{ii}$ of the QR factor are approximately $1, \sqrt{1 - \varepsilon^2}, \sqrt{1 - \varepsilon^2 - \ldots} \ldots \to 0$ , so per-layer noise tolerance shrinks exponentially in $n$ . At any fixed SNR, the Babai estimate is wrong at most layers, and the zigzag explodes.

Practical remedy: LLL reduction

Pre-processing with the LLL (Lenstra–Lenstra–Lovász) lattice reduction algorithm rotates the basis so that the columns are closer to orthogonal, restoring the Babai estimate's quality. LLL runs in $O(n^6)$ and is a one-time cost; after LLL, the sphere decoder's per-use complexity returns to $O(n^3)$ at high SNR. This LLL + sphere-decoder pipeline is the standard MIMO detector recipe of Damen–El Gamal–Caire 2003, and of the LAST codes of Ch. 17. $\blacksquare$

🔧Engineering Note

Lattice Decoding in DVB-C2 and DOCSIS 4.0

Lattice decoding is not yet the default detector in the widest consumer-electronics standards — LDPC + BICM (Ch. 9) remains the universal workhorse. But two standards push into the lattice-decoding regime:

DVB-C2 (digital cable broadcasting, European standard 2010) uses $4096$ -QAM with LDPC. At its highest modes, the $12$ -bit per-symbol decoding uses a soft sphere-decoder variant to compute bit LLRs — essentially running a truncated sphere search per bit position to identify the most likely constellation point.

DOCSIS 4.0 (cable-plant, 2019) targets $16384$ -QAM. At this density, hard-decision decoding is insufficient; the receiver uses an MMSE + lattice-reduction + soft sphere decoder chain. The per-symbol decoding cost at $n = 14$ (bits) is tractable with a pre-computed LLL-reduced basis for each OFDM bin.

The forward-link to Ch. 17: the same sphere decoder, scaled up to a matrix-MMSE-GDFE front end, is the MIMO detector for DMT-optimal LAST codes. Damen–El Gamal–Caire (2003) is the paper that made this chain rigorous.

Practical Constraints

•
For dense constellations ( $M \ge 4096$ ), hard-decision decoding saturates at high SNR — soft decoding via sphere-decoder LLRs is required
•
Complexity budget per bit is $\sim 200$ ns in modern ASICs, which limits sphere-decoder depth to $n \sim 16$ at per-bin granularity
•
LLL reduction is typically pre-computed offline at initialisation or whenever the channel updates — not per-symbol

📋 Ref: ETSI EN 302 769 (DVB-C2); CableLabs DOCSIS 4.0

Historical Note: Pohst (1981) and Schnorr–Euchner (1994): The Two Ancestors of the Sphere Decoder

1981–1999

The sphere-decoder idea has two mathematical ancestors in two unrelated fields. M. Pohst (1981, algebraic number theory) proposed an enumeration algorithm for finding all lattice vectors of bounded norm — motivated by computations in algebraic number fields, with no communications application in mind. Schnorr and Euchner (1994, cryptography) proposed a refined enumeration order for lattice basis reduction, motivated by attacks on the Merkle–Hellman knapsack cryptosystem.

Viterbo and Boutros (1999) rediscovered and communicated the algorithm for wireless communications, in a $5$ -page IEEE Trans. IT correspondence. They noticed that the sphere decoder, run with a specific initial radius tied to the expected noise norm, is a near-ML detector for lattice codes at polynomial average complexity — a game-changer for the practical deployment of space-time and lattice codes. The Damen–El Gamal–Caire (2003) paper then gave the first rigorous analysis of the average complexity and justified the sphere decoder's use in the LAST construction of Ch. 17, completing the arc from pure number theory (Pohst) to operational space-time coding (Caire et al.). A rare example where three unrelated research strands — algebraic number theory, cryptography, communications — converged on the same algorithm.

,

Common Mistake: Lattice Decoder ≠ Lattice Code

Mistake:

Conflating "lattice decoder" (a decoding algorithm) with "lattice code" (a codebook that is a subset of a lattice). The two are not the same. One can use a lattice decoder (sphere decoder, Babai nearest-plane, etc.) to decode a non-lattice codebook (like random Gaussian), and one can decode a lattice code with a non-lattice decoder (like MAP or bit-wise MMSE).

In particular, the Erez–Zamir theorem of s02 proves that the lattice code (with Gaussian ML decoding) achieves capacity, not the lattice decoder per se. A closely related theorem, the "MMSE lattice decoding achieves the capacity of the unconstrained lattice channel" (Erez–Litsyn–Zamir 2005), concerns the decoder and is a separate result.

Correction:

Always specify both the codebook (lattice code: $\Lambda_c \cap \mathcal{V}(\Lambda_s)$ ) and the decoder (lattice decoder: $Q_{\Lambda_c}$ applied to processed received vector). The Erez–Zamir scheme achieves capacity only when both are lattice-based, with the specific MMSE scaling and dither.

Common Mistake: Naïve ML Search Is Intractable at Any Real Rate

Mistake:

Implementing ML decoding by enumerating all $2^{n R}$ codewords in $\mathcal{C} = \Lambda_c \cap \mathcal{V}(\Lambda_s)$ and picking the one closest to the received vector. At even modest rates ( $R = 2$ bits/real dim) and modest dimensions ( $n = 64$ ), this is $2^{128}$ operations per codeword decision — far beyond any conceivable computational budget.

Correction:

Always use a structured CLP solver. The Pohst / Schnorr–Euchner sphere decoder, optionally preceded by LLL reduction, is the standard: $O(n^3)$ average complexity at high SNR, $O(n^{c})$ with larger $c$ near Poltyrev capacity, $O(n^6)$ for LLL pre-processing (one-time). For lattices with special structure (e.g., $E_8$ , $\Lambda_{24}$ , or nested constructions from binary codes), there exist fast dedicated decoders (Forney 1989; Conway–Sloane Ch. 20) that reduce the per-decoding cost to $O(n)$ or $O(n \log n)$ .

Why This Matters: Forward Reference: Lattice Decoding in LAST Codes (Ch. 17)

The sphere decoder's practical utility in this chapter is the AWGN decoder of the Erez–Zamir mod- $\Lambda$ scheme. In Chapter 17, the same machinery — QR + LLL + sphere search — becomes the MIMO decoder of the LAST (Lattice Space-Time) code of El Gamal, Caire, and Damen (2004). There, the matrix generator is $\mathbf{H}\mathbf{G}$ (channel × lattice basis), and the sphere decoder operates in the "whitened" residual after an MMSE-GDFE front-end cancels the ISI between MIMO streams. Damen–El Gamal–Caire (2003) proved the polynomial average complexity of this pipeline, which was the certificate that made LAST codes practical.

Closest-lattice-point problem

Given a lattice $\Lambda$ and a vector $\mathbf{y}$ , find $\arg\min_{\boldsymbol{\lambda} \in \Lambda} \|\mathbf{y} - \boldsymbol{\lambda}\|$ . NP-hard in the worst case; polynomial average time at high SNR via sphere decoder.

Sphere decoder

Branch-and-bound algorithm (Pohst 1981, Schnorr–Euchner 1994) that computes the closest lattice point via layer-by-layer exploration with norm-based pruning. Average complexity $O(n^3)$ at high SNR; exponential near Poltyrev capacity.

Babai estimate

The zero-order approximation $\mathbf{u}_{\text{Babai}} = \mathbf{G}^{-1} \mathbf{y}$ rounded component-wise. Correct at high SNR with high probability; used to seed the zigzag order of the sphere decoder. Polynomial-time but suboptimal for poorly-conditioned lattices.

Quick Check

The sphere decoder's average complexity for lattice decoding at high SNR (well below Poltyrev capacity) is:

$O(2^{n R})$ — exponential

$O(n^3)$ — polynomial (cubic)

$O(n)$ — linear

$O(n^6)$ — quartic or higher

Correction:

O(n^3)

— polynomial (cubic)

Correct. Viterbo–Boutros (1999) established this empirically; Damen–El Gamal–Caire (2003) proved it rigorously. The $n^3$ factor comes from $O(n^2)$ per- decoding zigzag operations plus $O(n^3)$ QR preprocessing.

Key Takeaway

The closest-lattice-point problem is NP-hard in the worst case but polynomial on average at high SNR, solved by the Pohst / Schnorr–Euchner sphere decoder with QR + branch-and- bound. At high SNR (well below Poltyrev capacity), the average complexity is $O(n^3)$ — cubic in the dimension, as cheap as the matrix algebra itself. Near capacity the complexity grows polynomially in $n$ with increasing degree, and backing off by $0.5$ – $1$ dB keeps the decoder tractable. LLL basis reduction ( $O(n^6)$ one-time cost) restores polynomial complexity for poorly-conditioned lattices. This is the computational certificate that turns the Erez–Zamir theorem from a non-constructive existence proof into a deployable algorithm — and the same machinery, generalised to matrix MMSE-GDFE, is the MIMO detector of the LAST codes of Ch. 17.

Lattice Decoding and the Closest-Point Problem

The Computational Cost of Capacity

Definition: Closest-Lattice-Point (CLP) Problem

Definition: Lattice-Decoding Error Probability

Pohst / Schnorr–Euchner Sphere Decoder

Theorem: Average Complexity of the Sphere Decoder (Viterbo–Boutros, Damen–El Gamal–Caire)

Sketch: high-SNR regime

Sketch: intermediate SNR

Near Poltyrev capacity

Sphere Decoder vs Brute Force: Complexity Scaling

Parameters

Example: Sphere Decoder on Z2\mathbb{Z}^2Z2 with a Received Point

Layer 2: enumerate $u_2$

Layer 1: enumerate $u_1$

Backtrack

Result

Example: CLP Hardness: Worst-Case Lattice That Defeats the Sphere Decoder

Construction

Why sphere decoder fails

Practical remedy: LLL reduction

Lattice Decoding in DVB-C2 and DOCSIS 4.0

Historical Note: Pohst (1981) and Schnorr–Euchner (1994): The Two Ancestors of the Sphere Decoder

Common Mistake: Lattice Decoder ≠ Lattice Code

Common Mistake: Naïve ML Search Is Intractable at Any Real Rate

Why This Matters: Forward Reference: Lattice Decoding in LAST Codes (Ch. 17)

Closest-lattice-point problem

Sphere decoder

Babai estimate

Quick Check

Key Takeaway

Definition:
Closest-Lattice-Point (CLP) Problem

Definition:
Lattice-Decoding Error Probability

Example: Sphere Decoder on $\mathbb{Z}^2$ with a Received Point