CaltechAUTHORS
  A Caltech Library Service

Invited paper: An efficient H∞ estimation approach to speed up the sphere decoder

Stojnic, Mihailo and Vikalo, Haris and Hassibi, Babak (2005) Invited paper: An efficient H∞ estimation approach to speed up the sphere decoder. In: 2005 International Conference on Wireless Networks, Communications and Mobile Computing. IEEE , Piscataway, NJ, pp. 1483-1488. ISBN 0-7803-9305-8 http://resolver.caltech.edu/CaltechAUTHORS:20110825-134003288

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

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20110825-134003288

Abstract

Maximum-likelihood (ML) decoding often 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 signal-to-noise ratios (SNR), the sphere decoding algorithm finds the exact solution with an expected complexity that is roughly cubic in the dimension of the problem. However, the computational complexity of sphere decoding becomes prohibitive if the SNR is too low and/or if the dimension of the problem is too large. In this paper, we target these two regimes and attempt 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. Using ideas from H∞ estimation theory, we have developed a general framework to compute the lower bound on the integer least-squares. Several special cases of lower bounds were derived from this general framework. Clearly, the tighter the lower bound, the more branches can be eliminated from the tree. However, finding a tight lower bound requires significant computational effort that might diminish the savings obtained by additional pruning. In this paper, we propose the use of a lower bound which can be computed with only linear complexity. Its use for tree pruning results in significantly speeding up the basic sphere decoding algorithm.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/WIRLES.2005.1549632DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1549632PublisherUNSPECIFIED
Additional Information:© 2005 IEEE. Issue Date: 13-16 June 2005; Date of Current Version: 05 December 2005. This work was supported in part by the National Science Foundation under grant no. CCR-0133818, by a fellowship from the David and Lucille Packard Foundation, and by Caltech's Lee Center for Advanced Networking.
Funders:
Funding AgencyGrant Number
NSFCCR-0133818
David and Lucille Packard FoundationUNSPECIFIED
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number8773810
Record Number:CaltechAUTHORS:20110825-134003288
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20110825-134003288
Official Citation:Stojnic, M.; Vikalo, H.; Hassibi, B.; , "An efficient H∞ estimation approach to speed up the sphere decoder," Wireless Networks, Communications and Mobile Computing, 2005 International Conference on , vol.2, no., pp. 1483- 1488 vol.2, 13-16 June 2005 doi: 10.1109/WIRLES.2005.1549632
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:25099
Collection:CaltechAUTHORS
Deposited By: Jason Perez
Deposited On:25 Aug 2011 21:02
Last Modified:25 Aug 2011 21:02

Repository Staff Only: item control page