A Caltech Library Service

On the sphere-decoding algorithm II. Generalizations, second-order statistics, and applications to communications

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. doi:10.1109/TSP.2005.850350.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 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
Issue or Number:8
Record Number:CaltechAUTHORS:VIKieeetsp05
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2135
Deposited By: Tony Diaz
Deposited On:10 Mar 2006
Last Modified:08 Nov 2021 19:45

Repository Staff Only: item control page