Vikalo, Haris and Hassibi, Babak (2005) On the spheredecoding algorithm II. Generalizations, secondorder statistics, and applications to communications. IEEE Transactions on Signal Processing, 53 (8). pp. 28192834. ISSN 1053587X. http://resolver.caltech.edu/CaltechAUTHORS:VIKieeetsp05

PDF
See Usage Policy. 553Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:VIKieeetsp05
Abstract
In Part 1, we found a closedform expression for the expected complexity of the spheredecoding 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 signaltonoise 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 maximumlikelihood decoding, which was hitherto thought to be computationally intractable, can, in fact, be implemented in realtimea result with many practical implications. To provide complexity information beyond the mean, we derive a closedform expression for the variance of the complexity of spheredecoding algorithm in a finite lattice. Furthermore, we consider the expected complexity of sphere decoding for channels with memory, where the latticegenerating 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.
Item Type:  Article 

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; frequencyselective channels; multipleantenna systems; polynomialtime complexity; sphere decoding; wireless communications 
Record Number:  CaltechAUTHORS:VIKieeetsp05 
Persistent URL:  http://resolver.caltech.edu/CaltechAUTHORS:VIKieeetsp05 
Alternative URL:  http://dx.doi.org/10.1109/TSP.2005.850350 
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  2135 
Collection:  CaltechAUTHORS 
Deposited By:  Tony Diaz 
Deposited On:  10 Mar 2006 
Last Modified:  26 Dec 2012 08:47 
Repository Staff Only: item control page