Paper Info
Title
Effects of the LLL Reduction on the Success Probability of the Babai Point and on the Complexity of Sphere Decoding
Abstract
A common method to estimate an unknown integer parameter vector in a linear model is to solve an integer least squares (ILS) problem. A typical approach to solving an ILS problem is sphere decoding. To make a sphere decoder faster, the well-known LLL reduction is often used as preprocessing. The Babai point produced by the Babai nearest plane algorithm is a suboptimal solution of the ILS problem. First, we prove that the success probability of the Babai point as a lower bound on the success probability of the ILS estimator is sharper than the lower bound given by Hassibi and Boyd . Then, we show rigorously that applying the LLL reduction algorithm will increase the success probability of the Babai point and give some theoretical and numerical test results. We give examples to show that unlike LLL's column permutation strategy, two often used column permutation strategies SQRD and V-BLAST may decrease the success probability of the Babai point. Finally, we show rigorously that applying the LLL reduction algorithm will also reduce the computational complexity of sphere decoders, which is measured approximately by the number of nodes in the search tree in the literature.
Year
DOI
Venue
2012
10.1109/TIT.2013.2253596
IEEE Transactions on Information Theory
Keywords
DocType
Volume
babai point,sphere decoding complexity,linear model,ils estimator,integer parameter vector,integer least squares,babai nearest plane algorithm,success probability,lll reduction,computational complexity,least squares approximations,complexity,integer least squares (ils) problem,lll reduction algorithm,sphere decoding,lll column permutation strategy,decoding,ils problem,probability
Journal
59
Issue
ISSN
Citations 
8
0018-9448
12
PageRank 
References 
Authors
0.63
12
3
Name
Order
Citations
PageRank
Xiao-Wen Chang120824.85
Jinming Wen2131.67
Xiaohu Xie3141.01