LDPC的BP译码算法

1、 课程名称：现代编码理论 任课教师：王琳洪少华 论文题目：LDPC码的BP译码算法 姓名：曹沙沙赵卜寒 学号：学32013115324323320131153274 2014年07月06日目录 摘要II. AbstractIII 第一章LDPC码的概述1 1.1 LDPC码的发展史1 1.2 、LDPC的表示1 1.3 二进制LDPC的编码方法3 1.3.1 校验矩阵的生成3 1.3.2 编码算法4 第二章LDPC码译码算法6. 1.1 . Gallager概率译码基本思路6 1.2 BP算法研究8 1.3 用对数似然比表示的BP算法11 第三章LDPC的性能分析14 LDPC的仿真模型14

2、LDPC的译码性能15 码长对性能的影响15 迭代次数对译码性能的影响16 结论18 参考文献H9摘要 低密度奇偶校验码是Gallager提出的一种线性分组码，其性能可以非常接近香农极限。 它是根据低密度稀疏校验矩阵H和二分图来构造的， 本文详细的阐述了二进制，规则的LDPC勺BP译码算法，其校验矩阵每一行和每一列的1的个数是相同的，分别为p和q,其Tanner图中比特节点的度和校验节点的度分别对应着一个固定值，通常用(min,p,q)表示。BP译码算法是一种迭代的概率译码算法，本文着重于BP译码算法及其简化运算。 本论文主要介绍了LDPCK的构造、编码和译码基本原理。阐述了LDP诉译码的过程

3、，并通过MATLAB&真工具对LDPCK在AWG陆道的误比特率性能进行了仿真，分析了信噪比、码长和迭代次数对误比特率性能的影响。 关键词：二进制LDPCBP算法迭代概率译码后验概率Abstract LowDensityParityCheck(LDPC)codesareaclassoflinearblockcodesproposedbyGallager,whichperformatarateextremelyclosedtotheShannoncapacity.Itisbasedonlow-densityparitycheckmatrixHandsparsebipartitegraphi

4、sconstructed,thepaperelaboratedbinary,LDPCdecodingalgorithmofBPrule,thenumberofoneofitscheckmatrixeachrowandeachcolumnisthesame,respectively,pandq,theTannergraphofbitnodesandchecknodesofdegreecorrespondstoafixedvalue,respectively,usuallyexpressedas(m,n,p,q).BPdecodingalgorithmistheprobabilityofanite

5、rativedecodingalgorithm,Thispaperfocusesonitssimplifiedoperation. Thispaperdescribesthestructure,thebasicprinciplesoftheencodinganddecodingofLDPCcodes.DescribestheLDPCencodinganddecodingprocess,andthroughMATLABsimulationtoolforLDPCcodesinthebiterrorrateperformanceAWGNchannelsimulation,analysisofthei

6、mpactofsignaltonoiseratio,codelengthandnumberofiterationsofthebiterrorrateperformance. Keywords:binaryLDPCBP-decodingalgorithmiterativeprobabilityposteriorprobability第一章LDPC码的概述 LDPC码的发展史 1、1963年，Gallager发现的LDPCB被称作古典码型：规则LDPC 199外,MacKayandSpielman发明了不规贝U的LDPC 3、RichardsonandUrbanke开创了用译码分析设计码型的方法。

7、 4、针对B-LDPC码优异的纠错性能，M.Davey和D.Mackay进一步将B-LDPC码一般化到多进制域上，并且研究结果表明Q-LDPC码在低码率(R0.50.5, ,则判X Xl,(l=1,2,.,N). A 若HTX=0,或者迭代次数达到最大迭代次数，则结束迭代，把输出，否则转到步骤(2)继续迭代。 2.3用对数似然比表示的BP算法 上述介绍的BP算法比较复杂。一方面该算法需要在每个变量节点和校验 XX 节点分别计算各比特为0或者为1的概率，并且在计算心和q ql时，要选择合适的系数“ml和1使之满足概率和为1的条件；另一方面，算法的表述太过复杂，采用很多相乘运算，耗费较多的运算时间

8、和硬件资源，不利于硬件实现。采用对数似然比描述的BP算法会有一个非常简单明了的形式。 考虑一个随机变量X,它的对数似然比L(X)定义为 L(x)=ln3) P(X)1) 根据对数似然比的定义，令 f0 0l v=lnTT fl 0 Vml二ln乎 qml v=lnq7 l1 q 0 r. Uml=ln不 r 1ml A X作为译码 那么根据式(2.2)和(2.3)得 01 qmlTml 01 qml7ml l ,J/、1I/1x tanh（x）=.ln（） 因为反曲正切函数21-x在开区间（-1.1）内单调增加，是 关于原点对称的奇函数。这样上式变为简洁形式: Uml=ln 1-II 1 1r

9、uml=2tanh l ”(q：l4)fL(ml 因为 qml+qml=1,上式右端各项除以 0.1 口同qml,右端各项分母 1 再除以qml,可得下式: 0qml 1 1qml uml2tanhH 三L(mlqml qml -1 1r uml=2tanh再 引用Vml的定义得下式： n ld_(m ev-1 4 eml.1 这里为了使形式更简洁，引用双曲正切函数: sh(x)e-etanh(x)=-x ch(x)ee 同理有:它是在（.已*）内单调增加，函数值三（1,1）,以 y=+1,-1为渐近线，关于原点 对称的奇函数。最后得到: 1tanhuml=2tanh2 一 l二L(ml (2

10、.12) 根据式（1.8）和（1.9）有 Vml=Vl umim二M(lm (2.13) 0- Vl=V|uml m三M(l) BP算法的步骤整理如下：对于校验矩阵元素hmlhml=1=1 的m,l执行如下步骤运 _0 (1)初始化：Vml=vl Vml tanh 2 l (2)校验节点更新: (5)比特判决：如果Vl0Vl0, ,则判XlXl=0;=0;否则判x x=1,=1,(l=1,2,.,N) 若HTx=0,或者迭代次数达到最大迭代次数,则结束迭代,把x作为译码输出,否则转到步骤(2)继续迭代。 上述是完整的的 LDPCLDPC 码译码的BP算法，但还没有说明如何去求得在x0 译码的初

11、始化过程中所需要的flfl或VlVl,这些值是与信道有关的。下面以 AWGAWG N N 信道为例，说明如何计算或VlVl0的值。flflx=P(xP(x= =x|y)x|y)表示不考虑比特之间的相关性，仅根据比特xlxl的接收信号值以及信道特性而得出的比特xlxl取值为 x x 的概率，其中 x x 的取值为0 0 或 1 1。 假设 AWGNAWGN 信道是二进制无记忆对称信道，其输入是来自信源的二进制 0 0、1 1 数字信号，经发端的二相 BPSKBPSK 调制器后变为 1,1,1 1 对极信号。经收端的二相相干解调器又把 1 1, ,- -1 1 对极信号变为 0,10,1 数字信号

12、还原输出。由于 AWGNAWGN 高斯白噪声的存在，相干解调的检测可能出现错误。用信号加噪以后的条件概率密度分布函数来分析误码的产生比较清楚。(2.14) 1r Uml=2tanh 一 l 三 L(m (3)变量节点更新： (4)似后验概率更新 0 vml=V+Uu, mllml m二M(lm 0,. Vl=Vl工Uml 第三章LDPC的性能分析 LDPC的仿真模型 图3-1LDPC仿真模型图 其中第二章详细介绍了LDPCK的译码算法，可知LDPCt码一般包括以下5个步骤：1、初始化2、校验节点更新3、变量节点更新4、判决5、停止。实际操作时发现判决时只需用到本轮迭代的校验节点的更新结果，变量

13、节点的更新在 下一轮迭代中才起作用。因此可以把步骤4和5安排在步骤3之前进行，这样可以节省一次变量节点的更新工作，译码流程图如下： / 、收完毕, 何始化 校独F点更新 软判决 勒闾束 图3-2译码流程图 LDPC的译码性能 通过前面几章的介绍，LDPC的译码基本完成，为了了解实现的译码性能，下文中给出了LDPC勺译码Tt能图。LDP编译码实现的编码输入是函数rand()产生的二进制随机序列，并记录LDPC码在不同性噪比下的误码率，再在matlab中画图。 仿真时LDPCK列重选择3,最大迭代次数设置为5次时进行仿验，分析研信噪比对LDPCK误码性能的影响，随着信噪比的增加，LDPCB的性能不

14、断提高。BP译码算法下，可以看成是无穷比特量化译码，它充分利用接收的信道信息，信道信息利用率得到了极大的提高。信道信息的充分利用，极大地提高了译码性能，使得译码可以迭代进行，充分挖掘接收的信道信息，最终获得出色误码性能 信噂比由 图3-3BP算法的BER曲线 码长对性能的影响 将LDPCK列重选择3,最大迭代次数设置为5次且信噪比为0.5dB时进行仿真实验,分析研究码长对LDPC码误码性能的影响，仿真得到了不同码长对LDPC 码的性能仿真结果如下图所示。从图中可以看出，在同样的信噪比条件下，随着码长的增加，LDPC码的性能不断提高。在小信噪比区域，码长的增加对误码率 的改进不大，但随着信噪比的

15、增大，LDPC码的误码率得到了明显改善。但随着码长的增加，LDPC码性能的提高是相对的，当达到一定码长后，性能将会有很小的提高。这是因为一定码长下编码性能有一定的极限，随着码长的增大，编码和译码的复杂度也增加，编码性能就会更接近极限，性能随码长增加改善的就更少。 图3-4码长对LDPC性能的影响 迭代次数对译码性能的影响 将码长为400的LDPCK,歹 J重为3,信噪比为0dB的情况下进行了仿真实验。 图中给出了上述情况下的不同迭代次数对LDPCK的性能仿真结果。可以看出，在相同的信噪比下，LDPCK的性能随着迭代次数的增加而逐渐提高。但是LDPC码的误码率并不能随着迭代次数的增加无限地减小，

16、当迭代次数足够大的时候，再增加LDPCK的迭代次数，只能增加系统的时延和复杂度，而LDPCB的性能不会再有提高。 图3-5迭代次数对性能的影响 结论 LDPC码是迄今为止发现的最接近香农限的信道编码之一， 在现代通信和数据传输系统中拥有广阔的应用前景。本文主要介绍了LDPC勺基础知识包括构造、编码、译码。着重介绍了LDPCK的高斯消去法编码原理和概率译码算法，并在AWGH道下对其进行了性能仿真，比较了LDPC3相又t于Turbo码的优越性能。 作为一种优秀的码型，LDPC码只有在实际中得到应用才能体现其真正的价值，纠错编码技术在通信系统中起着关键的作用，为可靠性信息传输提供保障，这一技术不管在

17、移动通信还是卫星通信抑或是磁盘存储中都得到了广泛的应用。 1王新梅，肖圉镇.纠错码一原理与方法.西安：西安屯子科技大学出版社， 1991. 2樊昌信， 张甫翊， 徐炳祥， 吴成柯.“通信原理”(第五版) 【M.国防工业出版社，2001. 3王育民，粱传甲.“信息与编码理论.西北电讯工程学院，1986. R.G.Gallager,Low-DensityParity-CheckCodesD.Cambridge,MAMrrPress,1963. R.G.Gallager,Low-DcmityParity-CheckCode.IRETransactionsonInformationTheory,1962.8(1):21-28. 王单.LDPCK编译码算法研究D.西安：西安电子科技大学,2006:1432 7刘利军.LDPCS码算法研究D.广州:华南理工大学,2011,52-5