LDPC码中一种基于节点残余的BP译码算法*

王兴成，王中训，郭 栋，于心乔

（烟台大学 光电信息科学技术学院，山东 烟台 264005）

1 引言

低密度奇偶校验（LDPC）码[1-3]是性能接近香农极限的纠错编码，因而得到广泛关注，对于无线通信有着至关重要的作用。在LDPC码译码时，校验节点与变量节点之间有大量的信息传送，因此降低LDPC码译码复杂度与译码器的功率消耗，关键在于减少信息传送的运算量。

在众多优秀的译码算法中，残余信息的LDPC码BP译码算法（RBP）[4]是一种有效动态调度的译码算法，在迭代次数较少情况下与无调度的译码算法相比译码速度较快，但误码率和复杂度较高。笔者研究的VC-RBP译码算法与RBP译码算法相比，具有优良的误码率性能，复杂度较低，同样具有快速译码的性能，不同之处在于残留信息的计算。RBP算法的残余信息的计算在校验节点传向变量节点信息更新前后，而VC-RBP算法的残余信息的计算在变量节点传向校验节点信息更新前后。

2 LDPC码中的BP译码算法及其改进

2.1 BP译码算法[5]

消息传递算法的信道输出符号集和译码过程中发送信息的符号集相同，都是实数集，也就是说采用连续性的消息时，适当地选择信息映射函数，就能把人工智能中的置信传播（BP）算法运用于LDPC码，从而形成LDPC码的现代译码方案。

该算法的主要思想在于利用接收到的软信息在变量节点和校验节点之间进行迭代运算，从而获得最大的编码增益，因此具有很好的性能。BP译码算法的迭代过程分为校验节点的信息更新和变量节点的信息更新。如图1所示，H为校验矩阵，t为迭代次数，完成一次迭代过程时，按照“若校验节点传递到变量节点的信息mc→v>0，则c＾=1，否则c＾=0”的规则进行译码判决。 在此迭代过程中，如果译码成功，译码过程立即结束而不是进行固定次数的迭代，有效地减少了算法的迭代次数，降低了运算复杂度。而且如果算法在预先限定的最大迭代次数tmax到达后仍未找到有效的译码结果，译码器将报错，这时的译码错误为“可检测的”。同时由于BP算法是一种并行算法，在硬件中的并行实现能够极大地提高译码速度。

2.2 RBP译码算法[6]

图1 BP译码算法流程图

LDPC译码的置信传播算法是通过变量节点和校验节点之间的消息迭代来实现的。设一个码长为N的LDPC 码，码字 V={v1，v2，v3，…，vN}表示一组信息节点{vj:j=1，2，3，…，N}，{ci:i=1，2，3，…，M}表示一组校验节点，节点间传递的信息为m，mk为传递的第k个信息。任意的校验节点ci与其相邻的变量节点vj传递信息的方程为

式中：CvJ=ln（p（yj|vj=1）/p（yj|vj=0）），为变量节点 vj的对数似然比，yi是信号译码器的接收序列。

RBP译码算法是一种动态调度的译码算法[7]，节点开始迭代时的最大残余随着迭代次数的增加逐渐减小至零，因此残余的值越大说明此消息还未被收敛，先处理这样的消息会加速译码。对于消息mk来说，其残余为

式中：fk（m）为变量节点k在更新后的对数似然比。

RBP算法可以概括为以下3个步骤：1）假设mci→vj的残余最大，则首先对mci→vj进行更新，此时设置该信息残余为零。 2）计算 mvj→ca的残余 r（mvj→ca），此时 ca∈N（vj）ci。3）计算 mca→vb的残余 r（mca→vb），此时 vb∈N（ca）vj，然后根据校验节点传向变量节点的信息更新前后的差异对将要更新的信息进行排序。

尽管RBP算法是一种有效的动态调度方案，由Vila casado等人应用到LDPC码上，但在误码率性能和复杂度方面不甚理想。RBP算法因其贪婪特性[5]会产生新的错误，这在非动态的译码方案中不会出现。在复杂度方面，当一个校验节点到变量节点更新时，mc→v不必重新计算信息量，因为在r（mc→v）确定时其值已经确定。另外，在译码算法最后，每个边缘残余被计算时，残余信息序列Q都会被重新排序，这样就增加了译码复杂度。

因此，RBP 译码算法流程为：1）初始化 1，mc→v=0；2）初始化 2，mvn→c=Cn；3）计算 r（mc→v）和生成 Q；4）mci→vj为Q 的首次传递信息；5）得到mci→vj迭代传递；6）令 r（mvj→ci）=0，重新排序Q；7）获得与变量节点j相连的除去i节点的校验节点的集合 ca∈N（vj）ci；8）得到 mvj→ca迭代传递；9）获得校验节点j相连的除去i节点的变量节点集合vb∈N（ca）vj；10）计算 r（mca→vb），重新排序 Q；11）若c＾·HT≠0，返回步骤4）。

2.3 VC-RBP译码算法[6]

VC-RBP译码算法在贪婪特性方面要优于RBP译码算法，主要区别在于VC-RBP的残余是根据变量节点传向校验节点更新信息前后的差异计算出来。与RBP译码算法相比，VC-RBP译码算法的程序少了一步。第一步，VC-RBP 选择相应的边缘最大值r（mvi→cj）并设置为零，然后更新所选边缘连接的校验节点。第二步，先更新mcj→va，va∈N（cj）vi；接着更新mva→cb，cb∈N（Va）cj，根据更新信息的差异计算出 r（mva→cb），与RBP相比可减少译码复杂度。

因此，VC-RBP 译码算法流程为：1）初始化 1，mc→v=0；2）初始化 2，mvn→c=Cn；3）确认 r（mc→v）最大值；4）确认mvi→cj节点；5）设置 r（mvi→cj）=0；6）获得 va∈N（cj）vi；7）得到mcj→va迭代传递；8）获得 cb∈N（va）cj；9）得到 mva→cb迭代传递；10）计算 r（mva→cb）；11）若c＾·HT≠0，返回步骤 3）。

在纠错性能方面，VC-RBP要优于RBP。RBP首先把信息传递给不太可靠的变量节点，因为包含最大残余的信息仅仅基于一个校验方程，这样的贪婪特性会产生新的错误，而纠错需要大量的信息更新。VC-RBP首先传递包含最大残余的信息时是基于全部校验方程的，通过更新以表示校验方程的校验节点和变量节点的信息，从而有效地解决了更新校验节点时的差错平底。

3 仿真结果

采用Matlab工具对提出的LDPC改进译码算法的性能进行了仿真验证，采用IEEE802.16e标准设计的QCLDPC码，在AWGN信道下码长为1024，码率为1/2，迭代次数为10的仿真结果如图2所示。随着信噪比的增大，RBP译码算法和VC-RBP译码算法均比传统的BP译码算法性能优越。迭代次数为10的VC-RBP在误码率为10-4时，与RBP相比有0.28 dB的增益。

4 小结

研究了VC-RBP与RBP和一般的BP译码算法相比具有的优越性能。在同一信噪比的情况下，VC-RBP译码算法性能最优，使LDPC译码算法收敛得更快。

[1]GALLAGER R G.Low-density-parity-check codes[EB/OL].[2010-03-05].http：//www.rle.mit.edu/rgallager/documents/ldpc.pdf.

[2]IEEE802.16e-2005，IEEE standard for Local and me2tropolitan area networks，part 16：air interface for fixed and mobile broadband wireless access systems[S].2006.

[3]杨知行，林之初，王军，等.准循环LDPC码的半并行译码器设计[J].电视技术，2006，30（2）：24-26.

[4]ELIDAN G，MCGRAW I，KOLLER D.Residual belief propagation:informed scheduling for asynchronous message passing[C]//Proc.22 Conf.Uncertainty in Artificial Intelligence.Cambridge：[s.n.]，2006：165-173.

[5]MACKAY D J C，NEAL R M.Near Shannon limit performance of low density parity check codes[J].Electronics Letters，1996，32（18）：1645-1646.

[6]CASADO A I V，GRIOT M，WESEL R D.Improving LDPC decoders via informed dynamic scheduling[EB/OL].[2010-03-06].http：//www.ee.ucla.edu/～csl/files/publications/Improving_LDPC_Decoders_IT-W2007.pdf.

[7]CASADO A I V，GRIOT M，WESEL R D.Informed dynamic scheduling for belief-propagation decoding of LDPC codes[C]//Proc.IEEE ICC 2007.Glasgow，Scotland：IEEE Press，2007：208-213.