Sphere Decoding Revisited

In this paper, the paradigm of sphere decoding (SD) for solving the integer least square problem (ILS) is revisited, where extra degrees of freedom are introduced to exploit the decoding potential. Firstly, the equivalent sphere decoding (ESD) is proposed, which is essentially the same with the classic Fincke-Pohst sphere decoding but characterizes the sphere radius $D>0$ with two new parameters named as initial searching size $K>1$ and deviation factor $σ>0$. By fixing $σ$ properly, we show that given the sphere radius $D\triangleqσ\sqrt{2\ln K}$, the complexity of ESD in terms of the number of visited nodes is upper bounded by $|S|<nK$, thus resulting in an explicit and tractable decoding trade-off solely controlled by $K$. To the best of our knowledge, this is the first time that the complexity of sphere decoding is exactly specified, where considerable decoding potential can be explored from it. After that, two enhancement mechanisms named as normalized weighting and candidate protection are proposed to further upgrade the ESD algorithm. On one hand, given the same setups of $K$ and $σ$, a larger sphere radius is achieved, indicating a better decoding trade-off. On the other hand, the proposed ESD algorithm is generalized, which bridges suboptimal and optimal decoding performance through the flexible choice of $K$. Finally, further performance optimization and complexity reduction with respect to ESD are also derived, and the introduced tractable and flexible decoding trade-off is verified through large-scale MIMO detection.