基于Max-Log更新的馬爾科夫鏈蒙特卡洛MIMO檢測增強算法

胡劍浩，周將運，何帥寧，陳杰男

?

基于Max-Log更新的馬爾科夫鏈蒙特卡洛MIMO檢測增強算法

胡劍浩，周將運，何帥寧，陳杰男

(電子科技大學通信抗干擾國家級重點實驗室 成都 611731)

針對傳統(tǒng)的馬爾科夫鏈蒙特卡洛(MCMC)算法，提出了一種基于Max-Log更新的MCMC-MIMO檢測算法。該算法采用了基于Max-Log更新的采樣，可以有效產(chǎn)生收斂于后驗概率(APP)分布的比特樣本列表集合，同時可避免計算傳統(tǒng)MCMC算法中的每比特概率分布。但是該檢測算法在高信噪比下，采樣過程會陷入鎖死到局部最優(yōu)態(tài)。在此基礎(chǔ)上，提出了3個增強技術(shù)：1) 抖動處理，對給定置信區(qū)間內(nèi)的更新進行抖動處理；2) 條件下重新初始化，對處在潛在鎖死態(tài)的采樣序列進行重新初始化；3) 修剪飽和處理，利用球形譯碼算法中的修剪飽和技術(shù)來處理MIMO檢測輸出的對數(shù)似然信息(LLR)。仿真結(jié)果顯示，基于Max-Log更新的MCMC增強算法能有效地解決陷入鎖死的問題，從而提高系統(tǒng)性能并降低系統(tǒng)的計算復(fù)雜度。在復(fù)雜度為MMSE-PIC檢測算法的90%的基礎(chǔ)上，性能提高了2 dB。

抖動處理; 修剪飽和; Max-Log更新; MCMC; 條件下重新初始化

MIMO技術(shù)能有效地提高系統(tǒng)容量和頻譜效率，已經(jīng)被3GPP LTE/LTE-Advanced和IEEE 802.16e/ 802.16m WiMax等無線協(xié)議采納?；谲涊斎胲涊敵?soft input soft output，SISO)模型的迭代檢測譯碼被認為能夠逼近MIMO信道的香農(nóng)限[1]，因此學術(shù)界和工業(yè)界提出了多種迭代檢測算法。文獻[2]提出了基于MMSE- PIC(parallel interference cancellation)的線性檢測算法，該算法利用譯碼器的外信息計算輸入的軟符號值，進行干擾消除，最后利用MMSE進行均衡處理。由于MMSE-PIC算法需要計算矩陣乘法和求逆，其實現(xiàn)復(fù)雜度依然較高且性能相對較差。LSD(list sphere decoder)算法[1]利用樹搜索中的深度優(yōu)先搜索產(chǎn)生一個列表集合來計算對數(shù)似然信息，但是LSD算法隨著信道和噪聲干擾的不同存在著不同的算法復(fù)雜度。文獻[3]中的STS(single tree search)算法在優(yōu)化LSD性能的同時降低了復(fù)雜度，每個節(jié)點最多被訪問一次，但是STS算法依然采用深度優(yōu)先搜索，存在著可變的復(fù)雜度和吞吐率。FSD(fixed sphere decoder)算法[4]利用寬度優(yōu)先搜索產(chǎn)生列表集合，其計算復(fù)雜度固定，但是FSD算法很難得到軟輸出似然值。且由于LSD、STS和FSD算法都是基于樹搜索，需要對信道矩陣進行QR分解，進一步增加了檢測復(fù)雜度。

文獻[5-11]提出了基于馬爾科夫鏈蒙特卡洛模型的MIMO檢測算法并進行了高速VLSI實現(xiàn)[11]，該算法利用蒙特卡洛積分簡化LLR的計算，其中符號樣本序列(或者比特樣本序列)通過Gibbs采樣得到。傳統(tǒng)的MCMC檢測算法具有如下優(yōu)勢：1) 復(fù)雜度低。由于Gibbs采樣是一種隨機搜索樣本序列的方法，使得該算法復(fù)雜度只與樣本集合大小有關(guān)，且不隨發(fā)射天線數(shù)和調(diào)制階數(shù)呈指數(shù)增長。2) 收斂速度快。利用Gibbs采樣可以使得MCMC的接受率等于1，能夠提高馬氏鏈的跳轉(zhuǎn)效率和收斂速度。3) 可并行處理。Gibbs更新過程和LLR的計算都可以并行處理。傳統(tǒng)MCMC算法也存在如下問題：1) Gibbs采樣過程是基于概率域的逐比特(逐符號)更新，需要計算每比特(每符號)的概率，然后根據(jù)概率分布進行采樣更新，該過程涉及到非線性指數(shù)運算，復(fù)雜度較高。2) Gibbs采樣在高信噪比(SNR)會陷入“鎖死”到一個局部最優(yōu)態(tài)[5-6,9]，使得采樣的狀態(tài)數(shù)減少，從而導致計算LLR時出現(xiàn)較大的誤差。目前，針對問題2)，文獻[5-6]提出增大溫度系數(shù)(temperature factor)和增加并行度的方法，但是仿真表明這兩個技術(shù)只能降低陷入鎖死的概率，而不能從根本上解決“鎖死”問題；文獻[9]利用ZF、MMSE進行預(yù)處理，增加了運算復(fù)雜度，并且無法在高SNR下消除誤碼平層[8]；在此基礎(chǔ)上，文獻[8]從根本上分析了進入“鎖死”狀態(tài)的原因，并且給出C-MCMC(constraint MCMC)的解決技術(shù)，但是C-MCMC需要自適應(yīng)地選擇ZF或SD作為預(yù)處理，增加了系統(tǒng)的復(fù)雜度。

本文提出了一種基于Max-Log更新的馬爾科夫鏈蒙特卡洛MIMO檢測算法。其原理是利用Max-Log采樣獲得樣本列表集合，然后利用該列表集合計算LLR。該采樣更新過程直接在對數(shù)域進行，因而不必計算傳統(tǒng)MCMC算法中的概率分布，從而避免了非線性指數(shù)計算，降低了計算復(fù)雜度，有效地解決了問題1)。但是，基于Max-Log更新的MCMC-MIMO檢測算法同樣面臨“死鎖”問題，導致在高SNR出現(xiàn)誤碼平層。針對該問題本文還提出3個增強技術(shù)：1) 抖動處理技術(shù)，對置信度為50%的置信區(qū)間內(nèi)的比特更新采用隨機更新的方式，該技術(shù)可為馬氏鏈提供一定的可能性跳出局部最優(yōu)態(tài)，從而保證馬氏鏈在較長的轉(zhuǎn)移時間內(nèi)不陷入鎖死到局部最優(yōu)態(tài)。2) 重新初始化技術(shù)，一旦發(fā)現(xiàn)馬氏鏈陷入鎖死到局部最優(yōu)態(tài)，就立即啟動該技術(shù)，以全新的初始態(tài)進行狀態(tài)轉(zhuǎn)移。3) 修剪飽和處理技術(shù)，利用球形譯碼算法中的修剪飽和技術(shù)處理MIMO檢測輸出的對數(shù)似然信息(LLR)，避免譯碼器因過大LLR值而無法正常工作于糾錯狀態(tài)，該技術(shù)一方面可以提升譯碼性能，另一方面也為后續(xù)的迭代檢測提供更加正確的先驗信息，從而幫助Gibbs采樣器采得更有效的樣本。上述3個技術(shù)可以在不增加硬件開銷的基礎(chǔ)上從根本上解決陷入鎖死問題，在有限迭代采樣周期內(nèi)搜索到更多歐氏距離較小的樣本，從而得到更加精確的LLR估計值，提升檢測性能。結(jié)果表明，基于Max-Log更新的MCMC-MIMO檢測增強算法在復(fù)雜度為MMSE-PIC檢測算法的90%的基礎(chǔ)上，性能提高了2 dB。

1 系統(tǒng)模型

圖1給出了空間復(fù)用MIMO迭代檢測的系統(tǒng)模型，其中發(fā)射天線數(shù)為，接收天線數(shù)為，且有。相應(yīng)的頻域MIMO系統(tǒng)模型為：

接收端采用了迭代檢測譯碼算法，主要由SISO檢測器和信道譯碼器模塊構(gòu)成。首先，SISO檢測器利用接受向量和先驗信息得到似然信息，在似然信息中減去先驗信息后作為外信息，即有。檢測器的外信息經(jīng)過解交織后作為信道譯碼器的先驗信息，譯碼輸出的似然信息減去先驗信息得到譯碼器外信息，即有。譯碼器的外信息經(jīng)過交織后作為檢測器的先驗信息。

SISO檢測器利用式(2)計算每比特的對數(shù)似然信息：

利用邊緣概率函數(shù)定義可知：

(3)

因此，式(2)的每比特似然信息可以表示為：

利用MAX-LOG-MAP算法[1]，式(6)可簡化為：

從式(7)(或者式(6))可以看出，計算每比特的外信息需要評估個比特向量，其復(fù)雜度隨著調(diào)制階數(shù)和發(fā)射天線數(shù)呈指數(shù)增長。因此，需要解決如何在避免這種窮舉搜索的同時得到較好性能的問題。

2 基于Max-Log更新的MCMC迭代檢測算法

為了降低式(7)計算LLR的復(fù)雜度，本文利用基于Max-Log更新的采樣得到服從式(3)右端分布的比特向量列表，該列表能以極大概率包含式(7)右端的兩項，分別被定義為和。和LSD類似，LLR的計算可以表示為：

(8)

為了推導本文的基于Max-Log更新的采樣算法，定義每比特的條件對數(shù)似然比為：

(10)

(11)

式(12)采樣更新過程可概括為式(13)，即Max-Log更新的基本原理:

(13)

結(jié)合式(8)、式(11)和式(12)，得到了本文提出的MCMC整體算法，如算法1所示。

算法1 MCMC MIMO Detection based on Max-Log Updating

For=1 to

// ------------Gibbs sampler-----------------

// ------------LLR Calculator-----------------

Compute

Compute

End for;

End for;

其中計算LLR時采取了和文獻[10]一樣的處理，即在計算第比特的外信息時，將當前時刻采樣得到的比特向量和翻轉(zhuǎn)第比特的比特向量用作計算和。最后對外信息進行處理。

3 基于Max-Log更新的MCMC算法的增強技術(shù)

基于Max-Log更新的MCMC算法也存在高信噪比下陷入鎖死的問題，當馬氏鏈轉(zhuǎn)移到狀態(tài)時，若有：1)；2)或或，但成立，，其中表示僅改變第個比特元素后的向量，那么狀態(tài)對應(yīng)的條件對數(shù)比將大于，此時馬氏鏈將長時間陷入鎖死到狀態(tài)，稱這樣的狀態(tài)為局部最優(yōu)態(tài)。例如，對于一個4-QAM調(diào)制的的MIMO系統(tǒng)，當發(fā)送比特向量為，那么便是全局最優(yōu)態(tài)。假設(shè)在狀態(tài)轉(zhuǎn)移過程中，系統(tǒng)到達了一個局部最優(yōu)態(tài)，即該狀態(tài)對應(yīng)的條件對數(shù)似然比比它的所有臨近態(tài)，，，都大。此時，系統(tǒng)將陷入鎖死到該局部最優(yōu)態(tài)，使得采樣的狀態(tài)數(shù)減少，從而導致計算LLR時出現(xiàn)較大的誤差。為了解決陷入鎖死問題，本文提出了如下3個增強技術(shù)。

3.1 抖動處理(biased-MCMC)

基于Max-Log更新的MCMC算法類似于爬山算法(hill climbing)，其實質(zhì)是一種簡單的貪心搜索算法，但是會陷入鎖死到局部最優(yōu)態(tài)。在此基礎(chǔ)上，本文提出了一種類似于模擬退火(simulated annealing)的抖動處理技術(shù)。將一個給定的抖動區(qū)間作為置信區(qū)間，在區(qū)間外以概率1接收更新，在區(qū)間內(nèi)認為其置信水平為50%，即對于處于區(qū)間內(nèi)的比特進行隨機采樣更新。此時，式(12)的比特更新過程變?yōu)椋?/p>

該技術(shù)可為馬氏鏈提供一定的可能性跳出局部最優(yōu)態(tài)，從而保證馬氏鏈在較長的轉(zhuǎn)移時間內(nèi)不陷入鎖死到局部最優(yōu)態(tài)。

3.2 條件下重新初始化(reinitialized-MCMC)

重新初始化可進一步提高系統(tǒng)性能，并且?guī)缀醪辉黾铀惴ㄩ_銷，僅僅需要一個1bit的狀態(tài)標志來識別是否達到潛在鎖死態(tài)。

3.3 修剪飽和處理(clipped-MCMC)

在LSD算法中，LLR-clipping技術(shù)能在復(fù)雜度和性能之間進行折中。由于較大的LLR值會使得譯碼器無法正常工作于糾錯狀態(tài)，本文將修剪飽和處理(clipping)技術(shù)運用到MCMC算法中對輸出外信息進行修剪飽和處理，即：

該技術(shù)一方面可以提升譯碼性能，另一方面也為后續(xù)的迭代檢測提供更加正確的先驗信息，從而幫助Gibbs采樣器采得更有效的樣本。

4 性能與復(fù)雜度仿真

4.1 性能仿真

本文的仿真研究都是基于128個子載波，收發(fā)天線數(shù)均為4的OFDM-MIMO系統(tǒng)模型，其編碼器采用碼率為1/2的卷積碼[133 171]，調(diào)制方式為16QAM。接收端采用迭代檢測譯碼算法，其中譯碼器為BCJR譯碼，信道模型為準靜態(tài)瑞利衰落信道。

圖2給出了傳統(tǒng)MCMC算法的仿真性能，其中serial表示串行深度為50的Gibbs采樣，parallel表示5路并行深度為10的Gibbs采樣，表示迭代次數(shù)。從圖中可以看出，雖然并行MCMC能提高系統(tǒng)性能，但是即在高信噪比下存在誤碼平層。

不同抖動區(qū)間下對基于Max-Log更新的MCMC檢測算法進行了仿真，如圖3所示。仿真結(jié)果顯示，抖動處理能有效地解決陷入鎖死問題，從而提高系統(tǒng)的檢測性能。但是抖動區(qū)間的大小會影響MCMC算法的性能：區(qū)間太大，Gibbs采樣過程跳轉(zhuǎn)更劇烈，類似于隨機游走，性能會降低；區(qū)間太小，采樣過程會出現(xiàn)原地踏步，拒絕大量的跳轉(zhuǎn)，同樣會降低性能。從圖3可以得到最佳的抖動參數(shù)為0.15。另外，從圖2和圖3的仿真結(jié)果對比發(fā)現(xiàn)，相比傳統(tǒng)MCMC算法，最佳抖動處理后的Max-Log更新的MCMC算法可獲得超過5 dB的性能增益。

經(jīng)過3種增強技術(shù)處理的MCMC檢測性能仿真如圖4所示。仿真結(jié)果顯示重新初始化在抖動處理的基礎(chǔ)上進一步帶來了1～2 dB的性能增益，修剪飽和處理在前兩者的基礎(chǔ)上繼續(xù)提高了0.2 dB的性能。圖4的結(jié)果還表明了第2次迭代能提高6 dB左右的性能，而后續(xù)的迭代增益較小?；诖?，圖5給出前兩次迭代的MMSE-wPIC算法[2]，STS算法[3]和本文的MCMC增強算法的性能仿真結(jié)果。從圖中可以看出，當時，相比MMSE-PIC算法，MCMC增強算法有1～2 dB的性能增益，當時，相比準MAP算法STS，MCMC增強算法在第2次迭代只有不到1 dB的性能損失。

4.2 復(fù)雜度仿真

本文利用基于FPGA面積開銷的運算器數(shù)目來評估MMSE-PIC算法、傳統(tǒng)MCMC算法和本文的MCMC增強算法的復(fù)雜度。由于STS算法的復(fù)雜度隨著信道和噪聲干擾的不同存在著不同的算法復(fù)雜度，且文獻[14]給出其復(fù)雜度遠大于線性檢測器，本文并未對其進行分析。和文獻[13]一樣，假設(shè)比較器為單位復(fù)雜度，加法器為比較器的2倍開銷，乘法器的復(fù)雜度為加法器的10倍，除法器和平方根分別為乘法器的4.5倍和3.8倍。復(fù)數(shù)乘法器的運算復(fù)雜度為4個實數(shù)乘法器和2個加法器的開銷之和。此外，根據(jù)文獻[13]，由于是由星座點向量構(gòu)成，式中乘法、、可通過移位加(shift-add)實現(xiàn)。表1給出了MMSE-PIC算法、傳統(tǒng)MCMC算法和本文的MCMC增強算法的運算復(fù)雜度，參數(shù)與系統(tǒng)模型參數(shù)一致，表示發(fā)射天線數(shù)，表示接收天線數(shù)，為調(diào)制階數(shù)，為MCMC采樣列表大小，最后的總體復(fù)雜度是當，，，時的運算復(fù)雜度開銷。從表中可以看出，MMSE-PIC算法和MCMC算法的復(fù)雜度都只是發(fā)射天線數(shù)和調(diào)制階數(shù)呈多項式增長。

表1 MMSE-PIC和MCMC運算復(fù)雜度

5 結(jié) 束 語

本文提出了基于Max-Log更新的MCMC檢測算法。該算法由Gibbs采樣和LLR計算構(gòu)成。首先，利用基于Max-Log更新的采樣得到服從所需后驗概率分布的比特向量列表，再利用MAX-LOG-MAP算法計算外信息。該MCMC檢測算法具備復(fù)雜度低和可并行處理等優(yōu)勢，但是在高信噪比存在陷入鎖死的問題，使得采樣狀態(tài)數(shù)減少，從而導致計算LLR時出現(xiàn)較大的誤差?；诖?，本文提出了3個增強技術(shù)：抖動處理、條件下重新初始化和修剪飽和處理。仿真結(jié)果表明：基于Max-Log更新的MCMC增強算法能有效提高系統(tǒng)的檢測性能，并能降低計算復(fù)雜度。

[1] HOCHWALD B M, BRINK S. Achieving near-capacity on a multiple-antenna channel[J]. IEEE Transactions on Communications, 2003, 51: 389-399.

[2] STUDER C, FATEH S, SEETHALER D. ASIC implementation of soft-input soft-output MIMO detection using parallel interference cancellation[J]. IEEE Journal of Solid-State Circuits, 2011, 46: 1754-1765.

[3] ZHENG C, CHU X, MCALLISTER J, et al. Real-valued fixed-complexity sphere decoder for high dimensional QAM-MIMO systems[J]. IEEE Transactions on Signal Processing, 2011, 59(9): 4493-4499.

[4] STUDER C, B?LCSKEI H. Soft-input soft-output single tree-search sphere decoding[J]. IEEE Transactions on Information Theory, 2010, 56: 4827-4842.

[5] FARHANG-BOROUJENY B, ZHU H D, SHI Z N. Markov chain Monte Carlo algorithms for CDMA and MIMO communication systems[J]. IEEE Transactions on Signal Processing, 2006, 54: 1896-1909.

[6] HASSIBI B, HANSEN M, DIMASKIS A G, et al. Optimized Markov chain Monte Carlo for signal detection in MIMO systems: an analysis of the stationary distribution and mixing time[J]. IEEE Transactions on Signal Processing, 2014, 62: 4436-4450.

[7] DATTA T, KUMAR N A, CHOCKALINGAM A, et al. A novel Monte-Carlo-sampling-based receiver for large-scale uplink multiuser MIMO systems[J]. IEEE Transactions on Vehicular Technology, 2013, 62(7): 3019-3038.

[8] AKOUM S, PENG R H, CHEN R R, et al. Soft detection using constrained Markov chain Monte Carlo simulations[C]//Proceeding of IEEE International Conference on Communications. Dresden, Germany: IEEE, 2009.

[9] MAO X H, AMINI P, FARHANG-BOROUJENY B. Markov chain Monte Carlo MIMO detection methods for high signal-to-noise ratio regimes[C]//Proceeding of GlobCom. Washington, DC: [s.n.], 2007.

[10] CHEN R R, PENG R H, ASHIKHMIN A, et al. Approaching MIMO capacity using bitwise Markov chain Monte Carlo detection[J]. IEEE Transactions on Communications, 2010, 58: 423-428.

[11] DEIDERSEN U, AURAS D, ASCHEID G. A parallel VLSI architecture for markov chain Monte Carlo based MIMO detection[C]//Proceedings of the 23rd ACM International Conference on Great Lakes Symposium on VLSI. [S.l.]: ACM, 2013: 167-172.

[12] MYLLYL? M, ANTIKAINEN J, JUNTTI M, et L. The effect of LLR clipping to the complexity of list sphere detector algorithms[C]//Proceeding of 41st Asilomar Conference on Signals, Systems, and Computers. Pacific Grove, CA: [s.n.], 2007. 1559-1563.

[13] AMIRI K, RADOSAVLJEVIC P, CAVALLARO J R. Architecture and algorithm for a stochastic soft-output MIMO detector[C]//Proceeding of the 41st Asilomar Conference on Signals, Systems and Computers. Pacific Grove, CA, [s.n.], 2007.

[14] SEETHALER D, JALDEN J, STUDER C, et al. On the complexity distribution of sphere decoding[J]. IEEE Transaction on Information Theory, 2011, 57: 5754-5768.

編 輯 稅 紅

An Enhanced MCMC Algorithm for MIMO Systems Based on Max-Log Updating

HU Jian-hao, ZHOU Jiang-yun, HE Shuai-ning, and CHEN Jie-nan

(National Key Lab of Science and Technology on Communications, University of Electronic Science and Technology of China Chengdu 611731)

In this paper, an enhanced Markov chain Monte Carlo (MCMC) algorithm based on max-log updating is proposed for multiple input multiple output (MIMO) system. The max-log updating can generate the list vectors to simply the complexity of the calculation of the extrinsic log-likelihood ratios (LLRs) efficiently. Meanwhile, it avoids calculating probability distribution per bit in conventional MCMC. However, the proposed MCMC detection suffers from the so called "stalling" problem, where the Markov chain may be trapped into local optimal state. Thus, we also propose three enhancement technologies: 1) biased processing, i.e., updating randomly in a given biased interval; 2) reinitialized processing, i.e., reinitialize the Markov chain under the sub-optimal states; 3) clipped processing, i.e., reprocessing the LLR with clipping. Simulation results show that the proposed algorithm can remedy the “stalling” problem efficiently with reduced complexity, and can achieve 2 dB performance gains with 10% less complexity than MMSE-PIC.

biased processing; LLR clipping; Max-Log updating; MCMC; reinitialized processing

TN92

A

10.3969/j.issn.1001-0548.2017.01.001

2015-03-23；

2015-11-20

國家自然科學基金(6150010678, 61371104)

胡劍浩(1971-)，男，博士，教授，主要從事無線通信技術(shù)和通信集成電路技術(shù)方面的研究.