Recursive Tree Search Maximum-Likelihood Detection for Underdetermined Systems

Abstract

The realization of the next-generation Internet of Things (IoT) will require extensive support for overloaded wireless systems, which occurs when the number of users or connected devices exceeds the available resources, such as antennas in multi-user, multi-input, multi-output (MU-MIMO) communications. Underdetermined box-constrained integer least squares (UBILS) can be used to represent the decoding problem of overloaded communication networks. Maximum likelihood (ML) detection provides optimal performance but suffers from high exponential complexity. User-by-user sequential interference cancellation (SIC), which decodes users in power order, offers significant computational cost reduction but is unreliable for high-order M-QAM modulation. Sphere decoding is another well-known strategy to lower ML decoding complexity, but it is also challenged by underdetermined systems and high-order M-QAM modulation. A few methods have proven to be effective for both higher-order modulations and underdetermined systems. However, these methods are unable to either provide ML optimal detection performance or significantly reduce its complexity. This study proposes a recursive tree search (RTS) method that significantly lowers the average complexity compared to exhaustive ML search for optimal ML decoding of underdetermined systems. The RTS approach has a straightforward structure with few parameters that require tuning, and its average complexity compares favorably with other recently presented methods. The computational performance and error rate are contrasted with those of other methods, such as generalized sphere decoding (GSD), alternating-direction method of multipliers (ADMM), and direct tree search (DTS).