MIMO系統(tǒng)的改進MCMC迭代檢測算法

李 蕓，李式巨，易志強，高明煜

（1.浙江大學(xué)信電系，310027 杭州;2.杭州電子科技大學(xué)電子信息學(xué)院，310018 杭州）

MIMO系統(tǒng)的改進MCMC迭代檢測算法

李 蕓1，2，李式巨1，易志強2，高明煜2

（1.浙江大學(xué)信電系，310027 杭州;2.杭州電子科技大學(xué)電子信息學(xué)院，310018 杭州）

由于傳統(tǒng)的馬爾可夫鏈蒙特卡羅(MCMC)方法在高信噪比或迭代過程中，容易“陷入”某一采樣狀態(tài)從而影響到檢測性能，本文提出一種改進的MCMC方法，基于最小均方誤差(MMSE)檢測算法確定采樣初值，使馬爾可夫鏈迅速收斂;對陷入狀態(tài)下的采樣序列，隨機反轉(zhuǎn)具有較大后驗方差的比特，以增加有效的采樣狀態(tài)數(shù).仿真結(jié)果表明，改進MCMC算法能改善系統(tǒng)的誤碼率(BER)性能、降低運算復(fù)雜度.

MIMO;迭代檢測;MCMC;Gibbs采樣

MIMO(Multiple-input multiple-output)技術(shù)是下一代移動通信系統(tǒng)的關(guān)鍵傳輸技術(shù)，它顯著提高了通信信道容量，但也對接收機的設(shè)計提出了挑戰(zhàn).MIMO接收機的設(shè)計主要圍繞降低處理復(fù)雜度和提高系統(tǒng)性能兩個目標(biāo)，近來研究較多的有BLAST結(jié)構(gòu)、球形譯碼(SD)技術(shù)、Turbo迭代技術(shù)等.Turbo迭代接收機被證明是逼近MIMO信道容量的有效途徑［1－2］，它采用軟輸入軟輸出(SISO)的檢測算法和SISO譯碼，并輔之以交織器，互相交換外信息.SISO檢測算法大致分為最大后驗概率(MAP)、最大似然(ML)和線性最小均方誤差(LMMSE)3種，它們的復(fù)雜度隨著發(fā)送天線的數(shù)目、信號的調(diào)制階數(shù)以及信道記憶長度的增加呈指數(shù)增長，實現(xiàn)起來異常困難.

近年來，統(tǒng)計學(xué)中的一些先進方法，如迭代的蒙特卡羅方法，被引入到無線通信系統(tǒng).它們?yōu)楦咚倏煽康耐ㄐ畔到y(tǒng)設(shè)計提供了全新的設(shè)計思路，能以較低的復(fù)雜度獲得接近理論最優(yōu)的性能.基于蒙特卡羅統(tǒng)計的MIMO信號檢測方法主要有兩種:序列蒙特卡羅(SMC:Sequential Monte Carlo)［3］和馬爾可夫鏈蒙特卡羅(MCMC:Markov Chain Monte Carol)［4－7］.前者是在線處理的方法，后者是批處理的方法.基于統(tǒng)計的檢測方法優(yōu)點是復(fù)雜度明確，只和迭代的次數(shù)和采樣點數(shù)有關(guān)，不受信道條件影響，這也是蒙特卡羅檢測方法被廣泛關(guān)注的原因.文獻(xiàn)［8］證明了在復(fù)雜度低于列表球形檢測(LSD)算法時，MCMC方法仍可獲得2 dB左右的性能增益.

傳統(tǒng)MCMC算法在信噪比較高時易出現(xiàn)“陷入”問題(stalling problem)［9］，即采樣“陷入”某一固定狀態(tài)，采樣狀態(tài)減少，從而導(dǎo)致后驗概率估計誤差.另外，初始值隨機分布的馬爾可夫鏈采樣，需要經(jīng)過足夠次數(shù)的采樣后才能趨于平衡分布.針對以上問題，本文提出了一種改進的MCMC算法，它基于MMSE算法得到采樣初始值，提高了蒙特卡羅綜合的精度，使馬爾可夫鏈?zhǔn)諗扛杆?對陷入狀態(tài)下的采樣序列，隨機反轉(zhuǎn)具有較大后驗方差的比特，能夠增加有效的采樣狀態(tài)數(shù)量，解決高信噪比時的陷入問題.仿真結(jié)果表明，該算法能提高系統(tǒng)性能、降低運算復(fù)雜度.

1 系統(tǒng)模型

假定1個有M根發(fā)送天線、N根接收天線的無線MIMO系統(tǒng)，系統(tǒng)模型可以表示為

其中x=［x1x2… xM］T為發(fā)送信號符號向量，每個符號對應(yīng)映射的比特數(shù)為Q，發(fā)送信號比特向量可以表示為x=［b1b2… bM·Q］T;y=［y1y2… yN］T為接收信號向量;H是N×M維信道傳輸矩陣;w是高斯噪聲向量，均值為零，協(xié)方差σ2wIN.

MIMO迭代接收機模型如圖1.

圖1 MIMO迭代接收機模型

迭代檢測器包括兩個模塊:SISO檢測器和一系列并行SISO前向糾錯(FEC)信道譯碼器.SISO檢測器由接收信號矢量y和前一次迭代時FEC譯碼器輸出的先驗信息產(chǎn)生符號序列的軟信息λ1.在λ1中將先驗信息去除，得到的剩余信息λ相對信道譯碼器是新(外)信息，經(jīng)過解交織器，輸入到譯碼器.同樣，F(xiàn)EC譯碼器輸出軟信息λ2也要去除每個譯碼器輸入軟信息，將剩余的新(外)信息λ提供給檢測器做為下次檢測的先驗信息.

二進制數(shù)據(jù)取值為{－1，+1}，SISO檢測器計算各比特的外信息，以對數(shù)似然比(LLR)的形式表示為

式(2)由標(biāo)準(zhǔn) turbo譯碼算法得到，例如BCJR算法.

其中 b－k=［b1… bk－1bk+1… bM·Q］T，式(3)需要計算所有可能的b－k，它可能的組合個數(shù)按M·Q的指數(shù)增長，可以采用蒙特卡羅統(tǒng)計方法來避免上述不可能實現(xiàn)的復(fù)雜運算.

2 MCMC檢測算法

MCMC算法通過統(tǒng)計抽樣獲得發(fā)射比特列表，并用統(tǒng)計的方法估計各比特的后驗概率，它的性能和運算量取決于采樣點數(shù)和迭代次數(shù)，而與待檢測變量的維數(shù)無關(guān).MCMC算法的基本思想是構(gòu)造1個具有任意初值的馬爾可夫鏈，其平衡分布即為目標(biāo)分布，利用目標(biāo)分布的樣本進行統(tǒng)計推斷.

考慮1個關(guān)于隨機變量x的函數(shù)h(x)的加權(quán)平均值問題，給定加權(quán)函數(shù)f(x)，則

根據(jù)蒙特卡羅積分原理［11］，可以通過對經(jīng)驗均值的估計來估計上式，即

其中xn是f(x)的采樣點.

為了減少采樣點數(shù)Ns，由重要抽樣原理，只取h(x)f(x)值比較重要的采樣點，可以得到［5］

將h(x)=P(bk=+1|y，b－k，λ)和f(x)=P(b－k|y，λ)代入上式，并由貝葉斯定理有

同樣可以得到 P(bk=－1|y，λ)，代入式(1)有

Gibbs采樣過程如下:

1)隨機產(chǎn)生初始采樣序列x(－Nb).

2)for n=－Nb+1 to Ns

其中前Nb個采樣為burn-in過程，用于使馬爾可夫鏈?zhǔn)諗坑谄胶夥植迹煤竺鍺s次迭代的采樣值進行LLR計算.

3 MCMC算法改進

傳統(tǒng)算法中，Gibbs采樣初始值是隨機產(chǎn)生的，需要經(jīng)過Nb個采樣才能收斂至平衡分布，考慮有效的采樣初值設(shè)計方法，結(jié)合MMSE檢測算法，使馬爾可夫鏈迅速收斂，減少采樣點個數(shù)，提高采樣估計精度，降低算法復(fù)雜度.由文獻(xiàn)［12］可知，第m根發(fā)送天線的發(fā)送信號xm的MMSE檢測表示為

從Gibbs采樣過程可以看到，采樣點bk是由后驗概率 P(bk|y，b－k，λ)得到的，k=1，2，…，MQ.在高信噪比時，bk為某一值的后驗概率遠(yuǎn)遠(yuǎn)大于它取其他值的后驗概率，即采樣過程容易“陷入”某一固定狀態(tài)，這樣會產(chǎn)生很多重復(fù)的采樣，從而影響MCMC檢測的性能.本文算法在前述基礎(chǔ)上對Gibbs采樣過程進行監(jiān)測，當(dāng)發(fā)現(xiàn)某一比特連續(xù)出現(xiàn)多個相同的采樣值時，認(rèn)為采樣已經(jīng)進入“陷入”狀態(tài)，按后驗方差排序，從后驗方差較大的幾位中隨機地選擇某一位取反，對“陷入”后的采樣序列進行分散，增加有效的采樣數(shù)量，從而提高MCMC檢測算法的性能.

后驗方差定義為

由文獻(xiàn)［14］知

后驗方差反映了不同取值時后驗概率的接近程度，后驗方差大說明該比特改變的可能性大，不同取值都具有較大的后驗概率;后驗方差小則該比特改變可能性小，也就是說該比特只有某一取值具有較大的后驗概率.

若在捏提的過程中，某一段特別疼（同樣的力度與手法），中醫(yī)稱為陽性反應(yīng)點，表示這個位置對應(yīng)的臟腑可能功能失調(diào)（不一定有實質(zhì)的病變）。此處可以多提幾下，以增強刺激，加大治療作用。

為了解決“陷入”問題，將重復(fù)采樣序列中的某些比特取反，強制Gibbs采樣狀態(tài)發(fā)生變化，隨機地分散重復(fù)采樣序列，可以獲得更多的采樣狀態(tài).將后驗方差較大的比特反轉(zhuǎn)，反轉(zhuǎn)后的采樣序列仍然具有較大的后驗概率，另外，在一定范圍內(nèi)隨機選擇一些比特反轉(zhuǎn)，能夠削弱采樣序列對后驗概率的依賴.

改進MCMC檢測算法實現(xiàn)過程如下:

Step 1:設(shè)定1個陷入狀態(tài)判斷門限值L，可反轉(zhuǎn)比特數(shù)L1，要求:L1≤L.當(dāng)有L個比特采樣值相同時，認(rèn)為采樣進入陷入狀態(tài).

Step 2:結(jié)合MMSE檢測算法，由式(4)得到Gibbs采樣的初始樣值x0.

Step 3:由式(5)計算Gibbs采樣每一比特的后驗方差，對后驗方差進行排序.

Step 4:判斷是否有連續(xù)L個采樣值相同，如果沒有，n=n+1.

Step 5:后驗方差較大的L1比特為可反轉(zhuǎn)比特，等概率地選取一位進行反轉(zhuǎn)，得到新的采樣序列，將其作為下一次Gibbs采樣的初值.

Step 6:由獲得的采樣值，進行LLR計算.

考慮門限值L的設(shè)置對檢測算法性能的影響，L值越大，需反轉(zhuǎn)的比特越少，有效的采樣狀態(tài)減少，性能下降，L值較小時，性能提高，但需要付出較大運算量的代價.

改進MCMC算法結(jié)合MMSE檢測得到Gibbs采樣的初始采樣序列，可以加快馬爾可夫鏈?zhǔn)諗克俣?在采樣序列具有較大后驗概率時，隨機分散重復(fù)采樣序列能夠增加有效采樣狀態(tài)數(shù)，避免高信噪比時的陷入問題.

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

考慮1個收發(fā)天線數(shù)均為4的MIMO系統(tǒng)，調(diào)制方式采用QPSK.信道編碼采用碼率為1/2的卷積碼，生成多項式為1+D+D2和1+D2;譯碼采用BCJR譯碼方法.

仿真結(jié)果中，傳統(tǒng)的 MCMC算法簡記為MC1，改進MCMC算法的簡記為MC2.

圖2是3種不同情況下，改進MCMC算法和傳統(tǒng)算法的BER性能比較，改進MCMC算法中取L=4，可反轉(zhuǎn)比特數(shù)L1=L.第一種情況:一條馬爾科夫鏈、采樣點數(shù)40，一次迭代檢測，由于采樣點數(shù)太少，特別是高信噪比情況下重復(fù)采樣點多，系統(tǒng)性能較差，從圖中可以看到，信噪比大于6 dB時，誤碼率性能進入瓶頸狀態(tài).第二種情況:兩條并行的馬爾科夫鏈(兩個并行Gibbs采樣)，每條各采樣20個點，一次迭代檢測，由圖看到，誤碼率性能得到了提高，并行Gibbs采樣減弱了采樣序列的相關(guān)性，可以獲得更多采樣狀態(tài)，在不增加運算量的情況下改善了性能.第三種情況:兩條并行的馬爾科夫鏈，每條各采樣20個點，三次迭代檢測，迭代檢測進一步提高了系統(tǒng)性能.

圖2說明，改進的MCMC算法，由于結(jié)合了MMSE檢測原理，提高了蒙特卡羅綜合的相似度;同時，依據(jù)一定規(guī)則隨機分散采樣序列，能夠獲得更多的有效狀態(tài)，在上述三種情況下，都能提高系統(tǒng)的BER性能，在高信噪比條件下，性能改進更多.這說明改進的MCMC算法有效地改善了高信噪比時的陷入問題，結(jié)合MMSE檢測原理，加快了馬爾可夫鏈的收斂速度，提高了蒙特卡羅綜合的相似度.

圖2 BER性能比較

圖3是兩條并行的馬爾科夫鏈，采樣點個數(shù)分別為20和40，三次迭代情況下，采樣點個數(shù)對傳統(tǒng)MCMC算法及改進MCMC算法性能的影響，改進MCMC算法仍然取L=L1=4.可以看到，采樣點個數(shù)的增加，可以提高算法的精度、降低誤碼率，這和第2節(jié)的推斷相符.

圖3 采樣點個數(shù)對性能的影響

圖4是改進MCMC算法中參數(shù)L取值對性能的影響，兩條并行的馬爾科夫鏈，每條20個采樣點，三次迭代檢測.高信噪比條件下，L值越小，需反轉(zhuǎn)的比特越多，有效的采樣狀態(tài)增加，性能提高，但需要付出較大運算量的代價.低信噪比時，L值對性能影響不大.

表1列出了和圖3相同仿真條件，誤碼率達(dá)到10－4時，兩種算法在采樣點個數(shù)分別為20和40時，SNR值和總的運算次數(shù).可以看到，改進的MCMC算法在性能接近時，復(fù)雜度更低.如，改進算法在20個采樣點數(shù)情況下和傳統(tǒng)算法在40個采樣點數(shù)時都實現(xiàn)了在信噪比8 dB之前達(dá)到目標(biāo)誤碼率，而前者的復(fù)雜度近似為后者的一半左右.

圖4 L取值對性能的影響

表1 算法復(fù)雜度比較

5 結(jié)論

MCMC算法是一種有效的檢測方法，針對傳統(tǒng)MCMC算法高信噪比時的陷入問題，以及馬爾可夫鏈要經(jīng)過相當(dāng)次數(shù)的采樣后才能趨于平衡分布，本文提出了一種改進的MCMC算法.在改進算法中，首先基于MMSE算法得到采樣初值，提高蒙特卡羅綜合的精度，使馬爾可夫鏈?zhǔn)諗扛杆伲瑥亩鴾p少采樣點個數(shù)，降低算法復(fù)雜度;其次對陷入狀態(tài)下的采樣序列，隨機分散重復(fù)采樣序列，增加有效的采樣狀態(tài)數(shù)，使其跳出陷入狀態(tài).仿真結(jié)果說明，改進MCMC算法較大幅度地改善了系統(tǒng)性能，在相同信噪比、達(dá)到同樣誤碼率情況下，改進MCMC算法的復(fù)雜度顯著降低.

［1］BERROU C，JEZEQUEL M，DOUILLARD C.Multidimensional turbo codes［C］//Information Theory and Networking Workshop.Metsovo:［s.n.］，1999:27.

［2］HOCHWALD B M，BRINK S T.Achieving near-capacity on a multiple antenna channel［J］.IEEE Trans Commun，2003，51(3):389－399.

［3］BIN D，XIAODONG W，ARNAUD D.A new class of soft MIMO demodulation algorithms［J］.IEEE Signal Processing Letters，2003，51(11):2752－2763.

［4］CHEN Rong，LIU J S，WANG Xiao-dong.Convergence analyses and comparisons of Markov Chain Monte Carlo algorithms in digital communications［J］.IEEE Trans on Signal Processing，2002，50(2):255－270.

［5］FILIPPO Z M，WANG Xiaodong，GIORGIO M V.A Bayesian multiuser detection algorithm for MIMO-OFDM systems affected by multipath fading，carrier frequency offset，and phase noise ［J］.IEEE Journal on selected areas in Communications，2008，26(3):506 －516.

［6］STEPHEN A L，BEHROUZ F B.Implementation of a Markov Chain Monte Carlo based multiuser/MIMO detector［J］.IEEE Trans on Circuits and Systems，2009，56(1):246－255.

［7］CHEN Rong-rong，PENG Rong-hui，ALEXEI A，et al.Approaching MIMO capacity using bitwise Markov Chain Monte Carlo detection ［J］.IEEE Trans Commun，2010，58(2):423－428.

［8］ZHU Hai-dong，BEHROUZ F B，CHEN Rong-rong.On performance of sphere decoding and Markov Chain Monte Carlo detection methods［J］.IEEE Trans on Signal Processing，2005，12(10):669－672.

［9］BEHROUZ F B，ZHU Hai-dong，SHI Zhen-ning.Markov Chain Monte Carlo algorithms for CDMA and MIMO communication systems［J］.IEEE Trans on Signal Processing，2006，54(5):1896－1909.

［10］SPALL J C.Estimation via Markov Chain Monte Carlo［J］.IEEE Control Systems Magazine，23(2)2003:34－45.

［11］FISHMAN G.Monte Carlo:concepts，algorithms and applications［M］.New York:Springer-Verlag，1996.

［12］WANG Li，XU Lei，CHEN Sheng，et al.MMSE softinterference-cancellation aided iterative center shifting K-Best sphere detection for MIMO channels［C］//IEEE International Conference on 2008.Piscataway:IEEE，2008:3819－3823.

［13］肖珂，蘇明超，郭書軍.MIMO系統(tǒng)中檢測算法得研究與改進［J］.北方工業(yè)大學(xué)學(xué)報，2009，21(3):4－9.

［14］DANGL M A，SHI Zhen-ning，REED M C，et al.Advanced Markov Chain Monte Carlo method for iterative(Turbo)multiuser detection［C］//Proc Int Symp on Turbo Codes and Related Topics.Munich:［s.n.］，2006:1－6.

An improved MCMC iterative detection algorithm for MIMO systems

LI Yun1，2，LI Shi-ju1，YI Zhi-qiang2，GAO Ming-yu2

(1.Dept.of Information Science and Electronic Engineering，Zhejiang University，310027 Hangzhou，China;2.Dept.of Electronic Information Hangzhou Dianzi University，310018 Hangzhou，China)

Because the general Markov Chain Monte Carlo(MCMC)method is easily to get trapped in some fixed state especially in the case of high SNR condition or iteration process that leads to performance degradation，in this paper，an improved MCMC algorithm is presented.Determining the initial sample value based on MMSE principle，the Markov chain is convergent rapidly.Simulation results show that the mentioned algorithm can improve the BER performance and reduce computational complexity.

MIMO;iterative detection;MCMC;Gibbs sampler

TN911

A

0367－6234(2012)09－0096－05

2011－05－02.

國家自然科學(xué)基金資助項目(61172132);浙江省教育

廳科研計劃資助項目(KYF045609004).

李 蕓(1977—)，女，博士研究生;

李式巨(1947—)，男，教授，博士生導(dǎo)師.

李 蕓，liyunr@163.com.

(編輯 張 宏)