Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the Complexity Distribution of Sphere Decoding
KTH, School of Electrical Engineering (EES), Signal Processing. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0001-6630-243X
Rice University, TX, USA.
ETH Zurich, Switzerland.
2011 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 57, no 9, 5754-5768 p.Article in journal (Refereed) Published
Abstract [en]

We analyze the (computational) complexity distribution of sphere decoding (SD) for random infinite lattices. In particular, we show that under fairly general assumptions on the statistics of the lattice basis matrix, the tail behavior of the SD complexity distribution is fully determined by the inverse volume of the fundamental regions of the underlying lattice. Particularizing this result to N x M, N ≥ M, i.i.d. circularly symmetric complex Gaussian lattice basis matrices, we find that the corresponding complexity distribution is of Pareto-type with tail exponent given by N-M+1. A more refined analysis reveals that the corresponding average complexity of SD is infinite for N = M and finite for N >; M. Finally, for i.i.d. circularly symmetric complex Gaussian lattice basis matrices, we analyze SD preprocessing techniques based on lattice-reduction (such as the LLL algorithm or layer-sorting according to the V-BLAST algorithm) and regularization. In particular, we show that lattice-reduction does not improve the tail exponent of the complexity distribution while regularization results in a SD complexity distribution with tails that decrease faster than polynomial.

Place, publisher, year, edition, pages
IEEE , 2011. Vol. 57, no 9, 5754-5768 p.
Keyword [en]
Complexity theory, Decoding, Lattices, MIMO, Polynomials, Probability density function, Symmetric matrices
National Category
Telecommunications
Identifiers
URN: urn:nbn:se:kth:diva-46470DOI: 10.1109/TIT.2011.2162177ISI: 000295738800013Scopus ID: 2-s2.0-80052360610OAI: oai:DiVA.org:kth-46470DiVA: diva2:453745
Note
QC 20111103Available from: 2011-11-03 Created: 2011-11-03 Last updated: 2017-12-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Jaldén, Joakim

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 98 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf