LDPC的BP译码算法

课程名称：现代编码理论任课教师：王琳洪少华论文题目：LDPC码的BP译码算法姓名：曹沙沙赵卜寒学号：23320131153243233201311532742014年07月06日目录摘要..............................................................................................................................IIAbstract......................................................................................................................III第一章LDPC码的概述..........................................................................................................11.1LDPC码的发展史.............................................................................................................11.2、LDPC码的表示...............................................................................................................11.3二进制LDPC码的编码方法.............................................................................................31.3.1校验矩阵的生成....................................................................................................31.3.2编码算法................................................................................................................4第二章LDPC码译码算法............................................................................................62.1Gallager概率译码基本思路.........................................................................................62.2BP算法研究...................................................................................................................82.3用对数似然比表示的BP算法.......................................................................................11第三章LDPC的性能分析..........................................................................................143.1LDPC的仿真模型...........................................................................................................143.2LDPC的译码性能...........................................................................................................153.2.1码长对性能的影响................................................................................................153.2.2迭代次数对译码性能的影响................................................................................16结论.............................................................................................................................18参考文献.....................................................................................................................19摘要低密度奇偶校验码是Gallager提出的一种线性分组码，其性能可以非常接近香农极限。它是根据低密度稀疏校验矩阵H和二分图来构造的，本文详细的阐述了二进制，规则的LDPC的BP译码算法，其校验矩阵每一行和每一列的1的个数是相同的，分别为p和q,其Tanner图中比特节点的度和校验节点的度分别对应着一个固定值，通常用（m，n，p，q）表示。BP译码算法是一种迭代的概率译码算法，本文着重于BP译码算法及其简化运算。本论文主要介绍了LDPC码的构造、编码和译码基本原理。阐述了LDPC编译码的过程，并通过MATLAB仿真工具对LDPC码在AWGN信道的误比特率性能进行了仿真，分析了信噪比、码长和迭代次数对误比特率性能的影响。关键词：二进制LDPCBP算法迭代概率译码后验概率LDPC码的BP译码算法AbstractLowDensityParityCheck(LDPC)codesareaclassoflinearblockcodesproposedbyGallager,whichperformatarateextremelyclosedtotheShannoncapacity.Itisbasedonlow-densityparitycheckmatrixHandsparsebipartitegraphisconstructed,thepaperelaboratedbinary,LDPCdecodingalgorithmofBPrule,thenumberofoneofitscheckmatrixeachrowandeachcolumnisthesame,respectively,pandq,theTannergraphofbitnodesandchecknodesofdegreecorrespondstoafixedvalue,respectively,usuallyexpressedas(m,n,p,q).BPdecodingalgorithmistheprobabilityofaniterativedecodingalgorithm,Thispaperfocusesonitssimplifiedoperation.Thispaperdescribesthestructure,thebasicprinciplesoftheencodinganddecodingofLDPCcodes.DescribestheLDPCencodinganddecodingprocess,andthroughMATLABsimulationtoolforLDPCcodesinthebiterrorrateperformanceAWGNchannelsimulation,analysisoftheimpactofsignaltonoiseratio,codelengthandnumberofiterationsofthebiterrorrateperformance.Keywords:binaryLDPCBP-decodingalgorithmiterativeprobabilityposteriorprobabilityLDPC码的BP译码算法1第一章LDPC码的概述1.1LDPC码的发展史1、1963年，Gallager发现的LDPC码被称作古典码型：规则LDPC。2、1998年，MacKayandSpielman发明了不规则的LDPC。3、RichardsonandUrbanke开创了用译码分析设计码型的方法。4、针对B-LDPC码优异的纠错性能，M.Davey和D.Mackay进一步将B-LDPC码一般化到多进制域上，并且研究结果表明Q-LDPC码在低码率（R1/2），AWGN信道下比B-LDPC码的纠错性能还要优越，Q-LDPC码的出现为LDPC码的研究开拓了一个全新的领域。1.2、LDPC码的表示LDPC是一种分组码，但是LDPC码与其他线性分组码不同的是，其他线性分组码由生成矩阵表征，而LDPC码是由校验矩阵来表征，其奇偶校验矩阵具有低密度的1。规则LDPC码可以用（n,j,k）的形式表示，其中n表示生成的码字的码长，j表示H矩阵的列重，k为行重。也可将j用c表示，k用r表示。如果用m表示H矩阵中的行数则有crnm。一个规则的（12，3，4）LDPC码的H矩阵如下图所示：001001110000110010000001000100001110010001100100H101000010010000110001001100110100000000001010011011000001100图1－1（12，3，4）LDPC的校验矩阵我们把H矩阵中的每一行看作一个校验点(checknode)，每一列看作一个变量点(variablenode)。则H矩阵反映了变量点与校验点的连接关系，如在第一行中有36780xxxx，表示模2加，表示第一个校验点约束3x、6x、7x、8xLDPC码的BP译码算法2这四个变量点。从而我们可以知道行重k表示一个校验点约束k个变量点。我们再来看第一列，它表示了第一个变量点受到check2、check5、check7的约束。因此我们又可以推出列重j表示了一个变量点受到j个校验点的约束。由于LDPC也是一种线性分组码，因此可以用（n,k）的形式表示。n表示码长，k表示信息位的个数。为了更形象的表示LDPC码中变量点与校验点的关系，九十年代中期科学家们引入双边图（biparttiegraphs）来表示LDPC码。双边图是LDPC的一个有用的工具。它将节点分成两类，节点之间用无向的边进行连接，并且连接只存在于不同类的节点之间即只存在与校验点与变量点之间，而两个校验点之间或者两个变量点之间不存在边的连接。我们把LDPC校验矩阵H的每一行表示一个校验点用方框表示，每一列表示一个变量点用圆表示。则由上述可知一个校验点连接k个变量点，一个变量点连接j个校验点。当对应H矩阵中1jiH时，第i个变量点就与第j个校验点连接，否则不连接。并且校验点发出的边的总数等于变量点发出的边的总数。每个节点发出的边的个数称为这个点的度。如对于（12，3，4）码其双边图为：图1－2（12，3，4）LDPC码的因子图表示当H矩阵中每列1的个数与（或）每行1的个数不同时称为不规则LDPC码。在双边图中表现为变量点与校验点的度允许改变。对于