Ferkans — Interactive Telecom Tutor

Why MIMO Detection Is Hard

A MIMO receiver sees a linear superposition of symbols, each drawn from a discrete constellation. The channel mixes them; the noise perturbs them. The receiver must untangle the mixture and snap each component back onto its finite alphabet. If the alphabet were continuous, least squares would suffice. Because it is discrete, the problem becomes combinatorial — and, in its exact form, as hard as the closest-vector problem in a general lattice. The story of MIMO detection is the story of trading complexity for accuracy along that discrete-continuous divide.

Definition:
MIMO Detection Model

Consider a narrowband point-to-point MIMO link with $n_t$ transmit and $n_r$ receive antennas. At a single channel use the received vector is $\mathbf{y} = \mathbf{H}\mathbf{x} + \mathbf{w}, \qquad \mathbf{H} \in \mathbb{C}^{n_r \times n_t}, \quad \mathbf{x} \in \mathcal{A}^{n_t}, \quad \mathbf{w} \sim \mathcal{CN}(\mathbf{0}, \sigma^2 \mathbf{I}_{n_r}).$ The constellation $\mathcal{A} \subset \mathbb{C}$ is a finite set of unit-energy symbols (e.g., QPSK, 16-QAM). Assuming the receiver knows $\mathbf{H}$ (pilot-based channel estimation; see Chapter 8), the MIMO detection problem is to produce an estimate $\hat{\mathbf{x}} \in \mathcal{A}^{n_t}$ of the transmitted vector.

In this chapter we hold $\mathbf{H}$ fixed and known. Joint estimation of $\mathbf{H}$ and $\mathbf{x}$ (blind / semi-blind detection) is a different beast entirely.

Definition:
Maximum-Likelihood MIMO Detector

With equiprobable symbols and white Gaussian noise, the maximum-likelihood detector minimizes the Euclidean distance between the observation and the noise-free hypothesis: $\hat{\mathbf{x}}_{\text{ML}} = \arg\min_{\mathbf{x} \in \mathcal{A}^{n_t}} \|\mathbf{y} - \mathbf{H}\mathbf{x}\|^2.$ The minimization is over a discrete set of size $|\mathcal{A}|^{n_t}$ .

The ML detector minimizes the symbol-vector error probability. It does NOT minimize the per-symbol (bit) error rate — for that, one needs the max-marginal (MAP) detector.

Theorem: Exponential Complexity of Exact ML Detection

Computing $\hat{\mathbf{x}}_{\text{ML}}$ by exhaustive search over $\mathcal{A}^{n_t}$ requires $|\mathcal{A}|^{n_t}$ evaluations of the metric $\|\mathbf{y} - \mathbf{H}\mathbf{x}\|^2$ . Moreover, the problem of deciding whether a given vector is the closest lattice point is $\mathcal{NP}$ -hard in the worst case.

The search space is a discrete product of constellations. Each additional transmit antenna multiplies the number of candidates by $|\mathcal{A}|$ . For $4\times 4$ 16-QAM we face $16^4 = 65{,}536$ candidates per channel use — already too many for real-time hardware at Gbps rates.

Proof

Counting candidates

There are $|\mathcal{A}|^{n_t}$ vectors in $\mathcal{A}^{n_t}$ . Each requires an $O(n_r n_t)$ matrix-vector product plus an $O(n_r)$ norm, giving $O(|\mathcal{A}|^{n_t} \cdot n_r n_t)$ total operations. This is exponential in $n_t$ .

NP-hardness of closest vector problem

Without the constellation constraint, the ML problem is equivalent to finding the closest point of the lattice $\Lambda(\mathbf{H})$ to $\mathbf{y}$ . Micciancio (2001) proved that the Closest Vector Problem (CVP) in $\ell_2$ is $\mathcal{NP}$ -hard. The MIMO detection problem is a bounded-CVP variant and inherits this worst-case hardness.

Consequence

No algorithm computes the exact ML solution in polynomial time in the worst case, assuming $\mathcal{P} \neq \mathcal{NP}$ . Sphere decoding (Section 12.4) circumvents worst-case complexity by exploiting the typical-case structure of Gaussian noise channels.

Remark on practical sizes

For $4\times 4$ 64-QAM: $64^4 \approx 1.68 \times 10^7$ candidates. For $8\times 8$ 256-QAM: $256^8 \approx 1.84 \times 10^{19}$ — a hopeless number at any clock rate. The need for suboptimal or structured search is not academic: it is forced by hardware reality. $\blacksquare$

Key Takeaway

MIMO detection is a discrete inverse problem: recover a finite-alphabet vector from a linear noisy mixture. The channel matrix $\mathbf{H}$ plays two roles simultaneously — it is both the regressor that constrains the estimate and the basis of a lattice whose geometry determines how hard the discrete search is.

Why This Matters: MIMO Detection in 5G NR

A 5G NR gNB running 4-layer spatial multiplexing with 256-QAM faces $256^4 \approx 4.3 \times 10^9$ candidate vectors per resource element. With 14 OFDM symbols, 273 PRBs, and thousands of REs per slot, brute-force ML is categorically impossible. Real basestations combine MMSE-SIC with list detection and soft-output iteration with the LDPC decoder. The latency budget — under 1 ms for URLLC — shapes every algorithmic choice.

See full treatment in The Restricted Isometry Property

ML Detection Complexity Grows Exponentially

Number of candidate vectors $|\mathcal{A}|^{n_t}$ as a function of $n_t$ for different constellation sizes. Note the logarithmic vertical axis.

Parameters

Maximum

n_t

8

Common Mistake: ML Vector Detection vs. Per-Bit MAP

Mistake:

One assumes the ML detector minimizes BER because it is "optimal."

Correction:

The ML detector minimizes the vector (symbol-block) error probability, not the bit error rate. A single symbol flip can corrupt many bits if the constellation is not Gray-coded. For minimum BER one should compute per-bit posterior probabilities via the max-marginal (bit-MAP) detector, which marginalizes rather than jointly minimizes. The distinction matters most at low SNR and for high-order constellations; at high SNR the two detectors are practically indistinguishable.

Example: $2 \times 2$ ML Detection by Exhaustive Search

With $\mathbf{H} = \begin{bmatrix} 1 & 0.6 \\ 0.3 & 0.9 \end{bmatrix}$ , QPSK alphabet $\mathcal{A} = \{\pm 1 \pm j\}/\sqrt{2}$ , and observation $\mathbf{y} = [0.85,\, 0.70]^T$ , compute $\hat{\mathbf{x}}_{\text{ML}}$ . Assume the noise is negligible and report the minimizer of $\|\mathbf{y} - \mathbf{H}\mathbf{x}\|^2$ .

Solution

Enumerate the alphabet

$|\mathcal{A}|^{n_t} = 4^2 = 16$ candidates. For a real-only sketch, restrict attention to $\mathbf{x} \in \{-1, +1\}^2 / \sqrt{2}$ (real QPSK). The four real-valued candidates are $\mathbf{x}^{(k)} \in \{(+,+), (+,-), (-,+), (-,-)\}/\sqrt{2}$ .

Compute the metric for each

For $\mathbf{x} = (+,+)/\sqrt{2}$ : $\mathbf{H}\mathbf{x} = (1.13, 0.85)^T$ , metric $= (0.85 - 1.13)^2 + (0.70 - 0.85)^2 = 0.0784 + 0.0225 = 0.1009$ . For $\mathbf{x} = (+,-)/\sqrt{2}$ : $\mathbf{H}\mathbf{x} = (0.28, -0.42)^T$ , metric $= 0.3249 + 1.2544 = 1.5793$ . For $\mathbf{x} = (-,+)/\sqrt{2}$ : symmetric — metric $= 1.5793$ . For $\mathbf{x} = (-,-)/\sqrt{2}$ : metric $= (0.85 + 1.13)^2 + (0.70 + 0.85)^2 = 3.9204 + 2.4025 = 6.3229$ .

Pick the minimum

The minimum occurs at $\mathbf{x} = (+1, +1)/\sqrt{2}$ , yielding $\hat{\mathbf{x}}_{\text{ML}} = (1, 1)/\sqrt{2}$ .

Interpret

Even for this toy $2 \times 2$ real case, the correct decision is not the one you would get by naively solving $\mathbf{x} = \mathbf{H}^{-1}\mathbf{y}$ and rounding — the coupling between streams biases the rounded estimate. This coupling is exactly what linear and nonlinear detectors (next sections) must compensate for.

Historical Note: The Birth of MIMO Detection

1995–2005

The MIMO channel model crystallized in the mid-1990s in two landmark papers: Telatar's information-theoretic analysis (1995, published 1999) established capacity, and Foschini's D-BLAST / V-BLAST architectures (1996, 1998) turned the capacity promise into a detection algorithm. Exact ML was recognized as infeasible from the start; the intellectual history of MIMO detection is the successive refinement of good suboptimal replacements, each exploiting a little more of the linear algebra or the lattice geometry than the previous one.

MIMO Detection

The task of recovering a finite-alphabet vector $\mathbf{x} \in \mathcal{A}^{n_t}$ from $\mathbf{y} = \mathbf{H}\mathbf{x} + \mathbf{w}$ given the channel $\mathbf{H}$ and the noise statistics.

Quick Check

For $n_t = 6$ transmit antennas and 16-QAM, how many candidates does exact ML detection enumerate per channel use?

$16 \cdot 6 = 96$

$6^{16}$

$16^{6} = 16{,}777{,}216$

$6! \cdot 16 = 11{,}520$