基于可靠度的LDPC碼梯度下降比特翻轉(zhuǎn)譯碼算法

彭偉夫，張高遠(yuǎn)，文 紅，王龍業(yè)，3

(1. 國家電網(wǎng)四川省電力公司信息通信公司，四川 成都 610041；2.電子科技大學(xué) 通信與抗干擾技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，四川 成都 611731；3.西藏大學(xué) 工學(xué)院，西藏 拉薩 850000)

基于可靠度的LDPC碼梯度下降比特翻轉(zhuǎn)譯碼算法

彭偉夫1，張高遠(yuǎn)2，文 紅2，王龍業(yè)2，3

(1. 國家電網(wǎng)四川省電力公司信息通信公司，四川 成都 610041；2.電子科技大學(xué) 通信與抗干擾技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，四川 成都 611731；3.西藏大學(xué) 工學(xué)院，西藏 拉薩 850000)

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

LDPC碼；梯度下降；不匹配；加權(quán)梯度下降；比特翻轉(zhuǎn)

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

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

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

1 基本定義

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

(1)

2 傳統(tǒng)GDBF算法的分析

2.1 GDBF算法描述

步驟1,迭代次數(shù)k初值設(shè)定為1，終值設(shè)定為Kmax。

步驟3,翻轉(zhuǎn)函數(shù)En的計(jì)算

(2)

步驟4,比特翻轉(zhuǎn)

(3)

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

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

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

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

為了分析方便，再次給出GDBF算法的翻轉(zhuǎn)函數(shù)

表1 不同碼、不同信噪比下的3σ區(qū)間

圖2 碼2條件下，不同信噪比、不同迭代次數(shù)下，Single-GDBF算法的相關(guān)項(xiàng)和補(bǔ)償項(xiàng)的變化情況

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

3 基于可靠度和歸一化的改進(jìn)策略分析

3.1 基于校驗(yàn)方程可靠度的改進(jìn)型GDBF算法

(5)

對應(yīng)地，目標(biāo)函數(shù)則變?yōu)?/p>

(6)

將以式(6)作為目標(biāo)函數(shù)，式(5)作為翻轉(zhuǎn)函數(shù)的算法稱為“基于校驗(yàn)方程可靠度的梯度下降加權(quán)比特翻轉(zhuǎn)算法(Gradient Descent Weighted Bit-flipping，GDWBF)”。顯然，如果令ωm=1，則式(5)將會變?yōu)槭?4)，GDWBF算法將變成GDBF算法，即如果將M個校驗(yàn)方程的權(quán)重統(tǒng)一設(shè)定為1，則GDWBF算法將變?yōu)镚DBF算法。

圖3給出碼2條件下，SNR=4.5 dB，不同迭代次數(shù)時，式(5)中的互相關(guān)項(xiàng)和補(bǔ)償項(xiàng)的變化情況。

圖3 碼2條件下，不同迭代次數(shù)下，Single-GDWBF算法的互相關(guān)項(xiàng)和補(bǔ)償項(xiàng)的變化情況

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

3.2 基于歸一化的改進(jìn)型GDBF算法

GDBF算法是將各個校驗(yàn)方程的權(quán)重統(tǒng)一設(shè)定為1，由此帶來了2.2節(jié)中描述的互相關(guān)項(xiàng)和補(bǔ)償項(xiàng)的不匹配現(xiàn)象，但復(fù)雜度卻大大降低。這里考慮一種折中的做法，即引入待優(yōu)化的加權(quán)因子α對雙極性校驗(yàn)子進(jìn)行加權(quán)，得到一種GDBF算法，其翻轉(zhuǎn)函數(shù)為

(7)

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

4 復(fù)雜度分析

為了分析方便，現(xiàn)給出MWBF算法的翻轉(zhuǎn)函數(shù)[8]

(8)

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

表2 不同算法的翻轉(zhuǎn)函數(shù)更新策略

5 仿真結(jié)果和統(tǒng)計(jì)分析

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

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

圖4 不同F(xiàn)G -LDPC碼在不同譯碼算法下的誤碼率

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

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

表3 BER=10-5時，不同算法性能統(tǒng)計(jì) dB

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

6 結(jié)束語

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

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

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

[3]KOU Y L，LIN S，F(xiàn)OSSORIER 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]朱方強(qiáng)，王中訓(xùn)，劉麗，等. 基于循環(huán)檢測的LDPC碼比特翻轉(zhuǎn)譯碼算法研究[J]. 電視技術(shù)， 2011， 35(13)：116-119.

[10]詹尹，李宏偉. 一種改進(jìn)的LDPC碼硬判決譯碼算法[J]. 電視技術(shù)，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]勝驟，謝式千，潘承毅. 概率論與數(shù)理統(tǒng)計(jì)[M]. 北京： 高等教育出版社， 2008.

責(zé)任編輯：時 雯

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

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

國家自然科學(xué)基金項(xiàng)目(61261021)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)(A03008023901004)

TN911.22 文獻(xiàn)表示碼：A

10.16280/j.videoe.2015.13.030

2014-11-05