A Caltech Library Service

Statistical Pruning for Near-Maximum Likelihood Decoding

Gowaikar, Radhika and Hassibi, Babak (2007) Statistical Pruning for Near-Maximum Likelihood Decoding. IEEE Transactions on Signal Processing, 55 (6, Pt.). pp. 2661-2675. ISSN 1053-587X.

See Usage Policy.


Use this Persistent URL to link to this item:


In many communications problems, maximum-likelihood (ML) decoding reduces to finding the closest (skewed) lattice point in N-dimensions to a given point xisin CN. In its full generality, this problem is known to be NP-complete. Recently, the expected complexity of the sphere decoder, a particular algorithm that solves the ML problem exactly, has been computed. An asymptotic analysis of this complexity has also been done where it is shown that the required computations grow exponentially in N for any fixed SNR. At the same time, numerical computations of the expected complexity show that there are certain ranges of rates, SNRs and dimensions N for which the expected computation (counted as the number of scalar multiplications) involves no more than N3 computations. However, when the dimension of the problem grows too large, the required computations become prohibitively large, as expected from the asymptotic exponential complexity. In this paper, we propose an algorithm that, for large N, offers substantial computational savings over the sphere decoder, while maintaining performance arbitrarily close to ML. We statistically prune the search space to a subset that, with high probability, contains the optimal solution, thereby reducing the complexity of the search. Bounds on the error performance of the new method are proposed. The complexity of the new algorithm is analyzed through an upper bound. The asymptotic behavior of the upper bound for large N is also analyzed which shows that the upper bound is also exponential but much lower than the sphere decoder. Simulation results show that the algorithm is much more efficient than the original sphere decoder for smaller dimensions as well, and does not sacrifice much in terms of performance.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© Copyright 2007 IEEE. Reprinted with permission. Manuscript received August 26, 2005; revised July 10, 2006. [Posted online: 2007-05-21] The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Franz Hlawatsch.
Subject Keywords:Maximum-likelihood decoding, multiple antenna systems, reduced complexity, sphere decoder
Issue or Number:6, Pt.
Record Number:CaltechAUTHORS:GOWieeetsp07
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:8465
Deposited By: Archive Administrator
Deposited On:14 Aug 2007
Last Modified:02 Oct 2019 23:51

Repository Staff Only: item control page