Vikalo, Haris and Hassibi, Babak (2005) On the sphere-decoding algorithm II. Generalizations, second-order statistics, and applications to communications. IEEE Transactions on Signal Processing, 53 (8). pp. 2819-2834. ISSN 1053-587X http://resolver.caltech.edu/CaltechAUTHORS:VIKieeetsp05
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:VIKieeetsp05
In Part 1, we found a closed-form expression for the expected complexity of the sphere-decoding algorithm, both for the infinite and finite lattice. We continue the discussion in this paper by generalizing the results to the complex version of the problem and using the expected complexity expressions to determine situations where sphere decoding is practically feasible. In particular, we consider applications of sphere decoding to detection in multiantenna systems. We show that, for a wide range of signal-to-noise ratios (SNRs), rates, and numbers of antennas, the expected complexity is polynomial, in fact, often roughly cubic. Since many communications systems operate at noise levels for which the expected complexity turns out to be polynomial, this suggests that maximum-likelihood decoding, which was hitherto thought to be computationally intractable, can, in fact, be implemented in real-time-a result with many practical implications. To provide complexity information beyond the mean, we derive a closed-form expression for the variance of the complexity of sphere-decoding algorithm in a finite lattice. Furthermore, we consider the expected complexity of sphere decoding for channels with memory, where the lattice-generating matrix has a special Toeplitz structure. Results indicate that the expected complexity in this case is, too, polynomial over a wide range of SNRs, rates, data blocks, and channel impulse response lengths.
|Additional Information:||© Copyright 2005 IEEE. Reprinted with permission. Manuscript received June 25, 2003; revised September 19, 2004. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Zhi Ding. The authors would like to thank R. Gowaikar for useful discussions on simplifying the derivation in Appendix A.|
|Subject Keywords:||expected complexity; frequency-selective channels; multiple-antenna systems; polynomial-time complexity; sphere decoding; wireless communications|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Tony Diaz|
|Deposited On:||10 Mar 2006|
|Last Modified:||26 Dec 2012 08:47|
Repository Staff Only: item control page