Effective LLL Reduction for Lattice Decoding

The use of Lenstra-Lenstra-Lovasz (LLL) lattice reduction significantly improves the performance of zero-forcing (ZF) and successive interference cancellation (SIC) decoders in multi-input multi-output (MIMO) communications. Capitalizing on the observation that the decision region of SIC is determined by the Gram-Schmidt vectors rather than the basis itself, we propose the use of effective LLL reduction in SIC decoding, where size reduction is only performed for pairs of consecutive basis vectors. We establish the theoretic upper bound O(n³ log n) on the average complexity of effective LLL reduction for the i.i.d. Gaussian model of MIMO fading channels, which is an order lower than previously thought. Moreover, an effectively LLL-reduced basis can easily be transformed into the standard LLL-reduced basis for the purpose of ZF decoding.