李 蕓，李式巨，易志強(qiáng)，高明煜

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

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

李 蕓1，2，李式巨1，易志強(qiáng)2，高明煜2

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

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

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

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

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

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

1 系統(tǒng)模型

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

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

MIMO迭代接收機(jī)模型如圖1.

圖1 MIMO迭代接收機(jī)模型

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

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

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

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

2 MCMC檢測算法

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

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

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

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

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

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

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

Gibbs采樣過程如下:

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

2)for n=－Nb+1 to Ns

其中前Nb個(gè)采樣為burn-in過程，用于使馬爾可夫鏈?zhǔn)諗坑谄胶夥植?，用后面Ns次迭代的采樣值進(jìn)行LLR計(jì)算.

3 MCMC算法改進(jìn)

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

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

后驗(yàn)方差定義為

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

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

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

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

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

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

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

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

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

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

Step 6:由獲得的采樣值，進(jìn)行LLR計(jì)算.

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

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

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

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

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

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

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

圖2 BER性能比較

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

圖3 采樣點(diǎn)個(gè)數(shù)對性能的影響

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

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

圖4 L取值對性能的影響

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

5 結(jié)論

MCMC算法是一種有效的檢測方法，針對傳統(tǒng)MCMC算法高信噪比時(shí)的陷入問題，以及馬爾可夫鏈要經(jīng)過相當(dāng)次數(shù)的采樣后才能趨于平衡分布，本文提出了一種改進(jìn)的MCMC算法.在改進(jìn)算法中，首先基于MMSE算法得到采樣初值，提高蒙特卡羅綜合的精度，使馬爾可夫鏈?zhǔn)諗扛杆伲瑥亩鴾p少采樣點(diǎn)個(gè)數(shù)，降低算法復(fù)雜度;其次對陷入狀態(tài)下的采樣序列，隨機(jī)分散重復(fù)采樣序列，增加有效的采樣狀態(tài)數(shù)，使其跳出陷入狀態(tài).仿真結(jié)果說明，改進(jìn)MCMC算法較大幅度地改善了系統(tǒng)性能，在相同信噪比、達(dá)到同樣誤碼率情況下，改進(jìn)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ìn)［J］.北方工業(yè)大學(xué)學(xué)報(bào)，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é)基金資助項(xiàng)目(61172132);浙江省教育

廳科研計(jì)劃資助項(xiàng)目(KYF045609004).

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

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

李 蕓，liyunr@163.com.

(編輯 張 宏)