Change search
ReferencesLink to record
Permanent link

Direct link
On the complexity of sphere decoding in digital communications
KTH, School of Electrical Engineering (EES), Signal Processing. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0001-6630-243X
KTH, School of Electrical Engineering (EES), Signal Processing. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0003-2298-6774
2005 (English)In: IEEE Transactions on Signal Processing, ISSN 1053-587X, E-ISSN 1941-0476, ISSN 1053-587X, Vol. 53, no 4, 1474-1484 p.Article in journal (Refereed) Published
Abstract [en]

Sphere decoding has been suggested by a number of authors as an efficient algorithm to solve various detection problems in digital communications. In some cases, the algorithm is referred to as an algorithm of polynomial complexity without clearly specifying what assumptions are made about the problem structure. Another claim is that although worst-case complexity is exponential, the expected complexity of the algorithm is polynomial. Herein, we study the expected complexity where the problem size is defined to be the number of symbols jointly detected, and our main result is that the expected complexity is exponential for fixed signal-to-noise ratio (SNR), contrary to previous claims. The sphere radius, which is a parameter of the algorithm, must be chosen to ensure a nonvanishing probability of solving the detection problem. This causes the exponential complexity since the squared radius must grow linearly with problem size. The rate of linear increase is, however, dependent on the noise variance, and thus, the rate of the exponential function is strongly dependent on the SNR. Therefore sphere decoding can be efficient for some SNR and problems of moderate size, even though the number of operations required by the algorithm strictly speaking always grows as an exponential function of the problem size.

Place, publisher, year, edition, pages
IEEE Signal Processing Society, 2005. Vol. 53, no 4, 1474-1484 p.
Keyword [en]
expected complexity, large deviation theory, ML detection, sphere decoding, lattice code decoder, space, time
National Category
URN: urn:nbn:se:kth:diva-14610DOI: 10.1109/tsp.2005.843746ISI: 000227711100022ScopusID: 2-s2.0-17444400753OAI: diva2:332651
QC 20100525 QC 20111104Available from: 2010-08-05 Created: 2010-08-05 Last updated: 2012-01-04Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Jaldén, JoakimOttersten, Björn
By organisation
Signal ProcessingACCESS Linnaeus Centre
In the same journal
IEEE Transactions on Signal Processing

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: 24 hits
ReferencesLink to record
Permanent link

Direct link