LDPC碼基于雙修正因子的剩余度置信傳播譯碼算法

周華 趙良 李誠謙

摘 ?要： 通過對LDPC碼的RBP和NWRBP譯碼算法進行研究，針對算法在譯碼過程中運算量過大，不利于在硬件上實現(xiàn)的問題，提出一種改進型的RBP和NWRBP譯碼算法。該算法在更新從檢驗節(jié)點到變量節(jié)點的信息時，采用最小和算法得出近似值，以此降低譯碼復雜度。同時，為了彌補近似值所帶來的譯碼性能損失，引入乘性修正因子和加性修正因子來提高譯碼性能。

關鍵詞： LDPC碼; RBP算法; NWRBP算法; 最小和算法; 修正因子引入; 信息更新

中圖分類號： TN919.3+2?34 ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2019）11?0015?04

Abstract： The residual belief?propagation （RBP） and node?wise residual belief?propagation （NWRBP） decoding algorithm for low?density parity?check （LDPC） codes is researched， but it has excessive computing amount in decoding process， and is difficult to implement with hardware. Therefore， the improved RBP and NWRBP decoding algorithm are proposed. When the algorithm is used to update the information from check nodes to variable nodes， the Min?Sum （MS） algorithm is adopted to obtain the approximate value， so as to reduce the complexity of decoding. In the meanwhile， in order to compensate for the decoding performance loss caused by the approximate value， the multiplicative correction factor and additive correction factor are introduced to improve the decoding performance successfully.

Keywords： low?density parity?check code; residual belief?propagation algorithm; node?wise residual belief?propagation algorithm; Min?Sum algorithm; correction factor introduction; information updating

0 ?引 ?言

低密度奇偶校驗碼（Low?Density Parity?Check Codes，LDPC）[1]是一種由二進制稀疏矩陣定義的線性分組碼。由于較強的糾錯能力和較大的靈活性，以及在加性高斯白噪聲下其置信傳播（BP）譯碼算法的性能逼近香農(nóng)限，LDPC成為近些年來編碼領域研究的熱點，并且LDPC碼于北京時間2016年10月14日被確定為5G 長碼編碼方案。

在眾多的LDPC譯碼算法中，剩余度置信傳播（Residual Belief?Propagation，RBP）和基于行的剩余度置信傳播（Node?wise RBP，NWRBP）算法[2?3]是一種高效的動態(tài)調(diào)度譯碼算法[4]。

RBP和NWRBP作為有效的動態(tài)調(diào)度譯碼算法，它們具有良好的譯碼性能，特別是在迭代次數(shù)較低的情況下這種優(yōu)勢更加明顯。然而，RBP和NWRBP算法在譯碼過程中需要大量地使用指數(shù)型和對數(shù)型乘法運算，特別是在譯碼時需要多次使用tanh函數(shù)，計算相當復雜，在實際應用中需要通過查表才能實現(xiàn)，因此需要占用大量的ROM資源，不利于硬件的實現(xiàn)[5?8]。

改進型RBP和NWRBP算法采用加法運算替代計算剩余度值過程中的指數(shù)型和對數(shù)型乘法運算，以便降低譯碼的復雜度，但也同時帶來了誤碼率的提高。為了彌補降低運算復雜度而帶來的譯碼性能上的損失，本文引入雙修正因子[α]和[β]對剩余度值的計算進行修正[9]，從而改善譯碼性能。

1 ?LDPC碼的RBP和NWRBP譯碼算法

假設一個[（N，M）]的LDPC碼，檢驗位數(shù)量為[M=N-K]，則檢驗矩陣[H]是一個[M×N]的矩陣。[H]矩陣中的[M]行和[N]列分別對應Tanner圖中的[M]個校驗節(jié)點和[N]個變量節(jié)點[10]，其中，校驗節(jié)點集為[cii=1，2，…，M]，變量節(jié)點集為[vjj=1，2，…，N]。在信息的傳輸過程中，使用二進制移相鍵控（Binary Phase Shift Keying，BPSK）將二進制碼字序列[z=（z1，z2，…，zN）]調(diào)制成[x=（x1，x2，…，xN）]傳送出去，經(jīng)加性高斯白噪聲（Additive White Gaussian Noise，AWGN）信道后接收到的序列[y=（y1，y2，…，yN）]為：

式中：BPSK的調(diào)制映射規(guī)則為[xi=2zi-1， i=1，2，…，N];[ni]是服從均值為0、方差為[σ2]的高斯白噪聲，即[ni～N0，σ2]，且它們之間相互獨立。信噪比（Signal?to?Noise Ratio，SNR）記為[EbN0]，[Eb]和[N0]分別用于表示每個信息比特發(fā)送之前的能量和噪聲功率譜密度[2][N0=][2σ2]。在譯碼前，接收序列的對數(shù)似然比（LLR）初始化為：

定義如下記號：[Nci=vjhij=1]表示Tanner圖中所有與第[i]個校驗節(jié)點連接的一組變量節(jié)點的集合;[Nci＼vj]表示[Nci]除去第[j]個變量節(jié)點后得到的子集;[Nvj=cihij=1]表示Tanner圖中所有與第[j]個變量節(jié)點連接的一組校驗節(jié)點的集合;[Nvj＼ci]表示[Nvj]除去第[i]個校驗節(jié)點后得到的子集;[Mvj→ci]表示從第[j]個變量節(jié)點向第[i]個校驗節(jié)點發(fā)送的信息;[Eci→vj]表示第[i]個校驗節(jié)點向第[j]個變量節(jié)點發(fā)送的信息。且有以下定義：

式（3）和式（4）具體描述了LDPC算法在譯碼過程中任意兩個變量節(jié)點和校驗節(jié)點之間消息更新及傳遞的信息方程[2]。RBP和NWRBP算法是Informal Dynamic Scheduling（IDS）策略中兩個基于剩余度值的主要算法機制。剩余度值用于表示從校驗節(jié)點到變量節(jié)點信息更新前后值之差的絕對值。在LDPC解碼中，剩余度值用公式表示為：

式中：[Enewci→vj]和[Eci→vj]分別表示從校驗節(jié)點[ci]向變量節(jié)點[vj]發(fā)送的更新之前和之后的消息。

RBP和NWRBP的譯碼計算步驟見算法1。

算法1：RBP和NWRBP算法譯碼流程

1） 初始化：所有[Eci→vj]設置為0;將所有的[Mvj→ci]值設置為[ri]。

2） 根據(jù)式（5）計算所有的剩余度值[R（Eci→vj）]。

3） 找出最大的剩余度值[R（Ecmax→vmax）]。

4） 將所有的剩余度值[R（Eci→vj）]設置為0。

5） RBP后續(xù)更新：

2 ?改進型的RBP和NWRBP譯碼算法

RBP和NWRBP算法的譯碼過程中，在計算[Eci→vj]時需要多次使用tanh函數(shù)，其計算的復雜度遠高于BP算法，根據(jù)它們所設計出的譯碼電路相當復雜，難以推廣使用。在使用RBP或NWRBP算法進行譯碼時的計算過程與BP算法中計算從校驗節(jié)點[ci]到變量節(jié)點[vj]的消息方法一致，而BP算法在計算這一消息值時可通過最小和（Min?Sum，MS）的方式降低運算量。因此，在RBP和NWRBP算法中引入MS來代替式（4），其具體的計算過程為：

采用MS方式能夠用加法運算代替計算[Eci→vj]過程中的浮點型指數(shù)和對數(shù)乘法運算。由于MS算法是通過近似計算而得出的結(jié)果，該方法應用在RBP和NWRBP算法中必然會導致其譯碼性能的下降。對于碼長為155，碼率為[12]的規(guī)則LDPC碼，對RBP進行簡化運算，化簡后RBP的誤碼率和誤幀率如圖1所示。

圖1 ?簡化后RBP的誤碼率和誤幀率對比

根據(jù)tanh函數(shù)的性質(zhì)可知，通過式（6）計算出的[Eci→vj]要比通過式（4）計算出的[Eci→vj]值略大，這造成了譯碼性能的損失。為了使通過近似方式計算出的[Eci→vj]值更加接近標準值，引入乘性修正因子[α]和加性修正因子[β]對[Eci→vj]進行修正來提高譯碼算法的性能，且[α]和[β]滿足關系[0<β<α]<1。將[Eci→vj]修正之前和之后分別標記為[E（1）ci→vj]和[E（2）ci→vj]，則有：

該修正方法根據(jù)[E（1）ci→vj]值的大小進行有差別的修正，即[E（1）ci→vj]的修正幅度隨著[E（1）ci→vj]值的增大而增大。如果想要獲得更好的譯碼性能，修正因子需要根據(jù)信道條件和傳輸碼長的變化而變化，但一般可以作為常數(shù)進行處理，這里將修正因子[α]和[β]分別取0.9和0.1，具體的計算步驟見算法2，算法流程如圖2所示。

算法2：改進型RBP和NWRBP算法譯碼流程

1） 初始化：將所有[Eci→vj]設置為0;所有的[Mvj→ci]值設置為[ri]。

2） 根據(jù)式（6）計算[Enewci→vj]的估值，并通過式（7）對[Enewci→vj]值進行修正。

3） 根據(jù)式（5）計算所有的剩余度值[R（Eci→vj）]。

4） 找出最大的剩余度值[R（Ecmax→vmax）]。

5） 將所有的剩余度值[R（Eci→vj）]設置為0。

6） RBP后續(xù)更新：

7） 嘗試判決：

IF未正確譯碼或沒有達到最大迭代次數(shù)

圖2 ?基于雙修正因子的RBP和NWRBP的譯碼流程圖

根據(jù)以上分析，改進型的RBP和NWRBP譯碼算法相對于原算法做出了兩點改進。首先通過加法運算替代乘法運算得出[Eci→vj]的近似值，從而避免tanh函數(shù)的計算，以便對硬件電路進行簡化;然后，為了彌補近似計算帶來的譯碼性能的損失，引入雙修正因子[α]和[β]對[Eci→vj]進行修正，從而達到降低計算復雜度的同時進一步提升譯碼性能的目的。

3 ?仿真結(jié)果與分析

為了進一步驗證該改進型的RBP和NWRBP算法的譯碼性能，選用Visual Studio 2012軟件作為平臺，并采用C++語言進行仿真實驗。本文所有的實驗數(shù)據(jù)均是在加性高斯白噪聲（BI?AWGN）信道下仿真獲得的，并通過BPSK方式進行調(diào)制。仿真選用IEEE 802.16e標準中碼長為155，碼率[R=12]以及IEEE 802.16e標準中碼長為576，碼率[R=12]的規(guī)則LDPC碼。具體的仿真結(jié)果如圖3～圖5所示。

圖3 ?碼長為155時改進型的RBP和NWRBP算法的譯碼性能

圖4 ?碼長為576時改進型RBP算法的譯碼性能

圖5 ?碼長為576時改進型NWRBP算法的譯碼性能

圖3和圖4分別為碼長155，碼長576，[α]和[β]分別取0.9和0.1，最大迭代次數(shù)為50的情況下各種譯碼方案的性能對比。在信噪比較低時，改進型RBP和改進型NWRBP與傳統(tǒng)的RBP和NWRBP相比，其誤碼率和誤幀率曲線相差不大。在較高的信噪比情況下，改進型的RBP和NWRBP算法的誤碼率和誤幀率曲線均明顯低于傳統(tǒng)的RBP和NWRBP算法。碼長為155時，如圖3所示，改進型的RBP和改進型的NWRBP在誤幀率FER為[10-2]的情況下其SNR分別得到0.2 dB和0.15 dB的增益;碼長為576時，如圖4和圖5所示，改進型的RBP和改進型的NWRBP在誤碼率BER為[10-3]的情況下其SNR分別得到0.15 dB和0.13 dB的增益。

4 ?結(jié) ?論

本文針對RBP和NWRBP算法在譯碼過程中計算復雜度高的問題做出改進，得到一種改進型的RBP和NWRBP譯碼算法。該算法通過在計算剩余度值[R（Ecmax→vmax）]時采用加法運算代替乘法運算的MS方法，從而使運算的復雜度得到明顯下降。為保證譯碼性能，本文又引入乘性修正因子[α]和加性修正因子[β]進行修正。仿真結(jié)果表明，改進型的RBP和NWRBP在155和576兩種碼長下均具有良好的譯碼性能，且誤碼率低于傳統(tǒng)的RBP和NWRBP算法。

參考文獻

[1] 吳軍，廖鑫，張小紅.一種改進的LDPC碼低復雜度最小和算法[J].電視技術，2015，39（1）：88?91.

WU Jun， LIAO Xin， ZHANG Xiaohong. Improved Min?Sum algorithm with low complexity for decoding LDPC codes [J]. Vi?deo engineering， 2015， 39（1）： 88?91.

[2] 周華，翁少輝，馮姣. LDPC碼節(jié)點剩余度置信傳播譯碼改進[J].電子技術應用，2017，43（11）：107?111.

ZHOU Hua， WENG Shaohui， FENG Jiao. Enhanced node?wise residual belief propagation for LDPC codes [J]. Application of electronic technique， 2017， 43（11）： 107?111.

[3] 張福星，許生旺.一種改進的多元LDPC碼譯碼算法[J].無線電通信技術，2016（6）：56?58.

ZHANG Fuxing， XU Shengwang. Modified?BP decoding algorithm of non?binary LDPC codes [J]. Radio communications technology， 2016（6）： 56?58.

[4] GONG Y， LIU X C. Effective informed dynamic scheduling for belief propagation decoding of LDPC codes [J]. IEEE transactions on communications， 2011， 59（10）： 2683?2691.

[5] LIU Xingcheng， ZHANG Yuanbin， CUI Ru. Variable?node?based dynamic scheduling strategy for belief?propagation deco?ding of LDPC codes [J]. IEEE communications letters， 2015， 19（2）： 147?150.

[6] SONG Lingyan， HOU Shujuan. Improved decoding of LDPC codes by variable?to?check residual belief propagation [C]// 2015 International Conference on Communications & Networ?king in China. Shanghai， China： IEEE， 2015： 163?166.

[7] 韓少聰，高飛飛，李云洲.一種改進的自糾正最小和LDPC碼的譯碼算法[J].電信科學，2013，29（6）：89?93.

HAN Shaocong， GAO Feifei， LI Yunzhou. An improved self?correct Min?Sum decoding algorithm for low?density parity?check code [J]. Telecommumications science， 2013， 29（6）： 89?93.

[8] ELIDAN G， MCGRAW I， KOLLER D. Residual belief propagation： informed scheduling for asynchronous message passing [C]// Proceedings of the 22nd Conference on UAI. ?Cambridge， MA： MIT Press， 2006： 165?173.

[9] CASADO A， GRIOT M， WESEL R D. Informed dynamic scheduling for belief?propagation decoding of LDPC codes [C]// Proceedings of 2007 ICC. Glasgow， Scotland： IEEE， 2007： 932?937.

[10] LI Hua， ZHENG Linhua. Efficient puncturing scheme for irregular LDPC codes based on serial schedules [J]. IEEE communications letters， 2015， 19（9）： 1508?1511.