Fixing the Complexity of the Sphere Decoder for MIMO Detection

A new detection algorithm for uncoded multiple input-multiple output (MIMO) systems based on the complex version of the sphere decoder (SD) is presented in this paper. It performs a fixed number of operations during the detection process, overcoming the two main problems of the SD from an implementation point of view: its variable complexity and its sequential nature. The algorithm combines a novel channel matrix ordering with a search through a very small subset of the complete transmit constellation. A geometrically-based method is used to study the effect the proposed ordering has on the statistics of the MIMO channel. Using those results, a generalization is given for the structure this subset needs to follow in order to achieve quasi-maximum likelihood (ML) performance. Simulation results show that it has only a very small bit error rate (BER) degradation compared to the original SD while being suited for a fully-pipelined hardware implementation due to its low and fixed complexity.