Reduced and Fixed-Complexity Variants of the LLL Algorithm for Communications

The Lenstra-Lenstra-Lovász (LLL) algorithm is a popular lattice reduction algorithm in communications. In this paper, variants of the LLL algorithm with either reduced or fixed complexity are proposed and analyzed. Specifically, the use of effective LLL reduction for lattice decoding is presented, where size reduction is only performed for pairs of consecutive basis vectors. Its average complexity (measured by the number of floating-point operations and averaged over i.i.d. standard normal lattice bases) is shown to be O(n³ log n), where n is the lattice dimension. This average complexity is an order lower than previously thought. To address the issue of variable complexity of the LLL algorithm, two fixed-complexity approximations are proposed. One is fixed-complexity effective LLL, for which the first vector of the basis is proven to be bounded in length; the other is fixed-complexity LLL with deep insertion, which is shown to be closely related to the well known V-BLAST algorithm. Such fixed-complexity structures are much desirable in hardware implementation since they allow straightforward constant-throughput implementation.