Best-First Tree Search with Probabilistic Node Ordering for MIMO Detection: Generalization and Performance-Complexity Tradeoff

The tree representation of the multiple-input multiple-output (MIMO) detection problem is illuminating for the development, interpretation, and classification of various detection methods. Best-first detection based on Dijkstra´s algorithm pursues tree search according to a sorted list of tree nodes. In the first part of the paper, a new probabilistic sorting scheme is developed and incorporated in a modified Dijkstra´s algorithm for MIMO detection. The proposed sorting exploits the statistics of the problem and yields effective tree exploration and truncation in the proposed algorithm. The second part of the paper generalizes the results in the first part and removes some limitations. A generalized Dijkstra´s algorithm is developed as a unified tree-search detection framework. The proposed framework incorporates a parameter triplet that allow the configuration of the memory usage, detection complexity, and sorting dynamic associated with the tree-search algorithm. By tuning different parameters, desired performance-complexity tradeoffs are attained and a fixed-complexity version can be produced. Simulation results and analytical discussions demonstrate that the proposed generalized Dijkstra´s algorithm shows abilities to achieve highly favorable performance-complexity tradeoffs.