A Caltech Library Service

Efficient statistical pruning for maximum likelihood decoding

Gowaikar, Radhika and Hassibi, Babak (2003) Efficient statistical pruning for maximum likelihood decoding. In: IEEE International Conference on Acoustics, Speech, and Signal Processing, 2003. Proceedings. (ICASSP '03). Vol.5. IEEE , Piscataway, NJ, pp. 49-52. ISBN 0-7803-7663-3.

[img] PDF - Published Version
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 x∈C^N. In its full generality, this problem is known to be NP-complete and requires exponential complexity in N. Recently, the expected complexity of the sphere decoder, a particular algorithm that solves the ML problem exactly, has been computed; it is shown that, over a wide range of rates, SNRs and dimensions, the expected complexity is polynomial in N. We propose an algorithm that, for large N, offers substantial computational savings over the sphere decoder, while maintaining performance arbitrarily close to ML. The method is based on statistically pruning the search space. Simulations are presented to show the algorithm's performance and the computational savings relative to the sphere decoder.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2003 IEEE. This work was supported in part by the National Science Foundation under grant no. CCR-0133818, by the Office of Naval Research under grant no. N00014-02-1-0578, and by Caltech's Lee Center for Advanced Networking.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-02-1-0578
Caltech's Lee Center for Advanced NetworkingUNSPECIFIED
Record Number:CaltechAUTHORS:20150212-070415519
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:54750
Deposited By: Shirley Slattery
Deposited On:17 Feb 2015 23:54
Last Modified:10 Nov 2021 20:37

Repository Staff Only: item control page