LDPC编码算法分析和研究

1、湖南大学毕业设计(论文) 第 2 页论文题目LDPC编码算法实现与分析学生姓名 学生学号专业班级学院名称信息科学与工程学院指导老师学院院长 2014年5月19日LDPC编码算法实现与分析摘 要 低密度奇偶校验码（Low Density Parity Check Codes）由Gallager在20世纪60年代首次提出，经过30多年的沉寂，最终因为具有逼近Shannon极限以及译码复杂度低等明显优势得到研究者的重视 Bernhard M.J. LDPC Codes a brief Tutorial. Technique Report, 2005。随着通信领域相关技术的不断发展，加上LDPC码结构

2、灵活，目前已广泛应用于深空通信、光纤通信、卫星数字视频和音频广播等领域。LDPC码已成为第四代通信系统强有力的竞争者。论文旨在研究基于MATLAB的LDPC码的编译性能仿真。主要的环节有：LDPC码的构造；LDPC码的相关编码实现；LDPC码的译码实现。在整个设计及过程中，基于以上主要环节，实现对LDPC码的性能分析，并得出相关结论。在实现编码方面，主要采用的是基于奇偶校验矩阵的编码算法，而译码过程用到的是比特翻转（Bit Flipping）译码算法。关键词：LDPC码； 校验矩阵； 编译码； MATLABImplementation and analysis of LDPC encoding

3、 algorithm Abstract LDPC (Low Density Parity Check Codes) was first proposed by Gallager in the 1960s, after 30 years of silence, because of eventually approaching the Shannon limit with decoding complexity and low obvious advantages, researchers paid more attention. 1 With the development of commun

4、ications technologies, with flexible LDPC code structure, LDPC code has been widely used in deep space communications, optical communications, satellite digital video and audio broadcasting and other fields. LDPC code has become the fourth-generation communications system strong competitor. The Pape

5、r aims to study the performance of the simulation based on MATLAB about LDPC codes. The main areas have been identified: LDPC codes construction; LDPC codes encoding; LDPC code decoder implementations. Throughout the design and process, achieve the performance of LDPC code analysis and draw relevant

6、 conclusions. In the realization of encoding, the main encoding algorithm used is based on the parity check matrix, and the decoding process used is bit flip (Bit Flipping) decoding algorithm.Keyword: LDPC codes Parity check matrix Encoding and decoding MATLAB 第 页目录1 绪论11.1课题背景及目的11.2国内外研究现状11.3论文的组

7、织结构及研究内容32 LDPC码的相关背景知识52.1 线性分组码52.1.1线性分组码的相关概念52.1.2 线性分组码的性质52.2纠错码简介62.3 LDPC码的表示72.4 LDPC码的构造83 LDPC码的编码113.1直接编码算法113.2基于校验矩阵的编码算法123.3小结154 LDPC码的译码174.1主要译码算法174.1.1比特翻转译码算法174.1.2加权比特翻转译码算法204.1.3置信传播译码算法214.2小结215 LDPC编译码算法仿真平台的实现225.1 LDPC编译码过程225.2 仿真结果展示分析22总结和展望26致谢28参考文献291 绪论1.1课题背景

8、及目的自从信道编码理论被提出以来，研究者们就在各个方面做了很多的努力。包括寻找接近香农极限的性能码；包括通过各种手段降低编码和译码的复杂度；也包括提出更具实践意义的信道方案。正因为有了这些成就，才使得后来的研究者有了完善和改进的基础，把信道编码更加广泛地运用到信息领域的各个角落。随着通信领域相关技术的发展，早期的码，例如：BCH码，Turbo码，已经无法完全适应当今的要求。而且信息系统越来越要求有更高的数据速率，加上计算机硬件的不断发展以及相关理论的更新，使得LDPC码在一段时间的停滞不前之后，有了新的发展和突破。不得不说明的是，LDPC码在某些条件下拥有很多已经得到实际应用的良好性能，相对的

9、他的复杂度并不算太高，而且结构又灵活，所以成为了时下第四代移动通信的热门研究点。同时LDPC码在很多领域都得到了良好地应用，比如：在探测未知的深空领域时。这些都给社会的发展带来了深远的影响。所以有理由相信LDPC码在未来的信息领域有巨大的前景。1.2国内外研究现状LDPC码能够取得现在的成就，自然少不了信道编码研究者们的不懈努力。Behairy H和Chang S.C提出了具有并行级联特点的Gallager码（PCGC），就是在Turbo码的编码中用到LDPC码。其方法就是在不适用交织机的情况下实现信息码元的输出，并且经实践得到了良好的效果 Behairy H, Chang S C. Para

10、llel concatenated Gallager codesJ. Electronics letters, 2000, 36(24): 2025-2026.。Yu Kou，Shu Lin等利用有线集合的代数方法，构造成功LDPC码，借此生成的循环码字可以用相对简单的具有线性反馈位移性质的寄存器进行编码，这一举措极大的简化了复杂性，从而使得到的纠错方面的能力更靠拢香农极限。根据查阅相关资料，当前在最好的情况下，LDPC码字性能与香农极限相比，仅仅相差0.0045dBYu Kou，Shu Lin, Fossorier M. Low Density Check Codes: Constructi

11、on Based on Finite Geometries. Proc Globecom ConfC. 2001,2(1):825-829。M.G.Luby等提出，在非二元有限域中这个情况下，定义码有性能的改进，同样有这种可能的还包括校验矩阵。同时相比基于正则图定义的码，基于非正则定义的码性能更加好。他还提出某种双向图的LDPC码在可擦除信道中有较多的运用，而且可以实现时间复杂度是线性规律的编码和译码。同时D.J.C.Mackay通过对超泊松分布结构的相关性能的验证，发现当相关的矩阵的结构呈现具的是三角形结构时，更能实现快速编码M.GLuby, M.Mitzenmacher, M.A.Shok

12、rollahi. Improved Low-Density Parity-Check Codes Using Irregular Graphs. IEEE Transaction on Information Theory. 2001,47(2):619-632。T.J.Richardson和R.L.Burbanke研究了如何通过确定校验矩阵的稀疏性来得到更高效的编码器，如何是编码时间和码长度更加贴合线性关系增长。T.J.Richardson通过研究非正则图的复杂性来发现更优的非正则码LDPC码。刘水平等将编码器分子若干个子相互串联级联的编码器，从而实现非正则LDPC码的设计。这样做不仅能够保

13、证低密度校验码的特点，实验还表明：这样一来简化了编码算法，而且码结构得到固定，从而实现更好的性能 刘水平，刘玉君.串行级联LDPC码J. 信息工程大学学报，2004,5（2）:76-79。贺玉成等经过研究提出了一种迭代译码量算法，该算法是基于置信传播。其优势在于：首先，极大降低存储要求；其次，计算复杂度得到改善；最后，算法是呈现对称性特点的，这些优势使得改进后的LDPC码在实际通信中成为现实。 由于摊就分析的不断深入，极大地优化了LDPC码的编码复杂性。因此，LDPC码在多个领域得到广泛应用 贺玉成，孙韶辉，慕建军，王新梅。 快速低密度校验码迭代译码量化算法J. 西安电子科技大学学报（自然科学

14、版），2002,29（3）：338-342。叶芳等人研究出一种填充算法，该算法是通过构造稀疏的校验形矩阵来实现的。这种算法的优势在于当需要构造高圈长的校验矩阵时，实现起来的复杂度会比较低 叶芳，刘钧雷，朱琦。 扩展比特填充算法与LDPC码的构造J. 重启有点学院学报， 2004,16（3）：21-24。彭立等人介绍了一种以某一矩阵为子矩阵，通过对这类矩阵进行合适的排列组合，进而构造出低密度校验矩阵的一种LDPC码编码器的设计方案。Chiani、Myhre和Wadayama等人的主要研究工作是LDPC码在衰落信道中的应用。其中Chiani的主要工作是对有记忆块衰落的信道进行性能估评。Myhre提

15、出了一种编码调制方案，主要是针对慢变化衰落信道的一种LDPC调制方案。Wadayama主要针对可能突发信道的LDPC码进行了研究，并且提出一种模型适用于隐马尔可夫噪声信道 Liva G, Chiani M. Protograph LDPC codes design based on EXIT analysisC/Global Telecommunications Conference, 2007. GLOBECOM'07. IEEE. IEEE, 2007: 3250-3254.。现今研究中，关于LDPC码的改进优化工作，主要往矩阵构造、编码算法改进优化等方面进行。随着LDPC吗的研究

16、深入，其出色的性能，已经得到广泛的关注，并被用于卫星通信，光纤通信，移动通信以及压缩图像输出等总所数字通信领域。1.3论文的组织结构及研究内容本文共分为六章：第一章为绪论，主要介绍“LDPC编码算法实现和分析”的课题的背景、选取该课题的目的以及国内外对于LDPC码的一些相关研究，最后介绍了论文的结构。第二章主要是讲述系统LDPC码的相关背景知识，主要研究内容集中在线性分组码的简单介绍、纠错码的介绍、LDPC码的阐发分析，这中间就包括LDPC码的构造。第三章是LDPC码的编码算法，本章节主要介绍几种使用广泛的编码算法，有直接编码算法和基于校验矩阵的编码算法。第四章是LDPC码的译码算法实现，介绍

17、了三种相关算法，主要集中在对于翻转译码算法的研究和分析，并且对相关内容进行了小结。第五章主要是对LDPC编译码算法基于MATLAB进行实际仿真实现。主要是对实验结果绘制出的曲线图截图进行展示，分析这些因素对于误码率的影响，并得出相关的结论。本课题的名称为“LDPC编码算法实现与分析”，研究的主要方向包含了下面几个内容：（1） 研究LDPC码在通信编码领域的产生以及发展道路，论叙LDPC码的发展状况，讨论LDPC码对于整个通信编码领域发展的重要意义。具体技术点具体分析，拆分为小的重点难点进行重点剖析，在不同的编码条件中以具体的不同的形式和内容表现出来。（2） 本文介绍了与LDPC码背景相关的知识

18、，包括其表现形式，结合相关的研究探究LDPC码的码构造常用方法：基于校验形矩阵H的构造。（3） 研究探讨LDPC码的编码和译码算法的实现，总结其相对传统的BCH码的优缺点。从对比的角度分析LDPC码的使用场景以及现阶段面临的困难、需要解决的问题，并且归纳其使用场景。（4） 总结了LDPC码相关研究的曲线图，通过分析联系实际总结LDPC码的优点。通过分析现在已有的研究成果，提出针对性的解决方案，研究在实际应用中的深远意义和价值。并对“LDPC编码算法的实现和分析”中研究的问题以及实际中遇到的问题进行解决。2 LDPC码的相关背景知识2.1 线性分组码考虑到LDPC码的本质是线性分组码，因此十分有

19、必要在本章节首先对线性分组码的相关知识做一个简单概述。线性分组码的本质其实是奇偶校验码，它的描述方式通常为（n，k）。2.1.1线性分组码的相关概念如果码字序列的表示是( cn-1，cn-2,， ，c1，c0)，那么分组码会对每段长度为k的信息组，通过增加 r = n k 数目的检验元的规则来完成。一般来说，通过编码器以后，二进制情形下数目为2k的信息组会产生2k个对应的码字。那么这些产生的码字集合就是（n，k）的分组码，长度为n的序列会有2n种排列方式。而长度是n的分组码可以用作前向纠错。在分组码中，形成新码的一般方式是监督位加上信息位；在编码中，被编成长度是n位，个数是（n-k）个的监督码

20、是由k个信息位而来，这些形成的监督码起到检错和纠错的作用 单亦先. 循环码的实现方法及其在前向纠错中的应用J. 石油大学学报: 自然科学版, 2001, 25(5): 98-99.。k比特序列又称作k元组，其实质是k位比特信息构成的序列，该序列包含有2k个信息，以此类推，n元组的概念是：n位比特构成的序列，当中包含有2n个元素。由于分组码的编码是遵循一一对应的原则，所以在编码过程中，每个k元组会相应地映射到2n个数中的某一个n元组中。通过一个查询表可以顺利实现这样的映射。介绍完基本的知识，现在从两个方面来分析线性分组码：（1）分组特点：对于线性分组码而言，码长会是恒定的，同样消息长度也是恒定的

21、。另外，如果存在码长是n时，若其中消息位显示为k，而且每次输出n位仅仅与当前的k位输入有关；（2）线性特点：在线性分组中，码字c相对应的各位码元与消息的关系是线性组合关系。2.1.2 线性分组码的性质对于一个线性分组码，能够用 c=mG来实现码字 c的可能表示，当中字母m有两种意思，第一是表示k长度的消息；第二就是表示k维度的向量。特别注意的是：矩阵运算采用模二加和模二乘。下面还有一些关于线性分组码不得不列出的有用性质，如下：性质1：零向量一定会是一个码字，可以记做=（0，0，0）。推而广之，在线性组合码中，任意码字的线性组合仍然是一个码字宫晓妍, 刘建伟. LDPC码编码方案研究与发展J.

22、通信技术, 2008, 15(10): 276-280。性质2：任意两码字的和仍然会是一个码字。性质3：可以用G来表示码字c。具体的表示是对G的行向量进行线性组合。行向量是码集里面的码字，因此要拥有的特点是呈现线性无关。假设(g0，g1 ，g2 ，gk-1)是线性组合（n，k）基底，那么对于任意属于G的码字c，其表现方式是唯一的，如下：C = a0g0 + a1g1 + + ak-1gk-12.2纠错码简介当出传输过程发生错误后，纠错码(Error Correcting Code)最大的好处就是能够在接受端发现并纠正错误新梅, 国镇. 纠错码: 原理与方法M. 西安电子科技大学出版社, 199

23、1.。提及的基本概念：检错码：一类用来发现错误的码；编码：码字之间建立关系。依据是否满足编码规则来判断接收端的码字是不是正确的。如果根据判断得到的反馈信息是码字错误，那就按照一定的规则将错误所在位置的码字纠正。这一个过程就是译码。当然，检错码结合其他检测手段，可以进行错误纠正。存在某种关系的纠错编码和信源编码是信息传输的两个方面，具体来说这种关系是一种对偶的关系。所谓对偶关系就是按照某些规则将原有码字改变成另一种码字，改变之后的码字要有一定的剩余度。而且要满足码字对应的码元之间保持某种的关系。而线性码就是指码元之间存在线性的关系；否则就是非线性码。纠错码是凭借较大的码字之间的差距来实现和完成检

24、错和纠错。译码环节是纠错码顺利实现难度最大的部分，也是纠错码最终是否可以应用的关键。已有的研究表明：当码长越大时，最终的误码率越小。但是加大码长带来的后果就会导致编译码设备更加复杂，而且会产生较大的延时。所以现有的研究主要是集中在寻找到一种当码长增加时，误码率会呈现指数下降的译码方法；随着码长的增加，译码的复杂程度会以线性增长，而且满足其计算量基本与码长无关。2.3 LDPC码的表示 首先需要说明，有关LDPC码的研究到目前为止并没有对其给出一个非常严格的定义。普遍认同的的LDPC码的表示方式有两种：第一种表示方法是像所有线性分组码一样它们能够通过矩阵被描述。第二种是通过图形被表示。矩阵表示的

25、例子如下： （1）上面方程式（1）定义的矩阵是不完全符合条件奇偶校验矩阵，其大小是n*m，表示形成（8， 4）的矩阵。现在定义两个数字来表示矩阵：Wr表示1所在的行，Wc表示其所在的列。对于一个可以被称作低密度矩阵的矩阵要满足的两个条件是：Wc n而且Wr m。为了满足这些条件，奇偶校验矩阵应该很大。所以上面例子里面的矩阵严格意义上说不是真正的低密度奇偶校验矩阵。Tanner图被认为是LDPC码的另一种有效图形表示。Tanner图是二分图，这就意味着图的节点被分成两个独特的部分，而边仅仅是用来联系两个不同类型的节点。 C1C0C35C6C7C2C3C4f1f2f3f0c_nodesv_node

26、s（2）以上Tanner图中有两类型的节点：变量节点（v_nodes）和校验节点（c_nodes）。结合奇偶校验矩阵，Tanner图可以理解成包含m个校验节点，校验节点就相当于奇偶校验位的数目，n个变量节点，其含义相当于在码字中的比特数。如果（1）中H矩阵中的某一元素hij是1，那么校验节点fi和变量节点Cj就要连接起来。2.4 LDPC码的构造 通常情况下，LDPC码的构造思路是：（1）先随机生成列为c和行为r的H矩阵，并且该矩阵要满足任意两列重叠为1的数目要尽可能少；（2）产生的H矩阵要满足满秩矩阵。经过高斯消元法，使之前的H矩阵进行变换，满足H = PT | I，再有校验矩阵和生成矩阵的

27、关系得到G = I | P。（3）然后可以由vT = GxT 得到编码后的码字。构造LDPC码H矩阵的部分代码如下：3 LDPC码的编码目前，直接编码算法和基于校验矩阵的编码算法是LDPC码的主流编码算法之一，而其中直接编码算法用到了高斯消元法黄炜, 张建秋. 构造准循环 LDPC 码生成矩阵的块高斯消元法J. 复旦学报: 自然科学版, 2009 (6).。因为在利用高斯消元法的过程中不可避免地会破坏矩阵的稀疏性，所以相比之下由Richardson和Urbanke提出的基于校验形矩阵的算法对于LDPC码的编码来说是一个更好的选择。3.1直接编码算法 直接编码方法的大致思路是：利用高斯消去法将m

28、*n的校验矩阵H变换成H = P I，因为校验矩阵H的不确定，所以在变换过程中可能会涉及到初等行列变换。如果进行了初等行列变换，则同时要记录下这些行列变换信息。如果校验矩阵 H 满足线性相关的，将会删去相关的行，那么这种情况下，LDPC 码的码率由该校验矩阵确定，其值将大于 1 k / n；然后，根据系统形式的校验矩阵H = P I，得到其对应的生成矩阵G = I PT。如果在生成系统形式的校验矩阵的过程中没有进行初等行列变换，则有 H GT = 0，否则H GT 0，而对于将校验矩阵H进行行列变换的依据则是根据记录之前记录下的行列变换信息。最后，m为信息序列，则编码后的序列为 c = mG。

29、需要说明的是，如果在生成系统形式的校验矩阵的过程中进行了初等行列变换，则需要使用进行过相应的初等行列变换的校验矩阵 H 进行译码。上面思路基本适用于对任意结构的LDPC码进行编码，得到的编码复杂度往往与码长成正比。由于这种编码算法的计算复杂度过于庞大，且会占用过大的存储空间。因此，不适合于硬件实现，这也是早期阻碍 LDPC 码发展的原因之一张晨. 高吞吐量 LDPC 码编码构造及其 FPGA 实现 DD. 上海交通大学, 2008.。由于LDPC 码的码长n很大，同时很多性能优良的LDPC码都是采用随机方式构造的，这就导致使用上述方法得到生成矩阵 G 的运算量很大。为降低编码复杂度，现在已发展

30、出多种已经简化的编码方法，而下面将讨论的这种编码算法就被视为一种高效的LDPC码编码算法，而且应用广泛。3.2基于校验矩阵的编码算法与传统的BCH码相比，LDPC码具备良好的性能以及更低的解码复杂度，但是其最大的缺点就是编码过于复杂。Richardson和Urbanke二人经过研究找到一种可以解决LDPC码编码过于复杂的方法，其主要思想就是要利用校验形矩阵具有的稀疏性来尽量减轻编码的运算量Urbanke T R R, Richardson T. Efficient encoding of low-density parity check codesJ. IEEE Trans. on Infor

31、m. Theory, 2001, 47(2): 638-656.。这个就是被简称为RU算法的核心思想。这种算法为了能得到一个近似下三角矩阵，会依靠行列置换来改变校验矩阵H，这么变换的好处就在于原来矩阵所具有的稀疏性会被保留。比如下图（3）：通过某种方法将原来矩阵分成六个分块的稀疏矩阵，图中显示的G竟可能小。M - GGN - MNG M - GMABCDTE0（3）首先，奇偶校验矩阵可以通过行变换和列变换实现重新排列，得到如上图（3）：是一个经过了行列变换得到的近似下三角形矩阵。因为原有的矩阵是非常稀疏的，在进行完行列变换以后，得到的矩阵仍然是具备稀疏性的奇偶校验矩阵。图中的A、B、C、D、E

32、、T，由前面的分析可知：这六个部分都是维稀疏矩阵；另一种表示是（M-G）*（N-M）、（M-G）*G、G *（N-M）、G *G、G *（M-G）、（M-G）*（M-G）。值得注意的是：T矩阵必须满足某些元素全是零，也就是指对角线上的元素。由此矩阵H可以表示成另外一种形式： ，现在假设信源s的长度是k = n-m，并且x =（s，p1 ，p2 ）被编码成码字向量，其中p1、p2都定义成校验向量，长度分别是：G和M-G。得到的编码步骤如下：（1）计算信源向量的上校正子 ZA=AsT （4）（2）找出第二个校验向量的临时值，使得上校正子为零 = T-1 ZA (5)该向量能够通过回头代入计算的算法

33、，并且在呈现线性关系的时间内得出结果，也就是运算的第一个比特，接着是运算第二个比特，接下来是第三个，以此类推。（3）接着计算向量的下校正子 ZB = CsT - EpA （6）（4）首先要做的就是准备求第一个检验向量p1。由矩阵F = -ET-1B+D来求逆矩阵，该计算完成一次的复杂度O(G2 )，这个逆矩阵是一个G*G维高密度矩阵。现在假设第一个校验向量p1是 (7)（5）接着放弃临时检验性向量，但是要找出新的有效地且符合条件的上校正子（可以在线性时间完成）： Zc =ZA + Bp1 (8)（6）接着求解出上面提到的p2的值，同样必须使上校正子满足全为零（利用回代算法在线性时间内求出）。

34、= -T-1zc (9)最后计算、的复杂度如表3.1和表3.2所示。表31计算的复杂度操 作复 杂 度说 明AO（N）稀疏矩阵和向量相乘 O（N）稀疏矩阵和向量相乘 O（N）稀疏矩阵和向量相乘向量的减法运算 O（N）矩阵的求逆运算高密度矩阵和向量相乘表32计算的复杂度 操 作复 杂 度说 明AO（N）稀疏矩阵和向量相乘 O（N）稀疏矩阵和向量相乘A+ O（N） 稀疏矩阵和向量相乘向量的加法运算- (A+) O（N）稀疏矩阵和向量相乘上述RU算法，利用了校验矩阵的稀疏性，适用于任何基于稀疏校验矩阵的编码。整个编码流程的示意图如下：开始编码接受二进制待编码序列校验比特编码器p1校验比特编码器p2将

35、信息源比特和生成的校验比特合成码字并且最终输出编码结束由上面两个表格可知，基于校验矩阵的编码算法的复杂度与N + G2 有关，具体的关系式成正比，换一句话说，编码复杂度随着G值的减小而降低。由此可以得出结论：如果想要达到降低编码复杂度的目的，可以在进行行列变化时，尽量减小G值。LDPC码编码算法实现部分代码如下：3.3小结 传统的LDPC码并不利于推广，原因是编码复杂度高，所以在构造LDPC码的H矩阵时，不能只单方面地想到如何去优化码字的性能，同时也要把编码的复杂度纳入考虑范畴。本章节里面所提到的编码算法，在降低编码复杂度方面都是利用H矩阵自身的某些特点对其进行处理，这样做可以使编码复杂度降低

36、到线性复杂度。Richardson和Urbanke首先提出的基于校验矩阵的编码方案通过对原有矩阵的处理完成编码，这个方法基本是适用于一般的H的矩阵。虽然对于LDPC码的研究已经取得很多的成果，但是目前并没有一套完善的、系统的LDPC编码理论。为了使编码复杂度随着码长呈现线性增长，现有的研究主要是利用稀疏性，也就是说保持校验矩阵的稀疏性来编码。我相信只有综合考虑运算的复杂度和存储量，才能设计出符合要求的低复杂度编码方法。因此，如何降低LDPC编码复杂度，成为研究者们争相研究的热点问题。4 LDPC码的译码4.1主要译码算法在讨论LDPC码的译码算法时，不得不涉及两个概念：硬判决译码和软判决译码。

37、比特翻转算法属于一种典型的硬判决算法。主要的优点在于较低的复杂度。考虑实际设计，本文主要对比特翻转译码进行实现和分析。4.1.1比特翻转译码算法 硬判决译码算法是由Gallager突出的一种简单易懂的算法，并且经过研究表明：这类算法运算量不高而且没有严格的存储量要求。比特翻转（Bit-Flipping）译码算法是由Gallager在1963年提出，后续研究表明，当某有线几何码的列重和行重尽可能大时，BF译码算法十分有效郭强. 基于可靠率的改进的 LDPC 码 BF 译码算法J. 南京理工大学学报: 自然科学版, 2009 (2): 165-167.。首先，介绍BF译码算法的原理：在比特传输过程

38、中若有可以检测或者可以纠正的错误发生时，接受序列不再满足校验方程，然后利用某一已知准则去计算各个比特的可靠性度量，然后再选择不可靠的比特位进行翻转，翻转之后再代入校验方程组计算，如果满足了条件，译码就会终止，接着会输出译码后的码字；相反如果没有满足条件，那么可以通过重复上面的过程，直到校验方程被满足或者达到迭代次数。现在我们设置c =（c0， c1， cN-1）为发送序列，经BPSK调制为序列x=(c0， c1， cN-1)，负责接收的序列表示成xi = (2ci - 1)，而经过这一个过程得到的硬判决向量序列z =（z0， z1， zN-1）表示是： 1，当ri > 0；Zi = 0，

39、当ri < 0。通过这样的过程得到的伴随式s =（s0， s1，s2， sJ-1）= z = HT如果能够满足sj = 0 ，就表明接收到的序列能够满足第j个校验方程式；若s=0，则表示接收向量满足所有校验方程，接收码字z正确，那么就表示译码成功；若s集合存在非零元素的向量，那就表示接受序列有错误存在，如果出现这种情况，就必须计算对应码字不满足校验方程式的个数，且要寻找其中的最大值，然后翻转对应位置的码元。不断重复上面的过程，当所有的的码字都译码成功或者达到设定的迭代次数时，才停止。归纳比特翻转译码算法的步骤如下：（1）利用相关公式计算校验和，判断s是不是满足全部是零，若满足这个条件，那

40、么就表示译码成功，如果不满足就转到步骤（2）；(2) 需要计算码字中的比特的可靠度量值； (3) 由步骤（2）中计算出的度量值将接收序列中最不可靠的比特对应的码元zj翻转，然后重新计算校验和；(4) 重复步骤（1）至步骤（3），直到所有的校验方程都被满足或者迭代次数达到设置的最大值。由于校验矩阵是一种稀疏矩阵，通常情况下是随机的，这就导致校验方程式的比特数目较少，而且这些比特比较分散，这么一来，任意校验方程式中的比特会存在两种情况：一是没有错；另外就是极有可能只包含一个比特错误。这样一来，比特翻转译码算法就可以有效地进行错误纠正。哪怕方程式中不只一个比特错误，也可以顺利进行纠错，不过这么做就是

41、以牺牲译码性能为代价。考虑到这一方面，于是在翻转译码算法的基础上提出一种加权硬判决译码算法，对比而言该算法性能得到了提高，下一节会有介绍。LDPC码比特翻转译码算法实现主要代码如下：4.1.2加权比特翻转译码算法加权比特翻转译码算法的思路是：当某个变量节点需要翻转时，必须要记录某些输出信息，而这些信息指得就是码元的信道信息，严格意义上说是指无法满足校验方程的码元。并以此信息来作为判决式的权重信息谢东觉, 张兴敢, 唐岚. 一种改进的 LDPC 码多比特翻转译码算法J. 现代电子技术, 2011, 34(003): 11-13.。加入令为接收端的信息，而调制信息则是，又有高斯白噪声为。其中有校验

42、矩阵，相关联的变量节点由来表示，同样，相关联的校验节点由表示。于是，当有m=0，1，M1；n=0，1，N1 加权BF译码算法的步骤如下表示：(1) 利用相关知识，分析集合s中的元素是否全为零，如果满足这个条件，就表示译码成功，如果存在非零元素，就进行步骤（2）；(2) 计算0<i<N1，nN(m)；(3) 当n=0，1，N1，代入运算：，并且寻找其中的最大值，进行对用的翻转； (4)将得到的新的向量序列代替原向量，实施步骤（1），如满足伴随式全为“0”，那么就表示译码成功，停止译码；否则反复执行上述步骤（1）至（4），当达到设置的迭代次数极限时，停止译码。通过软判决算法和附加信息来

43、计算加权校验信息的思路是加权译码算法的核心，虽然与的单纯的比特翻转译码算法相比，这种算法的复杂度会增加；不过相应地，其译码性能会更好。4.1.3置信传播译码算法使用置信传播算法进行相关的译码操作时，表示LDPC码的二分图中环路的长度决定了性能的好坏。如果一个环路的周长很小，那么就会存在高度相关的译码信息，尤其是当环路的周长是4的时候，而这些高度相关的译码信息会使译码性能受到局限。所以若要使置信传播译码算法尽可能地发挥优良性能，那么就必须避免周长很小的环路，特别是周长是4的环路郭锐, 刘济林. LDPC 码的一种低复杂度 BP 译码算法J. 浙江大学学报: 工学版, 2008, 42(3): 4

44、50-455.。置信传播算法包括两个交替的部分，在这一过程中，每一个位于奇偶校验矩阵H中的非零元素，都会有两个对应的变量，而这两个变量进行迭代并且会更新，直到因为译码成功而停止或者因为达到最大迭代而终止。特别要说明的是：就存储需求量方面，有关对数域和一般的置信传播这两种译码算法的要求是基本相同的贺玉成, 杨莉, 王新梅, 等. 置信传播译码算法的性能测度J. 电子学报, 2002, 30(4): 576-580.。他们的不同点在于：一般的置信传播算法以进行乘法运算为代价，而另外一个是加法运算。再综合函数方面的运算，并且结合硬件限制条件可以得出：就硬件实现这一项，显然对数域的置信传播算法要更好。

45、4.2小结研究表明：有多种译码算法适用于LDPC码的译码，对于那些性能较好的译码算法，相应的复杂度也越高，而那些复杂度较低的译码算法，其性能也会相对较差。20LDPC码译码方法相对其他信道编码较为简单，其间一个重要的原因是校验性矩阵的拥有稀疏性的特点，所以在一定条件下，运算量会呈现线性增长。当然，译码性能的差异是一定存在的，原因可能很多，比如：不同的译码方法要进行的运算有所差别。比特翻转译码算法（BF译码算法）在很多情况下相对复杂度低，在一些特殊场合也具有重要的应用前景。然而在实际情况中，必须综合考虑性能要求、硬件本身的条件等多个因素，从而在性能与复杂度之间找到一个合理点，以此来选择合适的译码

46、算法。5 LDPC编译码算法仿真平台的实现5.1 LDPC编译码过程由前面的章节绘制得出LDPC编译码流程如下：开始构造近似下三角形H矩阵输入信息比特流编码与调制信道中传输接收端BF译码统计误码个数计算BER结束5.2 仿真结果展示分析这次的所有编译码的实现都是基于MATLAB，因为MATLAB能够集成可视化和数值计算，在操作过程中极大地提供了便捷。MATLAB本身提供了大量的函数，这些函数覆盖了与科学有关的计算、关于系统的控制、信息处理等领域，能够完成的工作包括从分析到仿真再到工作设计。由于MATLAB的开放式结构使得在扩充功能方面变得相对容易。MATLAB另一个优点就是分析和处理数据的能力十分强大，而且对于矩阵的处理运算有十分高效，因此可以运用MATLAB完成对LDPC码的仿真贺玉成, 杨莉, 王新梅, 等. 置信传播译码算法的性能测度J. 电子学报, 2002, 30(4): 576-580.。如下截图： 由信道编码定理确定Eb / N0的下限，得出LDPC码在不同的误码率下的特征曲线图。在不同信噪比下（设置的是由0到1.8），当码长L是504，比特率r为1/2时，LDPC码在加性高斯白噪声AWGN下的性能仿真。由图片可以看出，随着信噪比增加，平均误码率减小很明显。一般来说，信噪比越大，说明混在信号里的噪声越小，声音回放的音质量