LDPC码BP译码算法研究

附件清单：编号附件内容页数1任务书32文献综述133外文翻译334开题报告95指导记录卡16进程安排与考核表17答辩记录表18指导教师评语及成绩评阅教师评语及成绩19评阅教师评语及成绩答辩小组评语及成绩表110答辩小组评语及成绩表成绩评定表111成绩评定表11浙江理工大学本科毕业设计（论文）任务书XXX同学（专业/班级：班）现下达毕业设计（论文）课题任务书，望能保质保量地认真按时完成。课题名称LDPC码的BP译码算法研究主要任务与目标低密度奇偶校验码（LDPC）是一种具有稀疏校验矩阵的线性分组码，研究结果表明，采用迭代的概率译码算法，LDPC码可以达到接近香农极限的性能。常用的LDPC码译码算法大致分为两种：比特反转(BitFlip，BF)算法和置信传播(BeliefPropagation，BP)算法。本课题的研究目的是针对LDPC码的BP译码算法进行研究，通过系统仿真给出BP算法在不同迭代次数和信噪比条件下的BER性能。主要内容与基本要求本课题的研究目的是针对LDPC码的BP译码算法的性能进行研究。本课题要求学生完成以下毕业设计内容：1.了解LDPC码的基础理论、编译码结构原理和编译码算法；2.在Matlab中实现AWGN信道下的LDPC码的编译码系统，其中的译码模块中采用BP译码算法。3.给出系统仿真结果，包括BP算法在不同迭代次数和信噪比条件下的BER性能。主要参考资料及文献阅读任务查阅中文文献10篇以上，外文文献5篇以上，撰写5000字以上的文献综述。主要参考资料：1．肖海勇.LDPC码的研究[D].南京:南京邮电大学，2002.2．胡维钢,赵振纲.LDPC码的译码算法研究[J].中国科技论文在线.．张焕明,叶梧,冯穗力.LDPC码的树图理论[J].计算机工程,2007.5:64-65.4．尹晓琦,殷奎喜,李忠慧.一种简化的LDPC码BP译码算法的研究[J].现代电子技术,2006.14：148-151.5．郭锐,刘济林.LDPC码的一种低复杂度BP译码算法[J].浙江大学学报(工学版),2008.3:450-455.2外文翻译任务要求阅读3篇以上外文文献，翻译2篇合计不少于一万印刷符号外文（每篇约5000印刷符号），译成中文至少2000汉字。1．MarcP.C.Fossorier,MildragMihaljevicandHidekiImai.Reducedcomplexityiterativedecodingoflow-densityparity-checkcodesbasedonbeliefpropagation［J］.IEEETransactionsonCommunications,1999,47(5):673-680.2．RajendraBShinde.AnalysisofBeliefPropagationDecoderofLDPCCodes.~rbs/Projects/IS_report.pdf.计划进度：起止时间内容2012.11.05~2012.12.22学生查阅中、英文文献资料，撰写文献综述、开题报告及外文翻译，并按时上交指导老师。2012.12.23~2013.01.15了解LDPC码的基础理论、编译码结构原理和编译码算法。2013.01.16~2013.03.01在Matlab中实现AWGN信道下的LDPC码的编译码系统，其中的译码模块中采用BP译码算法。2013.03.02开题报告答辩，成绩评定，并对开题报告、文献综述、外文翻译进行修改。2013.03.03~2013.03.23给出系统仿真结果，包括BP算法在不同迭代次数和信噪比条件下的BER性能。2013.03.24~2013.04.26撰写论文，调试程序，论文初稿上交指导教师；修改论文和程序，论文定稿上交。2013.04.27~2013.05.11学生上交毕业论文，教师评阅。2013.05.12~2013.05.17评阅组教师评阅。2013.05.18毕业设计成果检查。2013.05.25毕业设计答辩。2013.06.05毕业设计二次答辩。实习地点指导教师签名年月日3系意见系主任签名：年月日学院盖章主管院长签名：年月日文献综述毕业设计题目：LDPC码的BP译码算法研究1LDPC码的BP译码算法研究XXX(XXXXXXXXXX)1前言低密度奇偶校验码(LOWDensityParityCheckCodes)在MacKay1995年的文献[25]发表以后，重新得到人们的重视[1]。所谓LDPC码是指一种线性分组码，它的校验矩阵H是稀疏矩阵。用(;;)njk来表示一个码长为n、校验矩阵的每列和每行中分别有j和k个1的LDPC码[2]。LDPC码的描述和实现较简单，译码算法中性能较好的是置信传播译BP(BeliefPropagation)算法[2]，BP算法译码的实质就是根据接收到的实数矢量R计算发送比特序列的后验概率，并根据其所参与的校验约束尽可能准确的对发送序列X进行译码[5]。BP算法不论在理论上还是实际中都能够在AWGN环境下达到非常接近信道容量的性能，在其迭代过程中，一旦试验译码成功就立即中止程序而不需要继续进行固定次数的迭代，这样就能有效地提高算法效率。另外BP算法还具有的复杂度与码长的成线性关系，在硬件中能够并行实现，没有误码率下降减速的ErrorFloor现象等优势，这些都使得具有BP算法的LDPC码必将在未来具有更加广阔的应用空间[3]。2课题应用背景及意义当今世界己进入了飞速发展的信息时代，信息产业已成为国民经济的主导产业，通信则成为信息产业中发展最为迅速，进步最快的行业。随着科学的进步和生活水平的提高，人们对于通信的需求量以及通信质量也日益增长。由于对于通信质量的高要求，人们希望找到一些提高通信质量的方法，而纠错码作为信道编码是提高通信质量特别是无线通信质量的好方法之一[6]。伴随着信息时代的到来以及微电子技术的飞速发展，今天纠错码己不再单纯是理论上探讨的话题了，它已经成为一门标准技术而被广泛采用。在移动通信中，纠错码被广泛用于模拟体制的信令传输及数字体制的整个传输，以提高传输的可靠性和节省珍贵的频谱资源；在卫星通信中，纠错码技术己成为用来降低对高功放的要求和减少地球站天线孔径的尺寸的经济可靠的方法，VSAT和USAT的兴起，都是和纠错码技术的应用有关的；在电话网上的数据传输中，纠错码、差错控制技术己是使高速数据2传输(9.6kbit/s以上的数据率)成为现实的关键技术。纠错码技术还广泛应用于计算机存储和运算系统中[7]。此外，纠错码技术还应用于超大规模集成电路(VLSI，ULSI)设计中，以提高集成电路芯片的成品率，降低芯片的成本。随着移动通信的发展，对纠错码不断地提出新的要求。Turbo码虽已成为3G的信道编码标准，但其译码复杂度高，时延长，难以适应最高数据速率远比3G要高的后3G(即B3G，或4G)未来移动通信系统的需求。LDPC码是一类可以用非常稀疏的校验矩阵(Parity-Check)或二分图(Bi-PartiteGraph)定义的线性分组纠错码，最初由Gallager发现，故亦称Gallager码[4,5]。经过数十年的沉寂，随着计算机能力的增强和相关理论的发展，LDPC码重新被重视，并证明它在采用基于置信传播(Belief-Propagation,BP)的迭代译码算法的条件下具有逼近Shannon限的良好性能，可以这么说，LDPC码的重新发现是继Turbo码后在纠错编码领域的又一重大进展[6,7]。LDPC码在新一代移动通信超3G中有着很大的用武之地，因为LDPC码本身即有抗突发差错的特性：不需要引入交织器，避免了可能带来的时延；可以实行完全并行的操作，便于硬件实现；吞吐量大，极具高速译码的潜力；它不仅具有接近Shannon限的优异性能，同时由于在码的构造、译码方法上的相关成果的获得使得LDPC码在信道条件较差的无线通信中展现出了巨大的应用前景，非常适合于在未来的移动通信系统中的实现[8]。3LDPC码的研究3.1LDPC码的表示校验矩阵H能完全刻画一个LDPC码，因此LDPC码可以由校验矩阵H表示，H矩阵的行M代表校验方程的个数，列N代表LDPC码的码长，一个H矩阵对应于一个LDPC码；除此之外还可以用双向图(又称Tanner图)来表示一个LDPC码。双向图不但表示方法方便，而且可以形象地刻画LDPC码的编译码特性。Tanner图可以用,GVE表示，其中V表示节点的集合，bcVVV。对十维数为MN的校验矩阵，12(,...)bNVbbb称为变量节点(或比特节点)，表示一帧中的各信息比特，对应校验矩阵中的列；12,...cMVccc表示校验节点(或函数节点)，对应各个校验方程，同时对应校验矩阵中的行。E是节点V之间所有相连的边的集合，bcEVV。在Tanner图中有一个特殊规定，即：同类节点之间不能有边的连接，只有在两类节点之间存在3边的连接。对于校验矩阵H的任意元素,ijh，若,1ijh则表示第i个校验节点ic与第j个信息节点jb之间有边的连接，否则表示没有边的连接。与节点相连的边数称为该节点的度；从某个节点出发沿边经过若干步又回到此节点称为一个循环，所经过的边数称为循环长度，所有循环中长度最小的循环的度称为图G的girth[9]。由校验矩阵H可以非常方便地得到此码的Tanner图表示。设一LDPC码的校验矩阵如下：11110000001000111000010010011000100101010001001011H(1)则其对应的Tanner图如式3-1。由图可知，每个校验节点与4个比特节点相连，与H矩阵每行有4个1对应，每个比特节点与2个校验节点相连，与H矩阵每列有2个1对应。例如校验节点1c与比特节点1234,,,bbbb相连，对应的H矩阵第1行的第1,2,3,4列为1；比特节点1b与校验节点12,cc相连，对应的H矩阵第1列的第1，2行为1。同样，由Tanner图可以写出LDPC码的校验矩阵H，Tanner图与校验矩阵H是一一对应的，对应的是一个LDPC码[10,11]。2.2LDPC的分类LDPC码可以用稀疏的校验矩阵来定义。根据稀疏矩阵的特点，可以将LDPC码分为规则LDPC码和非规则LDPC码；根据稀疏矩阵的组成元素，可以将LDPC码分为二元LDPC码和非二元LDPC码[12]。二元规则LDPC码是指其稀疏校验矩阵的元素在有限域GF(2)上取值，随后，Davey和Maekey将二元LDPC码推广到了一般有限域上，即对于校验矩阵中的每个非0元素(不一定是l)，它可以有个值作为选择[12,13]。LDPC码还可以用二分图(BipartiteGraph)的方法来表示。规则LDPC码的二分图如图l所示，lc表示信息节点，代表编码后的比特位，对应校验矩阵中相应的列；lf表示校验节点，代表编码比特组成的校验方程，对应校验矩阵中相应的行。连接信息节点与校验节点的边对应校验矩阵中非0元素，每一列有3vd个非零元，每一行有6cd个非零元。在二分图中，vd、cd分别表示信息节点和校验节点相连的边数,，4称为该节点的度(degree)。当二分图中信息节点的度各不相同(校验节点的度也有相应的变动)时，这样的LDPC码称为非规则(irregular)LDPC码[8]。图1(10,3,6)规则LDPC码的二分图2.3LDPC码的构造校验矩阵不但决定了LDPC码的码字结构，而且在译码过程中也起着至关重要的作用。不同结构的LDPC码的性能有很大不同，同时编译码复杂度也有很大区别，因此如何构造性能优异、编译码简单的LDPC码一直是信道编码领域的热点问题。总结起来，LDPC编码要遵循以下二个原则：(1)校验矩阵H中无短环存在，特别是不能存在4环；(2)有较大的最小码重和较大的最小码距；(3)编码复杂度低。目前，构造校验矩阵的方法主要有两种:随机构造和代