Change search
ReferencesLink to record
Permanent link

Direct link
Achieving a Vanishing SNR Gap to Exact Lattice Decoding at a Subexponential Complexity
KTH, School of Electrical Engineering (EES), Signal Processing. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0001-6630-243X
2012 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, Vol. 58, no 6, 3692-3707 p.Article in journal (Refereed) Published
Abstract [en]

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-Lovasz-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.

Place, publisher, year, edition, pages
2012. Vol. 58, no 6, 3692-3707 p.
Keyword [en]
Computational complexity, detection, lattice decoding, MIMO, performance-complexity tradeoff
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
URN: urn:nbn:se:kth:diva-97996DOI: 10.1109/TIT.2012.2190709ISI: 000304245100026ScopusID: 2-s2.0-84861359992OAI: diva2:535042
EU, European Research Council, 228044 257616 (CONECT)ICT - The Next Generation

QC 20120619

Available from: 2012-06-19 Created: 2012-06-18 Last updated: 2013-04-11Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Jaldén, Joakim
By organisation
Signal ProcessingACCESS Linnaeus Centre
In the same journal
IEEE Transactions on Information Theory
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 35 hits
ReferencesLink to record
Permanent link

Direct link