Achieving a Vanishing SNR Gap to Exact Lattice Decoding at a Subexponential Complexity

This study identifies the first lattice decoding solution that achieves, in the general outage-limited multiple-input multiple-output (MIMO) setting and in the high-rate and high-signal-to-noise ratio limit, both a vanishing gap to the error performance of the exact solution of regularized lattice decoding, as well as a computational complexity that is subexponential in the number of codeword bits and in the rate. The proposed solution employs Lenstra-Lenstra-Lovász-based lattice reduction (LR)-aided regularized (lattice) sphere decoding and proper timeout policies. These performance and complexity guarantees hold for most MIMO scenarios, most fading statistics, all channel dimensions, and all full-rate lattice codes. In sharp contrast to the aforementioned very manageable complexity, the complexity of other standard preprocessed lattice decoding solutions is revealed here to be extremely high. Specifically, this study has quantified the complexity of regularized lattice (sphere) decoding and has proved that the computational resources required by this decoder to achieve a good rate-reliability performance are exponential in the lattice dimensionality and in the number of codeword bits, and it in fact matches, in common scenarios, the complexity of ML-based sphere decoders. Through this sharp contrast, this study was able to, for the first time, rigorously demonstrate and quantify the pivotal role of LR as a special complexity reducing ingredient.