Complexity Evaluation for MIMO Sphere Decoder with Various Tree-searching Algorithms

摘要

Since finding the nearest point in a lattice for multi -input multi-output(MIMO) channels is NP-hard, simplified algorithms such as a sphere decoder (SD) have been proposed with various tree-searching strategy. This paper evaluate the complexity of MIMO Sphere Decoder in terms of resource complexity and processing cycle with various tree-searching algorithm for SD. Resource complexity is analyzed in closed form with various parameter such as the number of antennas and modulations, etc. and processing cycles is evaluated by computer simulation, as a result the resource complexity of Fincke and Phost algorithm is the lowest resource complexity among tree-searching algorithms for SD, but to obtain same processing cycles per one MIMO vector, Schnorr Euchner algorithm has the smallest resource complexity among tree-searching algorithms for SD.