Vanishing the gap to exact lattice search at a subexponential complexity: LR-aided regularized decoding

Singh, Arun; Elia, Petros; Jalden, Joakim
ALLERTON 2011, Conference on Communication, Control and Computing, September 28-30, 2011, Allerton, USA

This work identifies the first lattice decoding solution that achieves, in the most general outage-limited MIMO setting and the high rate and high SNR 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 as well as the rate. The proposed solution employs lattice reduction (LR)-aided regularized (lattice) sphere decoding and proper timeout policies. In light of the fact that, prior to this work, a vanishing gap was generally attributed only to full lattice searches that have exponential complexity, in conjunction with the fact that subexponential complexity was generally attributed to early-terminated (linear) solutions which have though a performance gap that can be up to exponential in dimension and/or rate, the work constitutes the first proof that subexponential complexity need not come at the cost of exponential reductions in lattice decoding error performance. Finally, these performance and complexity guarantees hold for the most general MIMO setting, for all reasonable fading statistics, all channel dimensions, and all lattice codes.

















Systèmes de Communication
Eurecom Ref:
© 2011 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.