Research on Low Complexity K-best Sphere Decoding Algorithm for MIMO Systems

In order to reduce the complexity of hard-output K-best decoding algorithm in multiple-input multiple-output (MIMO) systems and guarantee performance of the system, we propose a bit-sort (BS) strategy based on bit counting operation in hardware implementation for the K-best decoder. The proposed BS K-best algorithm finds out the smallest \(K\) paths by scanning and counting the bits of every candidate, which is much simpler than the pairwise comparison operation in conventional K-best algorithm. Moreover, we proposed a dynamic bit-sort (DBS) strategy for the K-best decoder based on the BS strategy. The DBS K-best algorithm further reduces the complexity of BS K-best algorithm by selecting a dynamic \(K\) value that depends on the candidates. The complexity analysis shows the complexity of bit counting operations in proposed BS K-best algorithm is much less than that of the pairwise comparisons in conventional K-best algorithm, and the DBS K-best algorithm can further reduce about 50 % counting complexity of BS K-best algorithm. The simulation results show both the BS K-best decoder and DBS K-best decoder can achieve the same performance as that of hard-output sphere decoding algorithm if a proper \(K\) is selected.