Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published February 2008 | Published
Journal Article Open

Speeding up the Sphere Decoder With ℋ∞ and SDP Inspired Lower Bounds

Abstract

It is well known that maximum-likelihood (ML) decoding in many digital communication schemes 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 (SNRs), the sphere decoding algorithm can be used to find the exact ML solution with an expected complexity that is often less than N^3. 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 decoding algorithm. The search tree is pruned by computing lower bounds on the optimal value of the objective function as the algorithm proceeds to descend down the search tree. We observe a tradeoff between the computational complexity required to compute a lower bound and the size of the pruned tree: the more effort we spend in computing a tight lower bound, the more branches that can be eliminated in the tree. Using ideas from semidefinite program (SDP)-duality theory and H∞ estimation theory, we propose general frameworks for computing lower bounds on integer least-squares problems. We propose two families of algorithms, one that is appropriate for large problem dimensions and binary modulation, and the other that is appropriate for moderate-size dimensions yet high-order constellations. We then show how in each case these bounds can be efficiently incorporated in the sphere decoding algorithm, often resulting in significant improvement of the expected complexity of solving the ML decoding problem, while maintaining the exact ML-performance.

Additional Information

© 2008 IEEE. Manuscript received September 3, 2006; revised May 11, 2007. This work was supported in part by the National Science Foundation under grant CCR-0133818, by the David and Lucille Packard Foundation, and by Caltech's Lee Center for Advanced Networking.

Attached Files

Published - STOieeetsp08.pdf

Files

STOieeetsp08.pdf
Files (1.2 MB)
Name Size Download all
md5:33df8462240aa89ceb0f80a5c5016db3
1.2 MB Preview Download

Additional details

Created:
August 22, 2023
Modified:
March 5, 2024