DocumentCode :
747245
Title :
On the complexity of sphere decoding in digital communications
Author :
Jaldén, Joakim ; Otterste, Björn
Author_Institution :
Dept. of Signals, R. Inst. of Technol., Stockholm, Sweden
Volume :
53
Issue :
4
fYear :
2005
fDate :
4/1/2005 12:00:00 AM
Firstpage :
1474
Lastpage :
1484
Abstract :
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.
Keywords :
computational complexity; decoding; digital communication; polynomials; probability; signal detection; digital communication; exponential complexity; large deviation theory; nonvanishing probability; polynomial complexity; signal detection; signal-to-noise ratio; sphere decoding; Block codes; Computational complexity; Decoding; Digital communication; Dispersion; Multiaccess communication; Multiuser detection; Polynomials; Signal to noise ratio; Viterbi algorithm; Expected complexity; ML detection; large deviation theory; sphere decoding;
fLanguage :
English
Journal_Title :
Signal Processing, IEEE Transactions on
Publisher :
ieee
ISSN :
1053-587X
Type :
jour
DOI :
10.1109/TSP.2005.843746
Filename :
1408197
Link To Document :
بازگشت