Title :
Worst- and average-case complexity of LLL lattice reduction in MIMO wireless systems
Author :
Jaldén, Joakim ; Seethaler, Dominik ; Matz, Gerald
Author_Institution :
Inst. of Commun. & Radio-Freq. Eng., Vienna Technol. Univ., Vienna
fDate :
March 31 2008-April 4 2008
Abstract :
Lattice reduction by means of the LLL algorithm has been previously suggested as a powerful preprocessing tool that allows to improve the performance of suboptimal detectors and to reduce the complexity of optimal MIMO detectors. The complexity of the LLL algorithm is often cited as polynomial in the dimension of the lattice. In this paper we argue that this statement is not correct when made in the MIMO context. Specifically, we demonstrate that in typical communication scenarios the worst-case complexity of the LLL algorithm is not even finite. For i.i.d. Rayleigh fading channels, we further prove that the average LLL complexity is polynomial and that the probability for an atypically large number of LLL iterations decays exponentially.
Keywords :
MIMO communication; Rayleigh channels; iterative methods; polynomials; signal detection; LLL lattice reduction; MIMO wireless systems; Rayleigh fading channels; average-case complexity; exponential decay; iteration method; optimal MIMO detectors; polynomial time; suboptimal detectors; worst-case complexity; Broadcasting; Context; Detectors; Iterative algorithms; Lattices; MIMO; Polynomials; Rayleigh channels; Stochastic processes; Stochastic systems; LLL; MIMO; complexity; decoding; lattice reduction; precoding;
Conference_Titel :
Acoustics, Speech and Signal Processing, 2008. ICASSP 2008. IEEE International Conference on
Conference_Location :
Las Vegas, NV
Print_ISBN :
978-1-4244-1483-3
Electronic_ISBN :
1520-6149
DOI :
10.1109/ICASSP.2008.4518202