基于Householder变换的模糊度规约算法

Ambiguity Reduction Algorithm Based on Householder Transformation

基于格进行整周模糊度估计时,为保证最近向量问题的计算效率,通常需首先对格基进行规约变换。设计了基于Householder变换的LLL规约算法(H-LLL),算法通过利用分解得到的上三角矩阵来构造规约变换矩阵,从而实现格基的大小规约和长度规约。利用实测数据与经典LLL规约算法进行了比较,结果表明两种方法规约效果相同,H-LLL规约更加高效。

In order to keep the calculation efficiency of closest vector problems in integer ambiguity estimation based on lattice, the lattice base is needed to be reduction-transformed previously. The design of H-LLL algorithm is based on Householder transformation, and the size reduction and length reduction of lattice base are realized through the upper triangular matrix produced by householder transformation to construct the reduction transformation matrix. The classic reduction algorithm on the basis of gram schmidt orthogonalization, is compared with H-LLL algorithm by using the measured data, and the result shows that the two methods have the same reduction effect, but H-LLL reduction method is more efficient.