Effects of the LLL Reduction on the Success Probability of the Babai Point and on the Complexity of Sphere Decoding
Effects of the LLL Reduction on the Success Probability of the Babai Point and on the Complexity of Sphere Decoding
复制标题
DOI：
10.1109/tit.2013.2253596
复制
发表时间：
2012-04
影响因子：
2.5
通讯作者：
X. Chang;Jinming Wen;Xiaohu Xie
中科院分区：
文献类型：
--
作者：
X. Chang;Jinming Wen;Xiaohu Xie
估计线性模型中未知整数参数向量的常用方法是求解整数最小二乘问题。解决ILS问题的一个典型方法是球体解码。为了使球体解码器更快，通常使用众所周知的最小二乘减少作为预处理。Babai最近平面算法产生的Babai点是盲降问题的次优解。首先，我们证明了Babai点的成功概率作为ILS估计器成功概率的下界比Hassibi和Boyd[1]给出的下界更锐利。然后，我们严格地证明了应用LLL约简算法可以提高Babai点的成功概率，并给出了一些理论和数值试验结果。举例说明，与LLL的列置换策略不同，常用的两种列置换策略SQRD和V-BLAST可能会降低Babai点的成功概率。最后，我们严格地证明了应用LLL约简算法也会降低球体解码器的计算复杂度，这是通过文献中搜索树中的节点数来近似衡量的。
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 [1]. 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.