New Approaches for Lowering Path Expansion Complexity of K-Best MIMO Detection Algorithms

The present paper proposes two original approaches to reduce computational resources necessary for expanding survivor paths while searching in a K-best manner the MIMO detection tree. The first approach involves precomputing some products that are so far recomputed for each path expansion. The second technique is a new method to compute the path metrics. In all K-best detection techniques proposed so far, the complexity necessary to expand a path grows with the path depth in the tree. The originality of our approach stems from the fact that the path expansion complexity decreases with the path depth. Since the number of expanded paths increases with their depth, our approach better balances the path expansion complexity and the number of expanded paths at a given depth, which can yield a significant complexity reduction. We then present a new K-best Hard-Output Lattice Decoding (K-HOLD) algorithm that combines both proposed techniques. A complexity analysis shows that K-HOLD can reduce by up to 70% the overall path expansion complexity as compared to the less-complex known algorithms. This advantage comes about at no cost in terms of performance degradation.