LDPC码性能研究毕业设计说明书

1、本科毕业设计（论文）题目ldpc码性能研究摘 要信道编码是数字通信系统的重要组成部分。ldpc信道编码技术是编码界的重要成果之一。1/2码率的二元ldpc码在awgn信道下的性能距信息理论中的shannon极限仅差0.0045db，它是目前距shannon极限最近的纠错码。gallagar在1962年提出ldpc码，1996年经过mackey、spielman和wiberg等人的再发现后，ldpc码以其性能优越、全并行迭代译码结构、便于硬件实现等优点，在无线通信、存储工业等领域得到了广泛应用。校验矩阵的构造是编码的前提，本文采用了随机构造法构造，并对矩阵的多种变换方法进行分析，比较了优缺点。译

2、码算法是ldpc码的关键，译码复杂度的大小直接影响系统的实现。主要分硬判决译码、软判决和复合译码。设计中采用的译码方式是软判决译码。在性能分析方面，利用matlab仿真码长、列重和迭代次数对ldpc码性能的影响。仿真结果表明，在一定范围内，ldpc码长码的误码性能优于短码；码长较小时，列重的增加会使性能变差，而对于长码，列重在一定范围内的增大会改善ldpc的误码性能；增加迭代次数会使误码率降低，但当迭代次数大到一定值时，误码率将不会再随着迭代次数的增加而降低。关键词 ldpc码 信道编码 矩阵变换 性能分析 abstractchannel coding is an important comp

3、onent for digital communication systems. ldpc channel coding technology is one important achievement of the encoding results. the performance of half of the binary bit-rate ldpc codes in awgn channel only has a tap of 0.0045db to the shannon limit that makes it be the latest error-correcting codes f

4、rom the shannon limit. gallager proposed ldpc codes in 1962, after mackey and others re-discovered it in 1996, with best performance, completely decoding algorithm in parallel scheme and easily realized for hardware design, ldpc codes has already been widely used in many practical systems such as wi

5、reless communication system and storage system.the construction of the check matrix is a precondition for coding; the randomized method was used in this paper. several ways to transform the matrix was discussed and being compared about the merits of each method. the decoding algorithm is the key to

6、ldpc code and the complexity of decoding direct impact realization of the system. there are three kinds of decoding algorithms: hard-decision method, soft-decision methods and hybrid decoding. the hard-decision method was used in this design.based on studying the basic theory of ldpc codes, the impa

7、ct of codes length, column weight and iteration times on ber performance of ldpc codes are demonstrated by computer simulation and theoretical analysis. the simulation experiment indicated that: ldpc codes long-code error performance is superior to short-code error performance, but when the code len

8、gth reaches a certain value, and then increase the code length, ber of ldpc codes lower rate will be small. when the code length is small, increasing the column weight, ldpc codes performance will deteriorate; when code length is large enough, increasing the column weight, ldpc codes performance wil

9、l be improved, but when the column weight reaches a certain value, as set out priority to increasing the performance of ldpc codes will be worse. to increase the number of decoding iterations, ldpc codes performance will be improved; but when the number of iterations is large enough, then increase t

10、he number of iterations, ldpc codes will no longer reduce the error rate.key wordsldpc codeschannel codingmatrix transformationperformance analysis目 录摘 要iabstractii第1章 绪论11.1 数字通信系统11.2 信道编码理论及其发展21.3 低密度奇偶校验码的提出、发展和现状4第2章 预备知识72.1 线性分组码72.2 信道容量和香农极限12第3章 ldpc码表示及编码143.1 ldpc码的定义及其tanner图表示143.1.1

11、ldpc码的定义及其描述143.1.2 ldpc码的tanner图表示153.2 二进制ldpc码的编码原理163.2.1 h矩阵的构造163.2.2 ldpc码的编码思想17第4章 ldpc码的译码思想224.1 软判决译码算法224.1.1 tanner图解析法原理224.1.2 spa算法原理244.1.3 对数域bp译码算法274.1.4 最小和（min-sum）译码算法（改进的对数域bp译码算法）284.2硬判决译码算法294.2.1 gallager的比特反转译码算法294.2.2 改进的比特反转译码算法304.3 优化的基于加权错误校验的ldpc比特反转算法（iwvbf）31第5

12、章 程序流程分析335.1 主程序335.2 h矩阵生成345.3 编码过程355.4 译码过程36第6章 ldpc码的性能分析376.1 码长对ldpc码性能的影响376.2 列重对ldpc码性能的影响376.3 迭代次数对ldpc码性能的影响386.4 h矩阵变换方法对性能的影响39总结与展望43参考文献44致 谢45附 录46第1章 绪论本章简要介绍了数字通信系统，并对系统中的每一部分进行了功能性说明，介绍了信道编码理论及其发展历程，最后概述了低密度奇偶校验码的提出、发展和现状。1.1 数字通信系统通信系统的基本目的在于将信息由信源高效、可靠、安全地传送到信宿。在信息传输的过程中，信道中

13、的噪声会不可避免地对传输信息产生干扰，从而导致了可靠性的降低。所以，通信系统设计的核心问题在于如何克服信道中随机噪声对信号的干扰，减小信息传输产生的差错，同时在最大程度上保证信息传输的效率，即如何解决系统有效性和可靠性的矛盾。一般地，通信系统的可靠性用误比特率（ber）来衡量，其有效性则用信息传输速率r比特/信道符号来衡量。早期的人们普遍认为：通信系统的可靠性与有效性之间存在不可调和的矛盾，一方的改善总是以牺牲另一方为代价，并指出当功率受限时，在有扰通信信道上实现任意小错误概率的信息传输的唯一途径就是把信息传输速率降低至零。shannon信息和编码理论的奠基性论文“通信的数学理论”于1948年

14、发表之后，改变了这一观点。他首次阐明了在有扰信道上实现可靠通信的方法，指出实现有效而可靠地信息传输的途径就是通过编码。根据shannon的信息理论，数字通信系统的基本组成如图1.1所示：图1.1 数字通信系统的基本组成图中，信源的作用为产生需要传送的信息，信息可以是模拟信号也可以是数字信号。如果是模拟信号，在进入数字通信系统之前需要进行采样和量化处理。信源编码器的主要作用是将信源发出的信息，例如语音、图像或者是文字等原始的数据进行转化，在保证通信质量的前提下，尽可能的通过对信号的压缩，提高通信系统的有效性。以更少的符号来表示原始信息，使信息能够更好的在传输媒介中进行传输。信道编码是在发送器和接

15、收器之间实现信号可靠传输的必要手段之一。传输信道中存在的噪声必然会对传输的信息引入失真和信号判决错误，因此需要采用差错控制码来检测和纠正这些比特错误。信道编码器的主要作用是通过对信源编码后的信息加入冗余信息，使得接收方在收到信号后，可以通过信道编码中的冗余信息进行前向纠错，以保证通信系统的可靠性。数字调制器的作用是使信息变成能够适应信道传输的信号。信号经过调制器后进入物理信道进行传输。典型的物理信道包括有线信道、无线信道、光纤信道、卫星信道等，针对不同的信道设计通信系统时要有不同的考虑，如无线信道会收到多径的影响而产生衰落，而卫星信道会受到信号功率衰减的影响等。信号到达接收端后，通过数字解调器

16、对接收到的调制信号序列或传输码字进行最优估计，然后输出数字编码序列送到信道译码器。信道译码器对信息进行估计和判决，估计准则是根据编码准则和信道特性而确定的，目的是最小化信道噪声的影响。最后信源译码器根据信源编码准则将得到的信道编码器输出的编码信息序列经过相应的信源译码后，得到对原始信息序列的估计。1.2 信道编码理论及其发展图1.1中的信道编译码部分是以特定的控制手段，引入适量冗余比特，以克服信息在传输过程中受到的噪声和干扰影响。根据shannon提出的信道编码定理，对任意一个平稳离散无记忆有噪声信源，都有一个固定的量，称之为信道容量，记做c。只要信息的传输速率低于信道容量，就必然存在一种编码

17、方法，使得信息出现差错的概率随码长的增加趋于任意小；反之，当信息传输速率超过信道容量时，则不存在这样的编码方法。这就是著名的信道编码定理，它给出了特定信道上信息传输速率的上确界。信道编码定理：任意离散输入无记忆平稳信道存在信道容量，对预期的任一数据速率和任一错误概率，有可能设计一对编译码器，以保证该信道中速率为r的数据传输具有小于p的译码错误概率。信道编码定理指出，在有扰信道中，只要信息传输速率小于信道容量，就有可能实现任意可靠的信息传输。这个存在性定理提醒我们可以实现以接近信道容量的传输速率进行通信。但遗憾的是该定理采用的是非构造性的证明方法，其中并没有给出逼近信道容量的码的具体编译码方法。

18、shannon在信道编码定理的证明中引用了三个基本条件，即：(1)、采用随机的编码方式；(2)、码字长度趋近于无穷大；(3)、译码采用最佳的最大似然译码。一般可将信道编译码器所使用的纠错码从性能上分为坏码和好码。所谓坏码是指只有将码率降至零才能使误码率为任意小的编码方式；而好码又可以分为当误码率任意小时，码率逼近信道容量限的非常好码和码率可达到的非零最大值小于信道容量限的一般好码。虽然shannon指出一个随机选择的码以很高的概率为好码，但随机码的最大似然译码的复杂度往往与码长呈指数关系，即在误码率随码长趋于无穷而趋向于零的同时，译码复杂度以指数增长，而在实际应用中，只能够使用以码长多项式的时

19、间和空间复杂度内完成编译码的纠错码，因而尽管一般的随机码是好码，但不能看作是实用码。自信道编码定理提出以来，如何构造一个逼近信道容量限的实用好码成了众多研究学者竟相研究的课题，并逐渐形成信息论的一个重要分支信道编码理论。五十多年来，人们构造实用好码的探索基本上是按照shannon所引用的基本条件的后两条为主线展开的。虽然从理论上讲，除了目前已知的码外，几乎所有的码都是好码，但到目前为止，构造出真正意义上的实用好码还有较长的距离。虽然如此，通过众多学者，特别是有关数学和信息论学术界的研究人员五十多年的共同努力，目前已经取得了很多成果。下面对其进行简要概述。纠错码从构造方法上可分为分组码（bloc

20、k codes）和卷积码（convolutional codes）两大部分。在分组码方面，第一个分组码是1950年发现的能纠正单个错误的hamming码；在整个50年代，基于代数理论又发现了多个短码长的分组码，如1954年golay发现的golay码以及reed和muller发现的rm码，prange在1957年发现的循环码等。最有意义的是bose和ray-chaudhuri在1960年及hocuenghem在1959年分别独立发现的能纠正多个错误的bch码，以及reed和solomon在1960发现的非二进制rs码。实际上，bch码可以看作是某个rs码的子域子码，而rs码又可以看作是bch码

21、的特例。其后发现的分组码主要有1970年的goppa码和1982年发现的代数几何码。在所有这些分组码中，除了goppa码和代数几何码中存在个别达到gv限的渐进好码外，其它均不是好码。分组码的译码主要采用基于代数的硬判决译码。卷积码最早由elias提出，早期被称为树码（tree codes），现在称为格图码（trellis codes）或卷积码。卷积码具有动态格图结构，可用有限状态机来描述其状态。由于缺乏有效的理论研究工具，对卷积码的有效研究成果不是很多，目前性能好的卷积码的构造方法主要借助于计算机搜索来获得。卷积码的译码一般采用概率译码，由于译码算法的简单、实用和易于实现，卷积码被广泛应用于实

22、际中。1966年，forney将分组码和卷积码结合起来，提出了级联码（concatenated codes）的概念。级联码一般采用rs码作为外码，卷积码作为内码。forney的研究表明，级联码在性能得到较大改善的情况下，其译码复杂度并不显著增加。根据对接收信号处理方式的不同，纠错码的译码可以分为硬判决译码和软判决译码。硬判决译码是基于传统纠错码观点的译码方法，解调器首先对信道输出值进行最佳硬判决，再将判决结果送入译码器，译码器根据解调器的判决结果，利用码字的代数结构来纠正其中的错误。而软判决译码则充分利用了信道输出的波形信息，解调器将匹配滤波器输出的一个实数值送入译码器，由于实数值包含了比硬判

23、决更多的信道信息，译码器能够通过概率译码充分利用这些信息，从而获得比硬判决译码更大的编码增益。总之，尽管随机码是理论上的好码，但由于其编码实现的困难性和无法承受的译码复杂度而只被用做理论分析的工具，在信道编码定理和后来的许多编码理论成果中，代数编码理论始终占据了主导地位，使得传统的信道编码技术受到临界速率（critical rate），也称做截止速率（cutoff rate）的限制。1993年turbo码的提出被看作是信道编码理论研究的重要里程碑。berrou等人将卷积码和随机交织器相结合，同时采用软输出迭代译码来逼近最大似然译码，取得了超乎寻常的优异性能，并一举超越了截止速率，直接逼近sha

24、nnon提出的信道容量限。turbo码是一种信道编码理论界梦寐以求的可实用非常好码，它的出现标志着信道编码理论研究进入了一个崭新的阶段。turbo码成功的根本原因在于其实现方案中长码构造的伪随机性是核心，它通过随机交织器对信息序列的伪随机置换实现了随机编码的思想，从而为shannon随机编码理论的应用研究奠定了基础。随着turbo码的深入研究，人们重新发现gallager早在1962年提出的低密度校验码（low density parity-check codes，简称ldpc码）也是一种具有渐进特性的非常好码，它的译码性能同样可以逼近shannon信道容量限。由于ldpc码具有在中长码长时超

25、过turbo码的性能，并且具有译码复杂度更低，能够并行译码及译码错误可检测等特点，成为目前信道编码理论的研究热点。研究表明，turbo码只是ldpc码的一个特例，两者都是基于图构造的低密度码，译码算法具有等价性，从而使两者在基于图模型的编译码研究中得到了统一。1.3 低密度奇偶校验码的提出、发展和现状1962年，gallager在他的博士论文中提出了二元正则ldpc码，也被称做gallager码。gallager证明了这类码具有很好的汉明距离特性，是满足gv限的渐进好码，在计算树上进行（n为码长）次后验概率迭代译码可以获得依码字长度指数降低的比特错误概率，但限于当时的计算能力，缺少可行的译码算

26、法，ldpc码被认为不是实用码，在很长一段时间内没有受到人们的重视。1981年，tanner在他的一篇奠基性的文章中正式提出了用图模型来描述码字的概念，从而将ldpc码的校验矩阵对应到被称为tanner图的双向二部图上。采用tanner图构造的ldpc码，通过并行译码可以显著地降低译码复杂度。tanner还仔细分析了最小和算法（min-sum algorithm）与和积算法（sum-product algorithm）两种信息传递算法，证明了基于有限无环tanner图的最小和译码算法与和积译码算法的最优性。但tanner图在实际当中是采用随机图构造的，其中不可避免地存在小环路现象，这些小的环路

27、会造成译码信息的重复传递，使译码过程中的消息之间不满足独立性假设，影响了迭代译码算法的收敛性。turbo码的发现重新引发了众多学者对ldpc码的研究兴趣。mackay和neal利用随机构造的tanner图研究了ldpc码的性能，发现采用和积译码算法的正则ldpc码具有和turbo码相似的译码性能，在长码时甚至超过了turbo码，这一结果引起了信道编码界的极大关注。此后，davey和mackay从减少tanner图上小环路的概念出发提出了基于的ldpc码，进一步提高了ldpc码的译码性能。在mackay和neal重新发现ldpc码优异性能的同时，spielman和sipser提出了基于二部扩展图

28、的扩展码。在对扩展码的研究中，他们证明了一个随机构造的tanner图以很大的概率为好的扩展图，而由好的扩展图构造的线性纠错码是渐进好码，从而证明了采用随机tanner图构造的ldpc码以很大概率是渐进好码。luby等人将采用非正则tanner图构造的扩展图用于删除信道，称之为tornado码。由于采用了非正则的tanner图，tornado码具有更大的扩展性和更好的收敛性，纠删性能更强。此后，采用优化度序列设计的非正则tanner图被用于构造ldpc码，称为非正则ldpc码，与正则ldpc码相比，非正则ldpc码的性能得到显著的提高。同时，wiberg结合turbo码和网格图的研究，将tann

29、er 图推广到包含隐含状态变量的因子图（factor graph），对turbo码和ldpc码的研究在因子图的基础上得到统一。wiberg对因子图的研究发现，对任意给定系统，无环图的状态复杂度是最大的，有环图的状态复杂度则会大大降低，从而证明了基于有环tanner图的ldpc码具有较低的译码复杂度。wiberg同时还证明了最小和算法和和积算法在本质上的同一性，在格图译码中，最小和算法退化为viterbi译码算法，和积算法退化为bcjr译码算法。近两年，richardson等人应用密度进化理论来测度ldpc码的性能。richardson等人在对ldpc码的研究中发现，译码信息的迭代传递过程中存在

30、着译码阈值现象，即当信噪比大于译码阈值时，迭代译码可使误码率趋于零，反之无论采用多长的ldpc码，经过多少次迭代译码，总存在一定的错误概率。应用中心极限定理，richardson等人证明了有限随机有环图的译码阈值可以逼近无环图的译码阈值。通过建立在无环图上的密度进化理论，可以精确地计算无环图上ldpc码的译码阈值，分析其译码收敛条件，从而近似估算有环tanner图上ldpc码的性能。研究表明，译码阈值的大小与ldpc码的构造参数密切相关，采用优化度序列设计的非正则ldpc码可以有效地改善阈值，因此密度进化理论可以用于指导ldpc码的优化设计。chung等通过对密度进化理论的研究，进一步提出了应

31、用高斯逼近原理来简化译码阈值计算和收敛性分析，从而使测度ldpc码性能的模型由多参数动态系统的密度进化理论模型简化为单一参数动态系统的高斯逼近模型。第2章 预备知识本章以汉明码为例，介绍了线性分组码的一般原理，并以此为后文中ldpc码的编码原理及程序中编码算法设计打下理论基础，同时通过对线性分组码的分析介绍，形象地表现了信道编解码过程中的纠错检错过程。此外，还对信道容量以及香农极限进行了说明。2.1 线性分组码在第一章中已经提到，信道编码的目的是提高信号传输的可靠性。信道编码是在经过信源编码的码元中增加一些多余的比特，目的在于利用这些特殊的多余比特去发现或纠正传输中发现的错误。在信道编码只有发

32、现错码能力而无纠错能力时，必须结合其他的措施来纠正错码，否则只能将发现为错码的码元删除，以求避免错码带来的负面影响。在线性分组码中，使用线性代数方程来决定监督位与信息位之间的关系，所谓监督位即在码元中添加的冗余比特。线性分组码的构造方式较为简单、理论较为成熟。本章以汉明码为例介绍线性分组码的一般原理。这种编码方法是由汉明（r. w. hamming）与1950年提出的。汉明码是一种能够纠正一个错码的效率较高的线性分组码。对于偶数监督码而言，在接收端解码时，实际上就是在计算下式： (2-1)若计算出的s=0，就认为无错码；若计算出的s=1，就认为有错码。现在将式(2-1)成为监督关系式，s为校正

33、子。由于校正子是一个二进制数字，他只有两种取值，故只能表示有错和无错，而不能进一步的指明错码的位置。不难推想，若此码长增加一位，即有两个监督位，则能增加一个类似式(2-1)的监督关系式。这样就能得到两个校正子。两个校正子的可能取值有4种组合，即00，01，10，11，故能表示4种不同的信息。若用其中一种组合表示无错码，则还有其他3种组合可以用于指明一个错码的3个不同位置。因此，若有r个监督关系式，则r个校正子可以指明一个错码的()个不同的位置。只有当校正子可以指明的错码位置数目等于或大于码组长度n时，才能够纠正码组中任何一个位置上的错码，即要求： (2-2)下面通过一个例子来说明如何具体构造监

34、督关系式。要求设计一个能够纠正1个错码的分组码(n,k)，给定的码组中有4个监督位，即k=4.由式(2-2)可知，这时要求监督位数。若取，则。现在用表示这7个码元，用表示校正子，这三个校正子恰好能够指明个错码的位置。例如，可以按照表2.1所示规定校正子和错码位置的关系。当然，也可以做其他的规定，这不影响讨论的一般性。表2.1 校正子和错码位置关系错码位置错码位置001101010110100111011000无错码由此表可见，仅当在位置上有错码时，校正子的值才等于1；否则的值等于0。这意味着4个码元构成偶数监督关系：(2-3)同理，构成如下偶数监督关系：(2-4)以及构成如下偶数监督关系：(2

35、-5)在编码时，信息位的决定于输入信号，他们是随机的。监督位是按照监督关系决定的，应该保证上列3个式子中的校正子等于0，即有：(2-6)上式可改写为：(2-7)若信息位的值给定，则可以根据上式计算出监督位的值。这样计算出的结果见表2.2。表2.2 监督位计算结果0000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111在接收端解码时，对于每个接收码组，先按式(2-3)至式(2-5)计算出校正子，然后按照表2.1判断错码的位置。例如

36、，若接收码组为0000011，则按式(2-3)至式(2-5)计算得到：。这样，由表2.1可知，错码位置在。按照上述方法构造的码成为汉明码。上面例子中的汉明码是(7,4)码，其最小码距。由式(2-4)和式(2-5)可知，此码能够检测2个错码，或纠正1个错码。汉明码的码率可以由式(2-2)取等号时的值得出： (2-8)当r或n很大时，上式趋近于1.所以汉明码是一种高效编码。在讨论上面实例的基础上，现在介绍线性分组码的一般原理。前面已经说明，线性分组码的监督位和信息位的关系是由一组线性代数方程决定的。式(2-6)就是这样的方程式，将此式改写成下列形式：(2-9)在上式中已经将简写成。代表模2加法。式

37、(2-9)可以改写成如下的矩阵形式：(2-10)将上式改写为： 或 (2-11)式中， (2-12)上标“t”表示将矩阵转置，即将矩阵的第一行变为矩阵的第一列，将矩阵的第二行变为矩阵的第二列我们将上式中的h称为监督矩阵。监督矩阵给定后，码组中的信息位和监督位的关系就随之确定了，比较式(2-9)和式(2-10)可以看出，h的行数就是监督关系式的数目，即监督位数r。h的每行中各个“1”的位置表示相应的码元参与监督关系。例如，h的第一行1110100表示监督位是由之和确定的。式(2-11)中的h可以分为如下两部分：(2-13)式中，为阶矩阵，为阶单位方阵。我们将如上式形式所表示的监督矩阵称为典型监督

38、矩阵。由代数理论可知，h矩阵的各行应该是线性无关的，否则将得不到r个线性无关的监督关系式，从而也得不到r个独立的监督位。若一个矩阵能够写成典型阵形式，则其各行也一定是线性无关的。因为容易验证，的各行是线性无关的，故的各行也是线性无关的。式(2-7)也可以仿照式(2-9)的做法，写成如下矩阵形式：(2-14)上式两端分别转置后，可以变成：(2-15)式中，q为阶矩阵，是p的转置，即：(2-16)式(1-15)表示，在信息位给定后，用信息位的行矩阵乘以矩阵q就得出监督位。我们将q的左边加上一个k阶单位阵，构成如下矩阵：(2-17)g称为生成矩阵，因为可以用它产生整个码组a，即有：(2-18)具有形

39、式的生成矩阵成为典型生成矩阵。由典型生成矩阵得出的码组a中，信息位的位置不变，监督位附加于其后。这种形式的码组称为系统码。比较式(2-13)和式(2-17)可见，典型监督矩阵h和典型生成矩阵g之间通过式(2-16)联系。与对矩阵h的要求相似，矩阵g的各行也必须是线性无关的。因为由式(2-18)得知，任意一个码组a都是g的各行的线性组合。g共有k行，若他们线性无关，则可以组合出种不同的码组，这恰好是有k位信息位的全部码组。若g的各行中有线性相关的，则不可能生成种不同的码组了。实际上，g的各行本身就是一个码组。因此，如果已有k个线性无关的码组，则可以将其用作生成矩阵g，并由它产生其余的码组。一般来

40、说，式(2-18)中的a是一个n列的列矩阵：(2-19)它的n个元素就是码组中的n个码元。所以发送码组就是a。由于传输中的干扰影响，接收码组可能出现错码而有别于a。设接收码组是一个n列的行矩阵：(2-20)令接收码组和发送码组之差为： (模2)(2-21)e就是错码的行矩阵，有时还称其为错误图样：(2-22)式中，。因此，若，则表示该码元未错；若，表示该码元为错码。式(2-21)还可以改写成：(2-23)上式表示发送码组a与错误码组e之和等于接收码组b。例如，若发送码组，错码矩阵，则接收码组。在接收端解码时，令式(2-11)中的a等于接收码组b进行计算。若接收码组b中无错码（），由式(2-23

41、)得知，则式(2-11)仍成立。这时有：(2-24)当接收码组中有错码时，此时将b代入式(2-11)后，该式不一定成立。此外，在错码较多并超出这种编码的检错能力时，b可能变为另一个许用码组，故式(2-11)仍有可能成立。这时的错码将是不可检测的。所以只有当错码未超出检测能力时，式(2-24)才不成立。假设，这时式(2-24)的右端等于s，即有：(2-25)将式(2-23)代入(2-25)，得到：由式(2-11)可知，上式右端第一项等于0，所以：(2-26)式中，s就是由式(2-1)中的校正子s构成的矩阵，所以也成为校正子，它同样可以用来指示错码的位置。当h确定后，式(2-26)中，s只与e有关

42、，而与a无关。这意味着s和错码e之间有确定的线性变换关系。若s和e有一一对应关系，则s将能代表错码位置。线性码有一个重要性质，就是它具有封闭性。封闭性是指一种线性码中任意两个码组之和仍为这种编码中的一个码组。下面对此做一简单证明：若和是两个码组，则由式(2-11)有： 将以上两式相加得：(2-27)所以也是一个码组。由于线性码具有封闭性，所以两个码组和之间的距离（即对应位不同的数目）必定是另一个码组的重量（即“1”的数目）。因此，码的最小距离就是码的最小重量（除全“0”码组外）。2.2 信道容量和香农极限信道容量表示一个信道下可靠传输的最大信息传输速率。不同的信道，噪声的存在形式不同，信道带宽

43、以及信号的各种限制不同，因而信道容量也不相同。香农在其文章中定义的信道容量为： (2-28)x和y分别代表信道的输入和输出，是x的概率密度函数；是x和y的互信息量；h(x)是信源熵；h(y/x)为信道条件熵，即因为信道噪声而造成的信息损失熵。对于宽带无限的加性高斯白噪声(awgn)信道，信道容量为： (2-29)是传输信号的平均功率，为高斯白噪声的功率谱密度。对于带宽为w，信号平均功率为的带限awgn信道，信道容量为： (2-30)式(2-30)即为著名的香农信道容量公式。对于低密度码的研究，需要涉及到输入离散、输出连续的awgn信道。由于只有输入符号均匀分布时才能使互信息量达到最大，因此假设

44、输入符号的概率密度函数为： (2-31)即： (2-32)对于awgn信道可得： (2-33)(2-34)将式(2-33)和(2-34)代入式(2-28)有(2-35)r表示码率，表示传输每一个比特所需要的能量，与关系为。因为式(2-35)无法求出解析解，故智能采用数值仿真的方法近似求解。同时需要根据y的特点对其积分区域进行缩减，于是得到： (2-36)其中当传输错误概率时，得到的shannon极限为(2-37)可以看出这与理想awgn信道的shannon极限是完全一致的。我们知道在实际研究中，r是不可能趋近于0的。所以利用式(2-36)，再考虑满速率传输的情况(r=c)，就可以得出不同的r下

45、达到信道容量极限时所需的做小信噪比，如图2.1所示。图2.1 二进制awgn的信道容量上图给出了不同编码速率r下二进制awgn信道的信道容量。可以看出，当评估某一信道编码的性能时，不能直接用它的性能和一般意义下的shannon极限（-1.6db）进行比较，而应该根据它的码率在达到实际信道容量时所需的最小信噪比，并用来和其性能做比较，这样才更合理。下表列举出了一些常见码率下所对应的最小信噪比值。表2.3 不同码率条件下awgn信道的最小信噪比码率(r)最低信噪比(db)8/93.0034/52.0402/31.0601/20.1871/3-0.4950-1.6第3章 ldpc码表示及编码本章系统

46、地概述了ldpc码的定义及其tanner图表示，以及二进制ldpc码的编码原理。3.1 ldpc码的定义及其tanner图表示3.1.1 ldpc码的定义及其描述一个码长为n、信息位个数为k的线性分组码可以由一个生成矩阵来定义，信息序列通过g被映射到码字。线性分组码也可以由一个一致校验矩阵来等效描述，所有码字均满足。校验矩阵每一行表示一个校验约束，其中所有非零元素对应的码元变量构成一个校验集，用一个校验方程表示；校验矩阵的每一行表示一个码元变量参与的校验约束，当列元素不为零时，表示该码元变量参与了该行的校验约束。码元变量与检验方程之间的关系成为结构。下面主要对二元ldpc码进行讨论。ldpc码

47、是一种线性分组码，它的名字来源于其校验矩阵h的稀疏性，即校验矩阵中只有数量很少的元素为“1”，大部分都是“0”。gallager最早给出了正则ldpc码的定义，具体来讲正则ldpc码的校验矩阵h满足下列三个条件：(1)、h的每行有个“1”；(2)、h的每列有个“1”，;(3)、与码长和h矩阵的行数相比，和都很小。图3.1 (20,3,4)ldpc码的校验矩阵矩阵h的每列各自包含个“1”，表示每个码元变量受到相同数目的校验约束；每行也各自包含个“1”，表示每个校验方程对相同数目的码元变量进行校验约束；由于和都很小，校验矩阵具有很低的“密度”，因此由校验矩阵所确定的码称为ldpc码。gallage

48、r证明了当时，这类码具有很好的汉明距离特性。正则ldpc码通常用来表示，其中n为码长,和的含义不变，图3.1给出了一个(20,3,4)正则ldpc码的校验矩阵。当校验矩阵h各行（列）中“1”的个数不全相同时，就得到了非正则ldpc码。3.1.2 ldpc码的tanner图表示设一个正则ldpc码c具有校验矩阵，其对应的tanner图模型可以表示为一个二部图。其中码字向量表示为一组比特节点，分别对应于校验矩阵的各列，而校验约束则表示为一组校验节点，对应与校验矩阵的各行。仅当时，比特节点与校验节点之间有一条边相连，节点与之间互称邻接节点，其间的连接边称为两个节点的邻接边。对于正则ldpc码，每个比

49、特节点与个个校验节点相连，称该比特节点的度为；每个校验节点与个比特节点相连，称该校验节点的度为，度表示与节点相连的边的数目。图3.2给出了图3.1所示校验矩阵对应的tanner图结构。图3.2 (20,3,4)ldpc码的tanner图表示根据比特节点与校验方程之间的约束关系可以得知，tanner图中中所有比特节点发出的边的数目必然等于所有校验方程所接收的边的总数。那么对于ldpc码(n，j，k)，若假设m为校验方程的个数，即校验矩阵h的行数，则以下等式必然成立：(3-1)对于非正则的ldpc码，每个校验方程约束的比特节点数目不一样，同时每个比特节点受约束的校验方程的数目也不一样。反映在tan

50、ner图中就是每个点（比特节点和约束节点）所连接的边的数目是不完全相同的。这样一种不规则的ldpc码在码长很大的时候性能要比正则的ldpc码好，这是由于“波浪效应”（wave effect）所致。一部分比特节点受到约束的校验方程数目比较多，即收到的约束度比较高，那么其正确译码的速度也相对比较快；以此同时，这些约束度较高的点也为其他约束度较低的点提供了更为准确的译码外信息，最终使得所有比特节点正确译码的速度更快。又因为校验矩阵h中每行和每列1的个数不同，所以不能再用(n,j,k)的方式来进行表示。为了准确地表达一个非正则的ldpc码，我们引入如下表达式： (3-2)其中表示比特节点的度的分布，表

51、示校验节点的度的分布；满足及。正则ldpc码可以看成是非正则ldpc码的特例，对于(n,3,4)形式的正则ldpc码，相应边的度分布多项式分别退化为。3.2 二进制ldpc码的编码原理3.2.1 h矩阵的构造由于ldpc码是以校验矩阵h为特征的，不同的校验矩阵h对应了不同的码字集合。因此，ldpc码的编码首先要设计校验矩阵h，同时这也是ldpc码编码的关键。对于规则的ldpc码(n,j,k)，在码长n一定的情况下，主要的参数选择则为j和k。目前的研究结果表明，性能最好的规则ldpc码是(n,3,6)码。根据式(3-1)可知，参数n,j,k确定后就可以得到校验方程的数目m，那么h矩阵的大小就可以

52、确定为。ldpc码校验矩阵h的一般构造步骤如下：首先生成一个的全0矩阵，然后随机地将每列中的j个0置换成1，每行当中的k个0置换成1。但是在随机置1的过程中，有两种情况是必须要避免的：(1)、出现长度为4的环在ldpc码校验矩阵h中有一个很重要的概念：h矩阵的最小围长(girth)，即通常说的环。h矩阵中的4环结构示意图如下：图3.3 h矩阵中的4环结构其对应tanner图如下：图3.4 tanner图中的4环结构当h矩阵中出现长度为4的环时，其结构会导致消息在两组点之间的反复传递，而难以得到更新，与迭代译码的思想初衷所违背，是必须清除的一种结构。我们另外做简单的解释，例如在图3.3所示的h矩

53、阵中，存在一个4环结构，于是这个4环对应的校验方程为：(3-3)(3-4)由于4环的存在，我们可以看到，上面两个校验方程含有共同的比特节点与，直观的说，如果这两个校验方程均出错，则我们无法确定与中究竟是哪个出错。从这个角度可以说明小循环对性能带来的影响。所以我们在矩阵h矩阵时要避免4环以及短环的存在。理论分析表明，最小环的长度为6的情况下，码字的最小距离为4。而随机构造的ldpc码的最小距离是随着分组长度，即码长的增加而线性增加的。(2)、比特节点所连接的校验方程过于集中当比特节点所连接的校验方程过于集中时，常常导致ldpc码错误地板的发生。例如在图3.5中，比特节点的度为3，但其中三个带阴影

54、的比特节点总共只连接了5个校验方程；除了最右边的一个校验方程外，其它4个校验方程中，每个都连接了两个阴影的比特节点。因此，如果这三个阴影的比特节点都出错时，左边的四个校验方程都不能检测到错误的存在。而当分组长度增大时，出现这种拓扑结构的可能性会随之减少。图3.5比特节点所连接校验方程过于集中的tanner图对于不规则的ldpc码其h矩阵的构造也遵循上述两个原则，不同的是校验矩阵h每行和每列中1的个数不再相同。在最早提出的不规则ldpc码中，比特节点和校验节点的度都是不均匀的，即校验矩阵h中每列，每行1的个数都不相同，但实际仿真结果表明，这种双边不均匀的情况并非最佳方案。实际的应用方案是让比特节

55、点的度(即校验矩阵h中每列i的个数)变化比较大，而保持校验节点的度(即校验矩阵h中每行1的个数)比较平均其中约束度比较大的比特节点称为优先点。在迭代译码过程中，优先点首先被正确译码的概率是最大的如何分配这些优先点，让哪些校验节点连接更多的优先点，是不规则ldpc码的一个研究方向。3.2.2 ldpc码的编码思想1、传统编码方法这种编码方法需要先将h矩阵进行变换得到一个生成矩阵g，然后利用信息序列与生成矩阵相乘进行编码。下面我们首先给出两个引理来说明校验矩阵经过高斯变换不会影响编码结果。引理1 设ldpc码的校验矩阵为，其中表示的是第k列的列向量，信息序列s编码后生成的码字为，如果将h矩阵的第i

56、列和第j列进行交换得到，则，原信息序列经过此新的校验矩阵编码后所得的码字为，即将原码字的第i个和第j个位置交换后得到新的码字。证明：由ldpc码校验矩阵和码字间的正交关系可得，即，所以。所以对校验矩阵进行列变换，得到的新码字也是对原码字进行同样位置的列变换。在编码时，只要记录下校验矩阵列变换的动作，对新校验矩阵下得到的码字进行同样位置的置换即可以得到原校验矩阵所对应的码字。引理2 使用高斯消元法对h矩阵进行行变换（即把h矩阵某一行按照模2相加到另一行上）不影响编码结果，变换所得的矩阵与原矩阵具有等价性。证明：在tanner图中可以看出，把h矩阵的第i行按照模2相加到第j行上，在tanner图上

57、即是从节点添加边到所有与相连的节点上，如果已经与该比特节点相连，则把该连接删掉。设分别表示原来与校验节点相连的所有比特节点的集合，表示的交集，表示与变换后的校验节点相连的比特节点的集合；符号表示按模2进行累加，“+”表示按模2 进行相加，表示第k个比特节点的值，由ldpc码的定义可得及，则有：(3-5)即，原来的码字仍可满足新校验矩阵的校验关系，所以，h矩阵进行行行变换不影响编码结果。下面介绍传统编码的基本理论和一般过程。设信息源为s，则编码生成的码字。这种编码方式是由最基本的原理推得的。当分组长度为n时，编码复杂度为，在移动通信中这种传播时延对于语音通信是不能忍受的。计算复杂度也会使得存储器的数量