基于可靠度的LDPC碼梯度下降比特翻轉譯碼算法

彭偉夫，張高遠，文 紅，王龍業，3

(1. 國家電網四川省電力公司信息通信公司，四川 成都 610041；2.電子科技大學 通信與抗干擾技術國家重點實驗室，四川 成都 611731；3.西藏大學 工學院，西藏 拉薩 850000)

基于可靠度的LDPC碼梯度下降比特翻轉譯碼算法

彭偉夫1，張高遠2，文 紅2，王龍業2，3

(1. 國家電網四川省電力公司信息通信公司，四川 成都 610041；2.電子科技大學 通信與抗干擾技術國家重點實驗室，四川 成都 611731；3.西藏大學 工學院，西藏 拉薩 850000)

仿真結果表明，對于列重和行重較小的低密度奇偶校驗(Low Density Parity-check，LDPC)碼而言，梯度下降比特翻轉(Gradient Descent Bit-flipping，GDBF)譯碼算法展現出巨大的性能優勢，但其對于基于有限域幾何構造的列重和行重較大的LDPC碼則性能損失嚴重。該文首先分析指出，對于大列重LDPC碼而言，翻轉函數中的“互相關項”和“雙極性校驗子求和項”之間的“不匹配”是造成性能損失的主要原因。其次，引入一種可靠性度量對雙極性校驗子進行加權，上述“不匹配”現象得到有效削弱，從而改善GDBF算法對大列重LDPC碼的譯碼性能。仿真結果表明，在加性高斯白噪聲信道下，相比于傳統的GDBF算法，新提出的算法在誤比特率為10-5時可獲得0.8 dB的增益。

LDPC碼；梯度下降；不匹配；加權梯度下降；比特翻轉

作為一種逼近香農限的信道編碼技術，低密度奇偶校驗(Low Density Parity Check code， LDPC)碼[1]在移動通信、數字衛星廣播(Digital Video Broadcasting，DVB)通信、深空通信和磁性記錄介質存儲等領域應用廣泛[2]。Gallager最早提出的比特翻轉(Bit Flipping， BF)算法[1]是最典型的硬判決譯碼算法。引入可靠度軟信息的加權BF(Weighted Bit Flipping， WBF)算法[3]獲得了一定編碼增益。MWBF(Modified Weighted Bit Flipping， MWBF)算法和IMWBF(Improved Modified Weighted Bit Flipping， IMWBF)算法[4-5]是兩種最為典型的改進算法。對于行重和列重較小的LDPC碼而言，基于可靠度比率的WBF(Reliability Ratio Based Weighted Bit Flipping ， RRWBF )算法[6]取得了不錯的編碼增益。更多相關研究可參考文獻[7-17]。

文獻[8]中的結果表明，梯度下降比特翻轉(Gradient Decent Bit Flipping， GDBF)算法的性能要優于MWBF和IMWBF的算法[8]。不同于MWBF和IMWBF算法，GDBF算法的另一個優勢在于不需要事先進行任何的參數優化[4-5，8]。此后，GDBF算法的各種改進方案被提出，但這些GDBF改進方案都局限于對列重較小的LDPC碼的研究[14-17]。本文則重點研究將GDBF算法運用于列重較大的LDPC碼時存在的問題并提出解決方案。

大量仿真標明，GDBF算法對低列重的LDPC碼譯碼時候，相對于IMWBF算法能獲得顯著的增益，但對于列重較大的LDPC碼，其卻展現出比WBF算法還差的譯碼性能。本文首先詳細分析LDPC碼的列重對GDBF譯碼性能的影響；其次，針對大列重的LDPC碼，提出梯度下降WBF (Gradient Decent Weighted Bit Flipping， GDWBF)和歸一化GDBF算法。仿真結果表明，在AWGN信道條件下，對于大行重和列重LDPC碼而言，本文提出的算法相對于傳統的GDBF算法在誤比特率為10-5時可獲得0.8 dB的增益。

1 基本定義

作為(N,K)線性分組碼，LDPC碼可由M≥N-K行N列的校驗矩陣H=[hmn]來決定。二元規則LDPC碼H矩陣第m行中1的數量恒為dc，并記Α(m)={n:hmn=1}；第n列中1的數量恒為dv，并記B(n)={m:hmn=1}。

(1)

2 傳統GDBF算法的分析

2.1 GDBF算法描述

步驟1,迭代次數k初值設定為1，終值設定為Kmax。

步驟3,翻轉函數En的計算

(2)

步驟4,比特翻轉

(3)

圖1所示為不同LDPC碼、不同算法，在不同信噪比(SNR)下的誤碼率(BER)仿真結果。

圖1 不同算法、不同LDPC碼下的譯碼性能比較

圖1a的迭代次數設定為50，采用列重和行重為(3，6)的(504，252)PEG-LDPC碼(記為碼1)[12]和列重和行重為(16，16)的(255，175)FG-LDPC碼(記為碼2)[3]；圖1b的迭代次數設定為100，采用列重和行重為(3，6)的(1 008，504)PEG-LDPC碼(記為碼3)[12]和列重和行重為(17，17)的(273，191)PG-LDPC碼(記為碼4)[3]。在AWGN信道條件下，采用BPSK調制，每個信噪比下至少采集1 000個錯誤接排比特。圖1a中，IMWBF算法的最優加權系數分別設定為0.2和2.1，MWBF算法的最優加權系數分別設定為0.3和1.5；圖1b中，IMWBF算法的最優加權系數分別設定為0.2和1.3，MWBF算法的最優加權系數分別設定為0.2和1.4[4-5，8]。由圖1可知，對于碼1和碼3而言，Single-GDBF算法的性能優于IMWBF算法，但對于碼2和碼4而言，WBF算法的性能要優于Single-GDBF算法。由此可知，對于行重和列重較大的LDPC碼而言，Single-GDBF算法譯碼性能損失嚴重。

2.2 大列重LDPC碼下譯碼性能分析

為了分析方便，再次給出GDBF算法的翻轉函數

表1 不同碼、不同信噪比下的3σ區間

圖2 碼2條件下，不同信噪比、不同迭代次數下，Single-GDBF算法的相關項和補償項的變化情況

由圖2可得到兩個結論：第一，在每個信噪比條件下(對應于圖2的每個子圖)，整體上而言，隨著迭代次數的增加，更多的校驗方程滿足校驗，故補償項的值將逐漸增大，當所有的校驗方程都滿足時，補償項達到最大值16，即補償項的值處于“動態遞增”狀態。但在整個迭代過程中rn·zn的值是“固定不變”的。從而補償項和互相關項間的“不匹配”現象將隨著迭代次數的增大而愈發嚴重。第二，對于每個固定的迭代次數下，隨著信噪比的增大(4個子圖的信噪比逐漸增大)，校驗方程滿足的個數同樣逐漸增大，從而補償項和互相關項間的“不匹配”現象同樣愈發嚴重。這種“不匹配”現象使得翻轉函數En的值更加依賴于“補償項”，而造成“互相關項”對翻轉函數的貢獻被削弱，從而造成En的不準確，導致譯碼性能降低。

3 基于可靠度和歸一化的改進策略分析

3.1 基于校驗方程可靠度的改進型GDBF算法

(5)

對應地，目標函數則變為

(6)

將以式(6)作為目標函數，式(5)作為翻轉函數的算法稱為“基于校驗方程可靠度的梯度下降加權比特翻轉算法(Gradient Descent Weighted Bit-flipping，GDWBF)”。顯然，如果令ωm=1，則式(5)將會變為式(4)，GDWBF算法將變成GDBF算法，即如果將M個校驗方程的權重統一設定為1，則GDWBF算法將變為GDBF算法。

圖3給出碼2條件下，SNR=4.5 dB，不同迭代次數時，式(5)中的互相關項和補償項的變化情況。

圖3 碼2條件下，不同迭代次數下，Single-GDWBF算法的互相關項和補償項的變化情況

由圖3可知，引入校驗方程可靠度之后，圖中的點大多都分布在y=x附近，這種現象表明：大多數情況下，互相關項和補償項的值不會隨著迭代次數的增大而差別過大，圖2中的“不匹配”現象得到有效地削弱，下文仿真結果將會表明，由此帶來了顯著的性能改善。

3.2 基于歸一化的改進型GDBF算法

GDBF算法是將各個校驗方程的權重統一設定為1，由此帶來了2.2節中描述的互相關項和補償項的不匹配現象，但復雜度卻大大降低。這里考慮一種折中的做法，即引入待優化的加權因子α對雙極性校驗子進行加權，得到一種GDBF算法，其翻轉函數為

(7)

式中：α>0，令α=1即得到GDBF算法。

4 復雜度分析

為了分析方便，現給出MWBF算法的翻轉函數[8]

(8)

式(8)右端第一項可稱為“內信息項”，這是因為它只與信息節點自身的可靠度有關。在第1次迭代時，對于每個信息節點，可用2個存儲單元分別存儲“內信息項”和“校驗式加權求和項”，然后二者求和得到翻轉函數。設在第k(2≤k≤Kmax)迭代中第η(1≤η≤N)個信息比特zη被翻轉，則需更新集合Φ={n∈A(m),m∈B(η)}中信息節點的翻轉函數[5]。更新的具體過程為：第一，對k-1迭代中的“校驗式加權求和項”取反得到第k次迭代的“校驗式加權求和項”；第二，用更新得到的第k次迭代的“校驗式加權求和項”與“內信息項”相加得到第k次迭代的翻轉函數。由于式(5)和式(8)有一定的相似之處，故GDWBF算法的翻轉函數更新過程與MWBF算法基本相同。唯一的不同之處在于zη的翻轉函數的更新過程：在GDWBF算法中需要對“互相關項”和“校驗式加權求和項”同時取反再相加得到翻轉函數，而MWBF算法只需對“校驗式加權求和項”取反即可，“內信息項”在迭代的整個過程中保持不變。兩種算法具體的更新方法如表2所示[5]。但考慮到只需對“互相關項”的符號位取反即能對其更新，故可近似認為GDWBF算法和MWBF算法的實現復雜度是相同的。

表2 不同算法的翻轉函數更新策略

5 仿真結果和統計分析

本節所采用的仿真參數如下：碼2，碼4，列重和行重為(32，32)的(1 023，781)FG-LDPC碼(碼5)，列重和行重為(33，33)的(1 057，813)PG-LDPC碼(碼6)。兩個短碼的迭代次數設定為100，兩個長碼則設定為200。MWBF算法和IMWBF算法在碼5和碼6條件下的最優加權系數都設定為1.8[4-5]。歸一化GDBF算法的加權因子分別設定為0.1，0.08，0.1和0.06。

圖4和圖5分別為最優參數下，不同碼條件下各譯碼性能曲線。表3給出誤比特率為10-5時，各算法性能比較。引入可靠度軟信息后，GDWBF翻轉函數的復計算雜度較GDBF算法有所增大，但由表3可知，由此帶來的增益也是十分顯著的。例如，在4種碼條件下，可獲得0.6～0.8 dB的增益，即便是歸一化GDBF算法最大也能獲得0.47 dB的增益。

圖4 不同FG -LDPC碼在不同譯碼算法下的誤碼率

圖6為碼4和碼6在各譯碼算法的平均迭代次數統計曲線。由圖6可知，在短碼條件下GDWBF算法的平均迭代次數略低于MWBF算法，長碼時在中低信噪比條件下則略高于MWBF算法。結合第4節中的分析可知，從平均意義上講，GDWBF算法和MWBF算法的實現復雜度基本相當。從圖4和圖5都可以看出，MWBF算法和GDWBF算法的性能基本一致。但有一點需要特別指出的是，對于不同的碼而言，前者需要事先通過仿真尋求最優的加權系數β，而后者則不涉及任何的參數優化問題，這也是GDWBF算法的另一個優勢所在。

圖5 不同PG -LDPC碼在不同算法下的誤碼率

表3 BER=10-5時，不同算法性能統計 dB

圖6 不同PG -LDPC碼在不同算法下的平均迭代次數比較

6 結束語

針對GDBF算法對大列重的LDPC碼譯碼時候，譯碼性能較差的現象，本文提出了GDWBF和歸一化GDBF算法。在AWGN信道下，誤比特率為10-5時，相比于傳統的GDBF算法，GDWBF算法可獲得0.8 dB的增益。本文重點研究了不需要預先設定翻轉門限θ的單比特翻轉模式的算法，翻轉門限θ對多比特翻轉模式的GDWBF算法的影響以及如何通過理論分析得到最優的θ仍有待深入研究。另一方面，本文只給出了一種較為簡單的目標函數和翻轉函數構造方法，其他類型的構造方法也有待進一步研究。

[1]GALLAGER R G. Low density parity check codes[J]. IRE Trans. Information Theory，1962，8(1)：21-28.

[2]安琪，張曉林. 基于子迭代次數的LDPC碼改進動態調度算法[J]. 電視技術， 2014， 38(1)：685-689.

[3]KOU Y L，LIN S，FOSSORIER M P C. Low-density parity-check codes based on finite geometries： a rediscovery and new results[J]. IEEE Trans. Information Theory， 2001， 47(7)：2711-2736.

[4]ZHANG J， FOSSORIER M P C. A modified weighted bit-flipping decoding of low-density parity-check codes[J]. IEEE Communications Letters， 2004， 8(3)：165-167.

[5]JIANG M， ZHAO C M， SHI Z， et al. An improvement on the modified weighted bit flipping decoding algorithm for LDPC codes[J]. IEEE Communications Letters， 2005(9)：814-816.

[6]GUO F，HANZO L. Reliability ratio based weighted bit-flipping decoding for low-density parity-check codes[J]. Electronics Letters， 2004， 40(21)：1356-1358.

[7]LIU Z， PADOS D A. A decoding algorithm for finite-geometry LDPC codes[J]. IEEE Trans. Communications， 2005， 53(3)：415-421.[8]WADAYAMA T， NAKAMURA K， YAGITA M， et al. Gradient descent bit flipping algorithms for decoding LDPC codes[J]. IEEE Trans. Communications， 2010， 58(6)：1610-1614.[9]朱方強，王中訓，劉麗，等. 基于循環檢測的LDPC碼比特翻轉譯碼算法研究[J]. 電視技術， 2011， 35(13)：116-119.

[10]詹尹，李宏偉. 一種改進的LDPC碼硬判決譯碼算法[J]. 電視技術，2013， 37(13)：109-112.

[11]CHEN T C. An efficient bit-flipping decoding algorithm for LDPC codes[C]//Proc. International Conference on Cross Strait Quad-Regional Radio Science and Wireless Technology. New Taipei City：IEEE Press， 2012：109-112.

[12]CHEN T. Channel-independent weighted bit-flipping decoding algorithm for low-density parity-check codes[J]. IET Communications， 2012， 6(17)：2968-2973.

[13]ZHANG G Y， ZHOU L， WEN H. Modified channel-independent weighted bit-flipping decoding algorithm for LDPC codes[J]. IET Communication， 2014， 8(6)：833-840.

[14]PHROMSA-ARD T， ARPORNSIRIPAT J， WETCHARUNGSRI J， et al. Improved gradient descent bit flipping algorithms for LDPC decoding[C]//Proc. 2012 2nd International Conference on Digital Information and Communication Technology and its Applications. Bangkok： IEEE Press， 2012：324-328.

[15]HAGA R， USAMI S. Multi-bit flip type gradient descent bit flipping decoding using no thresholds[C]//Proc. 2012 International Symposium on Information Theory and its Application. Honolulu： IEEE Press， 2012：6-10.

[16]WEBBER J，NISHIMURA T，OHGAME T，et al. Performance investigation of reduced complexity bit-flipping using variable thresholds and noise perturbation[C]//Proc. 2014 16th International Conference on Advanced Communication Technology. Pyeongchang：IEEE Press， 2014：206-213.

[17]IAMAIL M， COON J， AHMED I， et al. Turbo adaptive threshold bit flipping for LDPC decoding[J]. IEEE Wireless Communications Letters， 2013， 2(1)：118-121.

[18]勝驟，謝式千，潘承毅. 概率論與數理統計[M]. 北京： 高等教育出版社， 2008.

責任編輯：時 雯

Reliability Based on Gradient Descent Bit-flipping Decoding Algorithm for LDPC Codes

PENG Weifu1，ZHANG Gaoyuan2，WEN Hong2，WANG Longye2,3

(1.Information&CommunicationCompany，StateGridSichuanElectricPowerCorporation，Chengdu610041，China；2.NationalKeyLaboratoryofScienceandTechnologyonCommunications，UniversityofElectronicScienceandTechnology，Chengdu611731，China；3.SchoolofEngineeringandTechnology，TibetUniversity，Lhasa850000，China)

Simulation results show that the gradient descent bit-flipping(GDBF)decoding algorithm performs extraordinarily well when it is used for some low density parity-check (LDPC) codes with low row/colum weight. However， the performace will degrade when GDBF decoding is used for large row/colum weight finite-geometry (FG) LDPC codes. The mismatch between “the correlation term” and “the sum term of bipolar syndromes” in the inversion function of GDBF algorithm for large row/colum LDPC codes is first theoretically analyzed in this paper， which is supposed to be the largest contribution to the performance degradation. Secondly， a reliability metric is considered to weight the bipolar syndrome， and improvement in performance is observed， which benefits from sufficiently impairing the aforementioned mismatch. Simulations show that the performance improvement is about 0.8 dB at BER of 10-5over an AWGN channel.

LDPC codes；gradient descent； mismatch；weighted gradient descent；bit flipping

【本文獻信息】彭偉夫，張高遠，文紅，等.基于可靠度的LDPC碼梯度下降比特翻轉譯碼算法[J].電視技術,2015，39(13).

國家自然科學基金項目(61261021)；中央高?；究蒲袠I務費專項(A03008023901004)

TN911.22 文獻表示碼：A

10.16280/j.videoe.2015.13.030

2014-11-05