A near-ML Performance Adaptive Dijkstra Algorithm for Large Scale MIMO Detection

Abstract

Employing Maximum Likelihood (ML) algorithm for signal detection in large scale Multiple-Input- Multiple Output (MIMO) system  with high modulation order is a computationally expensive approach. In this paper an adaptive search algorithm is proposed for ML detection based MIMO receiver that can be classified as a derivative of Dijkstra’s Search (DS) algorithm based best first search  algorithm; hence naming Adaptive Dijkstra’s Search (ADS) algorithm. The proposed ADS exploits the resources available in the search procedure to reduce the required number of nodes to be visited in the tree. Results are obtained depending on a tunable parameter, which is defined to control the number of the best possible candidate nodes. Unlike the conventional DS, the ADS  algorithm results in signal detection with low computation complexity and quasi-optimal performance for systems under low and medium SNR regimes. Simulation results demonstrate 25% computational complexity reduction, compared to the conventional DS. For Symbol Error Rate (SER) of 10-2, such computation complexity reduction is also a trade-off with 2 dB SNR degradation, while attaining the same SER with conventional DS. The reduction of the computation complexity with the proposed ADS is non-linearly proportional to the dimension of MIMO combination as well as the modulation order.

French title: Une quasi ML performance par un algorithme adapté de Dijkstra pour une detection MIMO à grande échelle

Utiliser l'algorithme de vraisemblance maximale (ML) pour la détection de signal dans un système MIMO (Multiple-Input-Multiple Output) à grande échelle et avec un ordre de modulation élevé est une approche coûteuse en calcul. Dans cet article, un algorithme adaptatif de recherche est proposé pour la détection ML dans un récepteur MIMO, qui peut être considéré comme un dérivé de l’algorithme de recherche de Dijkstra (DS); d'où le nom de l'algorithme ADS (Adaptive Dijkstra’s Search). L'ADS proposé exploite les ressources disponibles dans la procédure de recherche pour réduire le nombre de noeuds à visiter dans l'arbre de recherche. Les résultats sont obtenus en fonction d'un paramètre ajustable, défini pour contrôler le nombre des meilleurs noeuds candidats possibles. Contrairement à la DS conventionnelle, l'algorithme ADS permet une détection de signal avec une complexité de calcul faible et des performances quasi optimales pour les systèmes sous un SNR faible et moyen. Les résultats de la simulation démontrent une réduction de la complexité de 25% par rapport à la DS classique. Pour un taux d'erreur de symbole (SER) de 10-2, une différence de 2 dB à la faveur l’algorithme ADS proposé par rapport à la DS conventionnelle. La réduction de la complexité de calcul avec l’ADS proposé est proportionnelle de manière non linéaire à la dimension de la combinaison MIMO ainsi qu’à l’ordre de modulation.