Comparison of the performance and the complexity of some ML detectors

Three ML detection algorithms are presented: semidefinite programming (SDP); sphere decoding (SD); branch-and-bound (BB). We apply these detectors to a digital communication system sending an n-dimensional PAM data vector that can be extracted from an n/2-dimensional QAM data vector. Before sending the data on a Rayleigh fading channel, it is precoded by rotation matrices that generate lattices with maximum diversity. After presenting the three detection methods, we run simulations to evaluate the performance of each algorithm in terms of bit error rate. The simulations are done for different values of the dimension n. They show that the SD algorithm and BB algorithm outperform the SDP algorithm. But it is also shown that the SDP algorithm is an interesting method to achieve near-ML performance with a complexity that is polynomial in the dimension n. We investigate the complexity of the SD and the BB algorithms in their different steps.