Graduate School and Research Center in Digital Sciences

Achieving a vanishing SNR gap to exact lattice decoding at a subexponential complexity

Singh, Arun; Elia, Petros; Jaldén, Joakim

IEEE Transactions on Information Theory, Volume 58, N°6, June 2012, ISSN: 0018-9448

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.

Document Doi Hal Bibtex

Title:Achieving a vanishing SNR gap to exact lattice decoding at a subexponential complexity
Keywords:Computational complexity , MIMO , detection , lattice decoding , performance-complexity tradeoff
Department:Communication systems
Eurecom ref:3647
Copyright: © 2012 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Bibtex: @article{EURECOM+3647, doi = {}, year = {2012}, month = {06}, title = {{A}chieving a vanishing {SNR} gap to exact lattice decoding at a subexponential complexity}, author = {{S}ingh, {A}run and {E}lia, {P}etros and {J}ald{\'e}n, {J}oakim}, journal = {{IEEE} {T}ransactions on {I}nformation {T}heory, {V}olume 58, {N}°6, {J}une 2012, {ISSN}: 0018-9448 }, url = {} }
See also: