Maximum likelihood soft-output detection through Sphere Decoding combined with box optimization

• Published in: Signal processing 2016-08, Vol.125, p.249-260
• Main Authors: Garcia-Molla, Victor M., Simarro, M. Angeles, Martínez-Zaldívar, F.J., González, Alberto, Vidal, Antonio M.
• Format: Article
• Language: English
• Subjects: Algorithms; Clipping; Decoding; MIMO; Optimization; Search algorithms; Searching; Soft-output maximum likelihood detection; Trees
• ISSN: 0165-1684; 1872-7557
• DOI: 10.1016/j.sigpro.2016.02.006

This paper focuses on the improvement of known algorithms for maximum likelihood soft-output detection. These algorithms usually have large computational complexity, that can be reduced by using clipping. Taking two well-known soft-output maximum likelihood algorithms (Repeated Tree Search and Single Tree Search) as a starting point, a number of modifications (based mainly on box optimization techniques) are proposed to improve the efficiency of the search. As a result, two new algorithms are proposed for soft-output maximum likelihood detection. One of them is based on Repeated Tree Search (which can be applied with and without clipping). The other one is based on Single Tree Search, which can only be applied to the case with clipping. The proposed algorithms are compared with the Single Tree Search algorithm, and their efficiency is evaluated in standard detection problems (4×4 16-QAM and 4×4 64-QAM) with and without clipping. The results show that the efficiency of the proposed algorithms is similar to that of the Single Tree Search algorithm in the case 4×4 16-QAM; however, in the case 4×4 64-QAM, the new algorithms are far more efficient than the Single Tree Search algorithm. •The paper is devoted to the study of MIMO soft-output detection algorithms, especially to those that calculate max-log Log-Likelihood ratios exactly.•The Repeated Tree Search (RTS) and Single Tree Search (STS) algorithms are studied, with and without the use of clipping.•Some modifications are proposed so that the computational cost is reduced without sacrificing accuracy.•The modifications have been extensively tested over 4×4 16QAM and 64QAM systems. The modifications are comparatively more efficient for larger constellations.