改进的LDPC码Normalized BP-Based译码算法

文章编号:1001-9081(2012)01-0150-03 doi:10.3724/SP.J.1087.2012.00150

摘 要:为了提高Normalized BP-Based算法的译码性能，提出了一种改进的Normalized BP-Based算法。根据校验节点传向变量节点的信息的大小来动态地改变校正因子，实现对BP-Based算法的非线性补偿。仿真结果表明：在误码率低于0.5×10-2时，与Normalized BP-Based算法相比，改进算法均可以获得约0.1dB的增益，而只增加少量运算，并且不增加迭代次数。

关键词:低密度奇偶校验码；可变校正因子；非线性补偿；迭代译码

中图分类号: TP911.22 文献标志码:A

Abstract: To further improve the decoding performance of the Normalized BP-Based algorithm, an improved Normalized BP-Based algorithm was proposed. The correction factor was changed dynamically according the amount of the information from the check nodes to variable nodes in order to achieve non-linear compensation of BP-Based algorithm. The simulation results show that when the bit error rate was less than 0.5×10-2, the improved algorithms could get about 0.1dB gain, compared with Normalized BP-Based algorithm, only with slight increase in complexity, and the number of iterations did not increase.

Key words: Low Density Parity Check (LDPC) code; variable correction factor; nonlinear compensation; iteration decoding

0 引言

低密度奇偶校验(Low Density Parity Check, LDPC)码是线性分组码的一种［1］，其性能接近香农极限，具有描述简单、译码复杂度低、可以并行实现等优点，并在2003年被欧洲DVB-S2采纳为标准［2］。目前LDPC码的研究主要集中在校验矩阵的构造、译码算法的简化、EXIT(Extrinsic Information Transfer Chart)图的分析［3］、通信与数据存储方面的应用、图像处理方面的应用［4］、LDPC码的硬件实现［5］等几个方面，且取得了有价值的研究成果。LDPC码的译码算法可分为基于硬判决的比特翻转译码和基于软判决的置信传播译码［6］。Gallager最早提出了通用的BP译码算法［1］，为了降低运算复杂度，提出了一些改进算法，包括LLR-BP［1］、BP-Based［7-8］、APP-Based［7］、Normalized BP-based［7］、Offset BP-Based［7］,还有一些利用曲线拟合化简非线性函数［9］。为了提高译码速度，基于差分的译码算法［10］、基于RMP调度的译码算法［11］、分层译码［12］等方法相继提出。Normalized BP-Based算法中校验节点的处理是增加了一个校正因子，是对BP-Based算法进行线性补偿，使之接近LLR BP算法的性能。而LLR BP算法中校验节点的处理是非线性的。针对这一特点提出一种改进型Normalized BP-Based算法，根据校验节点传向变量节点的信息大小来动态地改变校正因子。

1 BP-Based和Normalized BP-Based算法

信号编码后,经过双相移相键控(Binary Phase Shift Keying, BPSK)调制，通过加性高斯白噪声(Additive White Gaussian Noise, AWGN)信道，接收到的信号为y=［y1,y2,y3,…］,BP-Based算法的译码步骤如下。

1)初始化。变量节点传向校验节点的初始信息L(0)(qij)=2y/σ2，其中σ2为噪声方差。

2)迭代处理。

步骤1 对检验节点j和与其相邻的变量节点i∈R(j)，第l次迭代时，变量节点传向校验节点的消息：

L(l)(rji)=2∏i′∈Rj\isgn(L(l－1)(qi′j))•tanh－1(∏i′∈Rj\itanh(12L(l－1)(qi′j)))(1)

即：

L(l)(rji)=∏i′∈Rj\isgn(L(l－1)(qi′j))•f(∑i′∈Rj\i f(L(l－1)(qi′j)))(2)

即：

L(l)(rji)≈∏i′∈Rj\isgn(L(l－1)(qi′j))•f(maxi′∈Rj\i f(L(l－1)(qi′j)))=∏i′∈Rj\isgn(L(l－1)(qi′j))•mini′∈Rj\iL(l－1)(qi′j)

其中f(|x|)=lne|x|+1e|x|－1=－ln tanh(|x|/2)。式(1)为LLR BP(tanh-ruln)算法，式(2)为LLR BP(Gallager)算法。

步骤2 对变量节点i和与其相邻的检验节点j∈C(i)，第l次迭代时，校验节点传向变量节点的消息：

L(l)(qij)=L(0)(qij)+∑j′∈Ci\jL(l)(rj′i)

步骤3 译码判决。计算硬判决消息：

L(l)(qi )=L(0)(qi j ) + ∏j∈Ci L(l)(rji )

若L(l)(qi)>0，则i=0；否则i=1。

3)停止。若H T=0，或者达到最大迭代次数，则结束运算；否则继续迭代。

若校验消息表示为：

L(l)(rji)=α•∏i′∈Rj\isgn(L(l－1)(qi′j))•mini′∈Rj\iL(l－1)(qi′j)(3)

其中α

2 改进的译码算法

BP-Based算法是用f(x)的最大值来替代∑xf(x)，会造成很大误差。式(2)是求∑i′∈Rj\i f(L(l－1)(qi′j))。因为f(x)是x的单调递减函数，而且当x越小时， f(x)的斜率越大。如果L(l－1)(qi′j)大多数较小，则其和∑i′∈Rj\i f(L(l－1)(qi′j))应该较大此处是否应该为“较小”？请仔细核实。，此时与maxi′∈Rj\i f(L(l－1)(qi′j)的误差也较大，应该补偿较小的校正因子；同理，如果L(l－1)(qi′j)(i′∈R(j))的值大多数较大，则应该补偿较大的校正因子。

改进的算法主要是对Normalized BP-Based算法中的L(rji)进行改进，其他步骤同上，改进部分如下。

当L(l－1)(qij)(i∈R(j))的均值小于1时，取：

L(l)(rji)=β•∏i′∈Rj\isgn(L(l－1)(qi′j))•mini′∈Rj\iL(l－1)(qi′j)(4)

当L(l－1)(qij)(i∈R(j))的均值大于1.8时，取：

L(l)(rji)=γ•∏i′∈Rj\isgn(L(l－1)(qi′j))•mini′∈Rj\iL(l－1)(qi′j)(5)

当L(l－1)(qij)(i∈R(j))的均值大于等于1而小于等于1.8时，取：

L(l)(rji)=α•∏i′∈Rj\isgn(L(l－1)(qi′j))•mini′∈Rj\iL(l－1)(qi′j)(6)

其中：α, β,γ均小于1，称为校正因子；α取值等于Normalized BP-Based算法中的α。

3 仿真与讨论

仿真条件如下。

1)Gallager随机构造法［13］产生校验矩阵H，N=408，K=204，M=204，码率R=0.5，列重为3，行重为6，随机种子此处是否应该为“随机种子数”？请明确。为884；

2)AWGN传输，BPSK调制；

3)每个信噪比(Signal-to-Noise Ratio, SNR)点采集500帧数据。

3.1 分类依据

将L(l－1)(qij)(i∈R(j))的均值按照小于1，大于等于1且小于等于1.8这个条件是否应该改为“大于1小于1.8”呢？如果是，那么“等于1”和“等于1.8”时，又归属于哪个阶段，请标明。，大于1.8这样进行分类的依据，选取一帧数据对L(l－1)(qij)(i∈R(j))进行分析。

图1~2中，标识符为“•”表示L(l－1)(qij)(i∈R(j))的均值；“×”表示L(l－1)(qij)(i∈R(j))的方差。从图1和图2可知L(l－1)(qij)(i∈R(j))有很多值都落在(0,2.5)。当方差很小的时候，均值很大。另外仿真时还发现在信噪比为1的时候也会出现类似于图2那样方差较小，均值较大的情况。当方差接近0时，均值很大。根据前面的分析可知：L(l－1)(qij)(i∈R(j))的均值较大，方差几乎为0的这部分数对误差的影响相对较小，而位于(0,2.5)的数对误差的影响相对较大；并且(0,2.5)的数越小，对误差的影响越大。

所以可以将L(l－1)(qij)(i∈R(j))的均值按照小于1、大于等于1且小于等于1.8、大于1.8这样进行分类,显然这不是唯一的分类方法。

3.2 确定α, β,γ的值

首先确定α的值，改进算法中α的值就是Normalized BP-Based算法中α的值，从图3中可以看出α取0.8。

其次确定β,γ的值。通过上面的分析，可知β应该不大于0.8，γ应该不小于0.8。这里用实验法。 β从0.5取到0.75， β,γ从0.8取到0.95，迭代次数选50次进行仿真。从表1中可以看出β取0.5,γ取0.85。

3.3 误码率分析

图4是α=0.8， β=0.5，γ=0.85的改进算法与Normalized BP-Based算法，LLR BP算法在相同迭代次数下性能比较。可以看出，当迭代50次时，改进算法的误码性能超过了Normalized BP-Based算法。在误码率(Bit Error Ratio, BER)为10-3时，与Normalized BP-Based算法相比，可获得约0.1dB的增益；与LLR BP算法相比，可以获得约0.3dB的增益。

图5给出了在最大迭代次数为50的条件下,各种算法所需要的平均迭代次数。从图5中可以看出，改进算法的平均迭代次数与Normalized BP-Based算法基本一致。

3.4 运算量和复杂度分析

改进算法改进的是校验节点的部分，所以复杂度比较只需要比较检验节点更新这部分的运算复杂度。各个算法的复杂度见表2，其中dc表示的是校验节点的度。

算法校验节点更新公式乘法次数加法次数特殊运算

LLR-BP(tanh-ruln)算法括号中是什么意思，请说明。式(1)2dcdc tanh (x),dc tanh h－1(x)

LLR-BP(Gallager)算法式(2)2dc2dcf(x)

Normalized BP-Based算法式(3)2dc+［lg dc］－2log的底是多少，请补充。

改进算法式(4)~(6)32dc+［lg dc］－3

改进算法每一个检验节点的更新，比Normalized BP-Based算法多了一个求均值计算。即多了一次乘法运算，dc-1次加法运算。当dc较大时，改进算法复杂度较大，所以规定dc≤6。

4 结语

改进的Normalized BP-Based译码算法，是根据校验节点传向变量节点信息的大小来选择不同的校正因子。与LLR BP算法和Normalized BP-Based算法相比，改进算法能够在不增加迭代次数的情况下获得较好的译码性能，而只增加少量运算。该算法只适合于校验节点度数不大于6的码，其他码该如何分类，需要进一步研究。

参考文献:

[1]

GALLAGER R G. Low-density-parity-check codes ［J］. IER Transactions on Information Theory, 1962, 8(1): 21-28.

[2]

European Telecommunications Standards Institute. ETSI EN 302 307 V1.1.1, DVB-S2 standard draft ［S］. New York: Springer, 2004.

[3]

毛倩，董德存，曹小清.一种AWGN信道下非规则LDPC码的优化方法［J］.计算机应用，2010，30(2)：292-294.

[4]

任通华，李晓峰，谢仕云，等.LDPC码的不等差错保护策略在SVC中的应用［J］.计算机应用，2011，31(1)：270-272.

[5]

KIM S, SOBELMAN G E, LEE H. A reduced-complexity architecture for LDPC layered decoding schemes ［J］. IEEE Transactions on Very Large Scale Integration Systems, 2011, 19(6): 1099-1103.

[6]

谢东觉，张兴敢，唐岚.一种改进的LDPC码多比特翻转译码算法［J］.现代电子技术，2011，34(3)：11-13.

[7]

袁东风，张海刚.LDPC码理论与应用［M］.北京：人民邮电出版社，2008.

[8]

KOU Y, LIN S, FOSSORIER M P C. Low-density parity-cheek codes based on finite geometries: A rediscovery and new results ［J］. IEEE Transactions on Information Theory, 2001, 47(7): 2711-2736.

[9]

贾向东,蔡德林,谢伟.性能接近最优的LDPC码LLR-BP简化译码算法［J］.信息技术，2007(10)：70-73.

[10]

吴湛击，傅婷婷，王文博.LDPC码的高效译码算法研究［J］.系统工程与电子技术学报，2010，32(3)：603-608.

[11]

陈旭灿，刘冬培.改进的LDPC译码算法研究［J］.电子科技大学学报，2010，39(2):219-222.

[12]

GUO KUN, HEI YONG, QIAO SHUSHAN. A parallel-layered belief-propagation decoder for non-layered LDPC codes ［J］. Journal of Communications, 2010, 5(5): 400-408.

[13]

MACKAY D J C. Encyclopedia of spare graph codes ［EB/OL］. ［2010-02-23］. .

收稿日期:2011-07-06;修回日期:2011-09-05。

作者简介:

张小花(1986-)，女，河南巩义人，硕士研究生，主要研究方向：通信信号处理、嵌入式系统； 李艳萍（1963-），女，山西太原人，教授，博士，主要研究方向：移动通信、光通信。