周　圍，張　茜，王新賀

(重慶郵電大學 a.移動通信技術(shù)重慶市重點實驗室；b.光電工程學院，重慶 400065)

?

MIMO系統(tǒng)中改進的LLL格基約減算法

周圍a，b，張茜a，王新賀a

(重慶郵電大學a.移動通信技術(shù)重慶市重點實驗室；b.光電工程學院，重慶 400065)

針對傳統(tǒng)LLL格基約減算法在MIMO系統(tǒng)中的誤比特性能較差的問題，提出了一種改進的LLL檢測算法。該算法利用后向LLL約減算法和同時對多個初始基進行約減的思想，從問題的多組初始基開始搜索，并對多組初始基進行約減，找到其中最好的一組基，擺脫了傳統(tǒng)格基約減算法僅從單組基開始搜索的局限。通過理論分析和計算機仿真，對算法的收斂性及不同收發(fā)天線數(shù)下不同檢測算法的誤比特性能進行了對比研究。結(jié)果表明，在MIMO系統(tǒng)中本文算法的檢測性能比傳統(tǒng)的格基約減算法更優(yōu)，且更接近于ML檢測算法。

多輸入多輸出；格基約減；LLL算法；后向LLL算法

隨著社會的發(fā)展，現(xiàn)有移動通信系統(tǒng)的業(yè)務(wù)越來越不能滿足人們的要求，因此對系統(tǒng)業(yè)務(wù)的要求也越來越高，全球無線通信進入高速發(fā)展階段。而多輸入多輸出(Multiple-InputMultiple-Output，MIMO)技術(shù)通過在收發(fā)雙端同時配置多根天線，充分利用空間資源，在空間產(chǎn)生多個獨立的并行信道，從而將多路數(shù)據(jù)流同時進行傳輸，因此MIMO無線系統(tǒng)能夠在成倍提高系統(tǒng)容量的同時提高頻譜資源的利用率，是無線領(lǐng)域關(guān)鍵技術(shù)的一個重大突破，吸引了通信領(lǐng)域?qū)W術(shù)界廣大學者的研究興趣。

目前學術(shù)界廣泛研究的MIMO系統(tǒng)信號檢測算法大致分為非線性與線性兩類。非線性檢測算法主要有最大似然檢測(MaximumLikelihood，ML),球形檢測(SphereDetection，SD),K-best,QRDM以及智能檢測算法等[1]；線性檢測算法主要有ZF、MMSE和半定松弛檢測算法。與線性檢測方法相比較，非線性檢測方法具有優(yōu)良的檢測性能，同時其計算復雜度也比較高，因此難以應(yīng)用到實際的工程環(huán)境中。MIMO系統(tǒng)信號檢測算法的性能和復雜度之間呈現(xiàn)一定的正相關(guān)關(guān)系，但對某一待檢測信號進行一定的預處理后，以增加一定的計算復雜度為代價，達到提升系統(tǒng)能檢測效果的目的。格基約減作為一種信號檢測前的預處理方法，以增加一定的復雜度，能夠提升系統(tǒng)的檢測性能。因此，將格基約減理論應(yīng)用到MIMO系統(tǒng)信號檢測中可以獲得更優(yōu)的檢測效果。文獻[2-5]中提及了幾種比較經(jīng)典的格基約減檢測算法，主要有LLL算法、HKZ算法和Gauss算法。而在各種格基約減方法當中，LLL格基約減算法因能在性能和復度之間得到很好的折衷而被廣泛使用[6-9]，同時也是本文研究的重點。基于LLL的格基約減算法作為一種比較成熟的格基約減技術(shù)，不僅能夠直接對復數(shù)域矩陣進行處理[10]，還能夠通過長度規(guī)約和列交換操作獲得接近正交的約減基，且復雜度較低為多項式時間復雜度。但也存在這樣一個問題，隨著MIMO系統(tǒng)收發(fā)天線數(shù)的增加，LLL檢測算法的性能也會隨之變差，傳統(tǒng)的LLL檢測算法在MIMO系統(tǒng)中已失效[11]。文獻[12-13]中提出一種聯(lián)合前向后向的LLL格基約減算法，在一定程度上可以改善格基約減在MIMO系統(tǒng)中的性能；文獻[14]中提出一種迭代LLL檢測算法，該方法在迭代次數(shù)較多的情況下可以改善檢測算法性能，但是其收斂速度過慢，需進行多次迭代；文獻[15-16]中提出一種基于遺傳算法的信道矩陣優(yōu)化，但是在初始種群的選取時復雜度較高，并且對隨后的檢測帶來的利益過小，對子代進行遺傳算子操作時其交叉過程會使得約減基維數(shù)加倍，對于信號檢測而言難以恢復出發(fā)送端信號。因此，本文利用前向后向LLL約減聯(lián)合算法的思想對MIMO系統(tǒng)的信號進行檢測，提出一種改進的LLL檢測算法。在前向后向LLL約減基的基礎(chǔ)上對多個初始基進行LLL約減，進而搜索出一組具有更短長度、更小正交缺陷度的約減基，構(gòu)成優(yōu)化矩陣H′，并在該優(yōu)化矩陣H′下進行信號檢測，繼而達到改善MIMO系統(tǒng)檢測性能的目的。

1　系統(tǒng)模型

在一個發(fā)射天線數(shù)為Nt，接收天線數(shù)Nr的MIMO系統(tǒng)中，接收端模型如式(1)所示

y=Hx+n

(1)

圖1　MIMO系統(tǒng)框圖

2　格基約減

格的多樣性表明一個格可以由多個不同的基來表示，而在信號檢測中，則希望能夠找到眾多基中最短的一組基，以有利于系統(tǒng)接收端信號的恢復。而選擇這樣一組基的過程稱為格基約減，且稱這組基為格的一組約減基。在MIMO系統(tǒng)中，格基約減操作的基本原理如式(2)所示

H′=HT

(2)

這里矩陣T為幺模矩陣，由式(2)可知格基約減就是利用幺模變換矩陣將H約減為一個新的、更正交的矩陣H′的過程。根據(jù)矩陣的右乘性質(zhì)可知，矩陣H與幺模矩陣T相乘可以理解為對H的列進行變換，即格基約減就是通過對信道矩陣進行列初等變換，繼而獲得更優(yōu)的等效矩陣的過程。

格基約減操作的關(guān)鍵就是如何尋找到最優(yōu)的等效矩陣H′，本文在傳統(tǒng)LLL格基約減算法的基礎(chǔ)上引入多個初始基，同時對多個初始基進行格基約減，求解出正交性更好的一組等效約減基H′，從而能夠進一步提升系統(tǒng)的檢測性能。

A. K. Lenstra， H. W. Lenstra 和L. Lovasz在文獻[17]中給出一種可以直接應(yīng)用于任意維MIMO系統(tǒng)的LLL格基約減算法，該算法與其他格基約減算法相比具有更大的靈活性，且復雜度較低。在MIMO系統(tǒng)中，對Nt維的信道矩陣H進行LLL約減，等效為對H進行QR分解，分解為酉矩陣Q和上三角矩陣R相乘的形式：H=QR，并使矩陣R中的元素滿足式(3)和式(4)所示的兩個約束條件

(3)

(4)

l=2,…,Nt(1/4<δ≤1)

(5)

(6)

(7)

(8)

式中：Q(·)表示對(·)進行量化處理，通過式(7)、(8)可以恢復出對原始發(fā)射信號的估計值

(9)

3　改進LLL算法

傳統(tǒng)LLL格基約減算法中，第m(m=1,2,…,Nt)根發(fā)射天線的發(fā)射符號誤碼率sm隨著下標m逐漸減小,其誤碼率sm逐漸增大。這意味著第一根發(fā)射天線的誤碼率最大，而第Nt根天線的誤碼率最小。這是由于LLL算法的整數(shù)格點特性，在發(fā)射端需要對發(fā)射符號x進行格點映射；在接收端經(jīng)量化判決后，還需經(jīng)過相應(yīng)的逆映射過程以恢復原始的發(fā)射信號，正是在逆映射恢復原始發(fā)射符號的過程中，會左乘一個上三角矩陣，而使得前幾根發(fā)射天線受到來自其他天線上發(fā)射符號的干擾，導致第一根發(fā)射天線上發(fā)射符號的誤碼率最大。

傳統(tǒng)LLL檢測算法是將信道矩陣H的第p列和第q列按一定規(guī)則進行迭代列變換(p>q)，而得到新的約減矩陣，這里將傳統(tǒng)LLL檢測算法進行迭代列變換的操作稱為前向約減，稱該算法為前向LLL算法；對前向約減的列變換取鏡像操作，即將信道矩陣的第p列和q列按一定規(guī)則進行列變換(q>p)，得到另一個約減矩陣，將該操作稱為后向約減，該算法稱為后向LLL算法。

由于采用前向和后向LLL算法之后的信道矩陣相關(guān)性較弱，因此能夠獲得更好的誤碼率性能，即更可靠的發(fā)射符號估計，但仍與最大似然檢測差距較大。因此本文引入一種信道矩陣優(yōu)化技術(shù)，將初始信道矩陣與初等變換矩陣相乘，得到多個初始基，對多個初始基進行LLL約減，就會生成多個性能上存在差別的約減基，選取其中最優(yōu)的一個作為最終輸出解。生成初等變換矩陣的具體步驟如下：對經(jīng)過前向后向LLL算法產(chǎn)生的上三角幺模矩陣和下三角幺模矩陣進行矩陣相乘操作，并對相乘后的矩陣進行隨機初等變換，即可生成初等變換矩陣。

改進LLL算法：

1)將輸入的初始信道矩陣H分別與M個初等變換矩陣相乘，可產(chǎn)生M組基；

3)將M組新基按正交缺陷度從高到低進行排序；

4)根據(jù)正交缺陷度值的大小，按正交缺陷的選取最優(yōu)即正交缺陷度最小的一組約減基作為輸出。

后向LLL算法具體步驟(偽代碼)：

2)令p=Nt-1；

3)whilep≥1；

4)forq=p+1,p+2,…,Nt,do；

6)ifμp,q≠0，then；

7)更新下三角矩陣和幺模矩陣：

T(:,p)=T(:,p)-μp,qT(:,q)；

8)end if；

9)end；

11)p=p-1；

14)p=min{p+1,Nt-1}；

15)else；

16)ifp=Nt-1；

17)end；

18)end；

19)end。

4　仿真結(jié)果及分析

圖2所示為性噪比SNR=22 dB的情況下，收發(fā)天線數(shù)為8的MIMO系統(tǒng)中，各天線的BER性能仿真曲線圖。其中，LLL曲線表明采用的格基約減方法為傳統(tǒng)LLL檢測算法，BLLL表示采用的格基約減方法為后向LLL檢測算法，F(xiàn)BLLL表示采用的格基約減方法為聯(lián)合前向后向LLL檢測算法。從圖中可以看出，傳統(tǒng)LLL檢測算法，第m(m=1,2,…,Nt)根發(fā)射天線的發(fā)射符號誤碼率sm隨著下標m逐漸減小其逐漸增大，后向LLL則呈現(xiàn)相反的變化趨勢，而前向后向LLL聯(lián)合檢測算法因其較弱的相關(guān)性而呈現(xiàn)出各根天線BER性能一致的趨勢。證明了聯(lián)合前向后向LLL檢測算法能有效地降低各根天線之間的相關(guān)性，得到更優(yōu)的檢測性能。

圖2　8×8 MIMO系統(tǒng)下各發(fā)射天線的誤碼率率曲線

圖3所示為各檢測算法在收發(fā)天線數(shù)為4的MIMO系統(tǒng)中的誤碼率性曲線圖?？梢钥闯?，傳統(tǒng)的LLL檢測算法能夠顯著地提升線性檢測算法的檢測性能；而本文算法在BER=10-3時性能相對于傳統(tǒng)的LLL線性檢測算法只有約1 dB的性能改善。其原因是在4×4 MIMO中，系統(tǒng)規(guī)模較小，傳統(tǒng)的LLL檢測算法能夠找到一個足夠短的新基來提高檢測算法的性能。因此，在收發(fā)天線數(shù)較小的MIMO系統(tǒng)中，可直接采用傳統(tǒng)LLL檢測算法來提高檢測算法的性能。

圖3　4×4 MIMO下不同檢測算法的誤比特率曲線

圖4　8×8 MIMO下不同檢測算法的誤比特率曲線

圖4所示為8×8 MIMO系統(tǒng)下，各檢測算法的BER性能曲線，在BER=10-3時，基于LLL的檢測算法相對于線性算法有約7 dB的性能改善；但仍與ML檢測存在較大的差距，而改進的LLL檢測算法相對于傳統(tǒng)LLL檢測算法大約有4 dB的性能改善，這樣大大縮短了LLL檢測算法與ML檢測算法之間的差距。原因在于初等變換矩陣的選取時，初等變換矩陣由傳統(tǒng)LLL檢測算法和后向LLL檢測算法生成的上三角和下三角矩陣變化而得，其相關(guān)性較小，而后利用初等變換矩陣生成的多個初始基也到達了對信道矩陣進行充分置亂的效果。因此對于生成的多個初始基而言，經(jīng)LLL約減操作之后能夠獲得正交性更好、長度更短的等效輸出基。使得本文算法的BER曲線更接近于ML檢測的BER曲線。

參照文獻[19]中提及的格基約減復雜度計算方法，若a取格基中向量長度的最大值，那么LLL格基約減算法的時間復雜度為o(n4lba)；對于一個n×n維的矩陣采用標準的矩陣乘法，其復雜度為o(n3)。假設(shè)初始格基的個數(shù)為m，那么采用基于本文改進LLL檢測算法的整體時間開銷為o(n3)+o((m+2)n4lba)。其中主要的時間開銷花費在對每組候選初始基進行LLL約減操作上。上述仿真條件中，設(shè)定的初始基的數(shù)量為4，因此本文的改進LLL約減算法的時間復雜度約為傳統(tǒng)LLL約減的6倍。

5　總結(jié)

本文提出一種在MIMO系統(tǒng)和MIMO系統(tǒng)下的改進LLL信號檢測算法，并且仿真分析表明，在收發(fā)天線數(shù)為8的MIMO系統(tǒng)中，本文算法能夠獲得更好的BER檢測性能，且更接近ML檢測。而在收發(fā)天線數(shù)為4的MIMO系統(tǒng)中，改進的LLL檢測算法相對于傳統(tǒng)的LLL檢測算法而言，其性能改善得并不明顯。因此，本文所提出的改進LLL檢測算法更加適用于較大規(guī)模的MIMO系統(tǒng)。本文算法以犧牲一定的復雜度為代價，顯著地改善了檢測算法的性能，使之更接近于ML檢測。

[1]吳軍， 王紹偉. 改進的K-Best檢測算法研究及實現(xiàn)[J]. 電視技術(shù)，2013，37(5)：146-149.

[2]WUBBEN D， SEETHALER S， JOAKIM J， et al. Lattice reduction[J]. IEEE transactions on signal processing，2011，28(3)：70-91. DOI：10.1109/MSP.2010.938758.

[3]MUSSI A M， ABRAO T. SDR lattice reduction aided detector[J]. IEEE transactions on latin America，2013，4(11)：1007-1014. DOI： 10.1109/TLA.2013.6601743.

[4]ZHOU Q， MA X L. An improved LR-aided K-best algorithm for MIMO detection[C]// Proc. Wireless Communications and Signal Processing. Huangshan：IEEE，2012：1-5.DOI： 10.1109/WCSP.2012.6542840.

[5]NAJAFI H， DAMEN M O. Lattice reduction aided conditional detection for MIMO systems[J]. IEEE transactions on communications，2014， 62(11)：3864-3873.DOI： 10.1109/TCOMM.2014.2361337.

[6]GESTNER B，MA X L， ANDERSON D V. Incremental lattice reduction： motivation， theory， and practical implementation[J]. IEEE transactions on wireless communications，2012，11(1)：188-198. DOI：10.1109/TWC.2011.120511.102286.

[7]SAKZAD A， HARSHAN J， VITRBO E. Integer-forcing MIMO linear receivers based on lattice reduction[J]. IEEE transactions on wireless communications， 2013， 12(10)：4905-4915. DOI： 10.1109/TWC.2013.090513.121465.

[8]YANG P，XIAO Y，LI S Q， et al. QRD-assisted adaptive modulation-aided MIMO systems[J]. IEEE transactions on vehicular technology，2014，63(1)：446-451. DOI： 10.1109/TVT.2013.2274482.

[9]ZHANG W，QIAO S Z，WEI Y M. A diagonal lattice reduction algorithm for MIMO detection[J]. IEEE transactions on signal processing letters， 2012，19(5)：311-314.DOI： 10.1109/LSP.2012.2191614.

[10]WEN Q S， ZHOU Q， MA X l. An enhanced fixed-complexity LLL algorithm for MIMO detection[C]// Proc. Global Communications Conference. Austin， TX：IEEE，2014：3231-3236. DOI： 10.1109/GLOCOM.2014.7037304.

[11]FUJINO T， SHIMOKAWA T. Combined forward and backward lattice reduction aided MMSE detection in MIMO systems[C]// Proc.Vehicular Technology Conference. Calgary， BC：IEEE，2008：1-6.DOI： 10.1109/VETECF.2008.283.

[12]FUJINO T， SHIMOKAWA T， TRAN X N. A combined forward and backward lattice-reduction aided MMSE list detection[C]// Proc.Advanced Technologies for Communications. Hanoi：IEEE，2008：39-44. DOI： 10.1109/ATC.2008.4760514.

[13]NEGISHI H， WEI H， FUJINO T. MMSE detector using forward and backward reciprocal lattice reduction in MIMO systems[C]// Proc. Signal Processing and Information Technology. Luxor：IEEE，2010：288-292. DOI： 10.1109/ISSPIT.2010.5711796.

[14]HUNUKUMBURE M， SARPERI L. An efficient feed-forward method for lattice reduction MIMO schemes[C]//Proc.22ndInternational Symposium on Personal Indoor and Mobile Radio Communications. Toronto：IEEE，2011：1485-1489. DOI： 10.1109/PIMRC.2011.6139750.

[15]劉金鑄， 萬翔. 基于遺傳算法的無線信道矩陣優(yōu)化技術(shù)[J]. 計算機仿真，2015，32(1)：224-228.

[16]劉向輝，韓文報，權(quán)建校. 基于遺傳策略的格基約化算法[J]. 電子與信息學報，2013，35(8)：1940-1945.

[17]LENSTRA A K， LENSTRA H W， LOVáSZ L. Factoring polynomials with rational coefficients[J]. Mathematische annalen，1982，261(4)：515-534.

[18]張海波，楊祥紅，張嵩. Lovasz條件下LLL算法最簡復Givens矩陣形式的研究[J]. 海軍航空工程學院學報，2012，27(6)：601-604.

[19]ZHANG W，QIAO S Z，WEI Y M，et al. Reduction algorithm for lattice reduction aided MIMO detection[J]. IEEE transactions on signal processing，2012，60(11)：5963-5976. DOI： 10.1109/TSP.2012.2210708.

周圍(1971— )，教授，碩士生導師，博士，主要研究方向為無線移動通信技術(shù)、通信系統(tǒng)及信號處理、智能天線技術(shù)等；

張茜(1991— )，女，碩士生，主研無線移動通信，信號檢測；

王新賀(1989— )，碩士生，主研無線移動通信，陣列信號處理。

責任編輯：閆雯雯

ImprovedLLLlatticereductionalgorithminMIMOsystem

ZHOUWeia，b，ZHANGXia，WANGXinhea

(a. Chongqing Key Laboratory of Mobile Communications Technology;b. College of Optoelectronic Engineering，Chongqing University of Posts and Telecommunications，Chongqing 400065，China)

AimingatthisproblemthatthetraditionalLLLlatticereductionalgorithmachievespoorBERperformanceinMIMOsystems，animprovedLLLalgorithmisproposed.UsingtheLLLalgorithmandreducingmultipleoforiginallatticebasesatthesametime，thealgorithmseeksthesolutionoftheproblemfrommultipleoriginallatticebases.Throughthereductionofthemultipleoriginallatticebases，thebestlatticebasecanbefound.TheimprovedalgorithmcanovercomethelimitationofthetraditionalLLLlatticereductionalgorithm，whichseekingfromasingleoriginallatticebase.Throughtheoreticalanalysisandcomputersimulation，theconvergenceofthealgorithmandtheBERperformanceofdifferentalgorithmsunderdifferentnumberoftransmitandreceiveantennasarestudied.ResultsshowthattheproposedalgorithmachievesbetterperformancethanthetraditionalLLLlatticereductionalgorithm，anditsperformanceisclosertothatofMLalgorithminMIMOsystem.

MIMO；latticereduction；LLLalgorithm；backwardLLLalgorithm

TN929.5

ADOI：10.16280/j.videoe.2016.08.018

國家“863”計劃項目(2009AA011302)；重慶郵電大學研究生教育創(chuàng)新計劃重點項目(Y201019)；重慶市教委科研項目(K1090513)

2015-12-19

文獻引用格式：周圍，張茜，王新賀.MIMO系統(tǒng)中改進的LLL格基約減算法[J].電視技術(shù)，2016，40(8)：93-98.

ZHOUW，ZHANGX，WANGXH.ImprovedLLLlatticereductionalgorithminMIMOsystem[J].Videoengineering，2016，40(8)：93-98.