基于高斯近似的LDPC码TDMP算法分析

王秀敏,曹维林,单 良,洪 波,李劲松

(中国计量大学 信息工程学院,浙江 杭州 310018)

基于高斯近似的LDPC码TDMP算法分析

王秀敏,曹维林,单 良,洪 波,李劲松

(中国计量大学 信息工程学院,浙江 杭州 310018)

针对目前缺少对LDPC码TDMP算法理论分析的问题,提出了TDMP算法的高斯近似.基于BP算法和对称条件,得到结果收敛的TDMP算法的高斯近似.利用高斯近似来分析TDMP算法的译码收敛性,为论证TDMP算法的优越性能提供了理论依据.基于Wimax标准,分别对BP算法和TDMP算法的高斯近似进行仿真.仿真结果表明,在相同情况下,TDMP算法译码收敛速度更快,需要的迭代次数更少.同时，给出了TDMP算法分别采用高斯近似和密度进化时的门限值,它们的差别仅为0.03～0.08 dB.

LDPC码;高斯近似;TDMP算法;收敛速度;门限值

LDPC码[1-2]是Gallager在1962年首次提出来的.1996年,D MacKay,M Neal等人[3]LDPC码重新进行了研究,发现LDPC码具有逼近Shannon极限且实现复杂度低的优异性能,并在Gallager的概率迭代译码算法的基础上,提出了BP算法[4],使得LDPC码的研究跨入了一个新的阶段,成为了信道编码理论的研究热点.

Richardson等人基于Gallager的思想,引入了密度进化[4]的概念,密度进化可以用来计算LDPC码消息传递译码时的容量,即信道参数的门限值[6-7].也就是说,会存在一个噪声功率σ*,当噪声功率大于σ*时,无论迭代多少次,误码率一定大于某一个正常数;当噪声功率小于σ*时,只要迭代次数足够多,误码率最终会趋向无穷小.于是，这个噪声功率σ*就是门限值.对于Binary input additive white gaussian noise(BIAWGN)信道,可以用高斯近似[8]代替密度进化,以简化译码算法的分析.BP算法是LDPC码译码的基本算法,虽然该算法能够获得接近Shannon限的误码率性能,但是迭代过程中的校验节点需要处理多次非线性运算,所以BP算法的实现复杂度较高.随着对译码算法研究的进一步深入,Mansour和Shanbhag提出了TDMP的分层译码算法[8-10].TDMP的分层译码算法在获得高吞吐率的同时可以加快迭代译码的收敛速度,最好的情况下,可以比BP算法减少一半的平均迭代次数.

Mansour在文献[10]中,利用EXIT图分析了TDMP算法的译码收敛性.而本文是在研究BP算法高斯近似的基础上,提出了TDMP算法的高斯近似,从高斯近似的角度来分析TDMP算法的译码收敛性,从而为论证TDMP算法的优越性能提供更多的理论依据;并在Wimax标准下,对LDPC码进行仿真,得到BP算法和TDMP算法高斯近似的性能曲线,从而验证了TDMP算法收敛速度更快.

1 BP算法的高斯近似

对于(dv,dc)规则LDPC码,校验节点消息和变量节点消息的迭代表示[5]分别如式(1)和(2):

(1)

(2)

已知均值为m,方差为σ2的高斯分布,在对称条件下可简化为σ2=2m[5],又由于高斯分布可以完全由其均值和方差决定,所以在迭代的过程中,只需考虑均值m.

(3)

(4)

其中,φ(x)的表达式如式(5)[8]:φ(x)=

(5)

规则和非规则LDPC码的误码率的计算都如式(6)[8]:

(6)

2 TDMP算法的高斯近似分析

TDMP算法的核心是对每个分层依次译码.在进行迭代译码时,下一层消息的更新可以直接使用上一层更新后的消息,这加快了译码的收敛速度.但是,这种分层译码算法的本质是优化消息传递的流程,并没有改变每一层水平消息更新算法的具体实现方式,因此BP算法也是适用于分层译码的.接下来对TDMP算法高斯近似的分析就是基于BP算法的.每一层水平消息更新的分析同BP算法校验节点消息的更新,而BP算法校验节点消息更新这部分内容在第1节中已经介绍过了,所以,接下来重点在于变量节点消息更新这部分内容.

(7)

(8)

根据对称性条件中的校验节点对称,式(8)右边可写成式(9)形式[13]:

(9)

(10)

对式(7)和式(10)左右两边同时取期望,得:

(11)

(12)

3 仿真结果分析

图1 BP算法时6种码率的误码率性能Figure 1 BER of BP algorithm at 6 code rates

Wimax标准定义了1/2、2/3A、2/3B、3/4A、3/4B和5/6共6种不同码率的LDPC码.在BIAWGN信道下,对这6种码率的LDPC码进行了仿真计算,BP算法时,最大迭代次数设为20,TDMP算法时,最大迭代次数设为10.

图1和图2分别为BP算法和TDMP算法在6种码率下的LDPC码高斯近似的性能曲线图,其中1/2码率信噪比取值区间为0～2.5 dB,2/3A和2/3B码率信噪比取值区间为0.5～3.0 dB,3/4A和3/4B码率信噪比取值区间为1.0～3.5 dB,5/6码率信噪比取值区间为1.5～4.0 dB.

图2 TDMP算法时6种码率的误码率性能Figure 2 BER of TDMP algorithm at 6 code rates

选择码率为1/2,信噪比为1.5 dB时进行详细讨论,此时BP算法和TDMP算法误码率与迭代次数的关系如图3.从图3中可以看出,TDMP算法的收敛速度比BP算法快,并且误码率都低于某一个误码率,例如10-5时,BP算法大约需要迭代8次,而TDMP算法只需4次.

图3 误码率与迭代次数的关系Figure 3 Relationship between BER and iterations

图4表示码率为1/2时,在不同信噪比下,达到期望误码率(设为10-5)时,BP算法和TDMP算法各需要的迭代次数.从图4中可以看出,当信噪比分别为0和0.5 dB时,在最大迭代次数内,BP算法和TDMP算法都达不到设定的期望误码率.当信噪比大于0.5 dB时,TDMP算法所需的迭代次数都比BP算法少,最好情况下,TDMP算法所需的迭代次数比BP算法少一半.

图4 不同信噪比下达到期望误码率时所需的迭代次数Figure 4 Iterations for reaching to excepted BER under different SNR

图3和图4的仿真结果表明,我们可以从高斯近似的角度证明TDMP算法比BP算法译码收敛速度更快,平均迭代次数更少.

4 门限值分析

信道参数具有一个门限值,门限值一般是指噪声功率.给定LDPC码度的分布、期望误码率、迭代次数,找到一个最大的噪声功率σ*,当噪声功率超过σ*时,在设定的迭带次数内,误码率无法达到期望误码率;当噪声功率小于σ*时,在设定迭带次数内,误码率都小于σ*.门限值也称为码容量,表示LDPC码能容忍的信道环境的恶劣程度,它是评价LDPC码的一个重要标准.

门限值计算流程图如图5[7],其中M表示设定的最大迭代次数,Pe表示设定的期望误码率,nstep1和nstep2分别表示噪声功率增加和减少的步长,nstart表示设定的初始噪声功率,n表示当前噪声功率,l表示当前的迭代次数,Pl表示第l次迭代时的误码率.

图5 门限值计算流程图Figure 5 Flow chart of calculating thresholds

Wimax标准下6种码率的LDPC码在BIAWGN信道下,TDMP算法分别采用密度进化和高斯近似时的门限值如表1.其中r为码率,σ1表示密度进化时TDMP算法的门限值,σ2表示高斯近似时TDMP算法的门限值,Δs表示σ1和σ2之间的距离,Δs的计算公式如式(13)[7]:

(13)

采用高斯近似,可将高维校验节点消息和变量节点消息的密度进化简化为一维的均值进化,可以很大地降低计算量.并且从表1可以看出,采用高斯近似计算出的门限值与采用密度进化计算出的门限值只有0.03～0.08 dB的差距.从而说明,在性能损失非常小的前提下,采用高斯近似可以更加容易地分析和计算信道参数的门限值.

表1 TDMP算法高斯近似和密度进化门限值

5 结 语

本文在研究BP算法高斯近似的基础上,提出了TDMP算法的高斯近似,并基于Wimax标准,对LDPC码的BP算法和TDMP算法进行仿真,从高斯近似的角度,证明了TDMP算法比BP算法译码收敛速度更快,平均迭代次数更少.同时,采用高斯近似的方法,可以更加方便地分析和计算信道参数的门限值.从而也给出了TDMP算法高斯近似和密度进化的门限值,它们的差别仅为0.03～0.08 dB.本文提出的TDMP算法的高斯近似也适用于其他标准.

[1] GALLAGER R. Low-density parity-check codes[J].IRE Transactions on Information Theory,1962,8(1):21-28.

[2] 王秀敏,洪芳菲,单良,等.LDPC/Turbo双模译码器技术发展与前景综述[J].中国计量学院学报,2016,27(1):63-67. WANG X M, HONG F F, SHAN L, et al. The advance overview on LDCP/Turbo dual-mode decoders[J].Journal of China University of Metrology,2016,27(1):63-67.

[3] MACKAY D J C, NEAL R M. Near Shannon limit performance of low density parity check codes[J].Electric Lett,1996,32:1645-1646.

[4] MACKAY D J C. Good error-correcting codes based on very sparse matrices[J].IEEE Trans on Information Theory,1999,45(2):399-431.

[5] RICHARDSON T J, URBANKE R L. The capacity of low-density parity-check codes under message-passing decoding[J].IEEE Transaction on Information Theory,2001,47:599-618.

[6] 肖娟,王琳,邓礼钊.不规则LDPC码的密度进化方法及其门限值确定[J].电子与信息学报,2005,27(4):617-620. XIAO J, WANG L, DENG L Z. Density evolution method and threshold decision for irregular LDPC codes[J].Journal of Electronics and Information Technology,2005,27(4):617-620.

[7] 袁东风,张海刚.LDPC码理论与研究[M].北京:人民邮电出版社,2008:122-123.

[8] CHUNG S Y, RICHARDSON T J, URBANKE R L. Analysis of sum-product decoding of low-density parity-check codes using a gaussian approximation[J].IEEE Transaction on Information Theory,2001,47:657-670.

[9] HOCEVAR D E. A reduced complexity decoder architecture via layered decoding of LDPC codes[C]//IEEE Workshop on Signal Processing Systems. Austin: IEEE,2004:107-112.

[10] MANSOUR M M. A Turbo-decoding message-passing algorithm for sparse parity-check matrix codes[J].IEEE Transaction on Signal Processing,2006,54(11):4376-4392.

[11] SUN Y, CAVALLARO J R. A flexible LDPC/Turbo decoder architecture[J].Journal of Signal Processing Systems,2011,64(1):1-16.

[12] ZEINEDDINE H, MANSOUR M M. A reconfigurable TDMP decoder for raptor codes[J].Journal of Signal Processing Systems,2012,69(3):293-304.

[13] 洪芳菲.基于DDE理论的LDPC双模译码器研究[D].杭州:中国计量大学,2016. HONG F F. The Research of dual-mode LDPC decoder based on DDE[D].Hangzhou: China Jiliang University,2016.

Analysis of TDMP algorithm of LDPC codes based on GA

WANG Xiumin, CAO Weilin, SHAN Liang, HONG Bo, LI Jinsong
(College of Information Engineering, China Jiliang University, Hangzhou 310018, China)

To solve the problem of lacking of a theoretical analysis of TDMP algorithm of LDPC codes, the Gaussian Approximation(GA) of TDMP algorithm was proposed. Based on BP algorithm and symmetry conditions, the convergent GA of TDMP algorithm could be obtained. When using GA to analyze the decoding convergence of TDMP algorithm, the theoretical basis for proving the superiority of TDMP algorithm could be provided. GAs of BP algorithm and TDMP algorithm were simulated based on the Wimax standard respectively. Simulation results show that the decoding convergence speed of TDMP algorithm is faster and its number of iterations is fewer compared with BP algorithm under the same condition. Meanwhile, the thresholds of GA and Density Evolution(DE) of TDMP algorithm were presented respectively. The gap of thresholds between GA and DE was 0.03～0.08 dB.

LDPC codes; Gaussian approximation; TDMP algorithm; convergence speed; threshold

2096-2835(2017)01-0076-05

10.3969/j.issn.2096-2835.2017.01.013

2016-12-21 《中国计量大学学报》网址：zgjl.cbpt.cnki.net

国家自然科学基金资助项目(No.61379027),国家自然科学青年基金资助项目(No.51404223),浙江省自然科学青年基金资助项目(No.LQ14E060003).

王秀敏(1963- )，女，辽宁省锦州人，教授，主要研究方向为电子信息与通信.E-mail:wxm6341@163.com

TN91

A