Ferkans — Interactive Telecom Tutor

Searching a Sphere, Not a Cube

Exhaustive ML search visits every vertex of the $n_t$ -dimensional hypercube $\mathcal{A}^{n_t}$ . Sphere decoding visits only those lattice points that lie inside a sphere of radius $r$ around the received vector. Because the noise is Gaussian, most of the probability mass on the distance to the true transmit vector concentrates on $O(r)$ with $r^2 \approx n_r \sigma^2$ — so a well-chosen radius captures the ML solution almost surely while pruning the search tree aggressively. At moderate-to-high SNR, the expected number of visited points grows polynomially in $n_t$ ; at low SNR, it degenerates to exponential.

Definition:
The MIMO Lattice

The set of all noise-free received vectors, as $\mathbf{x}$ ranges over $\mathbb{Z}^{n_t}$ (after rescaling/shifting the constellation into an integer grid), is the lattice $\Lambda(\mathbf{H}) = \{\mathbf{H}\mathbf{z} : \mathbf{z} \in \mathbb{Z}^{n_t}\} \subset \mathbb{C}^{n_r}.$ The MIMO detection problem becomes a closest-vector problem within a bounded region corresponding to the constellation $\mathcal{A}^{n_t}$ .

Real-valued sphere decoders work in $\mathbb{R}^{2n_r}$ with $\mathbb{R}^{2n_t}$ -valued integers by stacking real and imaginary parts. QAM constellations map naturally to integer lattices after scaling.

Theorem: QR Decomposition Enables Depth-First Pruning

Let $\mathbf{H} = \mathbf{Q}\mathbf{R}$ be the economy QR factorization with $\mathbf{R}$ upper-triangular and $\mathbf{Q} \in \mathbb{C}^{n_r \times n_t}$ having orthonormal columns. Let $\mathbf{y}' = \mathbf{Q}^H \mathbf{y}$ . Then for any candidate $\mathbf{x} \in \mathcal{A}^{n_t}$ , $\|\mathbf{y} - \mathbf{H}\mathbf{x}\|^2 = \|\mathbf{y}' - \mathbf{R}\mathbf{x}\|^2 + \text{const} = \sum_{i=1}^{n_t}\!\left|y'_i - \sum_{j=i}^{n_t} R_{ij} x_j\right|^2 + \text{const}.$ The sum is triangular: its $i$ -th term depends only on $x_i, \ldots, x_{n_t}$ .

The triangular structure lets us bound the total metric by partial sums. If the partial sum from level $i$ down already exceeds the current best radius, every extension is hopeless — we prune.

Proof

Rotate the observation

Because $\mathbf{Q}$ has orthonormal columns, the Euclidean norm is preserved under multiplication by $\mathbf{Q}^H$ on the image of $\mathbf{H}$ . A projection onto the null space contributes a constant term depending only on $\mathbf{y}$ , which we absorb into "const."

Use upper-triangularity

The $i$ -th component of $\mathbf{R}\mathbf{x}$ involves only $x_i, x_{i+1}, \ldots, x_{n_t}$ because $R_{ij} = 0$ for $j < i$ .

Decompose the metric

Since $\|\mathbf{y}' - \mathbf{R}\mathbf{x}\|^2 = \sum_{i=1}^{n_t} |y'_i - (\mathbf{R}\mathbf{x})_i|^2$ , each summand is a function of $x_i,\ldots,x_{n_t}$ only.

Pruning principle

Enumerating $\mathbf{x}$ from the last coordinate $x_{n_t}$ backward to $x_1$ , the partial sum $\sum_{i=\ell}^{n_t}|y'_i - \sum_{j\geq i} R_{ij} x_j|^2$ is non-decreasing in $\ell$ . If it ever exceeds $r^2$ (the current best known radius), any completion of $(x_1,\ldots,x_{\ell-1})$ yields a worse candidate — we prune the subtree. $\blacksquare$

Schnorr-Euchner Sphere Decoder

Complexity: Expected

O(n_t^p)

at moderate SNR; worst case

O(|\mathcal{A}|^{n_t})

Input:

\mathbf{y}

,

\mathbf{H}

, alphabet

\mathcal{A}

, initial radius

r

Output:

\hat{\mathbf{x}}_{\text{ML}}

1. Compute

\mathbf{H} = \mathbf{Q}\mathbf{R}

and

\mathbf{y}' = \mathbf{Q}^H \mathbf{y}

2. Initialize

k \leftarrow n_t

,

T_k \leftarrow 0

, best radius

r^\star \leftarrow r

,

\hat{\mathbf{x}} \leftarrow \text{NULL}

3. Compute the Babai estimate

\check{x}_k \leftarrow (y'_k - \sum_{j>k} R_{kj} x_j) / R_{kk}

4. Order candidates in

\mathcal{A}

by increasing

|x_k - \check{x}_k|

(Schnorr-Euchner zig-zag)

5. loop

6.

\quad x_k \leftarrow \text{next candidate in the SE order for level } k

7.

\quad \text{partial} \leftarrow T_k + |R_{kk}(x_k - \check{x}_k)|^2

8.

\quad

if

\text{partial} \geq r^{\star 2}

then backtrack:

k \leftarrow k+1

; if

k > n_t

then return

\hat{\mathbf{x}}

9.

\quad

else if

k = 1

then update best:

\hat{\mathbf{x}} \leftarrow (x_1,\ldots,x_{n_t})

;

r^\star \leftarrow \sqrt{\text{partial}}

; backtrack

10.

\quad

else descend:

T_{k-1} \leftarrow \text{partial}

;

k \leftarrow k-1

; recompute Babai

\check{x}_k

11. end loop

The Schnorr-Euchner enumeration orders children by increasing metric, which causes the best candidates to be found first and shrinks $r^\star$ aggressively. Radius updating (line 9) is the key speed-up over the original Viterbo-Boutros decoder with fixed radius.

Theorem: Sphere Decoding is ML-Optimal on Termination

If the initial radius $r$ is chosen so that at least one lattice point in $\mathbf{H}\mathcal{A}^{n_t}$ lies within distance $r$ of $\mathbf{y}$ , the Schnorr-Euchner sphere decoder terminates and returns $\hat{\mathbf{x}}_{\text{ML}}$ .

The algorithm enumerates every point inside the sphere whose partial metric does not already exceed the current best. The radius is only ever decreased when an improvement is found. Nothing can be missed that was not provably worse.

Proof

Pruning is safe

A subtree is pruned only when its partial metric at some level exceeds $r^{\star 2}$ . Since partial metrics are non-decreasing in completion, no descendant can achieve a total metric smaller than the current $r^{\star 2}$ . Hence no potential improvement is discarded.

Radius updates maintain feasibility

When a new best candidate is found, $r^\star$ is tightened to the exact distance of that candidate, guaranteeing at least one lattice point still lies within the (new) sphere.

Finite termination

The search tree is finite — there are at most $|\mathcal{A}|^{n_t}$ leaves. Depth-first traversal with pruning visits a subset, terminating in finitely many steps.

Optimality

At termination, $\hat{\mathbf{x}}$ is the candidate with the smallest observed metric. Pruning guarantees no discarded candidate had a smaller metric. Hence $\hat{\mathbf{x}} = \hat{\mathbf{x}}_{\text{ML}}$ . $\blacksquare$

Expected Complexity and Its Honest Limit

Hassibi and Vikalo (2005) showed that under i.i.d. Rayleigh channels and fixed SNR, the expected number of lattice points inside the sphere grows as $O(n_t^{p(\text{SNR})})$ for some SNR-dependent exponent $p(\text{SNR})$ . Jaldén and Ottersten (2005) proved, however, that the expected complexity is exponential at any fixed SNR — the polynomial behavior only holds when the SNR scales up with $n_t$ . The practical message: sphere decoders are fast where practical wireless systems operate (moderate-to-high SNR), but one should not call them "polynomial" without qualification.

,

Sphere Decoder Nodes Visited vs. SNR

Average number of tree nodes visited by the Schnorr-Euchner sphere decoder as a function of SNR. At high SNR, the search is nearly linear in $n_t$ ; at low SNR it approaches exhaustive.

Parameters

n_t = n_r

4

Sphere Decoder: $\mathbf{R}$ -Triangular Search and Pruning

Visualizes the depth-first search over a small lattice, with pruned subtrees highlighted as the radius

r

shrinks after each improvement.

Tree nodes colored by fate: green = best-so-far, red = pruned, gray = explored. Radius tightens each time a shorter lattice vector is discovered.

Example: Two-Dimensional Sphere Decoder by Hand

With $\mathbf{R} = \begin{bmatrix} 1.0 & 0.4 \\ 0 & 0.8 \end{bmatrix}$ , $\mathbf{y}' = (0.9, 0.5)^T$ , alphabet $\{-1, +1\}$ , and initial radius $r = 2$ , trace the Schnorr-Euchner search and report $\hat{\mathbf{x}}_{\text{ML}}$ .

Solution

Level $k = 2$: Babai estimate

$\check{x}_2 = y'_2 / R_{22} = 0.5/0.8 = 0.625$ . SE order: $+1$ first (distance $0.375$ ), then $-1$ (distance $1.625$ ). Try $x_2 = +1$ : partial $= |0.8 \cdot (1 - 0.625)|^2 = 0.09$ . OK, continue.

Level $k = 1$ under $x_2 = +1$

$\check{x}_1 = (y'_1 - R_{12} x_2)/R_{11} = (0.9 - 0.4)/1.0 = 0.5$ . SE order: $+1$ (distance $0.5$ ), then $-1$ (distance $1.5$ ). Try $x_1 = +1$ : total $= 0.09 + |1.0 \cdot (1 - 0.5)|^2 = 0.09 + 0.25 = 0.34$ . Leaf! Update $\hat{\mathbf{x}} = (+1,+1)^T$ , $r^{\star 2} = 0.34$ .

Level $k = 1$ with $x_1 = -1$

Partial on $x_1 = -1$ : $|1.0 \cdot (-1 - 0.5)|^2 = 2.25 > 0.34$ . Prune. Backtrack to $k = 2$ .

Level $k = 2$ with $x_2 = -1$

Partial: $|0.8 \cdot (-1 - 0.625)|^2 = 1.69 > 0.34$ . Prune. No candidates remain at level 2. Terminate.

Result

$\hat{\mathbf{x}}_{\text{ML}} = (+1, +1)^T$ with metric $0.34$ . Out of $2^2 = 4$ possible leaves, only one was fully evaluated — the other three were pruned by partial-metric bounds. This is the sphere decoder in action.

Historical Note: From Fincke-Pohst to Wireless Receivers

1985–1999

Sphere decoding originated in number theory: Fincke and Pohst (1985) introduced the lattice enumeration algorithm for computing short vectors. Viterbo and Boutros (1999) adapted it to wireless communications, presenting the first sphere decoder for MIMO-like problems. Schnorr and Euchner (1994), working independently in cryptographic lattice contexts, introduced the zig-zag enumeration order that dramatically accelerates the search. The combined algorithm — Viterbo-Boutros structure with Schnorr-Euchner ordering — is what most modern MIMO implementations use.

Common Mistake: Choosing the Wrong Initial Radius

Mistake:

One picks an initial radius $r$ too small, and the sphere decoder returns "no candidate found."

Correction:

A safe choice is $r^2 = \beta \cdot n_r \cdot \sigma^2$ with $\beta \in [2, 4]$ , calibrated to cover the typical noise norm with high probability. Alternatively, initialize from the Babai / ZF estimate: compute $\hat{\mathbf{x}}_{\text{ZF}}$ , snap to the alphabet, and use $r = \|\mathbf{y} - \mathbf{H} \hat{\mathbf{x}}_{\text{ZF}}\|$ . This guarantees at least one lattice point inside the sphere and provides an immediate radius tightening on the first leaf.

⚠️Engineering Note

Sphere Decoders in Hardware

Commercial MIMO receivers ship sphere decoders only when $n_t \leq 4$ and the constellation is 16-QAM or smaller. Above that, the variable throughput (a data-dependent node count per channel use) becomes incompatible with deterministic latency budgets. FPGA implementations typically use a K-best variant: keep only the $K$ best partial candidates at each level, sacrificing ML optimality for fixed throughput.

Practical Constraints

•
K-best: deterministic latency, near-ML for $K \geq 8$ and $n_t \leq 4$
•
Pure sphere decoder: variable latency, unusable in fixed-rate pipelines

Sphere Decoding

A depth-first lattice search that enumerates only lattice points within a given radius of the received vector, using QR-based triangular metric bounds to prune subtrees. ML-optimal when it terminates with a candidate.

Schnorr-Euchner Enumeration

A zig-zag ordering of lattice candidates at each level, visiting points in order of increasing distance from the Babai / continuous estimate. Accelerates sphere decoding by finding good candidates early and tightening the radius faster.

Quick Check

Sphere decoding prunes a subtree when:

The partial metric already exceeds the current best radius squared

The candidate symbol is not the nearest to the Babai estimate

The QR decomposition has zero diagonal entries

A random threshold is met

Correction:

The partial metric already exceeds the current best radius squared

Partial metrics are non-decreasing, so the best completion cannot beat the current incumbent.

Sphere Decoding

Searching a Sphere, Not a Cube

Definition: The MIMO Lattice

Theorem: QR Decomposition Enables Depth-First Pruning

Rotate the observation

Use upper-triangularity

Decompose the metric

Pruning principle

Schnorr-Euchner Sphere Decoder

Theorem: Sphere Decoding is ML-Optimal on Termination

Pruning is safe

Radius updates maintain feasibility

Finite termination

Optimality

Expected Complexity and Its Honest Limit

Sphere Decoder Nodes Visited vs. SNR

Parameters

Sphere Decoder: R\mathbf{R}R-Triangular Search and Pruning

Example: Two-Dimensional Sphere Decoder by Hand

Level $k = 2$: Babai estimate

Level $k = 1$ under $x_2 = +1$

Level $k = 1$ with $x_1 = -1$

Level $k = 2$ with $x_2 = -1$

Result

Historical Note: From Fincke-Pohst to Wireless Receivers

Common Mistake: Choosing the Wrong Initial Radius

Sphere Decoders in Hardware

Sphere Decoding

Schnorr-Euchner Enumeration

Quick Check

Definition:
The MIMO Lattice

Sphere Decoder: $\mathbf{R}$ -Triangular Search and Pruning