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

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

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

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

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

1 基于ADMM的LPDC碼懲罰譯碼

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

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

(1)

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

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

2.1 碼字所滿足校驗(yàn)約束個(gè)數(shù)分析

(2)

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

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

(3)

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

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

3.1 參數(shù)選擇

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 束 語

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