Random selection LLL algorithm and its fixed complexity variant for MIMO detection

We propose a variant of the well-known Lenstra, Lenstra, Lovász algorithm (LLL) for MIMO detection in this paper, which is called random selection LLL (RSLLL). Not like the original LLL algorithm which sequentially searches through the whole basis, the new algorithm takes a random selection of the next pair of columns for LLL reduction. The proposed algorithm is proved to finish within finite number of iterations. Lower complexity is observed through computer simulation for MIMO systems. For fixed complexity implementation, pseudo random selection sequence can be taken to fix the execution flow. Simulation results show that the proposed fixed complexity RSLLL aided MIMO detection achieves lower complexity compared to the other fixed complexity variants of LLL without sacrificing the performance.