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

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

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

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

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

1 基于ADMM的LPDC碼懲罰譯碼

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

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

(1)

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

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

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

(2)

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

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

(3)

2.2 早停止方法設(shè)計

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

2.3 計算復(fù)雜度分析

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

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

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

3 仿真實驗

以IEEE 802.16e標準中碼率為0.5的(576， 288)LDPC碼C1和碼率為0.75的 (1 152， 288)LDPC碼C2為例，從譯碼平均迭代次數(shù)和譯碼性能(誤幀率)兩個方面，對所設(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ù)選擇

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

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

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

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

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

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

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

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

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

4 結(jié) 束 語

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