基于ADMM的懲罰函數(shù)構(gòu)造方法優(yōu)化

陳紫強(qiáng)，王廣耀

(桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林 541000)

基于ADMM的懲罰函數(shù)構(gòu)造方法優(yōu)化

陳紫強(qiáng)，王廣耀

(桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林 541000)

為了提升傳統(tǒng)交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)懲罰譯碼算法的誤碼性能和收斂速率，對(duì)罰函數(shù)做進(jìn)一步優(yōu)化，提出一種基于三段式罰函數(shù)的ADMM懲罰譯碼算法(Three-Segment ADMM-Penalized Decoding,TS-ADMM-PD)。通過(guò)引入過(guò)渡函數(shù)，其斜率介于前后兩段函數(shù)之間，達(dá)到折衷譯碼性能和收斂速度的目的。優(yōu)化后的罰函數(shù)在x=0和x=1附近斜率較大，以增強(qiáng)對(duì)偽碼字的懲罰力度，降低誤碼率并加快譯碼收斂；在x=0.5附近斜率較小，以便此處的變量節(jié)點(diǎn)信息進(jìn)行傳遞。仿真結(jié)果表明，相比于I-ADMM-PD算法，所提的TS-ADMM-PD算法有著更優(yōu)秀的誤碼性能和收斂速度。

LDPC碼；交替方向乘子法；懲罰函數(shù)；誤碼性能；收斂速度

0 引言

低密度奇偶校驗(yàn)(Low-Density Parity-Check,LDPC)碼是Gallager博士于1962年提出的一種線性分組碼[1]，是迄今為止發(fā)現(xiàn)的誤碼性能最接近香農(nóng)極限的碼字之一，成為繼Turbo之后信道編碼領(lǐng)域的研究熱點(diǎn)。線性規(guī)劃(Linear Programming,LP)最早由J.Feldman提出作為置信傳播(Belief Propagation,BP)譯碼的備選方案[2]，然而在實(shí)際應(yīng)用中，LP譯碼存在收斂速度慢、難以硬件實(shí)現(xiàn)等弊端。針對(duì)這一問題，國(guó)內(nèi)外研究人員展開了大量研究[3-6]。

為了解決LP譯碼算法收斂速度慢的問題，文獻(xiàn)[3-7]提出了基于ADMM的LP譯碼方案。由于ADMM技術(shù)具有分布式運(yùn)算、并行處理的特點(diǎn)[8]，從而加快譯碼收斂速率核心思想是通過(guò)引入輔助矢量z與傳輸碼字x交替更新。然而，該算法在低信噪比區(qū)域誤碼率仍然很高。為了進(jìn)一步改善低信噪比區(qū)域的誤碼性能，文獻(xiàn)[9-14]通過(guò)引入懲罰項(xiàng)，避免碼字解為偽碼字，從而降低誤碼率，但同樣造成了高信噪比區(qū)域的錯(cuò)誤平層問題。文獻(xiàn)[15]通過(guò)對(duì)罰函數(shù)進(jìn)行重構(gòu)，降低了ADMM懲罰譯碼的誤碼率，不過(guò)該算法的罰函數(shù)結(jié)構(gòu)還可以繼續(xù)完善，誤碼率有待進(jìn)一步降低。

本文針對(duì)傳統(tǒng)ADMM懲罰譯碼算法提出一種改進(jìn)方案TS-ADMM-PD。充分利用懲罰函數(shù)的結(jié)構(gòu)特點(diǎn)，對(duì)罰函數(shù)做進(jìn)一步優(yōu)化，引用過(guò)渡函數(shù)對(duì)譯碼性能和收斂速度進(jìn)行折衷。優(yōu)化后的罰函數(shù)更加細(xì)分了在不同端點(diǎn)處斜率的取值，最終所提的TS-ADMM-PD算法在僅增加少量計(jì)算復(fù)雜度的條件下，譯碼性能和收斂速度均有所改善。

1 LP譯碼

考慮長(zhǎng)度為N的二進(jìn)制LDPC碼C，校驗(yàn)矩陣為HM*N，其中M為校驗(yàn)節(jié)點(diǎn)數(shù)，N為變量節(jié)點(diǎn)數(shù)(M≤N)。令I(lǐng)=(1,2,...,N)和J=(1,2,...,M)分別代表變量節(jié)點(diǎn)集合和校驗(yàn)節(jié)點(diǎn)集合。所有的變量節(jié)點(diǎn)度數(shù)為dv，校驗(yàn)節(jié)點(diǎn)度數(shù)為dc，可用Tanner圖來(lái)表示。Hij=1表示變量節(jié)點(diǎn)vi與校驗(yàn)節(jié)點(diǎn)ci之間有一條相連的邊。Nc(j)和Nc(j)i分別表示變量節(jié)點(diǎn)中與校驗(yàn)節(jié)點(diǎn)ci相鄰的節(jié)點(diǎn)及除變量節(jié)點(diǎn)i外校驗(yàn)節(jié)點(diǎn)j的所有相鄰節(jié)點(diǎn)，Nv(i)和Nv(i)j分別表示校驗(yàn)節(jié)點(diǎn)中與變量節(jié)點(diǎn)vi相鄰的節(jié)點(diǎn)及除校驗(yàn)節(jié)點(diǎn)j外變量節(jié)點(diǎn)i的所有相鄰節(jié)點(diǎn)。

對(duì)于一給定碼C，定義其碼字多面體為碼C中所有有效碼字的凸包,記為Conv(C)。如果LDPC碼在有噪聲的信道中傳播，則LP譯碼問題可被轉(zhuǎn)化為碼字多面體上的線性規(guī)劃問題。碼字多面體的頂點(diǎn)與傳輸碼字相對(duì)應(yīng)，碼字多面體上的每一點(diǎn)都是傳輸碼字的凸組合，并且線性規(guī)劃譯碼的最優(yōu)解總是在碼字多面體的頂點(diǎn)處取得[16]。設(shè)傳輸碼字為x∈C，接收矢量為y，則LP譯碼問題可被表達(dá)為一般形式如下：

式中，γ表示對(duì)數(shù)似然比(LLR)矢量；Tj表示選出與校驗(yàn)節(jié)點(diǎn)j對(duì)應(yīng)的碼字x的分量；PPdj表示所有由長(zhǎng)度為dj且包含偶數(shù)個(gè)元素‘1’的二進(jìn)制矢量構(gòu)成的凸包，稱為檢驗(yàn)多面體。

綜上所述，線性規(guī)劃譯碼是一種基于最優(yōu)化技術(shù)的譯碼方案，主要思想是將譯碼問題轉(zhuǎn)化為數(shù)學(xué)上的整數(shù)規(guī)劃問題[17]。通過(guò)松弛約束條件，將原先難以解決的LP問題分解為小的、易于處理的簡(jiǎn)單LP問題，然后再利用最優(yōu)化理論完成整個(gè)譯碼過(guò)程[18]。不過(guò)仍然存在瀑布區(qū)臨界值較大、硬件實(shí)現(xiàn)復(fù)雜度高等問題[19]。

2 ADMM懲罰譯碼

為了改善LP譯碼在低信噪比時(shí)的誤碼性能，加快譯碼收斂，提出了基于ADMM的改進(jìn)懲罰譯碼算法(I-ADMM-PD)。該方法的主要思想為向LP譯碼的目標(biāo)函數(shù)中添加一個(gè)懲罰項(xiàng)，將譯碼問題轉(zhuǎn)化為數(shù)學(xué)上非線性非凸優(yōu)化問題，此時(shí)的目標(biāo)函數(shù)被改變?yōu)椋?/p>

基于ADMM的懲罰譯碼問題可寫為一般形式：

式中，β為懲罰系數(shù)；g(xi)為引入的懲罰函數(shù)，對(duì)譯碼錯(cuò)誤的碼字進(jìn)行懲罰。隨著迭代次數(shù)的增加，漸趨于正確譯碼。 ADMM懲罰譯碼算法過(guò)程如下：

① 對(duì)于?j∈J，構(gòu)建轉(zhuǎn)換矩陣Tj和接收矢量r的對(duì)數(shù)似然比γ；

② 設(shè)置最大解碼迭代次數(shù)Tmax為50，譯碼容差值ε為3.8×10-5；

③ 對(duì)于?j∈J，將拉格朗日乘子矢量yj中的所有元素初始化為0，將輔助矢量zj中的所有元素初始化為0.5。迭代次數(shù)k初始化為0；

由γi計(jì)算初始解矢量x0，γi為線性規(guī)劃目標(biāo)函數(shù)的系數(shù)。對(duì)于?i∈I，有

式中，xi=∏[0,1](xi)為xi在[0,1]間隔上的投影，總是選取離x=0.5最遠(yuǎn)的駐點(diǎn)；

yj+1=yj+μ(Tjx-zj)；

文獻(xiàn)[20]中定義了2個(gè)不同的懲罰函數(shù)g1(x)和g2(x)，g1(x)=-α|x-0.5|，g2(x)=-α(x-0.5)2。這里α>0為常量，取值依賴于具體的譯碼問題，應(yīng)選取能加快收斂速度的α值。

ADMM懲罰譯碼器進(jìn)行迭代譯碼的過(guò)程中，z和y的更新規(guī)律保持不變；在基于ADMM的x更新中：

通過(guò)對(duì)xi的表達(dá)式進(jìn)行求導(dǎo)，然后令其為零，得到駐點(diǎn)從而求得局部解。由函數(shù)性質(zhì)得到，懲罰函數(shù)g(x)在g1(x)(0,0.5)上單調(diào)遞增。所以如果存在多個(gè)駐點(diǎn)，采用簡(jiǎn)單的閾值總是選擇離0.5最遠(yuǎn)的那個(gè)。

①l1懲罰譯碼：采用ADMM算法，利用g1(x)=-α|x-0.5|，將譯碼問題轉(zhuǎn)換為解決以下的線性規(guī)劃問題：

目標(biāo)函數(shù)為f(x)=γTx-α‖x-0.5‖1，則其(xf)i=γi-αsgn(xi-0.5)，其中xf表示f(x)關(guān)于x的微分。令給定一個(gè)ti值，xi有2個(gè)解，總是選擇離0.5更遠(yuǎn)的那個(gè)解，取閾值ti=di/2，di為第i個(gè)變量節(jié)點(diǎn)的度數(shù)，x的分量xi的更新規(guī)律歸納如下：

②l2懲罰譯碼：采用ADMM算法，利用g2(x)=-α|x-0.5|，將譯碼問題轉(zhuǎn)換為解決以下的線性規(guī)劃問題：

3 TS-ADMM-PD算法

正如本文之前所提，要改善譯碼性能，加快譯碼收斂速度，需加大懲罰函數(shù)在x=0及x=1附近的斜率以增加對(duì)偽碼字的懲罰力度；減小在x=0.5附近的斜率以便ADMM譯碼器對(duì)變量節(jié)點(diǎn)信息進(jìn)行轉(zhuǎn)換。文獻(xiàn)[20]中給出了3種不同形式的懲罰函數(shù)，g1(x),g2(x)上文中已給出，現(xiàn)給出罰函數(shù)g3(x)=-lg(|x-0.5|)，且證明了懲罰函數(shù)為對(duì)數(shù)函數(shù)時(shí)的譯碼性能不及前2種。從3個(gè)函數(shù)曲線中可以看出，在(0,0.5)區(qū)間上，g1(x)的斜率恒定為1，g2(x)的斜率從1遞減到0，g3(x)的斜率從2lge遞增到+；在(0.5,1)區(qū)間上的斜率則恰恰相反。將g3(x)的斜率變化與g1(x)，g2(x)相對(duì)比可得到結(jié)論，懲罰函數(shù)在(0,1)區(qū)間兩端附近的點(diǎn)處斜率應(yīng)該避免取較小的值，在x=0.5附近的點(diǎn)斜率應(yīng)取較小的值。

所設(shè)計(jì)的罰函數(shù)結(jié)構(gòu)，需滿足在(0,1)區(qū)間上對(duì)稱，且斜率在區(qū)間兩端較大，在x=0.5處較小，容易聯(lián)想到構(gòu)造分段函數(shù)以盡可能滿足要求。對(duì)于g1(x)和g2(x)，文獻(xiàn)[20]將(0,0.5)之間的罰函數(shù)劃分為2個(gè)函數(shù)段，一定程度上降低了誤碼率并加快譯碼收斂。本文的設(shè)計(jì)思想是對(duì)二段分段罰函數(shù)進(jìn)行再一步的劃分以得到更優(yōu)秀的誤碼性能。

對(duì)于罰函數(shù)g1(x)，選取數(shù)a，b(0

將構(gòu)造的罰函數(shù)命名為TS-l1-PF，表示為：

結(jié)合上文中給出的xi和ti的表達(dá)式及所構(gòu)造的罰函數(shù)g(x)，得到以TS-l1-PF為罰函數(shù)ADMM懲罰譯碼的碼字x的更新規(guī)律如下：

式中，ρ為罰函數(shù)TS-l1-PF的第一、二、五、六段的懲罰系數(shù)；β為第三、四段的懲罰系數(shù)。

對(duì)于罰函數(shù)g2(x)，選取數(shù)c，d(0

將構(gòu)造的罰函數(shù)命名為TS-l2-PF，表示為：

式中，k0>1，k=2(0.5-d)，0

結(jié)合給出的xi和ti的表達(dá)式及所構(gòu)造的罰函數(shù)g(x)，得到以TS-l2-PF為罰函數(shù)ADMM懲罰譯碼的碼字x的更新規(guī)律如下：

式中，λ為罰函數(shù)TS-l2-PF第一、二、四、五段的懲罰系數(shù);β為TS-l2-PF第三段的懲罰系數(shù)。所設(shè)計(jì)的罰函數(shù)如圖1所示。

圖1 TS-l1-PF和TS-l2-PF罰函數(shù)圖像

可知，ADMM懲罰譯碼性能對(duì)罰函數(shù)的選取比較敏感，本文為了滿足預(yù)期的譯碼需求，引入大量參數(shù)來(lái)構(gòu)造罰函數(shù)。然而，如何取得這些參數(shù)的最優(yōu)解是個(gè)很棘手的問題。本文按照各參數(shù)的取值范圍構(gòu)造一個(gè)有限集合，然后依次進(jìn)行仿真比較。令

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

為了驗(yàn)證基于本文所構(gòu)造罰函數(shù)的譯碼算法的有效性，選取2種規(guī)則LDPC碼C1和C2，C1為[2640,1320]“Margulis”碼，行重為6，列重為3，碼率為0.5；C2為[999,888]高碼率“MacKay”碼，碼率為0.89。設(shè)置ADMM懲罰因子μ=5，過(guò)松弛系數(shù)ρ=1.9，譯碼容差值ε為3.8×10-5。通過(guò)仿真，對(duì)不同譯碼方法的性能和收斂速度進(jìn)行分析比較。碼C1在不同性噪比情況下，BP、LP、I-ADMM-PD、TS-ADMM-PD算法的譯碼性能比較如圖2所示。由圖2可看出，與BP算法相比，當(dāng)信噪比大于2.6 dB時(shí)，LP譯碼可以改善譯碼性能且沒有錯(cuò)誤平層，而此時(shí)BP譯碼出現(xiàn)了錯(cuò)誤平臺(tái)現(xiàn)象。相較于LP譯碼，I-ADMM-PD算法改善了低信噪比(SNR<2.4 dB)區(qū)域的譯碼性能且接近BP算法，同時(shí)在高信噪比(SNR>2.4 dB)區(qū)域也沒有發(fā)生錯(cuò)誤平層現(xiàn)象，因此性能優(yōu)于BP、LP譯碼。TS-ADMM-PD算法則在其基礎(chǔ)上進(jìn)一步降低了誤碼率。2種改進(jìn)懲罰譯碼算法中，我們發(fā)現(xiàn)TS-l2-PD具備更優(yōu)秀的糾錯(cuò)性能。 碼C2在不同性噪比條件下，LP、TS-ADMM-PD算法的譯碼性能如圖3所示。從圖3中可以看出，相較于LP譯碼，I-ADMM-PD算法改善了低信噪比(SNR<5 dB)區(qū)域的譯碼性能；然而在高信噪比(SNR>5 dB)區(qū)域，LP譯碼的誤碼率開始逐漸低于TS-ADMM-PD，此時(shí)可將懲罰項(xiàng)置0，便可實(shí)現(xiàn)LP譯碼。因此，對(duì)于高碼率的碼字，TS-ADMM-PD算法仍具備優(yōu)異的譯碼性能。

圖2 碼C1條件下的的誤碼性能比較

圖3 碼C2條件下的的誤碼性能比較

圖4 碼C1條件下的迭代次數(shù)變化曲線

碼C1取不同α值時(shí)，I-ADMM-PD與TS-ADMM-PD算法譯碼的迭代次數(shù)如圖4所示，設(shè)置最大迭代次數(shù)Tmax為1 000。在2種信噪比情況下，0.5<α<3.5時(shí)，改進(jìn)后的TS-ADMM-PD算法的譯碼迭代次數(shù)要小于I-ADMM-PD。尤其是當(dāng)α=2，信噪比為3 dB時(shí)，TS-ADMM-PD算法的迭代次數(shù)為50左右，比I-ADMM-PD算法減少了10次，譯碼收斂速度提升了近1.2倍。

5 結(jié)束語(yǔ)

針對(duì)傳統(tǒng)ADMM懲罰譯碼算法誤碼性能不理想，收斂速度慢的問題，提出了基于三段式罰函數(shù)的TS-ADMM-PD算法。在(0,a)區(qū)間兩端和(b,0.5)之間分出一段過(guò)渡函數(shù)，將誤碼率和收斂速率進(jìn)行折衷。仿真實(shí)驗(yàn)表明，對(duì)于中高碼率的碼字，與I-ADMM-PD算法相比，本文所提算法在一定信噪比區(qū)域降低了誤碼率，在特定的α范圍內(nèi)譯碼收斂速度提升近1.2倍，具有一定的工程應(yīng)用價(jià)值。

[1] GALLAGER R.Low-density Parity-check Codes[J].IRE Transaction on Information Theory,1962,8(1):21-28.

[2] FELDMAN J.Decoding Error-correcting Codes via Linear Programming[M].Massachusetts Institute of Technology,2003.

[3] DEBBABI I,GAL B L,KHOUJA N,et al.Analysis of ADMM-LP Algorithm for LDPC Decoding,a First Step to Hardware Implementation[C]∥IEEE International Conference on Electronics,Circuits,and Systems.IEEE,2015:356-359.

[4] ZHANG X,SIEGEL P H.Efficient Iterative LP Decoding of LDPC Codes with Alternating Direction Method of Multipliers[C]∥IEEE International Symposium on Information Theory Proceedings.IEEE,2013:1501-1505.

[5] WEI H,JIAO X,MU J.Reduced-complexity Linear Programming Decoding Based on ADMM for LDPC Codes[J].IEEE Communications Letters,2015,19(6):909-912.

[6] 范慶輝,慕建君,焦曉鵬,等.基于加速交替方向乘子法的LDPC碼線性規(guī)劃譯碼方法[P].陜西：CN104092468A,2014-10-08.

[7] 王勇超,白晶,杜倩.基于最小多面體模型的LDPC碼線性規(guī)劃譯碼方法[P].陜西：CN105959015A,2016-09-21.

[8] BOYD S,PARIKH N,CHU E,et al.Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers[M].Found.Trends Mach.Learn,2011:1-122.

[9] LIU X,DRAPER S C.ADMM LP Decoding of Non-binary LDPC Codes in MathbbF2m[C]∥IEEE International Symposium on Information Theory.IEEE,2014:2449-2453.

[10] JIAO X,WEI H,MU J,et al.Improved ADMM Penalized Decoder for Irregular Low-density Parity-check Codes[J].IEEE Communications Letters,2015,19(6):913-916.

[11] JIAO Xiaopeng,MU Jianjun.Lowering the Error Floor of ADMM Penalized Decoder for LDPC Codes[J].中國(guó)通信,2016(8):127-135.

[12] DEBBABI I,GAL B L,KHOUJA N,et al.Comparison of Different Schedulings for the ADMM Based LDPC Decoding[C]∥International Symposium on Turbo Codes and Iterative Information Processing.IEEE,2016:51-55.

[13] DEBBABI I,GAL B L,KHOUJA N,et al.Fast Converging ADMM-penalized Algorithm for LDPC Decoding[J].IEEE Communications Letters,2016,20(4):648-651.

[14] LIU X,DRAPER S C,RECHT B.Suppressing Pseudocodewords by Penalizing the Objective of LP Decoding[C]∥Information Theory Workshop.IEEE,2012:367-371.

[15] WANG B,MU J,JIAO X,et al.Improved Penalty Functions of ADMM Penalized Decoder for LDPC Codes[J].IEEE Communications Letters,2017,99:234-237.

[16] FELDMAN J,MALKIN T,SERVEDIO R A,et al.LP Decoding Corrects a Constant Fraction of Errors[J].IEEE Transactions on Information Theory,2007,53(1):82-89.

[17] HALABI N,EVEN G.LP Decoding of Regular LDPC Codes in Memoryless Channels[C]∥IEEE International Symposium on Information Theory Proceedings.IEEE,2010:744-748.

[18] FELDMAN J,WAINWRIGHT M J,KARGER D R.Using Linear Programming to Decode Binary Linear Codes[J].IEEE Transactions on Information Theory,2005,51(3):954-972.

[19] 陳紫強(qiáng),歐陽(yáng)繕,李民政，等.一種基于改進(jìn)線性規(guī)劃的LDPC碼混合譯碼算法[J].電路與系統(tǒng)學(xué)報(bào),2013(1):107-112.

[20] LIU X,DRAPER S C.The ADMM Penalized Decoder for LDPC Codes[J].IEEE Transactions on Information Theory,2014,62(6):2966-2984.

ConstructionMethodOptimizationBasedonADMMPenaltyFunction

CHEN Zi-qiang,WANG Guang-yao

(SchoolofInformationandCommunicationEngineering,GuilinUniversityofElectronicTechnology,GuilinGuangxi541000,China)

In order to improve the error-rate performance and the converging rate for traditional ADMM penalized decoding algorithm,we further optimized the penalty function and proposed the TS-ADMM-PD algorithm based on three-segment penalty function.The algorithm introduced a transition function whose slope is between the front and rear one.And the function is applied to make a compromise on decoding performance and convergence rate.The optimized penalty function has a larger slope nearx=0 andx=1 to penalize the pseudo code word more heavily,so as to reduce the error rate and accelerate the converging speed.It has a smaller slope nearx=0.5 to make it easier to update the variables nodes information.Experimental simulation results show that the proposed TS-ADMM-PD algorithm has more excellent error-rate performance and converging speed than I-ADMM-PD algorithm.

LDPC codes;ADMM;penalty function;error-rate performance;converging rate

10.3969/j.issn.1003-3106.2017.12.06

陳紫強(qiáng)，王廣耀.基于ADMM的懲罰函數(shù)構(gòu)造方法優(yōu)化[J].無(wú)線電工程,2017,47(12):24-29.[CHEN Ziqiang,WANG Guangyao.Construction Method Optimization Based on ADMM Penalty Function[J].Radio Engineering,2017,47(12):24-29.]

TN911.22

A

1003-3106(2017)12-0024-06

2017-06-22

國(guó)家自然科學(xué)基金資助項(xiàng)目(61461015)；廣西自然科學(xué)基金資助項(xiàng)目(2014GXNSFAA118399)；廣西教育廳科研基金資助項(xiàng)目(ZD2014052)。

陳紫強(qiáng)男，(1973—)，博士，副教授，碩士生導(dǎo)師。主要研究方向：信號(hào)與信息處理、陣列信號(hào)處理、模式識(shí)別和信道編碼識(shí)別分析等。

王廣耀男，(1992—)，碩士研究生。主要研究方向：信號(hào)與信息處理。