On maximum-likelihood detection and the search for the closest lattice point

TLDR

Maximum‑likelihood decoding for Gaussian MIMO linear channels is traditionally implemented via sphere decoders that exploit lattice‑point search techniques. This work revisits sphere decoding and introduces two new algorithms. The first algorithm, based on Pohst enumeration, cuts complexity relative to the Viterbo‑Boutros decoder, while the second, derived from the Schnorr‑Euchner strategy and enhanced by preprocessing, further reduces complexity and preserves near‑ML performance. Simulation and theoretical analysis confirm that the new algorithms achieve substantial complexity savings over existing sphere decoders while maintaining near‑ML detection accuracy across many scenarios.

Abstract

Maximum-likelihood (ML) decoding algorithms for Gaussian multiple-input multiple-output (MIMO) linear channels are considered. Linearity over the field of real numbers facilitates the design of ML decoders using number-theoretic tools for searching the closest lattice point. These decoders are collectively referred to as sphere decoders in the literature. In this paper, a fresh look at this class of decoding algorithms is taken. In particular, two novel algorithms are developed. The first algorithm is inspired by the Pohst enumeration strategy and is shown to offer a significant reduction in complexity compared to the Viterbo-Boutros sphere decoder. The connection between the proposed algorithm and the stack sequential decoding algorithm is then established. This connection is utilized to construct the second algorithm which can also be viewed as an application of the Schnorr-Euchner strategy to ML decoding. Aided with a detailed study of preprocessing algorithms, a variant of the second algorithm is developed and shown to offer significant reductions in the computational complexity compared to all previously proposed sphere decoders with a near-ML detection performance. This claim is supported by intuitive arguments and simulation results in many relevant scenarios.