LDPC碼ADMM懲罰譯碼的早停止方法

王 彪，慕建君，焦曉鵬，王鐘斐

(1. 西安電子科技大學 計算機學院，陜西 西安 710071；2. 寶雞文理學院 數(shù)學與信息科學學院，陜西 寶雞 721013)

近年來，具有逼近香農(nóng)限良好性能的低密度校驗(Low-Density Parity-Check，LDPC)碼受到了研究學者的普遍關注[1-2]． 線性規(guī)劃(Linear Programming，LP)譯碼是LDPC碼的一種重要譯碼方法，但其譯碼復雜度較高[3]． 文獻[4]提出了一種基于交替方向乘子法(Alternating Direction Method of Multipliers，ADMM)的LP譯碼方法，該方法能夠降低LDPC碼LP譯碼方法的譯碼復雜度[4]． 為了進一步降低LDPC碼ADMM譯碼的復雜度，許多學者進行了以下幾個方面的研究:簡化譯碼過程，主要包括利用割查找算法(Cut Search Algorithm，CSA)來設計低復雜度的歐幾里德投影算法[5]，提出用單純形(Simplex)替代校驗多胞體(Check Polytope)的歐幾里德投影算法[6]，直接降低歐幾里德投影的次數(shù)[7]，基于查表法提出簡化的歐幾里德投影算法[8]，以及設計不需排序的迭代歐幾里德投影算法[9];通過改變消息在變量節(jié)點和校驗節(jié)點間的傳遞方式，設計高效的消息調度策略[10];利用多核處理器的結構特征優(yōu)化ADMM譯碼算法的軟件實現(xiàn)[11];通過在LP模型目標函數(shù)中加入罰函數(shù)[12]、加權罰函數(shù)[13]和改進罰函數(shù)[14]來設計ADMM懲罰譯碼方法，此類方法不僅可以降低ADMM譯碼復雜度，同時能夠改善LDPC碼的譯碼性能．

早停止(Early Termination，ET)方法也是一種能夠降低LDPC碼譯碼復雜度的有效方法． 當譯出正確碼字或達到最大迭代次數(shù)時，LDPC碼譯碼器會停止譯碼[15]． 如果譯碼器能夠在早期階段(即不達到最大譯碼迭代次數(shù)時)停止譯碼，即判斷出正確碼字或錯誤碼字，那么就可以節(jié)省不必要的譯碼迭代，從而降低譯碼的平均迭代次數(shù)． 目前，針對LDPC碼置信傳播(Belief Propagation，BP)譯碼方法，基于奇偶校驗計算的早停止方法[16]和基于后驗對數(shù)似然比的早停止方法[17]均能夠有效降低LDPC碼的譯碼復雜度．

關于LDPC碼ADMM懲罰譯碼算法的研究，學者們目前主要集中在簡化歐幾里德投影、設計合適的調度策略及優(yōu)化實現(xiàn)方法等方面來降低其譯碼復雜度，還未深入開展針對該算法的早停止方法研究． 現(xiàn)有ADMM懲罰譯碼的停止方法只有兩種: 標準的ε規(guī)則[4]和HxT=0 的早停止方法[5]． 標準的ε規(guī)則將ADMM譯碼中每次迭代的主殘差(Primal Residual)和對偶殘差(Dual Residual)分別與ε(ε>0) 比較，若這兩個殘差值都小于ε，則譯碼迭代停止; 而HxT=0 的早停止方法主要依據(jù)所有校驗方程HxT=0 是否滿足來確定譯碼停止． 通過計算LDPC碼譯碼迭代過程中碼字所滿足的校驗約束個數(shù)，設計了LDPC碼ADMM懲罰譯碼的一種早停止方法，該方法能夠在早期階段判斷出錯誤碼字而停止譯碼． 仿真結果表明，所設計的早停止方法能夠在低信噪比區(qū)域降低LDPC碼ADMM懲罰譯碼的平均迭代次數(shù)，且其譯碼性能幾乎沒有損失．

1 基于ADMM的LPDC碼懲罰譯碼

設LDPC碼C的校驗矩陣為m×n的矩陣H，其對應的Tanner圖中所有變量節(jié)點集合I= {1，2，…，n}，所有校驗節(jié)點集合J= {1，2，…，m}． 設集合Nv(i)表示與變量節(jié)點vi相關聯(lián)的所有校驗節(jié)點集合，而集合Nc(j)表示與校驗節(jié)點cj相關聯(lián)的所有變量節(jié)點集合． 令dvi= |Nv(i)|，表示變量節(jié)點vi的度數(shù)；dcj= |Nc(j)|，表示校驗節(jié)點cj的度數(shù)．

假設發(fā)送端將碼字x={xi∈{0，1}|i∈I}經(jīng)過加性高斯白噪聲(Additive White Gaussian Noise，AWGN)信道發(fā)送后，接收端接收到的序列r= {ri|i∈I}，r對應的對數(shù)似然比向量記為γ= {γi|i∈I}，其中γi= log(Pr(ri|0)/Pr(ri|1))，Pr(·)表示括號內(nèi)代表的事件發(fā)生的概率． 通過引入輔助變量zj∈Rdcj(j∈J) 可以得到LP譯碼數(shù)學模型為[4]

(1)

其中，校驗多胞體Pdcj表示所有長度為dcj且含有偶數(shù)個1的二進制向量構成的凸包，dcj×n二進制轉換矩陣Tj選出x中與第j校驗節(jié)點所關聯(lián)的dcj個分量．

2 ADMM懲罰譯碼的早停止方法

2.1 碼字所滿足校驗約束個數(shù)分析

(2)

其中，1T表示長度為m的全1行向量．

圖1 (576， 288)LDPC碼ADMM懲罰譯碼迭代時10個碼字所滿足的校驗約束個數(shù)變化規(guī)律

(3)

2.2 早停止方法設計

所設計的LDPC碼ADMM懲罰譯碼的早停止方法可以概括為:

2.3 計算復雜度分析

表1 每次迭代中3種停止方法的計算復雜度比較

表1中，“*”表示在迭代過程中文中的早停止方法在最壞情況下進行的計算復雜度分析．

由此可見，文中所設計的早停止方法的計算復雜度低于標準ε規(guī)則的計算復雜度，而該早停止方法在最壞情況下的計算復雜度略高于HxT=0 的早停止方法的計算復雜度(假設比較運算和加減法運算的計算復雜度相近)．

3 仿真實驗

以IEEE 802.16e標準中碼率為0.5的(576， 288)LDPC碼C1和碼率為0.75的 (1 152， 288)LDPC碼C2為例，從譯碼平均迭代次數(shù)和譯碼性能(誤幀率)兩個方面，對所設計的LDPC碼ADMM懲罰譯碼的早停止方法與現(xiàn)有ADMM懲罰譯碼的標準的ε規(guī)則及HxT=0 的早停止方法進行了比較．仿真實驗中，ADMM懲罰譯碼器采用l1罰函數(shù)進行譯碼，所涉及的罰參數(shù)按照文獻[12]中的方法進行優(yōu)化選擇，且最大迭代次數(shù)、譯碼容差值(Error Tolerance Value)和超松弛參數(shù)(Over Relaxation Parameter)分別取40、10-5和1.9．

3.1 參數(shù)選擇

下面給出所設計的LDPC碼ADMM懲罰譯碼的早停止方法所涉及的檢測錯誤碼字的比較閾值T、統(tǒng)計計數(shù)器Ncounter的起始迭代次數(shù)Imin及檢測錯誤碼字的起始迭代次數(shù)Idec這3個關鍵參數(shù)的選擇方法．

圖2 T變化時碼C1的譯碼平均迭代次數(shù)和誤幀率比較

首先，取Imin=15和Idec=20來研究比較閾值T的變化對譯碼效果的影響． 圖2給出了T依次取260、270和280時，碼C1采用所設計早停止方法的譯碼平均迭代次數(shù)和譯碼性能比較． 從圖2可以看出，采用3種不同T值時，在高信噪比區(qū)域的譯碼平均迭代次數(shù)大致相同，而在低信噪比區(qū)域T=280 時，譯碼的平均迭代次數(shù)最低，然而其譯碼誤幀率反而最差． 當T=260 和T=270 時的譯碼平均迭代次數(shù)基本相同，而在低信噪比區(qū)域T=270 時的誤幀率較好． 因此，選取T=270 作為所設計早停止方法的參數(shù)值．

圖3 Imin和Idec變化時碼C1的譯碼平均迭代次數(shù)和誤幀率比較

其次，取T=270來研究Imin和Idec的變化對譯碼效果的影響．針對3組不同參數(shù)值 (Imin=10，Idec=15)，(Imin=15，Idec=20) 和 (Imin=20，Idec=25)，圖3給出了碼C1采用所設計的早停止方法的ADMM懲罰譯碼時，譯碼平均迭代次數(shù)和譯碼性能比較． 由圖3可以看到，Imin和Idec的3組不同取值的譯碼平均迭代次數(shù)在高信噪比區(qū)域大致相同，而在低信噪比區(qū)域有所不同，其中取參數(shù)值 (Imin=20，Idec=25) 時譯碼的平均迭代次數(shù)最高，取參數(shù)值 (Imin=10，Idec=15) 時譯碼的平均迭代次數(shù)最低; 3組不同取值的誤幀率在高信噪比區(qū)域幾乎相同，而在低信噪比區(qū)域選取 (Imin=15，Idec=20) 的誤幀率較好． 因此，選取 (Imin=15，Idec=20) 作為所設計早停止方法的參數(shù)值．

3.2 平均迭代次數(shù)和譯碼性能比較

適當選擇所設計早停止方法的參數(shù)后，以碼C1和碼C2為例，比較了所設計的LDPC碼ADMM懲罰譯碼的早停止方法、標準的ε規(guī)則以及HxT=0 的早停止方法3種停止方法的平均迭代次數(shù)和誤幀率．

針對碼C1所設計的早停止方法取定參數(shù)T=270、Imin=15和Idec=20，圖4給出了所設計的早停止方法與標準的ε規(guī)則以及HxT=0 的早停止方法的譯碼平均迭代次數(shù)和誤幀率的比較． 從圖4看出，譯碼時利用3種停止方法的誤幀率大致相同，而其平均迭代次數(shù)則明顯不同． 在較低信噪比區(qū)域HxT=0 的早停止方法的平均迭代次數(shù)高于標準的ε規(guī)則，這是因為較低信噪比區(qū)域錯誤碼字通常較多，而HxT=0 的早停止方法需要更多的迭代次數(shù)才能判定錯誤碼字． 而所設計的早停止方法克服了HxT=0 的早停止方法的這一缺點，在較低信噪比區(qū)域可明顯降低LDPC碼譯碼的平均迭代次數(shù)，且譯碼性能幾乎沒有損失．

圖4 碼C1采用3種停止方法的譯碼平均迭代次數(shù)和誤幀率比較

圖5 碼C2采用3種停止方法的譯碼平均迭代次數(shù)和誤幀率比較

類似地，對于碼C2所設計早停止方法的參數(shù)依次取T=270，Imin=15和Idec=20．圖5給出了采用3種停止方法的譯碼平均迭代次數(shù)和誤幀率的比較．從圖5可以看出，與現(xiàn)有兩種停止方法相比較，所設計早停止方法在較低信噪比區(qū)域降低了譯碼的平均迭代次數(shù)，且譯碼性能幾乎沒有損失．

4 結 束 語

通過計算迭代譯碼中碼字所滿足的校驗約束個數(shù)，設計了一種能夠在LDPC碼ADMM懲罰譯碼早期階段檢測出錯誤碼字的早停止方法． 針對IEEE 802.16e標準中兩個典型LDPC碼的仿真實驗結果表明，與現(xiàn)有ADMM懲罰譯碼的標準的ε規(guī)則和HxT=0 的早停止方法相比較，所設計的早停止方法能夠在幾乎沒有損失譯碼性能的同時可降低LDPC碼低信噪比區(qū)域譯碼的平均迭代次數(shù)． 因此，該方法適合在噪聲較大環(huán)境下作為LDPC碼ADMM懲罰譯碼的停止方法來提高譯碼收斂速度．