A Caltech Library Service

Further Results on Speeding up the Sphere Decoder

Stojnic, M. and Vikalo, H. and Hassibi, B. (2006) Further Results on Speeding up the Sphere Decoder. In: 2006 IEEE International Conference on Acoustics, Speech, and Signal Processing. International Conference on Acoustics Speech and Signal Processing (ICASSP) . IEEE , Piscataway, NJ, pp. 549-552. ISBN 1-4244-0469-X.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


In many communication applications,maximum-likelihood decoding reduces to solving an integer least-squares problem which is NP hard in the worst-case. On the other hand, it has recently been shown that, over a wide range of dimensions and SNR, the sphere decoder can be used to find the exact solution with an expected complexity that is roughly cubic in the dimension of the problem. However, the computational complexity becomes prohibitive if the SNR is too low and/or if the dimension of the problem is too large. In earlier work, we targeted these two regimes attempting to find faster algorithms by pruning the search tree beyond what is done in the standard sphere decoder. The search tree is pruned by computing lower bounds on the possible optimal solution as we proceed to go down the tree. A trade-off between the computational complexity required to compute the lower bound and the size of the pruned tree is readily observed: the more effort we spend in computing a tight lower bound, the more branches that can be eliminated in the tree. Thus, even though it is possible to prune the search tree (and hence the number of points visited) by several orders of magnitude, this may be offset by the computations required to perform the pruning. In this paper, we propose a computationally efficient lower bound which requires solving a single semi-definite program (SDP) at the top of the search tree; the solution to the SDP is then used to deduce the lower bounds on the optimal solution on all levels of the search tree. Simulation results indicate significant improvement in the computational complexity of the proposed algorithm over the standard sphere decoding.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2006 IEEE. Issue Date: 14-19 May 2006. Date of Current Version: 18 September 2006. This work was supported in part by the National Science Foundation under grant no. CCR-0133818 and CCR-0326554, by the David and Lucille Packard Foundation, and by Caltech’s Lee Center for Advanced Networking.
Funding AgencyGrant Number
David and Lucile Packard FoundationUNSPECIFIED
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number9154384
Series Name:International Conference on Acoustics Speech and Signal Processing (ICASSP)
Record Number:CaltechAUTHORS:20110726-144521891
Persistent URL:
Official Citation:Stojnic, M.; Vikalo, H.; Hassibi, B.; , "Further Results on Speeding up the Sphere Decoder," Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings. 2006 IEEE International Conference on , vol.4, no., pp.IV, 14-19 May 2006 doi: 10.1109/ICASSP.2006.1661027 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:24555
Deposited By: Tony Diaz
Deposited On:27 Jul 2011 20:19
Last Modified:03 Oct 2019 02:57

Repository Staff Only: item control page