王艷麗， 陰國富

(渭南師范學院 網絡安全與信息化學院， 陜西 渭南　714000)

?

·信息科學·

低復雜度的新型球形譯碼檢測算法

王艷麗， 陰國富

(渭南師范學院 網絡安全與信息化學院， 陜西 渭南714000)

在多輸入多輸出(MIMO)信號檢測算法中,球形譯碼檢測算法的復雜度會隨著半徑的增大而迅速增加,代價較高。為了避免這一問題,提出一種改進的球形譯碼算法,該算法考慮改變搜索的起始位置,從最接近信號點上下限中間位置開始搜索,并根據信號點和中間位置的距離對信號點升序排序,隨著譯碼半徑的改變，排序不變,這樣就減少搜索次數,降低算法復雜度。仿真結果表明,隨著半徑取值的增加,新型球形譯碼算法復雜度大幅度降低的同時,仍然保證了譯碼性能最接近性能最優(yōu)的最大似然檢測算法。

多輸入多輸出;球形譯碼算法;譯碼半徑;譯碼復雜度

多輸入多輸出(multiple input multiple output, MIMO)技術利用多天線抑制信道衰落,其出發(fā)點是將多發(fā)送天線與多接收天線相結合,改善每個用戶的通信質量或提高通信效率,無線信道容量隨著天線數目的增加而線性增大[1],在4G移動通信系統(tǒng)中，作為一項關鍵技術得到長足發(fā)展[2],但多天線的引入導致了MIMO系統(tǒng)接收端信號檢測復雜度的提高,尋找一種低復雜度、高檢測性能的信號檢測算法仍是研究的熱點。

MIMO系統(tǒng)的信號檢測算法主要有最大似然(maximum likelihood,ML)算法、線性檢測算法、非線性檢測算法和許多次優(yōu)檢測算法及其改進算法。傳統(tǒng)的ML算法是最優(yōu)檢測算法,但其復雜度呈指數增長,實際應用很難;線性檢測算法包括迫零(zero-forcing,ZF)算法和最小均方誤差(minimum mean-square error,MMSE)算法,ZF算法付出了增加噪聲的代價,并在低信噪比時性能較差,MMSE算法雖然考慮了噪聲的干擾,但在高信噪比時,其檢測性能收斂于ZF算法;非線性檢測算法主要包括串行干擾消除(successive interference cancellation,SIC)算法,其擁有較低的復雜度,但檢測效果不佳;許多次優(yōu)檢測算法及其改進算法進一步提高了檢測效率和檢測性能,文獻[3]針對MIMO系統(tǒng)信號檢測的V-BLAST算法預處理具有較高運算復雜度的問題,提出了降低復雜度的V-BLAST算法。文獻[4]聯(lián)合SIC和QRD-M樹搜索,提出一種低復雜度的V-BLAST算法。

在眾多的信號檢測算法中,最接近ML算法檢測性能的是球形譯碼(sphere decoding,SD)算法[4-5],SD算法仍存在復雜度較高的問題。各種改進算法仍存在對矩陣的復雜計算,并沒有真正降低復雜度[6]。文獻[5]指出球形譯碼算法可以用準正交空時編碼,達到降低系統(tǒng)復雜度的目的。文獻[7]利用QAM復數調制信號表達式中的相似性并通過減少單個節(jié)點的計算量達到簡化球形譯碼的目的。文獻[8]基于傳統(tǒng)的Dijkstra球形譯碼算法,引入查找表機制和單樹更新軟值的算法,改進Dijkstra球形譯碼進出棧的方法,減少系統(tǒng)的存儲開銷,有效減少接收機的復雜度。文獻[9]根據信道質量的好壞和噪聲的大小選擇SD算法的初始半徑,并通過減少搜索點數降低算法的復雜度,但檢測性能損失較大。文獻[10]考慮噪聲對檢測效果的影響,為提高SD算法半徑的收縮速度,將控制半徑收縮參數k(t)的取值修改為常量0.1,從而達到降低復雜度的目的。本文針對以往研究的不足,提出一種新型球形譯碼檢測算法,該算法的搜索起始位置不同于其他算法，是從最接近信號點上下限的中間位置開始搜索，根據信號點和中間位置的距離，對信號點升序排序;當半徑更新時,排序不變，因此，無需再次進行排序,避免對已經確定的有效點進行再次搜索,進一步降低算法復雜度。

1　系統(tǒng)模型

在nR×nTMIMO系統(tǒng)中,發(fā)送天線數nT,接收天線數nR,接收信號矢量Y表示為

Y=HX+V，

(1)

其中,X=[x1,x2,…，xnT]T是發(fā)送信號矢量,每個信號分量等概率地選自復星座集合S,Y=[y1,y2,…，ynR]T,各分量列數與每根發(fā)送天線傳輸的符號數有關,H表示nR×nT復信道矩陣,用hi,j表示第i根發(fā)射天線到第j根接收天線的信道頻域響應,V是均值為零,方差為σ2的高斯噪聲,

2　球形譯碼算法及其改進算法

2.1ML檢測算法

假設接收端是理想信道估計,接收端信道矩陣H已知,信號檢測過程是求解‖Y-HX‖2的最小值,即在星座調制圖上進行譯碼搜索,尋找與接收信號距離最近的點,則ML檢測算法可表示為

(2)

ML檢測算法是遍歷的搜索方法,可以獲得最佳的性能。但是，復雜度高達Ο(2QnT),其中,Q是調制比特數。ML檢測算法由于較高的復雜度,影響了其在工程上的應用。

2.2傳統(tǒng)球形譯碼算法

球形譯碼算法[11]與ML算法的不同之處體現(xiàn)在球形譯碼算法的搜索范圍是在以Y為圓心,c為半徑的球內。若以c2表示球的平方化半徑,則球中點滿足下式:

‖Y-HX‖2≤c2。

(3)

圖1　球形譯碼算法檢測過程Fig.1　Process of the sphere decoding algorithm

2.3現(xiàn)有的改進球形譯碼算法

2.3.1改進算法一文獻[9]針對傳統(tǒng)球形譯碼檢測算法在噪聲方差較大時,譯碼復雜度較高的問題,提出一種新的譯碼半徑選擇方法,主要改進思想體現(xiàn)在，半徑的選取根據信道的狀態(tài)和噪聲的大小進行動態(tài)調整。

初始半徑用c表示,半徑c的選擇方法由式(4)給出

(4)

if(a

elsec=b。

(5)

由式(4)和式(5)可以看出,當噪聲方差較小時,a與b接近;當噪聲方差較大時,a

文獻[9]所提改進算法在信噪比較低的情況下,是以犧牲10%的性能為代價換取復雜度40%～50%的降低。

2.3.2改進算法二文獻[10]考慮初始半徑的選取和噪聲對檢測效果的影響,改進思路主要體現(xiàn)在以下兩個方面:

1)由于球形譯碼算法半徑的選取存在不確定性,當球形譯碼算法進行有效點搜索時,若找到第一個有效點后,新的搜索半徑c′2=k(t)*c2,針對k(t)的不確定性以及計算k(t)會進一步提高算法復雜度的缺點,將k(t)用常數0.1替換,克服存在問題。

2) 由于噪聲影響算法的復雜度,當信噪比較低時,即噪聲干擾較強時,算法的搜索次數會增多,進一步導致復雜度的提高?？紤]MMSE檢測算法的優(yōu)點,將MMSE檢測算法和球形譯碼算法相結合達到提高檢測性能的目的。

文獻[10]算法在實現(xiàn)過程中引入MMSE檢測,濾波矩陣的求取會進一步增加計算量,如何降低算法的復雜度并進一步提高檢測性能是本文的出發(fā)點。

2.3.3改進算法三文獻[12]提出適用于較大MIMO系統(tǒng)和較高信噪比情況下的SPSD(statisticalpruningspheredecoder)算法,該算法對原始SD算法進行了改進,主要體現(xiàn)在以下兩個方面:

1) 選取初始半徑c=∞,對信道矩陣H進行QR分解,可得

(6)

2) 搜索順序從頂層到底層,以第k層為例,SPSD算法以滿足式(6)節(jié)點的局部分支路徑為代價作升序排序;若沒有滿足式(6)的節(jié)點,則進入下一層搜索,直至搜索到最底層,更新球半徑,繼續(xù)下一輪搜索。

文獻[12]對比了不同裁剪策略下各種算法的性能,采用深度裁剪函數,獲得近似ML算法的性能。但是,該算法復雜度在低信噪比時仍舊較高[13]。

3　新型球形譯碼算法

3.1原算法問題分析

傳統(tǒng)SD算法在實現(xiàn)過程中存在以下問題:

1) 從圖1可以看出,傳統(tǒng)SD算法實現(xiàn)過程中需要對半徑的大小實時更新,當找到候選向量后,便將半徑更新為找到的候選向量到球心的距離,然后在新半徑的球內搜索,直至沒有解為止;

2) 傳統(tǒng)SD算法及現(xiàn)有的改進算法考慮從球面開始搜索,沒有最大程度減少搜索次數。

3.2新算法描述

根據原算法和現(xiàn)有改進算法存在的問題,本文在現(xiàn)有改進算法的基礎上,考慮搜索的位置并將排序思想應用于SD算法。具體檢測過程是:

1) 確定檢測順序

初始半徑c的選取根據傳統(tǒng)SD算法中的經驗公式[14]

c2=αnσ2，

(7)

(8)

其中,Γ(·)為Gamma函數,n是接收信號維數,α是控制收縮速度的參數,ξ表示搜索不到網格點的概率,取值為0.01。

(9)

其中,「?和?」分別表示上限和下限。

式(9)中上限用Ui表示,下限用Li表示,依據點到Ui和Li中間位置的距離,根據|zij-Si|2對調制星座點中的格點進行升序排序,zij表示第i個坐標的可能值，其中,1≤j≤Ni,Ni表示在S中介于Li和Ui之間的點,Ni=length(Li,Ui,S)。

2) 確定搜索位置和半徑更新

傳統(tǒng)SD算法從球的表面開始搜索直至找到與球中心最接近的有效點為止,這種方法不是有效的方法,特別是在高維球體的情況下。為了降低算法復雜度,本文算法不同于傳統(tǒng)SD算法從最接近Li的位置開始搜索,考慮從最接近Ui和Li中間位置開始。

當搜索到一個有效點后,用cnew表示該點到球心的距離,需要對球的半徑進行更新:

(10)

設置k為自適應量[15],即

(11)

其中,q是每個信號對應的比特數,γs是信噪比。

k值的選擇影響SD算法復雜度,表1給出k值對算法復雜度的影響。

表1　k值對算法復雜度影響

從表1可以看出，當0.1

半徑更新后需要重新計算上限Ui和下限Li,同時,Ni也會隨著上限和下限的變化而發(fā)生改變。本質上,更新后的界限是在Ni減少的條件下以及在原有的Ui和Li的基礎上得到的,其排序是在原有的基礎上進行的,不進行重新排序,避免了對已經確定的有效點進行二次搜索。

綜上所述，新型球形譯碼檢測算法的過程可以歸納為如下3步:

1) 排序過程

① 利用式(7)和式(8)計算初始半徑,根據初始半徑的取值,利用式(9)計算發(fā)送信號向量的上限和下限,并進一步確定信號空間S中介于Ui和Li之間的信號點個數。

② 在集合S中,根據星座調制圖上所有點與Ui和Li的中間位置的距離，對其升序排序。

2) 半徑的更新過程

① 從最接近Ui與Li中間位置開始搜索,當發(fā)現(xiàn)第一個有效點后,該點到球心的距離設為cnew,根據式(10)計算新的搜索半徑。

② 在Ni減少的情況下,根據新半徑取值重新計算上限和下限,此時,不需要重新排序,避免了重復搜索。

3) 循環(huán)實現(xiàn)所有發(fā)送符號向量檢測過程

① 若檢測出有效點的數目在Ni范圍內,需要重復(2)步驟,直到檢測完Ni個有效點。

② 與網格矢量的成分個數相比,若檢測的是最后一個矢量成分,則輸出結果,否則,繼續(xù)返回上述過程,直到所有矢量成分被檢測出。

4　算法復雜度及檢測性能分析

實驗采用MATLAB進行仿真,構造2×2MIMO系統(tǒng),信道為已知的平坦瑞利衰落信道,均值為0且獨立同分布的高斯白噪聲,調制方式為4QAM。

仿真1各檢測算法的誤比特性能仿真分析

圖2對比了不同算法的誤比特性能。其中,橫坐標表示信噪比,縱坐標表示誤比特率。REV-SD算法是文獻[9]提出的改進球形譯碼算法,KSD-MMSE算法是文獻[10]提出的改進球形譯碼算法。SPSD算法是文獻[12]提出的改進球形譯碼算法。

圖2　不同算法的誤比特性能對比Fig.2　BER comparison with different algorithms

從圖2可以看出,ML算法和SD算法的曲線幾乎重合,驗證了SD算法能夠達到ML算法的檢測效果。在信噪比較小的情況下,SD，REV-SD，KSD-MMSE，SPSD算法和本文算法與ML算法的性能接近,并且本文算法與KSD-MMSE算法、SPSD算法性能相當。在信噪比較大的情況下,5種算法誤碼率增加的很小,特別是SPSD算法和本文算法依然十分接近ML算法。

仿真2各檢測算法的復雜度仿真分析

圖3示出SD，REV-SD，KSD-MMSE和本文算法的復雜度隨初始半徑變化的結果。其中,橫坐標表示初始半徑,縱坐標表示浮點運算次數。

圖3　不同算法復雜度對比Fig.3　Complexity comparison of different algorithms

從圖3可以看出,與SD，REV-SD和KSD-MMSE算法相比,隨著初始半徑的增加,本文算法浮點運算次數曲線呈現(xiàn)平穩(wěn)狀態(tài),而其他3種算法呈現(xiàn)急速增長趨勢。本文算法的運算量主要體現(xiàn)在H=QR的計算以及在Ni范圍內對有效點的搜索。本文算法計算復雜度有了顯著的降低,是因為算法在執(zhí)行過程中進行了排序并且搜索的過程是從最接近Ui與Li的中間位置開始,而并非其他算法從最接近Li的位置開始搜索。

圖4示出SD，REV-SD，KSD-MMSE和本文算法的復雜度隨信噪比變化的結果。

圖4　不同算法復雜度與信噪比關系Fig.4　Complexity comparison of different algorithms with SNR

從圖4可以看出,傳統(tǒng)SD算法具有較高復雜度,而其他算法復雜度較低。低信噪比時，KSD-MMSE體現(xiàn)了其優(yōu)勢,計算復雜度較低。隨著信噪比的增高,噪聲的影響隨之減少,REV-SD算法和本文算法體現(xiàn)了優(yōu)勢,計算復雜度較低,與前面的分析一致,從而驗證了本文算法在保證檢測性能的前提下降低了算法計算復雜度這一結論。

SPSD算法初始半徑為無窮大,當到達葉子節(jié)點時，對半徑進行更新,根據SPSD算法的特征,采用實際經過的節(jié)點數衡量其復雜度,圖5示出SPSD算法和本文算法實際經過的節(jié)點數隨信噪比變化的結果。

從圖5可以看出,SPSD算法在低信噪比情況下具有較高的復雜度,當信噪比增大時,呈現(xiàn)平緩趨勢;本文算法復雜度低于SPSD算法,說明限制初始半徑可以有效降低復雜度。

圖5　 本文算法和SPSD算法復雜度比較Fig.5　Complexity comparison of SPSD algorithm and this paper′s algorithm

5　結　語

本文在原有改進算法的基礎上,基于MIMO系統(tǒng)，提出一種新型球形譯碼檢測算法,選擇不同于其他算法的搜索方法,改進算法從最接近信號點上限和下限的中間位置開始,并對調制空間集中的信號點升序排序,當半徑更新時,無需二次排序,避免已經發(fā)現(xiàn)的有效點再次被搜索的可能,新型球形譯碼算法在保證檢測性能的同時,相對于其他算法有著更低的復雜度。本文算法為降低MIMO系統(tǒng)復雜度提供了一種良好的選擇。

[1]GOLDSMITH A,JAFAR S A,JINDAL N, et al.Capa-city limits of MIMO channels[J].IEEE Journal on Selected Areas in Communications,2003,21 (5): 684-702.

[2]趙新雪,李瓊,肖維杰,等.低復雜度最大似然MIMO信號檢測算法[J].計算機工程與設計,2014,35(1): 144-147.

[3]劉謙雷,楊綠溪,許道峰.用于MIMO信號檢測的降低復雜度V-BLAST算法[J].通信學報,2007,28(9): 40-45.

[4]熊春林,王德剛,劉偉,等.聯(lián)合SIC和QRD-M 樹搜索的低復雜度VBLAST檢測算法[J].信號處理, 2009, 25(5):746-750.

[5]PENG A Y C, KIM I M, YOUSELFI S. Low-complexity sphere decoding algorithm for quasi-orthogonal space-time block codes[J]. IEEE Transactions on Communications,2006, 54(3): 377-382.

[6]LIU L, L?FGREN J, NILSSON P. Low-complexity likelyhood information generation for spatial-multiplexing MIMO signal detection[J].IEEE Trans Vehicular Technology,2012, 61(2): 607-617.

[7]岳珍梅,藺俊杰,杜少波.一種改進的球形譯碼算法性能分析[J].蘭州理工大學學報,2013,39(6):94-96.

[8]盧炳山,劉偉,余暉,等.一種低復雜度多輸入多輸出球形譯碼算法[J].上海交通大學學報(自然科學版),2012,46(11)：1833-1837.

[9]陳發(fā)堂,侯彥莊.基于MIMO-OFDM系統(tǒng)的一種低復雜度球形譯碼檢測算法[J].計算機應用研究, 2011,28(9):3436-3438.

[10] 李世平,王隆.結合最小均方誤差的改進球形譯碼檢測算法[J].計算機應用,2012,32(2): 385-387.

[11] CHAN A M, LEE I. A new reduced-complexity sphere decoder for multiple antenna systems[J]. IEEE Trans Vehicular Technology, 2012, 61(2):607-617.

[12] CUI T, HAN S, TELLAMBURA C. Probability distribution based node pruning for sphere decoding[J].IEEE Transactions on Vehicular Technology,2013,62(4):1586-1596.

[13] 金鑫,倪蕓,姚曉東. 基于概率裁剪的球形譯碼算法[J].華東理工大學學報(自然科學版),2014,40(3):371-375.

[14] VITERBO E,BOUTROS J.A universal lattice code decoder for fading channels[J].IEEE Transactions on Information Theroy,1999, 45(5)：1639-1642.

[15] 劉凱,行雙雙.基于可靠性度量排序的λ-廣義球形解碼算法[J].計算機應用,2013,33(4): 923-930.

(編輯李靜)

A new type of sphere decoding detection algorithm with low complexity

WANG Yan-li， YIN Guo-fu

(College of Network Security and Information Technology, Weinan Normal University, Weinan 714000， China)

The performance of sphere decoding algorithm is similar to the optimal maximum likelihood detection algorithm and the decoding complexity is greatly reduced in MIMO system. However, the complexity of detection will increase rapidly as the radius increasing and lead to the higher price. In order to avoid the complexity increasing in the detection process, this paper consider changing the search position, and make the nearest signal point to the upper and lower intermediate position as the starting position. Meanwhile, the detection order is in ascending order according to the signal point and the distance of the length of the intermediate position, the order remains unchanged with the radius changing. This method reduces the number of searches and complexity of the algorithm. Simulation results show that the new sphere decoding algorithm can greatly reduce complexity with the increase of radius and make the performance close to the maximum likelihood decoding algorithm.

MIMO; sphere decoding; decoding radius; decoding complexity

2014-12-19

國家自然科學基金資助項目(61172071);渭南市科技計劃基金資助項目(2015KYJ-2-2);渭南師范學院科研基金資助項目(15YKP006); 渭南市科技計劃基金資助項目(2015KYJ-2-3)

王艷麗，女，陜西咸陽人，從事無線通信信號處理、無線網絡技術研究。

TP3391.9；TN929

A

10.16152/j.cnki.xdxbzr.2016-02-008