An Efficient Tree Search for Reduced Complexity Sphere Decoding

The complexity of sphere decoding (SD) has been widely studied due to the importance of this algorithm in obtaining the optimal maximum likelihood (ML) performance with lower complexity. In this paper, we propose a proper tree search traversal technique that reduces the overall SD computational complexity without sacrificing the performance. We exploit the similarity among the complex symbols in a square QAM lattice representation and rewrite the squared norm ML metric in a simpler form allowing significant reduction of the number of operations required to decode the transmitted symbols. We also show that this approach achieves > 45% complexity gain for systems employing 4-QAM, and that this gain becomes bigger as the constellation size is larger.