Circular Sphere Decoding: A Low Complexity Detection for MIMO Systems With General Two-dimensional Signal Constellations

We propose a low-complexity, complex-valued sphere decoding (CV-SD) algorithm, which is referred to as circular sphere decoding (CSD) and is applicable to multiple-input-multiple-output (MIMO) systems with arbitrary 2-D constellations. CSD provides a new constraint test. This constraint test is carefully designed so that the elementwise dependence is removed in the metric computation for the test. As a result, the constraint test becomes simple to perform without restriction on its constellation structure. By additionally employing this simple test as a prescreening test, CSD reduces the complexity of the CV-SD search. We show that the complexity reduction is significant, while its maximum-likelihood (ML) performance is not compromised. We also provide a powerful tool to estimate the pruning capacity of any particular search tree. Using this tool, we propose the predict-and-change strategy, which leads to a further complexity reduction in CSD. Extension of the proposed methods to soft output sphere decoding (SD) is also presented.