Complexity study of sphere decoding in multi-antenna systems

In this article a bridge between the expected complexity and performance of sphere decoding (SD) is built. The expected complexity of SD for infinite lattices is then investigated, which naturally is the upper-bound of those for all the finite lattices if given by the same channel matrix and signal noise ratio (SNR). Such expected complexity is an important characterization of SD in multi-antenna systems, because no matter what modulation scheme is used in practice (generally it has finite constellation size) this upper-bound holds. Above bridge also leads to a new method of determining the radius for SD. The numerical results show both the real value and upper-bound of average searched number of candidates in SD for 16-QAM modulated system using the proposed sphere radius determining method. Most important of all new understandings of expected complexity of SD are given based on above mentioned theoretic analysis and numerical results.