On Improving the Efficiency of the Fixed-Complexity Sphere Decoder

Fixed-complexity sphere decoder (FSD), which consists of ordering stage and tree-search stage, achieves a quasi-ML, performance while requiring a fixed computational effort independent of the noise power and channel conditioning. Nevertheless, it requires a specific signal ordering using the VBLAST algorithm which has a high complexity due to the iterative pseudo-inversion of the channel matrix. In this paper, we propose two schemes to reduce the complexity of FSD algorithm in the ordering and tree-search stages, respectively, while achieving quasi-ML, performance. In the ordering stage, we propose QR-decomposition-based FSD signal ordering (FSD-SQRD) that requires only a few number of additional complex flops compared to the unsorted QRD. In the tree-search stage, we introduce a threshold-based complexity reduction approach for FSD depending on the reliability of the signal with the lowest received SNR. Numerical results show that in a 4x4 system, the proposed FSD-SQRD requires only 17.2% of the computational efforts required by a reduced-complexity VBLAST approach. Moreover, using 16-QAM, simulation results show that when the proposed threshold-based approach is employed, FSD requires only 69.5% of its full complexity.