A tree-search algorithm for ML decoding in underdetermined MIMO systems

It is well known that maximum likelihood (ML) detection for multiantenna and/or multiuser systems has complexity that grows exponentially with the number of antennas and/or users. A number of suboptimal algorithms has been developed in the past that present an acceptable computational complexity and good approximations of the optimal solution. In this paper we propose a tree-search algorithm that provides the exact ML solution with lower computational complexity than that required by an exhaustive search of minimum distance. Also a two-stage tree-search algorithm is presented based on the idea that the ML solution is in the set of equilibrium points of a Hopfield neural networks (HNN). The two algorithms work without any modification both in underloaded and overloaded (underdetermined) systems. Numerical simulations show that improvements, in terms of computational complexity measured as the average number of required sum and/or products, are encouraging.