一種改進的球形解碼算法

王 寧，李 君，金 寧

（中國計量學院 信息工程學院，浙江 杭州 310018）

近年來，隨著因特網(wǎng)和多媒體應用在下一代無線通信中的集成，寬帶高速數(shù)據(jù)通信服務的需要正在不斷增長.另一方面，可利用的無線頻譜是有限的，如果通信頻譜的利用率沒有得到顯著提高，就不能滿足通信容量的需求.信息論的研究證明，在發(fā)送端和接收端都采用多天線的MIMO技術可以大量提高頻譜利用率，這使其在通信領域得到了廣泛的應用［1］.信號的檢測性能對MIMO系統(tǒng)的性能至關重要，因此，MIMO系統(tǒng)中的檢測算法是當前研究的重點.

在MIMO信號檢測算法中，最大似然（ML）檢測是在誤比特率最小的意義下的最優(yōu)接收，但其計算復雜度隨著發(fā)射天線數(shù)及調(diào)制星座點數(shù)的增加而呈指數(shù)增長，這使其成為一個NP問題.除此之外，還有一些次優(yōu)的檢測算法，如迫零（ZF）算法、最小均方誤差（MMSE）算法、串行干擾抵消（V－BLAST）算法等，這些算法的復雜度較低，但其誤比特率性能較差.

近年來出現(xiàn)了一些準最大似然檢測算法，球形解碼算法就是其中之一.球形解碼算法通過設定一個以接受向量為中心的超球，僅搜索超球內(nèi)的格點來找到最大似然解，從而避免了繁瑣復雜的搜索，降低了球形解碼算法的復雜度，使其在很大的信噪比范圍內(nèi)與天線數(shù)呈多項式關系［2］.

但在低信噪比范圍內(nèi)或調(diào)制階數(shù)較高時，球形解碼算法的復雜度仍然是很高的，這也是近年來球形解碼算法研究的重點.信號的檢測順序與球形解碼算法的復雜度密切相關，因此可以通過對信道矩陣的列進行重排來改變信號的檢測順序［3-13］，從而減低球形解碼算法的復雜度.文獻［3］以信道矩陣的列范數(shù)作為依據(jù)；文獻［4，5］則將最優(yōu)檢測順序的V－BLAST［6］算法運用到球形解碼中；文獻［7－10］是基于排序的QR分解算法，將排序算法嵌入在QR分解的過程中，其中文獻［7］只考慮了信道矩陣，文獻［8－10］則綜合考慮了信道矩陣和接收向量；文獻［11－13］中提出用迫零算法的初始估計值作為參考來確定發(fā)射向量的可靠性，從最可靠的元素開始檢測.這些改進算法都不同程度地降低了球形解碼算法的計算復雜度，但在高信噪比范圍內(nèi)，由于球形解碼算法中SE搜索策略的限制，其復雜度最終會收斂于2m－1.本文所提出的算法主要針對高信噪比范圍內(nèi)球形解碼算法復雜度的進一步降低，通過累積分布函數(shù)得到一個閾值，在搜索到葉子節(jié)點后，將其累積度量值和閾值進行比較來判斷是否找到最大似然解，從而降低了球形解碼算法在高信噪比范圍內(nèi)的復雜度.

1 系統(tǒng)模型

考慮一個未編碼的MIMO系統(tǒng)，發(fā)射天線數(shù)為M，接收天線數(shù)為N（N≥M），假定信道是平坦瑞利衰落的，其接收信號可表示為：

上式中采用復數(shù)信號模型，其中y＝［y1，y2，...，yN］T是N×1的接收信號向量.s＝［s1，s2，...，sM］T是M×1的發(fā)射信號向量.H 是N×M的信道矩陣，H的每一個元素hi，j都是獨立同分布的復高斯隨機變量，且其均值為零，方差為1.w為加性高斯白噪聲，服從復高斯分布，且其均值為零，方差為σ2.

為了簡化編程細節(jié)，我們通常先將信號模型從復數(shù)域轉(zhuǎn)換到實數(shù)域，轉(zhuǎn)換后各個量的維數(shù)加倍，即m＝2 M，n＝2 N.

假設發(fā)送符號采用L2－QAM調(diào)制方式（QAM是指正交幅度調(diào)制），則s的每個元素有L個可能取值，在信道已知的條件下，接收端的最大似然檢測可表示為：

其中下標中的集合D代表所有可能的發(fā)送信號向量的集合，‖·‖代表向量的歐氏范數(shù).

球形解碼的基本思想是在一個以接受向量為球心的超球內(nèi)搜索格點，離球心最近的格點即為相應的譯碼.通過僅搜索超球內(nèi)部的點，而避免了搜索整個格點集合，其具體算法如下：

假定球形解碼的初始半徑為d0，則在超球內(nèi)的點必須滿足：

對H進行QR分解，可得：

其中，R是m×m的上三角矩陣，（·）＊表示矩陣的Hermitian轉(zhuǎn)置.Q＝是n×n的酉矩陣，Q1和Q2分別代表矩陣Q的前m列和后n－m列.在此，令d2＝－，z＝y(tǒng)，則式（8）可變?yōu)椋?/p>

利用上三角矩陣R可將上式右邊展開，可得：

通過上式我們可以得到sm的取值范圍，之后通過迭代可依次得到sm－1、sm－2直至s1的取值范圍，從而形成一個深度為m的樹形搜索結(jié)構，如圖1所示.當搜索到葉子節(jié)點即樹的最底層時，若其累積度量值小于當前半徑，則可將半徑更新，繼續(xù)搜索，直至找到累積度量值最小的格點，即最大似然解.

圖1 球形解碼算法的樹形搜索結(jié)構示意圖Figure 1 Search tree of the sphere detection algorithm

在球形解碼算法的樹形搜索過程中，有兩種搜索策略，分別是 Fincke－Pohst（FP）策略和Schnorr－Euchner（SE）策略.這兩種策略的主要區(qū)別是在枚舉候選節(jié)點時的順序，F(xiàn)P策略在訪問下一層節(jié)點時按照信號星座的順序，從左到右依次枚舉信號星座點.SE策略則是將下一層的信號星座點按其當前層的度量值從小到大排序，在訪問下一層節(jié)點時按此順序枚舉.

SE策略是以折線搜索（zig－zag）的方法進行，該算法搜索的第一個點為當前層度量值最小的點，因此若搜索失敗，則可直接跳過該層剩余節(jié)點，從而大大減少了算法的計算復雜度.

SE策略在半徑設為無窮時搜索到的第一個點即為Babai點，因此SE策略對半徑的選擇不敏感.由于SE策略是從最小化分支度量的節(jié)點開始搜索，所以能比FP策略更快的找到最大似然解，其復雜度也相對更低，因此對球形解碼算法的研究也主要是基于SE策略.

2 改進的球形解碼算法

球形解碼算法中，對信道矩陣H進行QR分解所得到的上三角矩陣R決定了信號的檢測順序，但這個順序并不一定是最優(yōu)的求解順序.因此，可以通過對信道矩陣H的列進行重排來改變信號的檢測順序，降低球形解碼算法的復雜度.在文獻［3－13］中，研究人員提出了許多種不同的排序策略來對信道矩陣的列進行重排，從而改變信號的檢測順序，這些改進算法均不同程度的降低了球形解碼算法的復雜度，特別是在低信噪比范圍內(nèi)，但在高信噪比范圍內(nèi)，由于SE搜索策略的限制，各算法的展開節(jié)點數(shù)均收斂于2m－1，本文所提出的算法主要針對高信噪范圍內(nèi)球形解碼算法復雜度的降低.

采用SE策略，在初始半徑為無窮時搜到的第一個點為Babai點，而在高信噪比范圍內(nèi)，這個點有很大的概率即為最大似然解.但由于SE策略的限制，此時并不能立即判決該點是否為最大似然解，而只有繼續(xù)回溯直到第一層，若此時仍是Babai點的累積度量值最小則表明找到最大似然解.因此，我們可以設法找到一個閾值，在搜索到葉子節(jié)點后將其累積度量值和閾值比較，若其小于閾值，我們可認為最大似然解已經(jīng)找到，停止搜索，而不必繼續(xù)回溯，從而降低球形解碼算法的復雜度.

對于實際的傳輸向量，總的累積度量值可以表示如下：

其中qi代表矩陣的第i列，上式中ωi～N（0，σ2），所以‖ωi‖2服從自由度為1的χ2分布，而Q1為酉矩陣，并不會改變‖ωi‖2的分布，因此累積度量值P服從自由度為m的χ2分布，并且正確格點的累積度量值服從中心的χ2分布，而錯誤格點的累積度量值則服從非中心的χ2分布，如圖2所示.

從圖2中可以看出，若某個格點的累積度量值在正確格點和錯誤格點交點的左側(cè)，則該點是正確格點的概率要大于其是錯誤格點的概率，而越往左側(cè)，該點是正確格點的可能性就越大.因此，我們可以選定一個概率值ε，根據(jù)正確格點的累積分布函數(shù)得到一個閾值，作為判斷最大似然解的依據(jù).若搜索到某個葉子節(jié)點后，其累積度量值小于閾值，我們認為最大似然解已找到，停止搜索，否則繼續(xù)搜索.

ε的取值對球形解碼算法的性能也有一定的影響，若ε取值過大，即表明閾值過大，此時，誤碼率也相應較高，特別是在低信噪比范圍內(nèi).而在高信噪比范圍內(nèi)，若ε取值過小，即閾值過小，則會降低閾值對球形解碼算法的約束作用，以致對高信噪比范圍內(nèi)球形解碼算法的復雜度影響不大.基于上述原因，我們在選取閾值時應對球形解碼算法的性能和復雜度作一個權衡，在低信噪比范圍內(nèi)減小閾值，而在高信噪比范圍內(nèi)則適當加大閾值.

圖2 χ2分布的概率分布圖Figure 2 Probability distribution of theχ2 distribution

3 仿真結(jié)果分析

在仿真過程中，將本文所提到的閾值運用到了不同排序策略的球形解碼算法中，這其中包括文獻［3］中的 V－BLAST算法，文獻［12］中的梯度（GRA）算法以及文獻［10］中的均衡排序的QR分解（BSQR）算法.本文對各算法的性能和復雜度均做了比較，采用樹形搜索結(jié)構中展開的節(jié)點數(shù)作為復雜度的判斷依據(jù).

圖3為4×4及6×6的MIMO系統(tǒng)中采用16QAM、64QAM星座調(diào)制方式下各算法的誤符號率性能圖.當信噪比為0～19dB時，ε＝0.05，當信噪比為20～30dB時，ε＝0.4.從圖中可以看出，由于在低信噪比范圍內(nèi)閾值較小，此時采用閾值后和原來的球形解碼算法相比性能相差不大；而在高信噪比范圍內(nèi)閾值較大，此時采用閾值后相比原來的球形解碼算法性能要差些，若想提高其性能，可通過減小閾值來實現(xiàn).

圖3 不同算法的誤符號率性能圖Figure 3 SER performance of different algorithms

圖4為4×4的MIMO系統(tǒng)中采用16QAM星座調(diào)制時的復雜度曲線圖.從圖中可以看出，相比原來的球形解碼算法，采用閾值后，各算法的復雜度均有不同程度的降低.在低信噪比范圍內(nèi)，各算法的復雜度降低幅度各不相同，其中GRA算法和BSQR算法的下降幅度較大.在高信噪比范圍內(nèi)，原來的算法在20dB之后展開節(jié)點數(shù)逐漸收斂于15左右，即為2m－1；而采用閾值后，各算法在20dB之后展開節(jié)點數(shù)逐漸收斂于8左右，即為樹的深度m.圖5為4×4的MIMO系統(tǒng)中采用64QAM星座調(diào)制時的復雜度曲線圖，由于調(diào)制階數(shù)較高，此時的復雜度也較高，各算法的復雜度在24dB之后開始收斂，在30dB時原來的算法收斂到16左右；而采用閾值后則收斂到9左右，可以看出，隨著信噪比的繼續(xù)增大，采用閾值后其復雜度最終會收斂于8，即為樹的深度m.在低信噪比范圍內(nèi)，采用閾值后，各算法的復雜度也有不同程度的降低.圖6為6×6的MIMO系統(tǒng)中采用16QAM星座調(diào)制時的復雜度曲線圖.同樣的，在低信噪比范圍內(nèi)，采用閾值后，各算法的復雜度均有不同程度的降低，而在高信噪比范圍內(nèi)，在20dB之后，原來算法的復雜度逐漸收斂到23左右，即2m－1；而采用閾值后，其復雜度逐漸收斂到12左右，即為樹的深度m.以上仿真結(jié)果表明，本文所提出的閾值算法有效的將球形解碼算法在高信噪比下展開節(jié)點數(shù)的收斂值從2m－1降到了搜索樹的深度m，并且使其在低信噪比范圍內(nèi)的復雜度也進一步得到了降低.

圖4 采用16QAM調(diào)制的4×4MIMO系統(tǒng)中不同算法的復雜度曲線圖Figure 4 Average computational complexity of different algorithms for 16QAM modulated4×4MIMO system

4 結(jié) 語

球形解碼算法由于其良好的性能被應用到通信系統(tǒng)的諸多領域，但由于SE搜索策略的限制，其在高信噪比下的展開節(jié)點數(shù)始終收斂于2m－1.本文所提出的算法將其在高信噪比下展開節(jié)點數(shù)的收斂值降到了m，并且使其在低信噪比范圍內(nèi)的復雜度也得到了相應的降低.在高信噪比范圍內(nèi)，該算法的性能相比原始的球形解碼算法有少許差距，但這可以通過對閾值的調(diào)整來改善，從而達到性能和復雜度的折中.

［1］郭麗娜，金 寧.瑞利信道下網(wǎng)格酉空時調(diào)制的仿真實現(xiàn)［J］.中國計量學院學報，2009，20（2）：163－166.

［2］VIAKALO H，HASSIBI B.On the sphere－decoding algorithm Ⅱ.Generalizations，second－order statistics，and applications to communications［J］.IEEE Transactions on the Signal Processing，2005，53（8）：2819－2834.

［3］DAMEN M O，GAMAL H E，CAIRE G.On maximumlikelihood detection and the search for the closest lattice point［J］.IEEE Transactions on Information Theory，2003，49（10）：2389－2402.

［4］BARBERO L G，THOMPSON J S.Fixing the complexity of the sphere decoder for MIMO detection［J］.IEEE Transactions on Wireless Communications，2008，7（6）：2131－2141.

［5］DING Y H，WANG Y，DIOURIS J F.Robust fixed complexity sphere decoder［C］／／IEEE Global Telecommunications Conference.［s.l.］：IEEE，2010.

［6］WOLNIANSKY P W，F(xiàn)OSCHINI G J，GOLDEN G D，et al.V－BLAST：An architecture for realizing very high data rates over the rich－scattering wireless channel［C］／／in Proc URSI International Symposium on Signals，Systems and Electronics（ISSSE 98）.Atlanta：IEEE，1998：295－300.

［7］WIESEL A，MESTRE X，PAGES A，et al.Efficient Implementation of sphere demodulation［J］.IEEE Workshop on Signal Processing Advances in Wireless Communications，2003，4：36－40.

［8］DAI Y M，YAN Z Y.Memory－constrained tree search detection and new ordering schemes［J］.IEEE Journal of Selected Topics in Signal Processing，2009，3（6）：1026－1037.

［9］WU X B，DAI Y M，YAN Z Y，et al.Improving the reliability of the k－best algorithm for MIMO detection with ordering［C］／／Wireless and Optical Communications Conference.［s.l.］：IEEE，2010.

［10］WU X B，DAI Y M，WANG Y，et al.Efficient ordering schemes for high－throughput MIMO detectors［J］.Journal of Signal Processing Systems，2010，64（1）：61－74.

［11］SHAYEGH F，SOLEYMANI M R.Low complexity implementations of sphere decoding for MIMO detection［C］／／Electrical and Computer Engineering. Canada：IEEE，2008：821－825.

［12］李慶坤，馬紅光，李 正，等.一種低復雜度的MIMO預處理球形譯碼算法［J］.信號處理，2009，25（12）：1867－1870.

［13］TRUJILLO R A，GARCIA V M，VIDAL A M，et al.A gradient－based ordering for MIMO decoding［C］／／Signal Processing and Information Technology.［s.l.］：IEEE，2009.