A unified view of sorting in lattice reduction: From V-BLAST to LLL and beyond

In this paper, we present a unified view of the role of sorting in lattice reduction. In particular, we show that V-BLAST sorting is a relative of the LLL algorithm. More precisely, we discover that if a lattice basis is sorted in the sense closely related to V-BLAST and is size-reduced, then it is reduced in the sense of LLL with deep insertion (LLL-deep). This discovery leads to two useful consequences. One consequence is a parallel version of LLL-deep that iteratively applying sorting and size reduction; we show that a hybrid strategy applying parallel LLL-deep at the early stage can improve the speed of LLL-deep. The other is a fixed-complexity algorithm of LLL, which consists of a few iterations of sorting and size reduction. This fixed-complexity structure is much desirable in hardware implementation that circumvents the variable complexity of standard LLL, and its throughput is only limited by that of V-BLAST when implemented in a pipeline structure.