LLL格基约减中选择δ的一种方法肖剑(西安电子科技大学电子工程学院，陕西西安710071)摘要LLL格基约减是一种强大的格基约减算法，其可在多项式时间里输出一组近乎正交的已减格基，且已被应用于预编码领域，可在无线通信中，获得理想的分集性能。LLL格基约减算法需要人为指定参数δ。参数δ的大小决定了算法的执行时间及已减格基的好坏。在LLL格基约减算法基础上，文中提出了一种改进算法，针对特定输入矩阵H，算法自动选择δ，在执行时间和已减格基质量间达到平衡。关键词MIMO;格基约减;预编码中图分类号TN919.3+1文献标识码A文章编号1007－7820(2012)06－038－03AMethodforChoosingδBasedontheLLLLatticeReductionAlgorithmXIAOJian(SchoolofElectronicEngineering，XidianUniversity，Xi'an710071，China)AbstractLLLlatticereductionisapowerfulalgorithmwhichcanoutputagroupofnearlyorthogonalreducedlatticebasisfromoriginalbasis．Recently，LLLlatticereductionhasbeenfoundusefulforprecodinginwirelessMI-MOsystems．ThereisafactorδinLLLlatticereductionwhichshouldbespecifiedmanually．AlgorithmexecutionOnthebaseoftheLLLlatticereductionalgorithm，timeandqualityofreducedlatticebasisdependonthefactorδ．thispaperproposeanimprovedalgorithmforchoosingthefactorδautomaticallyaccordingtoaspecificinputmatrixHtomeetthetradeoffbetweenthequalityofreducedlatticebasisandalgorithmexecutiontime．KeywordsMIMO;latticereduction;precoding1l=m在预编码领域，为获得尽可能低的误码率性能，BertrandM.Hochwal［1－2］等提出矢量微扰(VectorPerturbation)算法。但该算法复杂度为NP，在MIMO背景下无法应用。球形解码［3］(SphereDecoding)的提出使得矢量微扰的应用成为可能，但直到格基约减的引入，才使得学者在算法复杂度和性能之间找到了平衡。基于LLL(Lenstra，Lenstra，Lovász)格基约减［4－5］的许多预编码算法［6］的提出，使得LLL格基约减算法的应用更加广泛。一组LLL已减格基b1，…，bm满足如下条件ζ(B)∏(3)=bdet(B)ll=1其中，det(B)是B的行列式是bl的范数。bl由定义可知ζ(B)≥1，ζ(B)越小，说明已减格基两两正交。问题提出在LLL格基约减算法中，当式(1)不满足时1rl－1，l∶=rl－1，l－roundrrl－1，(4)l－1，l－1rl－1，l－1其中，round(*)是四舍五入求整。当式(2)不满足时，即1rk，rk，k，1≤k＜l≤m(1)≤22＞2+2，l=2，…，m(5)δrl－1，l－1rr2≤2+2，l=2，…，m(2)δrl－1，l－1rrl，ll－1，ll，ll－1，l将交换bl、bl－1的位置，并利用Givens变换更新Q，Rrk，l为矩阵B=［b1，…，bm］进行QR分解得到的上(6)l∶=l－11三角矩阵R中的元素，＜δ＜1。在式(2)中存在一个人为设定的变量δ。δ越大，式(2)不成立的概率越大，从而间接增加了式(1)不成立情况的次数。正因为频繁交换b1、bl－1，尽可能地削减两基间相关的部分，从而得到一组正交缺陷更小的基。在MIMO背景下，利用Matlab产生8×8服从高斯分布的随机矩阵，并将随机矩阵的逆作为LLL格基约4对已减格基b1，…，bm的优劣，常采用正交缺陷(OrthogonalityDefect)进行衡量。一个矩阵的正交缺陷定义为收稿日期:2011-12-29作者简介:肖剑(1987—)，男，硕士研究生。研究方向:MI-MO无线通信系统中的预编码信号处理技术。减算法的输入。针对不同的δ值(0.25～1，步长38www.dianzikeji.org图像·编码与软件肖剑:LLL格基约减中选择δ的一种方法0.05)，进行了10组随机矩阵的模拟发现，式(5)成立的发生次数与正交缺陷存在反比关系。if(i==1)l=l+1elseif(i＜l)count=l－iwhile(count)2改进算法再回到式(5)中，交换bl－1，bl的目的是使式(1)不成立，实施式(4)，从而使bl－1，bl更加正交。因此式(5)可以修改为～～交换hl，hl－1更新R，Ql=l－1count=count－1endendend4cos2arctanrl，2＞2+2，l=2，…，mrrrl－1，l－1l－1，ll，lrl－1，l(7)与对比式(5)和式(7)，不难发现cos2arctanrl，rl－1，lδ对应。在式(5)中，当δ＞4cos2arctan时，将rl，仿真结果3rl－1，人为导致交...