基于可靠度的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)；中央高校基本科研业务费专项(A03008023901004)

TN911.22 文献表示码：A

10.16280/j.videoe.2015.13.030

2014-11-05