Improved Maximum Likelihood detection through sphere decoding combined with box optimization

• A modification of the Sphere Decoding algorithm for MIMO detection is proposed, based on continuous minimization.
• In the low SNR regime, the proposed algorithm is orders of magnitude faster than the standard Schnorr–Euchner Sphere Decoding algorithm.
• Graphs show that the new algorithm obtains virtually noise-independent Maximum Likelihood decoding.
• Other known optimizations (such as reordering of the channel matrix) can be applied, so that further increases in performance can be expected.

Sphere Decoding is a popular Maximum Likelihood algorithm that can be used to detect signals coming from multiple-input, multiple-output digital communication systems. It is well known that the complexity required to detect each signal with the Sphere Decoding algorithm may become unacceptable, especially for low signal-to-noise ratios. In this paper, we describe an auxiliary technique that drastically decreases the computation required to decode a signal. This technique was proposed by Stojnic, Hassibi and Vikalo in 2008, and is based on using continuous box-bounded minimization in combination with Sphere Decoding. Their implementation is, however, not competitive due to the box minimization algorithm selected. In this paper we prove that by judiciously selecting the box minimization algorithm and tailoring it to the Sphere Decoding environment, the computational complexity of the resulting algorithm for low signal-to-noise ratios is better (by orders of magnitude) than standard Sphere Decoding implementations.