article · IEEE Transactions on Signal Processing · 2007

Statistical Pruning for Near-Maximum Likelihood Decoding

Cited by 90Abstract and details only

Abstract

In many communications problems, maximum-likelihood (ML) decoding reduces to finding the closest (skewed) lattice point in N-dimensions to a given point xisin C <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</sup> . 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 N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> 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

Cite this paper

APA 7

Gowaikar, R., & Hassibi, B. (2007). Statistical Pruning for Near-Maximum Likelihood Decoding. IEEE Transactions on Signal Processing, 55(6), 2661–2675. https://doi.org/10.1109/tsp.2006.890912

MLA 9

Gowaikar, Radhika, and Babak Hassibi. “Statistical Pruning for Near-Maximum Likelihood Decoding.” IEEE Transactions on Signal Processing, vol. 55, no. 6, 2007, pp. 2661–75, https://doi.org/10.1109/tsp.2006.890912.

Chicago

Gowaikar, Radhika, and Babak Hassibi. 2007. “Statistical Pruning for Near-Maximum Likelihood Decoding.” IEEE Transactions on Signal Processing 55 (6): 2661–75. https://doi.org/10.1109/tsp.2006.890912.

Harvard

Gowaikar, R. and Hassibi, B. (2007) ‘Statistical Pruning for Near-Maximum Likelihood Decoding’, IEEE Transactions on Signal Processing, 55(6), pp. 2661–2675. Available at: https://doi.org/10.1109/tsp.2006.890912.

BibTeX

@article{gowaikar2007statistical,
  title = {{Statistical Pruning for Near-Maximum Likelihood Decoding}},
  author = {Gowaikar, Radhika and Hassibi, Babak},
  journal = {IEEE Transactions on Signal Processing},
  volume = {55},
  number = {6},
  pages = {2661--2675},
  year = {2007},
  doi = {10.1109/tsp.2006.890912}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.