基于改進(jìn)LLL規(guī)約的MIMO系統(tǒng)解碼算法*

韓志勇 王澤宇

(91919部隊(duì) 黃岡 438000)

基于改進(jìn)LLL規(guī)約的MIMO系統(tǒng)解碼算法*

韓志勇 王澤宇

(91919部隊(duì) 黃岡 438000)

LLL算法是一種經(jīng)典的格基規(guī)約算法,它廣泛應(yīng)用于MIMO通信系統(tǒng)的線性接收機(jī)中。LLL算法依賴于Gram-Schmidt正交化算法,這種算法按照增益矩陣中向量的初始順序產(chǎn)生正交基。論文提出一種排序Gram-Schmidt正交化算法,這種算法可以產(chǎn)生更短的正交基。然后在LLL算法中,用排序Gram-Schmidt正交化算法代替原正交化,以改進(jìn)規(guī)約算法的性能。在仿真實(shí)驗(yàn)中,比較了論文提出的改進(jìn)LLL算法、LLL算法和排序QR分解算法的解碼性能。結(jié)果顯示本文提出的方法誤碼率(BER)最低。

多輸入多輸出; 格基規(guī)約; LLL; Gram-Schmidt正交化

(No. 91919 Troops of PLA, Huanggang 438000)

Class Number TP301.6

1 引言

MIMO技術(shù)能在不提高發(fā)射功率或者增加通信帶寬的情況下,提高數(shù)據(jù)的傳輸速率,增強(qiáng)無線信道的可靠性,是一種非常實(shí)用有效的通信技術(shù)。雖然MIMO技術(shù)讓高吞吐量的數(shù)據(jù)通信成為可能,但是也面臨如何在接收機(jī)端可靠解碼數(shù)據(jù)的挑戰(zhàn)。幸運(yùn)的是,以LLL算法為代表的格基規(guī)約技術(shù)的應(yīng)用,大大增加了數(shù)據(jù)解碼的可靠性。

在數(shù)學(xué)領(lǐng)域,對格基規(guī)約的研究可以追溯到18/19世紀(jì)。Lagrange,Hermite,Korkine與Zolotarev以及Minkowski分別在不同條件下提出了規(guī)約基的算法[1～4]。但是這些算法大多停留在純理論領(lǐng)域,很難實(shí)際應(yīng)用。重大突破來自于Lenstra,Lenstra和Lov’asz一起提出了LLL規(guī)約,并給出了具體的實(shí)現(xiàn)算法[5]。由于LLL規(guī)約能夠在多項(xiàng)式時(shí)間內(nèi)實(shí)現(xiàn),因此得到了各行各業(yè)最廣泛的應(yīng)用:從計(jì)算機(jī)科學(xué)到密碼學(xué)[6～7],從衛(wèi)星導(dǎo)航精密定位到MIMO系統(tǒng)通信[8～9],都可以看到LLL算法的身影。

另一方面,諸如排序QR分解為代表的排序分解算法,也可以取得很高的解碼可靠性[9]。本文通過把排序QR分解中的排序引入LLL算法,提出了一種新的LLL改進(jìn)算法,并把新算法應(yīng)用到MIMO系統(tǒng)解碼中。仿真實(shí)驗(yàn)表明,本文提出的改進(jìn)LLL算法性能優(yōu)于LLL算法和排序QR分解算法。

2 MIMO系統(tǒng)格基規(guī)約

考慮一個(gè)由m個(gè)發(fā)信機(jī)和n個(gè)接收機(jī)(m≥n)組成的m×n維MIMO通信系統(tǒng)。發(fā)送信號向量x和接收信號向量y之間的關(guān)系可描述為

y=Gx+w

(1)

其中G=[g1,g2,…,gn]是一個(gè)m×n維的復(fù)矩陣,代表平緩衰弱瑞利信道中的增益矩陣;w是高斯分布的加性噪聲,其元素互相獨(dú)立。所謂“格”:l?m×n,是復(fù)數(shù)空間m×n的一個(gè)離散子集,它的元素全部由一組格基g1,g2,…,gn∈m×n通過整數(shù)系數(shù)的線性組合構(gòu)成:

L(G)={∑xigi|xi∈}

(2)

一個(gè)格可以由無數(shù)組格基組成,其中一些格基具有非常優(yōu)良的性能,這些格基被稱作“規(guī)約的”。LLL規(guī)約算法就是把“非規(guī)約的”格基變換成“規(guī)約的”格基的算法,它包括三個(gè)部分:Gram-Schmidt正交化,長度規(guī)約和向量交換。

2.1 Gram-Schmidt正交化

(3)

算法一 Gram-Schmidt正交化

輸入:向量序列g(shù)1,g2,…,gn

2: fori=2:n

3: forj=1:i-1

5: end for

7: end for

2.2 LLL算法

定義1 一個(gè)格基G={g1,g2,…,gn}∈n可以被稱作是δ-LLL規(guī)約的,當(dāng)且僅當(dāng)以下兩個(gè)條件同時(shí)滿足:

2) ?1≤i

式中δ∈(1/4,1]是一個(gè)可調(diào)參數(shù),為了達(dá)到算法性能和復(fù)雜度的平衡,通常取δ=3/4。上式中的第一個(gè)條件叫“長度規(guī)約”,它保證規(guī)約后向量之間的近似正交性。第二個(gè)條件叫“Lovász條件”,它保證規(guī)約基的長度不至于縮減太快。記“〔·〕”為取整符號,長度規(guī)約可步驟可描述為算法二。

算法二 長度規(guī)約

輸入: 格基G={g1,…,gn}∈?n,Gram-Schmidt參數(shù)矩陣u

輸出: 長度規(guī)約基G

1: fori=2:n

2: forj=i-1:n

4:gi=gi-〔uij〕gj,uij=uij-〔uij〕

5: forl=1:j-1

6:uil=uil-〔uij〕uil

7: end for

8: end if

9: end for

10: end for

算法二用gi之前的向量g1,g2,…,gi-1對gi進(jìn)行長度規(guī)約。所造成的結(jié)果是越往前面的向量,規(guī)約越不充分。為了對所有向量充分進(jìn)行規(guī)約,LLL算法一邊進(jìn)行長度規(guī)約一邊進(jìn)行向量位置交換。如果“Lovász條件”在向量gi處不滿足,那么gi和gi+1交換,算法后退至gi-1;否則執(zhí)行長度規(guī)約后,算法前進(jìn)至gi+1繼續(xù)判斷“Lovász條件”。LLL算法的執(zhí)行步驟可描述為算法三。

算法三 LLL算法

輸入: 格基G={g1,…,gn}∈n,參數(shù)δ

輸出: 規(guī)約基G

2:i=2

3: whilei≤n

4: 對gi執(zhí)行長度規(guī)約

6: 交換gi和gi+1,更新Gram-Schmidt正交基

7:i=max(i-1,2)

9: else

10:i=i+1

11: end if

12: end while

3 基于排序Gram-Schmidt正交化的LLL改進(jìn)算法

從上節(jié)敘述可知,LLL算法只對相鄰近的向量進(jìn)行交換。Chang (2005)在GNSS定位領(lǐng)域的研究顯示:在規(guī)約前對向量進(jìn)行統(tǒng)一排序,能進(jìn)一步提高規(guī)約性能[10]。著名的SQRD算法就是一種這樣的排序算法(Wübben等2000)[9]。在這一節(jié)中,我們把SQRD算法引入Gram-Schmidt正交化過程,提出排序Gram-Schmidt正交化算法。

算法四 排序Gram-Schmidt正交化

輸入:向量序列g(shù)1,g2,…,gn

1:gk=min:1≤i≤n‖gi‖

3: forl=2:n

4: fori=l:n

5: forj=1:i-1

7: end for

9: end for

12: end for

用排序Gram-Schmidt正交化算法對LLL算法進(jìn)行改進(jìn),就是把LLL算法步驟一中的Gram-Schmidt正交化替換成排序Gram-Schmidt正交化算法,然后再執(zhí)行標(biāo)準(zhǔn)的LLL規(guī)約過程。因?yàn)榕判騁ram-Schmidt正交化算法每一步得到的正交化向量長度都不長于原Gram-Schmidt正交化。在更短的正交基下再進(jìn)行LLL規(guī)約可以得到更好的規(guī)約基,同時(shí)縮短規(guī)約時(shí)間。

4 仿真實(shí)驗(yàn)

由于格基規(guī)約算法在接收機(jī)端解碼的巨大作用,導(dǎo)致了以LLL算法為代表的規(guī)約算法在實(shí)時(shí)MIMO通信中的巨大應(yīng)用。本節(jié)通過仿真一個(gè)瑞利衰落信道下的MIMO接收機(jī)解碼算法。分別比較應(yīng)用SQRD、LLL算法和本文提出的改進(jìn)LLL算法的MIMO系統(tǒng)的比特誤碼率(BER)。

實(shí)驗(yàn)中設(shè)置在發(fā)送方和接受方的天線數(shù)量均為4,數(shù)據(jù)調(diào)制方式基于64-QAM,數(shù)據(jù)解碼方案設(shè)置為迫零檢測(ZF)。在上述實(shí)驗(yàn)方案下,三種算法的解碼比特誤碼率如圖1所示。結(jié)果顯示,隨著信噪比(SNR)的提高,三種算法的BER均大幅下降。其中基于改進(jìn)LLL算法的解碼有最低的BER,略低于原LLL算法,遠(yuǎn)低于SQRD算法。例如圖中顯示,當(dāng)BER小于10-2時(shí),基于改進(jìn)的LLL算法的解碼可以獲得2dB的增益。這說明了改進(jìn)LLL算法優(yōu)于其它兩種算法,實(shí)驗(yàn)結(jié)果符合本文預(yù)期。

圖1 三種算法在64-QAM調(diào)制下4×4 MIMO系統(tǒng)中的BER性能表現(xiàn)

5 結(jié)語

為了加強(qiáng)MIMO系統(tǒng)解碼性能,本文提出了一種改進(jìn)的LLL規(guī)約算法。在改進(jìn)LLL算法中,引入了經(jīng)典的SQRD排序改進(jìn)Gram-Schmidt正交化算法,使得Gram-Schmidt正交化能夠獲得更短的正交基。基于更短正交基的LLL規(guī)約可以獲得更好的規(guī)約性能。基于一組64-QAM調(diào)制下4×4 MIMO系統(tǒng)接收機(jī)解碼仿真實(shí)驗(yàn),比較了SQRD、LLL算法和改進(jìn)LLL算法的性能,結(jié)果表明本文提出的改進(jìn)LLL算法由于其它兩種算法。

[1] Lagrange L. Recherches d’arithm`etique, Nouv. M`em[M]. Berlin: Acad,1773.

[2] Hermite C. Jacobi sur diff’erents objets de la th’eorie des nombres[J]. J Reine Angew Math,1850,40:279-290.

[3] Korkine A, Zolotarev G. Sur les formes quadratiques[J]. Math Ann,1873,6(3):366-389.

[4] Minkowski H. Geometrie der Zahlen[M].Stuttgart:Teubner-Verlag,1896.

[5] Lenstra AK,Lenstra HW Jr,Lov′asz L.Factoring polynomials with rational coefficients[J].Math Ann,1982,261:515-534.

[6] Papachristoudis DG,Halkidis ST,Stephanides G.An experimental comparison of some LLL-type lattice basis reduction algorithms[J].Int J Appl Comput Math,2015,1(3):327-342.

[7] Fontein F,Schneider M,Wagner U.PotLLL:a polynomial time version of LLL with deep insertions[J].Des Codes Cryptogr,2014,73:355-368.

[8] Jazaeri S,Amiri-Simkooei A,Sharifi MA.On lattice reduction algorithms for solving weighted integer least squares problems:comparative study[J].GPS Solut,2014,18:105-114.

[9] Wübben D,B?hnke R,Rinas J,et al.Efficient Algorithm for Decoding Layered Space-Time Codes[J].Electronics Letters,2000,37:1348-1350.

[10] Chang X,Yang X,Zhou T.MLAMBDA:A Modified LAMBDA Method for Integer Least-Squares Estimation[J].J Geod,2005,79:552-565.

A Modified LLL Reduction Aided MIMO System Decoding Method

HAN Zhiyong WANG Zeyu

The classical lattice reduction algorithm, known as the LLL, is widely applied in the linear receivers of the multiple-input-multiple-output (MIMO) system. The LLL depends on the Gram-Schmidt orthgonalization (GSO) which generates the orthogonal basis by the original order. In this contribution, a sorted GSO strategy is proposed in order to obtain shorter orthogonal basis of the lattice. Then the LLL algorithm is modified by replacing the standard GSO with the sorted one. In the simulation study, the modified LLL, classical LLL and the SQRD are compared. The result has revealed that the proposed algorithm is superior to the other two in the term of the bit-error-rate (BER) performances.

MIMO, lattice reduction, LLL, GSO

2016年6月6日,

2016年7月17日

國家自然科學(xué)基金項(xiàng)目(編號:41504029)資助。

韓志勇,男,碩士,工程師,研究方向:移動(dòng)通信,對潛通信。王澤宇,男,助理工程師,研究方向:短波通信。

TP301.6

10.3969/j.issn.1672-9730.2016.12.024