基于ADMM的懲罰函數構造方法優化

陳紫強，王廣耀

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

基于ADMM的懲罰函數構造方法優化

陳紫強，王廣耀

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

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

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

0 引言

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

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

本文針對傳統ADMM懲罰譯碼算法提出一種改進方案TS-ADMM-PD。充分利用懲罰函數的結構特點，對罰函數做進一步優化，引用過渡函數對譯碼性能和收斂速度進行折衷。優化后的罰函數更加細分了在不同端點處斜率的取值，最終所提的TS-ADMM-PD算法在僅增加少量計算復雜度的條件下，譯碼性能和收斂速度均有所改善。

1 LP譯碼

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

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

式中，γ表示對數似然比(LLR)矢量；Tj表示選出與校驗節點j對應的碼字x的分量；PPdj表示所有由長度為dj且包含偶數個元素‘1’的二進制矢量構成的凸包，稱為檢驗多面體。

綜上所述，線性規劃譯碼是一種基于最優化技術的譯碼方案，主要思想是將譯碼問題轉化為數學上的整數規劃問題[17]。通過松弛約束條件，將原先難以解決的LP問題分解為小的、易于處理的簡單LP問題，然后再利用最優化理論完成整個譯碼過程[18]。不過仍然存在瀑布區臨界值較大、硬件實現復雜度高等問題[19]。

2 ADMM懲罰譯碼

為了改善LP譯碼在低信噪比時的誤碼性能，加快譯碼收斂，提出了基于ADMM的改進懲罰譯碼算法(I-ADMM-PD)。該方法的主要思想為向LP譯碼的目標函數中添加一個懲罰項，將譯碼問題轉化為數學上非線性非凸優化問題，此時的目標函數被改變為：

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

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

① 對于?j∈J，構建轉換矩陣Tj和接收矢量r的對數似然比γ；

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

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

由γi計算初始解矢量x0，γi為線性規劃目標函數的系數。對于?i∈I，有

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

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

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

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

通過對xi的表達式進行求導，然后令其為零，得到駐點從而求得局部解。由函數性質得到，懲罰函數g(x)在g1(x)(0,0.5)上單調遞增。所以如果存在多個駐點，采用簡單的閾值總是選擇離0.5最遠的那個。

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

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

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

3 TS-ADMM-PD算法

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

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

對于罰函數g1(x)，選取數a，b(0

將構造的罰函數命名為TS-l1-PF，表示為：

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

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

對于罰函數g2(x)，選取數c，d(0

將構造的罰函數命名為TS-l2-PF，表示為：

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

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

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

圖1 TS-l1-PF和TS-l2-PF罰函數圖像

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

4 仿真結果及分析

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

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

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

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

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

5 結束語

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

[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碼線性規劃譯碼方法[P].陜西：CN104092468A,2014-10-08.

[7] 王勇超,白晶,杜倩.基于最小多面體模型的LDPC碼線性規劃譯碼方法[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].中國通信,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] 陳紫強,歐陽繕,李民政，等.一種基于改進線性規劃的LDPC碼混合譯碼算法[J].電路與系統學報,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

陳紫強，王廣耀.基于ADMM的懲罰函數構造方法優化[J].無線電工程,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

國家自然科學基金資助項目(61461015)；廣西自然科學基金資助項目(2014GXNSFAA118399)；廣西教育廳科研基金資助項目(ZD2014052)。

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

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