LDPC码改进型LBP 译码算法研究

刘明山，王亚忠，刘珊珊

(吉林大学通信工程学院，长春130022)

LDPC码改进型LBP 译码算法研究

刘明山，王亚忠，刘珊珊

(吉林大学通信工程学院，长春130022)

针对LDPC(Low Density Parity Check)码分层(LBP:Layered Belief-Propagation)译码算法计算复杂度高、不易于硬件实现的问题，提出一种改进算法。该算法首先引入函数f(x)使LBP译码算法的计算复杂度大大降低;同时引入具体参数校正因子和偏移因子，提升译码性能。仿真结果表明，改进后的算法相比LBP算法在计算复杂度降低的同时，也提升了译码性能，从而达到了易于硬件实现的目的。

LDPC码;BP译码算法;最小和译码算法;分层译码算法

0 引 言

低密度奇偶校验码［1］(LDPC:Low Density Parity Check)属于线性分组码的一种，LDPC码的校验矩阵是一种低密度矩阵，可构造出低复杂度、高性能的LDPC码，由于其描述简单、吞吐量高并具有优越的编译码性能［2-8］，已经吸引了众多研究者的目光，成为下一代宽带移动通信系统的主要备选方案。

因此，高效的硬件实现LDPC译码器的设计已经成为一个重要的课题，中国移动多媒体广播(CMMB:China Mobile Multimedia Broadcasting)中的信道编码使用的也是LDPC码。除此之外，LDPC码将在深空通信、光纤通信、移动和固定无线及声频传播等领域中得到广泛应用。

目前主要有两大类译码方法，第1种是基于校验和统计迭代的比特翻转译码算法，简称BF算法;第2种是基于概率的置信传播迭代译码算法，简称BP算法。

LDPC码基于软消息判决的译码算法都是以BP译码算法为基础。BP译码算法可以分为两种:概率BP译码算法和对数似然比(LLR:Log-Likelihood Ratio)BP译码算法。这两种算法的本质一样，只是消息的表现形式不同。后续研究人们提出多种改进算法，或是降低译码算法的计算复杂度，如最小和(MS:Min-Sum)算法;或是提高译码算法的性能，如分层(LBP:Layered Belief-Propagation)算法、Shuffled BP算法［2］，它们都是在BP译码算法基础上的改进。

笔者在LBP算法基础上提出一种改进算法，首先引入函数f(x)使LBP算法的计算复杂度大大降低，这必然会带来译码性能的降低，然后引入具体参数校正因子和偏移因子，可以降低引入f(x)后因近似计算所带来的误差，从而提升译码性能。通过仿真表明，改进的算法相比LBP算法在计算复杂度降低的同时，也提升了译码性能，易于硬件实现。

1 LDPC码

LDPC码是一种优秀的线性分组码。设线性分组码LDPC的码长为n，k为线性分组码的信息位长度，n-k为线性分组码的校验位长度，H为线性分组码的校验矩阵，H矩阵的维数为m×n。H矩阵的每行和一个校验方程相对应，每列和码字的位相对应［3］。H中只有很少数的非零元素“1”，其余的都是元素“0”，即非零元素的密度很低，因此称作低密度校验码。

LDPC码可由其校验矩阵定义。如果校验矩阵的码长为N，其每列都有固定数量的非零元素，并且每列都有 dv个;其每行也有固定数量的非零元素，并且每行都有 dc个，则 H可记为(N，dv，dc)。(10，3，6)的规则LDPC码

相应的校验方程式

LDPC码可以用二分因子图［4］表示，二分因子图可以生动地描述LDPC码的编译码特性。每个Tanner图和其相应的校验矩阵直接对应，式(1)所示校验矩阵对应的Tanner图如图1所示。

图1 规则LDPC码二分图Fig.1 Tanner of regular LDPC

LDPC码基于软判决的BP类译码算法核心思想是:在每次的迭代过程中得到判决序列，然后开始下一轮的迭代，直到所有校验方程都满足，或达到最大迭代次数，则译码结束。

2 常见译码算法

2.1 LLR BP算法

设信号经过信道传输和输入信号经过BPSK调制信号的过程中［5-8］，每个码字c=(c1，c2，…，cn)映射为序列x=(x1，x2，…，xn)，输入序列x经过传输信道，所接收到的序列为y=(y1，y2，…，yn)。再根据得到的y进行译码，最终得到的译码序列为^c。

为了便于描述，定义以下符号:M为校验节点个数;为变量节点个数;N(ci)/vj表示与校验节点ci相连的比特节点的集合除以比特节点表示校验节点向比特节点传递的信息;表示比特节点vj向校验节点ci传递的信息;mvj表示比特节点vj的后验概率信息;Cvj表示比特节点vj从信道接收的对数似然信息。

LLR BP译码算法［5］步骤如下。

1)初始化。设定最大迭代次数Imax

2)迭代处理。

①校验节点消息处理。计算变量节点传向校验节点的消息

②变量节点的消息处理。计算变量节点传向校验节点的消息

③译码判决。对所有变量节点计算硬判决消息

如果mvj＞0，则=0，否则，=1。

3)停止。

LLR BP译码算法能有效地提高译码速度，降低译码延时［9-12］。因为其迭代过程是并行实现的。然而该算法引入了tanh函数，而tanh函数计算很复杂，并且要占用很多硬件资源，所以译码器电路非常复杂，不利于硬件实现。

2.2 最小和算法

最小和算法［6］在UP-BP算法的基础上进行了改进，主要对LLR BP算法中校验节点消息处理的公式做了改进，依据原理是利用tanh(x)、tanh-1(x)奇函数的性质。

最小和算法在处理校验节点消息时只含有比较运算和加法运算，特别适合硬件实现，但同时其译码性能有所降低［10］。

2．3 分层算法

BP算法是一种并行的迭代译码算法，在一次迭代过程中，首先更新所有的校验节点信息，然后更新所有的变量节点信息，而校验节点的更新只能利用上一次迭代过程中的变量节点信息。在这种情况下，分层算法［7］(Layered BP)被提出，分层算法能尽可能早地利用已经更新过的变量节点的信息，从而可以达到加快码字的收敛迭代速度的目的。

LBP算法译码步骤如下。

1)初始化。设定最大迭代次数Imax，

2)迭代步骤:i=0，1，…，M-1。

①校验节点更新

②后验概率更新

LBP算法在迭代过程中和BP算法有明显区别，LBP算法开始时不更新所有的校验节点的信息，而是更新所有校验节点中其中一个校验节点信息，接着找到所有与这个校验节点连接的变量节点，然后更新找到的变量节点信息;上述过程结束后，再更新另一个校验节点信息，所有校验节点信息都更新完毕，这一次的迭代过程才结束［13-15］。

3 改进算法

笔者提出了一种改进型译码算法，新的译码算法把分层译码算法和改进的最小和算法相结合，使校验节点的更新过程简化，降低译码的复杂度，并且提升译码性能。

类似最小和译码算法对LLR BP译码算法的改进，由于tanh函数本身的计算复杂度较高，所以首先引入函数=-ln(tanh(x/2))降低函数的计算复杂度。由于采用了近似计算，使译码性能降低，因此，笔者又引入参数α，为了方便起名为校正因子。对式(9)进行简化

从式(11)可以看出，校验节点更新公式只需进行两个运算:第1个是符号乘积的运算;第2个是最小值的计算。所以类似最小和算法，引入函数的算法虽然能降低计算复杂度且使计算简化，但由于引入了近似计算，必然会使译码性能降低。

为了解决近似计算所带来的性能损失，笔者引入参数校正因子α，由于近似算法使检验节点公式的幅度变大，这里取值0＜α＜1，这样就可以减小校验节点更新时的幅度，使与真实的幅度更加接近。从而使检验节点的更新公式在较低的复杂度和好的性能之间取得一个平衡。

笔者还提出另一种改进算法，在引入f(x)的基础上，引入参数β，为了方便称其为偏移因子，则校验节点的更新公式可以化简为

这种改进方法使模值小于β的校验节点信息为0。为了获得相对最好的译码性能。校正因子和偏移因子应该随着不同的迭代过程以及信噪比的不同做出相应的变化，但实现相当复杂，虽然可以达到最好的译码性能，但是极大地增加了译码复杂度。因此综合权衡，在仿真实验中对所有的校正因子α和偏移因子β都采取统一的参数。为了仿真方便，笔者把改进的译码算法分别称为NLBP和OLBP译码算法。

NLBP、OLBP译码算法和LBP算法在译码过程中仅仅是水平过程不一样，为了比较改进后的算法和LBP算法在计算复杂度上的区别，只需要比较水平过程，NLBP、OLBP译码算法和LBP算法的计算复杂度之间的区别见表1所示。

表1 NLBP、OLBP和LBP算法运算复杂度比较Tab.1 NLBP、OLBP and LBP algorithm computational complexity

表1中仅仅列出了NLBP、OLBP和LBP算法校验节点更新时的计算复杂度，因为NLBP、OLBP算法和LBP算法的其他运算过程一样，把比较运算当作加法运算对待，其中dc表示校验矩阵中每行非零个数，符号「⌉表示取整。通过比较发现，改进后的NLBP、OLBP算法的计算复杂度大大小于改进之前的LBP算法。

4 NLBP、OLBP算法仿真分析

为了验证改进译码算法的性能，以Matlab软件作为平台进行实验仿真，采用BPSK调制、AWGN信道;选用规则LDPC码，它的码长为256，码率R=1/2。对最小和算法(MS)、分层算法(LBP)以及笔者中改进的算法(NLBP、OLBP)进行仿真，比较译码性能。

4.1 α和β对算法性能的影响

信噪比分别取2．0以及3．0时，在α和β取不同值时分别对两种改进的算法(NLBP、OLBP)在最大迭代次数为20时做了算法仿真，得到了误码率性能曲线。图2表示了α在取不同值时(0.65～1.0)对NLBP算法性能的影响，图3表示了β取不同值时(0～0.40)对OLBP算法性能的影响。

图2 α对算法性能影响Fig.2 Effect ofαto algorithm performance

图3 β对算法性能影响Fig.3 Effect ofβto algorithm performance

从图2可以看出，无论在信噪比为2 dB或为3 dB，NLBP算法的误码率都是随着α的逐渐增大先减小后增大，并且α取0.75时算法的性能达到最佳，系统的误码率达到最低。

从图3可以看出，无论在信噪比为2 dB或3 dB，OLBP算法的误码率都是随着β的逐渐增大先减小后增大，并且β取0．10时，算法的性能达到最佳，系统的误码率达到最低。而在β＞0．25时，算法的性能不如改进前的性能，这是因为如果偏移量β取值较大，检验节点的更新公式的幅度会比改进前小。故在NLBP和OLBP算法中，可以将校正因子α和偏移因子β看作常数，其中α=0．75，β=0.10。

4.2 改进后的算法性能比较

最小和算法、分层算法、NLBP(α=0.75)译码算法和OLBP(β=0.10)译码算法在最大迭代次数为10时的误码率性能曲线如图4所示，在最大迭代次数为20时的误码率性能曲线如图5所示。

图4 最大迭代次数10Fig.4 Maximum iteration 10

图5 最大迭代次数20Fig.5 Maximum iteration 20

从图4，图5可以看出，无论最大迭代次数是10还是20，分层算法的性能都要优于最小和算法，而改进后的NLBP和OLBP两种算法的性能都要优于分层算法和最小和算法。而最大迭代次数的不同算法仿真的性能也有所差别，随着最大迭代次数从10增加到20，4种仿真算法的性能都有所提高。

在最大迭代次数为10时，OLBP算法的性能一直优于分层算法，NLBP在性能上一直优于其他3种算法，而最小和算法一直是BBER性能最差的。在BBER=10-2时，NLBP算法比分层算法性能提高了约0.3 dB，OLBP算法也比分层算法性能提高了约0.1 dB;在BBER=10-3时，NLBP算法比分层算法性能提高了约0.5 dB，OLBP算法也比分层算法性能提高了约0.3 dB。在最大迭代次数为20时，NLBP算法和OLBP算法的性能都要优于分层算法和最小和算法，当信噪比小于3.5时，OLBP算法在性能上优于NLBP算法，而在信噪比大于3.5 dB后，NLBP算法在性能上又优于OLBP算法，在BBER=10-3时，NLBP算法比分层算法性能提高了约0.2 dB，OLBP算法也比分层算法性能提高了约0.3 dB;在BBER=10-4时，NLBP算法和OLBP算法的性能相近，都比分层算法的性能提高约0.3 dB。

5 结 语

LDPC码是一种线性分组码，具备很强的纠错能力，当LDPC码的译码算法为并行算法时，在硬件实现时可以实现完全并行的操作。笔者在分层算法和最小和算法的基础上进行了算法的改进，改进的算法通过引入参数改变校验节点消息的更新数据，能有效地降低由于近似计算所带来的误差。改进后的算法和分层算法相比，硬件上只增加了少量的加法器和乘法器，所以解码电路较为简单，易于实现。仿真结果表明，改进的NLBP和OLBP算法相比LBP算法在计算复杂度大大降低的同时，也提升了译码性能，从而达到了易于硬件实现的目的，这使LDPC码具有更好的应用潜力，能更好地应用在光纤通信、卫星数字视频、移动和固定无线等领域中。

［1］GALLAGER R G.Low-Density Parity-Check Codes［J］.IRE Transactions on Information Theory，1962，8(1):21-28.

［2］KSCHISCHANG FR，FREY B J，LOELIGERH A.Factor Graphs and the Sum-Product Algorithm［J］.IEEE Transactions on Information Theory，2001，47(2):498-519.

［3］BERROU A，GLAVIEUX PTHITIMAJSHIMA.Near Shannon Limit Error-Correcting Coding and Decoding:Turbo-Codes［C］∥IEEE International Conference on Communications，1993.ICC 93.Nagaoka，Japan:［s.n.］，1993，2:1064-1070.

［4］TANNER R M.A Recursive Approach to Low Complexity Codes［J］.IEEE Tran on Inform Theory，1981，27(5):533-547.

［5］MACKAY D JC，NEALR M.Near Shannon Limit Performance of Low-Density Parity-Check Codes［J］.Electronics Letters，1996，32(18):1645-1646.

［6］袁东风，张海刚.LDPC码理论与应用［M］.北京:人民邮电出版社，2008. YUAN Dongfeng，ZHANG Haigang. LDPC Code Theory and Application［M］. Beijing: People's Posts and Telecommunications Press，2008.

［7］HOCEVAR D.A Reduced Complexity Decoder Architecture via Layered Decoding of LDPC Codes［C］∥Proc Signal Processing Systems SIPS 2004.Seoul，Korea:［s.n.］，2004:107-112.

［8］HAMMING RW.Error Detecting and Error Correcting Codes［J］.Bell System Technical Journal，1950，29(7):147-160.

［9］傅祖芸.信息论基础理论与应用［M］.北京:电子工业出版社，2001. FU Zuyun.Information Theory-Fundamental Theory and Application［M］.Beijing:Publishing House of Electronics Industry，2001.

［10］王众，祝宇鸿.基于LDPC码的HARQ系统仿真［J］.吉林大学学报:信息科学版，2011，29(5):395-400. WANG Zhong，ZHU Yuhong.HARQ System Simulation Based on LDPC Code［J］.Journal of Jilin University:Information Science Edition，2011，29(5):395-400.

［11］LIU Yuanhua，ZHANG Meiling.Quasi-Cyclic LDPC Codes with High-Rate and Low Error Floor Based on Euclidean Geometries［J］.Journal of China Universities of Posts and Telecommunications，2012，19(2):96-99.

［12］MING Yangyang，YANG Bo.Rate Estimate for Regular LDPCA Codec in Distributed Video Coding［J］.Journal of China Universities of Posts and Telecommunications，2012，19(1):50-54.

［13］WANG Xiuni，MA Xiao.Design of Efficiently Encodable Nonbinary LDPCCodes for Adaptive Coded Modulation［J］.Science China:Information Sciences，2014，57(2):1-11.

［14］LIU Bin，GAO Jun.Weighted Symbol-Flipping Decoding Algorithm for Nonbinary LDPC Codes with Flipping Patterns［J］. Journal of Systems Engineering and Electronics，2011，22(5):848-855.

［15］ZHANG Lijun，LI Bing.Constructions of QC LDPC Codes Based on Integer Sequences［J］.Science China:Information Sciences，2014，57(4):1-14.

(责任编辑:刘东亮)

Research on Modified LBPDecoding Algorithm of LDPC Codes

LIU Mingshan，WANG Yazhong，LIU Shanshan

(College of Communication Engineering，Jilin University，Changchun 130022，China)

To solve the problem of high complexity and difficult implementation in hardware of LBP(Layered Belief-Propagation)algorithm.A modified decoding algorithm is proposed based on LBP algorithm，a function

low density parity check(LDPC)codes;belief propagation(BP)algorithm;min sum algorithm; layered belief propagation algorithm

TN911.22

A

1671-5896(2015)04-0367-06

2014-10-09

刘明山(1965— )，男，山东掖县人，吉林大学副教授，主要从事无线通信、智能信息处理研究，(Tel)86-13504314285 (E-mail)liums@jlu.edu.cn。

f(x)is introduced in the first step in order to reduce its complexity.Specific parameters correction factor and offset factor are introduced in the second step in order to improve its decoding performance.The simulation results demonstrate that the modified decoding algorithm reduces the complexity and improves the decoding performance compared to LBP algorithm which facilitates the hardware.