基于改進LLL規約的MIMO系統解碼算法*

韓志勇 王澤宇

(91919部隊 黃岡 438000)

基于改進LLL規約的MIMO系統解碼算法*

韓志勇 王澤宇

(91919部隊 黃岡 438000)

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

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

(No. 91919 Troops of PLA, Huanggang 438000)

Class Number TP301.6

1 引言

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

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

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

2 MIMO系統格基規約

考慮一個由m個發信機和n個接收機(m≥n)組成的m×n維MIMO通信系統。發送信號向量x和接收信號向量y之間的關系可描述為

y=Gx+w

(1)

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

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

(2)

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

2.1 Gram-Schmidt正交化

(3)

算法一 Gram-Schmidt正交化

輸入:向量序列g1,g2,…,gn

2: fori=2:n

3: forj=1:i-1

5: end for

7: end for

2.2 LLL算法

定義1 一個格基G={g1,g2,…,gn}∈n可以被稱作是δ-LLL規約的,當且僅當以下兩個條件同時滿足:

2) ?1≤i

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

算法二 長度規約

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

輸出: 長度規約基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進行長度規約。所造成的結果是越往前面的向量,規約越不充分。為了對所有向量充分進行規約,LLL算法一邊進行長度規約一邊進行向量位置交換。如果“Lovász條件”在向量gi處不滿足,那么gi和gi+1交換,算法后退至gi-1;否則執行長度規約后,算法前進至gi+1繼續判斷“Lovász條件”。LLL算法的執行步驟可描述為算法三。

算法三 LLL算法

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

輸出: 規約基G

2:i=2

3: whilei≤n

4: 對gi執行長度規約

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改進算法

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

算法四 排序Gram-Schmidt正交化

輸入:向量序列g1,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算法進行改進,就是把LLL算法步驟一中的Gram-Schmidt正交化替換成排序Gram-Schmidt正交化算法,然后再執行標準的LLL規約過程。因為排序Gram-Schmidt正交化算法每一步得到的正交化向量長度都不長于原Gram-Schmidt正交化。在更短的正交基下再進行LLL規約可以得到更好的規約基,同時縮短規約時間。

4 仿真實驗

由于格基規約算法在接收機端解碼的巨大作用,導致了以LLL算法為代表的規約算法在實時MIMO通信中的巨大應用。本節通過仿真一個瑞利衰落信道下的MIMO接收機解碼算法。分別比較應用SQRD、LLL算法和本文提出的改進LLL算法的MIMO系統的比特誤碼率(BER)。

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

圖1 三種算法在64-QAM調制下4×4 MIMO系統中的BER性能表現

5 結語

為了加強MIMO系統解碼性能,本文提出了一種改進的LLL規約算法。在改進LLL算法中,引入了經典的SQRD排序改進Gram-Schmidt正交化算法,使得Gram-Schmidt正交化能夠獲得更短的正交基?；诟陶换腖LL規約可以獲得更好的規約性能。基于一組64-QAM調制下4×4 MIMO系統接收機解碼仿真實驗,比較了SQRD、LLL算法和改進LLL算法的性能,結果表明本文提出的改進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日

國家自然科學基金項目(編號:41504029)資助。

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

TP301.6

10.3969/j.issn.1672-9730.2016.12.024