• Home
•  
• Call for Papers
• Paper Status
• Registration
• Workshops
• Exhibits
•  
• Technical Program
• Side Meetings
• Tutorials
• Plenaries
• Special Sessions
• Panel Sessions
• My Schedule
•  
• Practicalities
• Housing & Venue
• Special Events
• Visits
• Supporters
•  
• Contact / Discussion
• Organizing Committee
• Program Committee
• Review Committee
•  
• Related Conferences

Technical Program

Paper Detail

Paper:	SPCOM-P8.6
Session:	MIMO STC and Decoding
Time:	Thursday, May 18, 10:00 - 12:00
Presentation:	Poster
Topic:	Signal Processing for Communication: MIMO precoder/decoder design, receiver algorithms
Title:	Further Results on Speeding up the Sphere Decoder
Authors:	Mihailo Stojnic, Haris Vikalo, Babak Hassibi, California Institute of Technology, United States
Abstract:	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.