1、I本科毕业设计（论文）题目LDPC码性能研究II摘要信道编码是数字通信系统的重要组成部分。LDPC信道编码技术是编码界的重要成果之一。1/2码率的二元LDPC码在AWGN信道下的性能距信息理论中的SHANNON极限仅差00045DB，它是目前距SHANNON极限最近的纠错码。GALLAGAR在1962年提出LDPC码，1996年经过MACKEY、SPIELMAN和WIBERG等人的再发现后，LDPC码以其性能优越、全并行迭代译码结构、便于硬件实现等优点，在无线通信、存储工业等领域得到了广泛应用。校验矩阵的构造是编码的前提，本文采用了随机构造法构造，并对矩阵的多种变换方法进行分析，比较了优缺点。
2、译码算法是LDPC码的关键，译码复杂度的大小直接影响系统的实现。主要分硬判决译码、软判决和复合译码。设计中采用的译码方式是软判决译码。在性能分析方面，利用MATLAB仿真码长、列重和迭代次数对LDPC码性能的影响。仿真结果表明，在一定范围内，LDPC码长码的误码性能优于短码；码长较小时，列重的增加会使性能变差，而对于长码，列重在一定范围内的增大会改善LDPC的误码性能；增加迭代次数会使误码率降低，但当迭代次数大到一定值时，误码率将不会再随着迭代次数的增加而降低。关键词LDPC码信道编码矩阵变换性能分析IIIABSTRACTCHANNELCODINGISANIMPORTANTCOMPONENTF
3、ORDIGITALCOMMUNICATIONSYSTEMSLDPCCHANNELCODINGTECHNOLOGYISONEIMPORTANTACHIEVEMENTOFTHEENCODINGRESULTSTHEPERFORMANCEOFHALFOFTHEBINARYBITRATELDPCCODESINAWGNCHANNELONLYHASATAPOF00045DBTOTHESHANNONLIMITTHATMAKESITBETHELATESTERRORCORRECTINGCODESFROMTHESHANNONLIMITGALLAGERPROPOSEDLDPCCODESIN1962,AFTERMACK
4、EYANDOTHERSREDISCOVEREDITIN1996,WITHBESTPERFORMANCE,COMPLETELYDECODINGALGORITHMINPARALLELSCHEMEANDEASILYREALIZEDFORHARDWAREDESIGN,LDPCCODESHASALREADYBEENWIDELYUSEDINMANYPRACTICALSYSTEMSSUCHASWIRELESSCOMMUNICATIONSYSTEMANDSTORAGESYSTEMTHECONSTRUCTIONOFTHECHECKMATRIXISAPRECONDITIONFORCODINGTHERANDOMIZ
5、EDMETHODWASUSEDINTHISPAPERSEVERALWAYSTOTRANSFORMTHEMATRIXWASDISCUSSEDANDBEINGCOMPAREDABOUTTHEMERITSOFEACHMETHODTHEDECODINGALGORITHMISTHEKEYTOLDPCCODEANDTHECOMPLEXITYOFDECODINGDIRECTIMPACTREALIZATIONOFTHESYSTEMTHEREARETHREEKINDSOFDECODINGALGORITHMSHARDDECISIONMETHOD,SOFTDECISIONMETHODSANDHYBRIDDECODI
6、NGTHEHARDDECISIONMETHODWASUSEDINTHISDESIGNBASEDONSTUDYINGTHEBASICTHEORYOFLDPCCODES,THEIMPACTOFCODESLENGTH,COLUMNWEIGHTANDITERATIONTIMESONBERPERFORMANCEOFLDPCCODESAREDEMONSTRATEDBYCOMPUTERSIMULATIONANDTHEORETICALANALYSISTHESIMULATIONEXPERIMENTINDICATEDTHATLDPCCODESLONGCODEERRORPERFORMANCEISSUPERIORTO
7、SHORTCODEERRORPERFORMANCE,BUTWHENTHECODELENGTHREACHESACERTAINVALUE,ANDTHENINCREASETHECODELENGTH,BEROFLDPCCODESLOWERRATEWILLBESMALLWHENTHECODELENGTHISSMALL,INCREASINGTHECOLUMNWEIGHT,LDPCCODESPERFORMANCEWILLDETERIORATEWHENCODELENGTHISLARGEENOUGH,INCREASINGTHECOLUMNWEIGHT,LDPCCODESPERFORMANCEWILLBEIMPR
8、OVED,BUTWHENTHECOLUMNWEIGHTREACHESACERTAINVALUE,ASSETOUTPRIORITYTOINCREASINGTHEPERFORMANCEOFLDPCCODESWILLBEWORSETOINCREASETHENUMBEROFDECODINGITERATIONS,LDPCCODESPERFORMANCEWILLBEIMPROVEDBUTWHENTHENUMBEROFITERATIONSISLARGEENOUGH,THENINCREASETHENUMBEROFITERATIONS,LDPCCODESWILLNOLONGERREDUCETHEERRORRAT
9、EKEYWORDSLDPCCODESCHANNELCODINGMATRIXTRANSFORMATIONPERFORMANCEANALYSIS目录摘要IABSTRACTIII第1章绪论111数字通信系统112信道编码理论及其发展213低密度奇偶校验码的提出、发展和现状4第2章预备知识721线性分组码722信道容量和香农极限11第3章LDPC码表示及编码1431LDPC码的定义及其TANNER图表示14311LDPC码的定义及其描述14312LDPC码的TANNER图表示1532二进制LDPC码的编码原理16321H矩阵的构造16322LDPC码的编码思想17第4章LDPC码的译码思想2241软判
10、决译码算法22411TANNER图解析法原理22412SPA算法原理24413对数域BP译码算法27414最小和（MINSUM）译码算法（改进的对数域BP译码算法）2942硬判决译码算法30421GALLAGER的比特反转译码算法30422改进的比特反转译码算法3143优化的基于加权错误校验的LDPC比特反转算法（IWVBF）31第5章程序流程分析3351主程序3352H矩阵生成3453编码过程3554译码过程36第6章LDPC码的性能分析3761码长对LDPC码性能的影响3762列重对LDPC码性能的影响3763迭代次数对LDPC码性能的影响3864H矩阵变换方法对性能的影响39总结与展望4
11、3参考文献44致谢45附录461第1章绪论本章简要介绍了数字通信系统，并对系统中的每一部分进行了功能性说明，介绍了信道编码理论及其发展历程，最后概述了低密度奇偶校验码的提出、发展和现状。11数字通信系统通信系统的基本目的在于将信息由信源高效、可靠、安全地传送到信宿。在信息传输的过程中，信道中的噪声会不可避免地对传输信息产生干扰，从而导致了可靠性的降低。所以，通信系统设计的核心问题在于如何克服信道中随机噪声对信号的干扰，减小信息传输产生的差错，同时在最大程度上保证信息传输的效率，即如何解决系统有效性和可靠性的矛盾。一般地，通信系统的可靠性用误比特率（BER）来衡量，其有效性则用信息传输速率R比特
12、/信道符号来衡量。早期的人们普遍认为通信系统的可靠性与有效性之间存在不可调和的矛盾，一方的改善总是以牺牲另一方为代价，并指出当功率受限时，在有扰通信信道上实现任意小错误概率的信息传输的唯一途径就是把信息传输速率降低至零。SHANNON信息和编码理论的奠基性论文“通信的数学理论”于1948年发表之后，改变了这一观点。他首次阐明了在有扰信道上实现可靠通信的方法，指出实现有效而可靠地信息传输的途径就是通过编码。根据SHANNON的信息理论，数字通信系统的基本组成如图11所示信源信源编码器信道编码器数字调制器信源译码器信道译码器数字解调器信道干扰信宿信宿调制信道编码信道图11数字通信系统的基本组成图中
13、，信源的作用为产生需要传送的信息，信息可以是模拟信号也可以是数字信2号。如果是模拟信号，在进入数字通信系统之前需要进行采样和量化处理。信源编码器的主要作用是将信源发出的信息，例如语音、图像或者是文字等原始的数据进行转化，在保证通信质量的前提下，尽可能的通过对信号的压缩，提高通信系统的有效性。以更少的符号来表示原始信息，使信息能够更好的在传输媒介中进行传输。信道编码是在发送器和接收器之间实现信号可靠传输的必要手段之一。传输信道中存在的噪声必然会对传输的信息引入失真和信号判决错误，因此需要采用差错控制码来检测和纠正这些比特错误。信道编码器的主要作用是通过对信源编码后的信息加入冗余信息，使得接收方在
14、收到信号后，可以通过信道编码中的冗余信息进行前向纠错，以保证通信系统的可靠性。数字调制器的作用是使信息变成能够适应信道传输的信号。信号经过调制器后进入物理信道进行传输。典型的物理信道包括有线信道、无线信道、光纤信道、卫星信道等，针对不同的信道设计通信系统时要有不同的考虑，如无线信道会收到多径的影响而产生衰落，而卫星信道会受到信号功率衰减的影响等。信号到达接收端后，通过数字解调器对接收到的调制信号序列或传输码字进行最优估计，然后输出数字编码序列送到信道译码器。信道译码器对信息进行估计和判决，估计准则是根据编码准则和信道特性而确定的，目的是最小化信道噪声的影响。最后信源译码器根据信源编码准则将得到
15、的信道编码器输出的编码信息序列经过相应的信源译码后，得到对原始信息序列的估计。12信道编码理论及其发展图11中的信道编译码部分是以特定的控制手段，引入适量冗余比特，以克服信息在传输过程中受到的噪声和干扰影响。根据SHANNON提出的信道编码定理，对任意一个平稳离散无记忆有噪声信源，都有一个固定的量，称之为信道容量，记做C。只要信息的传输速率低于信道容量，就必然存在一种编码方法，使得信息出现差错的概率随码长的增加趋于任意小；反之，当信息传输速率超过信道容量时，则不存在这样的编码方法。这就是著名的信道编码定理，它给出了特定信道上信息传输速率的上确界。信道编码定理任意离散输入无记忆平稳信道存在信道容
16、量，对预期的任一数据速率和任一错误概率，有可能设计一对编译码器，以保证该信道中速率为R的数据传输具有小于P的译码错误概率。信道编码定理指出，在有扰信道中，只要信息传输速率小于信道容量，就有可能实现任意可靠的信息传输。这个存在性定理提醒我们可以实现以接近信道容量的传输速率进行通信。但遗憾的是该定理采用的是非构造性的证明方法，其中并没有给出逼3近信道容量的码的具体编译码方法。SHANNON在信道编码定理的证明中引用了三个基本条件，即1、采用随机的编码方式；2、码字长度趋近于无穷大；3、译码采用最佳的最大似然译码。一般可将信道编译码器所使用的纠错码从性能上分为坏码和好码。所谓坏码是指只有将码率降至零
17、才能使误码率为任意小的编码方式；而好码又可以分为当误码率任意小时，码率逼近信道容量限的非常好码和码率可达到的非零最大值小于信道容量限的一般好码。虽然SHANNON指出一个随机选择的码以很高的概率为好码，但随机码的最大似然译码的复杂度往往与码长呈指数关系，即在误码率随码长趋于无穷而趋向于零的同时，译码复杂度以指数增长，而在实际应用中，只能够使用以码长多项式的时间和空间复杂度内完成编译码的纠错码，因而尽管一般的随机码是好码，但不能看作是实用码。自信道编码定理提出以来，如何构造一个逼近信道容量限的实用好码成了众多研究学者竟相研究的课题，并逐渐形成信息论的一个重要分支信道编码理论。五十多年来，人们构造
18、实用好码的探索基本上是按照SHANNON所引用的基本条件的后两条为主线展开的。虽然从理论上讲，除了目前已知的码外，几乎所有的码都是好码，但到目前为止，构造出真正意义上的实用好码还有较长的距离。虽然如此，通过众多学者，特别是有关数学和信息论学术界的研究人员五十多年的共同努力，目前已经取得了很多成果。下面对其进行简要概述。纠错码从构造方法上可分为分组码（BLOCKCODES）和卷积码（CONVOLUTIONALCODES）两大部分。在分组码方面，第一个分组码是1950年发现的能纠正单个错误的HAMMING码；在整个50年代，基于代数理论又发现了多个短码长的分组码，如1954年GOLAY发现的GOL
19、AY码以及REED和MULLER发现的RM码，PRANGE在1957年发现的循环码等。最有意义的是BOSE和RAYCHAUDHURI在1960年及HOCUENGHEM在1959年分别独立发现的能纠正多个错误的BCH码，以及REED和SOLOMON在1960发现的非二进制RS码。实际上，BCH码可以看作是某个RS码的子域子码，而RS码又可以看作是BCH码的特例。其后发现的分组码主要有1970年的GOPPA码和1982年发现的代数几何码。在所有这些分组码中，除了GOPPA码和代数几何码中存在个别达到GV限的渐进好码外，其它均不是好码。分组码的译码主要采用基于代数的硬判决译码。卷积码最早由ELIAS
20、提出，早期被称为树码（TREECODES），现在称为格图码（TRELLISCODES）或卷积码。卷积码具有动态格图结构，可用有限状态机来描述其状态。由于缺乏有效的理论研究工具，对卷积码的有效研究成果不是很多，目前性能好的卷积码的构造方法主要借助于计算机搜索来获得。卷积码的译码一般采用概率译码，由于译4码算法的简单、实用和易于实现，卷积码被广泛应用于实际中。1966年，FORNEY将分组码和卷积码结合起来，提出了级联码（CONCATENATEDCODES）的概念。级联码一般采用RS码作为外码，卷积码作为内码。FORNEY的研究表明，级联码在性能得到较大改善的情况下，其译码复杂度并不显著增加。根据
21、对接收信号处理方式的不同，纠错码的译码可以分为硬判决译码和软判决译码。硬判决译码是基于传统纠错码观点的译码方法，解调器首先对信道输出值进行最佳硬判决，再将判决结果送入译码器，译码器根据解调器的判决结果，利用码字的代数结构来纠正其中的错误。而软判决译码则充分利用了信道输出的波形信息，解调器将匹配滤波器输出的一个实数值送入译码器，由于实数值包含了比硬判决更多的信道信息，译码器能够通过概率译码充分利用这些信息，从而获得比硬判决译码更大的编码增益。总之，尽管随机码是理论上的好码，但由于其编码实现的困难性和无法承受的译码复杂度而只被用做理论分析的工具，在信道编码定理和后来的许多编码理论成果中，代数编码理
22、论始终占据了主导地位，使得传统的信道编码技术受到临界速率（CRITICALRATE），也称做截止速率（CUTOFFRATE）的限制。1993年TURBO码的提出被看作是信道编码理论研究的重要里程碑。BERROU等人将卷积码和随机交织器相结合，同时采用软输出迭代译码来逼近最大似然译码，取得了超乎寻常的优异性能，并一举超越了截止速率，直接逼近SHANNON提出的信道容量限。TURBO码是一种信道编码理论界梦寐以求的可实用非常好码，它的出现标志着信道编码理论研究进入了一个崭新的阶段。TURBO码成功的根本原因在于其实现方案中长码构造的伪随机性是核心，它通过随机交织器对信息序列的伪随机置换实现了随机编
23、码的思想，从而为SHANNON随机编码理论的应用研究奠定了基础。随着TURBO码的深入研究，人们重新发现GALLAGER早在1962年提出的低密度校验码（LOWDENSITYPARITYCHECKCODES，简称LDPC码）也是一种具有渐进特性的非常好码，它的译码性能同样可以逼近SHANNON信道容量限。由于LDPC码具有在中长码长时超过TURBO码的性能，并且具有译码复杂度更低，能够并行译码及译码错误可检测等特点，成为目前信道编码理论的研究热点。研究表明，TURBO码只是LDPC码的一个特例，两者都是基于图构造的低密度码，译码算法具有等价性，从而使两者在基于图模型的编译码研究中得到了统一。1
24、3低密度奇偶校验码的提出、发展和现状1962年，GALLAGER在他的博士论文中提出了二元正则LDPC码，也被称做GALLAGER码。GALLAGER证明了这类码具有很好的汉明距离特性，是满足GV限的渐进好码，在计算树上进行（N为码长）次后验概率迭代译码可以获得依码字长度指数降低的比特5错误概率，但限于当时的计算能力，缺少可行的译码算法，LDPC码被认为不是实用码，在很长一段时间内没有受到人们的重视。1981年，TANNER在他的一篇奠基性的文章中正式提出了用图模型来描述码字的概念，从而将LDPC码的校验矩阵对应到被称为TANNER图的双向二部图上。采用TANNER图构造的LDPC码，通过并行
25、译码可以显著地降低译码复杂度。TANNER还仔细分析了最小和算法（MINSUMALGORITHM）与和积算法（SUMPRODUCTALGORITHM）两种信息传递算法，证明了基于有限无环TANNER图的最小和译码算法与和积译码算法的最优性。但TANNER图在实际当中是采用随机图构造的，其中不可避免地存在小环路现象，这些小的环路会造成译码信息的重复传递，使译码过程中的消息之间不满足独立性假设，影响了迭代译码算法的收敛性。TURBO码的发现重新引发了众多学者对LDPC码的研究兴趣。MACKAY和NEAL利用随机构造的TANNER图研究了LDPC码的性能，发现采用和积译码算法的正则LDPC码具有和T
26、URBO码相似的译码性能，在长码时甚至超过了TURBO码，这一结果引起了信道编码界的极大关注。此后，DAVEY和MACKAY从减少TANNER图上小环路的概念出发提出了基于的LDPC码，进一步提高了LDPC码的译码性能。在MACKAY和NEAL重新发现LDPC码优异性能的同时，SPIELMAN和SIPSER提出了基于二部扩展图的扩展码。在对扩展码的研究中，他们证明了一个随机构造的TANNER图以很大的概率为好的扩展图，而由好的扩展图构造的线性纠错码是渐进好码，从而证明了采用随机TANNER图构造的LDPC码以很大概率是渐进好码。LUBY等人将采用非正则TANNER图构造的扩展图用于删除信道，称
27、之为TORNADO码。由于采用了非正则的TANNER图，TORNADO码具有更大的扩展性和更好的收敛性，纠删性能更强。此后，采用优化度序列设计的非正则TANNER图被用于构造LDPC码，称为非正则LDPC码，与正则LDPC码相比，非正则LDPC码的性能得到显著的提高。同时，WIBERG结合TURBO码和网格图的研究，将TANNER图推广到包含隐含状态变量的因子图（FACTORGRAPH），对TURBO码和LDPC码的研究在因子图的基础上得到统一。WIBERG对因子图的研究发现，对任意给定系统，无环图的状态复杂度是最大的，有环图的状态复杂度则会大大降低，从而证明了基于有环TANNER图的LDPC
28、码具有较低的译码复杂度。WIBERG同时还证明了最小和算法和和积算法在本质上的同一性，在格图译码中，最小和算法退化为VITERBI译码算法，和积算法退化为BCJR译码算法。近两年，RICHARDSON等人应用密度进化理论来测度LDPC码的性能。RICHARDSON等人在对LDPC码的研究中发现，译码信息的迭代传递过程中存在着译码阈值现象，即当信噪比大于译码阈值时，迭代译码可使误码率趋于零，反之无论采用多长的LDPC码，经过多少次迭代译码，总存在一定的错误概率。应用中心极限定理，6RICHARDSON等人证明了有限随机有环图的译码阈值可以逼近无环图的译码阈值。通过建立在无环图上的密度进化理论，可
29、以精确地计算无环图上LDPC码的译码阈值，分析其译码收敛条件，从而近似估算有环TANNER图上LDPC码的性能。研究表明，译码阈值的大小与LDPC码的构造参数密切相关，采用优化度序列设计的非正则LDPC码可以有效地改善阈值，因此密度进化理论可以用于指导LDPC码的优化设计。CHUNG等通过对密度进化理论的研究，进一步提出了应用高斯逼近原理来简化译码阈值计算和收敛性分析，从而使测度LDPC码性能的模型由多参数动态系统的密度进化理论模型简化为单一参数动态系统的高斯逼近模型。7第2章预备知识本章以汉明码为例，介绍了线性分组码的一般原理，并以此为后文中LDPC码的编码原理及程序中编码算法设计打下理论基
30、础，同时通过对线性分组码的分析介绍，形象地表现了信道编解码过程中的纠错检错过程。此外，还对信道容量以及香农极限进行了说明。21线性分组码在第一章中已经提到，信道编码的目的是提高信号传输的可靠性。信道编码是在经过信源编码的码元中增加一些多余的比特，目的在于利用这些特殊的多余比特去发现或纠正传输中发现的错误。在信道编码只有发现错码能力而无纠错能力时，必须结合其他的措施来纠正错码，否则只能将发现为错码的码元删除，以求避免错码带来的负面影响。在线性分组码中，使用线性代数方程来决定监督位与信息位之间的关系，所谓监督位即在码元中添加的冗余比特。线性分组码的构造方式较为简单、理论较为成熟。本章以汉明码为例介
31、绍线性分组码的一般原理。这种编码方法是由汉明（RWHAMMING）与1950年提出的。汉明码是一种能够纠正一个错码的效率较高的线性分组码。对于偶数监督码而言，在接收端解码时，实际上就是在计算下式21若计算出的S0，就认为无错码；若计算出的S1，就认为有错码。现在将式21成为监督关系式，S为校正子。由于校正子是一个二进制数字，他只有两种取值，故只能表示有错和无错，而不能进一步的指明错码的位置。不难推想，若此码长增加一位，即有两个监督位，则能增加一个类似式21的监督关系式。这样就能得到两个校正子。两个校正子的可能取值有4种组合，即00，01，10，11，故能表示4种不同的信息。若用其中一种组合表示
32、无错码，则还有其他3种组合可以用于指明一个错码的3个不同位置。因此，若有R个监督关系式，则R个校正子可以指明一个错码的个不同的位置。只有当校正子可以指明的错码位置数目等于或大于码组长度N时，才能够纠正码组中任何一个位置上的错码，即要求22下面通过一个例子来说明如何具体构造监督关系式。要求设计一个能够纠正1个错码的分组码N,K，给定的码组中有4个监督位，即K4由式22可知，这时要求监督位数。若取，则。现在用表示这7个码元，用表示校正子，这三个校正子恰好能够指明个错码的位置。例如，可以按照表21所示规定校正子和错码位置的关系。当8然，也可以做其他的规定，这不影响讨论的一般性。表21校正子和错码位置
33、关系错码位置错码位置001101010110100111011000无错码由此表可见，仅当在位置上有错码时，校正子的值才等于1；否则的值等于0。这意味着4个码元构成偶数监督关系23同理，构成如下偶数监督关系24以及构成如下偶数监督关系25在编码时，信息位的决定于输入信号，他们是随机的。监督位是按照监督关系决定的，应该保证上列3个式子中的校正子等于0，即有26上式可改写为27若信息位的值给定，则可以根据上式计算出监督位的值。这样计算出的结果见表22。表22监督位计算结果0000000100011100010111001100001010110100100011110101100101001101
34、100001010110111010100110011111010001110001111111在接收端解码时，对于每个接收码组，先按式23至式25计算出校正子，然后按照表21判断错码的位置。例如，若接收码组为0000011，则按式23至式25计算得到。这样，由表21可知，错码位置在。按照上述方法构造的码成为汉明码。上面例子中的汉明码是7,4码，其最小码距。由式24和式25可知，此码能够检测2个错码，或纠正1个错码。汉明码的码率可以由式22取等号时的值得出RRK2R1R21289当R或N很大时，上式趋近于1所以汉明码是一种高效编码。在讨论上面实例的基础上，现在介绍线性分组码的一般原理。前面已经
35、说明，线性分组码的监督位和信息位的关系是由一组线性代数方程决定的。式26就是这样的方程式，将此式改写成下列形式29在上式中已经将简写成。代表模2加法。式29可以改写成如下的矩阵形式210将上式改写为或211式中，212上标“T”表示将矩阵转置，即将矩阵的第一行变为矩阵的第一列，将矩阵的第二行变为矩阵的第二列我们将上式中的H称为监督矩阵。监督矩阵给定后，码组中的信息位和监督位的关系就随之确定了，比较式29和式210可以看出，H的行数就是监督关系式的数目，即监督位数R。H的每行中各个“1”的位置表示相应的码元参与监督关系。例如，H的第一行1110100表示监督位是由之和确定的。式211中的H可以分
36、为如下两部分213式中，为阶矩阵，为阶单位方阵。我们将如上式形式所表示的监督矩阵称为典型监督矩阵。由代数理论可知，H矩阵的各行应该是线性无关的，否则将得不到R个线性无关的监督关系式，从而也得不到R个独立的监督位。若一个矩阵能够写成典型阵形式，则其各行也一定是线性无关的。因为容易验证，的各行是线性无关的，故的各行也是线性无关的。式27也可以仿照式29的做法，写成如下矩阵形式214上式两端分别转置后，可以变成215式中，Q为阶矩阵，是P的转置，即216式115表示，在信息位给定后，用信息位的行矩阵乘以矩阵Q就得出监督位。我们将Q的左边加上一个K阶单位阵，构成如下矩阵217G称为生成矩阵，因为可以用
37、它产生整个码组A，即有21810具有形式的生成矩阵成为典型生成矩阵。由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于其后。这种形式的码组称为系统码。比较式213和式217可见，典型监督矩阵H和典型生成矩阵G之间通过式216联系。与对矩阵H的要求相似，矩阵G的各行也必须是线性无关的。因为由式218得知，任意一个码组A都是G的各行的线性组合。G共有K行，若他们线性无关，则可以组合出种不同的码组，这恰好是有K位信息位的全部码组。若G的各行中有线性相关的，则不可能生成种不同的码组了。实际上，G的各行本身就是一个码组。因此，如果已有K个线性无关的码组，则可以将其用作生成矩阵G，并由它产生其余
38、的码组。一般来说，式218中的A是一个N列的列矩阵219它的N个元素就是码组中的N个码元。所以发送码组就是A。由于传输中的干扰影响，接收码组可能出现错码而有别于A。设接收码组是一个N列的行矩阵220令接收码组和发送码组之差为模2221E就是错码的行矩阵，有时还称其为错误图样222式中，。因此，若，则表示该码元未错；若，表示该码元为错码。式221还可以改写成223上式表示发送码组A与错误码组E之和等于接收码组B。例如，若发送码组，错码矩阵，则接收码组。在接收端解码时，令式211中的A等于接收码组B进行计算。若接收码组B中无错码（），由式223得知，则式211仍成立。这时有224当接收码组中有错码
39、时，此时将B代入式211后，该式不一定成立。此外，在错码较多并超出这种编码的检错能力时，B可能变为另一个许用码组，故式211仍有可能成立。这时的错码将是不可检测的。所以只有当错码未超出检测能力时，式224才不成立。假设，这时式224的右端等于S，即有225将式223代入225，得到由式211可知，上式右端第一项等于0，所以11226式中，S就是由式21中的校正子S构成的矩阵，所以也成为校正子，它同样可以用来指示错码的位置。当H确定后，式226中，S只与E有关，而与A无关。这意味着S和错码E之间有确定的线性变换关系。若S和E有一一对应关系，则S将能代表错码位置。线性码有一个重要性质，就是它具有封
40、闭性。封闭性是指一种线性码中任意两个码组之和仍为这种编码中的一个码组。下面对此做一简单证明若和是两个码组，则由式211有将以上两式相加得227所以也是一个码组。由于线性码具有封闭性，所以两个码组和之间的距离（即对应位不同的数目）必定是另一个码组的重量（即“1”的数目）。因此，码的最小距离就是码的最小重量（除全“0”码组外）。22信道容量和香农极限信道容量表示一个信道下可靠传输的最大信息传输速率。不同的信道，噪声的存在形式不同，信道带宽以及信号的各种限制不同，因而信道容量也不相同。香农在其文章中定义的信道容量为IJPXJIIJIXYJCMAXIXYHYHY/XPY/XPXPY/XLOGPY228
41、X和Y分别代表信道的输入和输出，是X的概率密度函数；是X和Y的互信息量；HX是信源熵；HY/X为信道条件熵，即因为信道噪声而造成的信息损失熵。对于宽带无限的加性高斯白噪声AWGN信道，信道容量为S20E1CLOG122N229是传输信号的平均功率，为高斯白噪声的功率谱密度。对于带宽为W，信号平均功率为的带限AWGN信道，信道容量为S20ECWLOG1NW230式230即为著名的香农信道容量公式。对于低密度码的研究，需要涉及到输入离散、输出连续的AWGN信道。由于只有输入符号均匀分布时才能使互信息量达到最大，因此假设输入符号的概率密度函数12为SS1PXXEXE2231即SSPXEPXE0523
42、2对于AWGN信道可得2SS00YE1PY/XEEXPNN2332SS00YE1PY/XEEXPNN234将式233和234代入式228有2BB000YRE4YRE1C1EXPLOG1EXPDYNNN235R表示码率，表示传输每一个比特所需要的能量，与关系为。因为式235无法求出解析解，故智能采用数值仿真的方法近似求解。同时需要根据Y的特点对其积分区域进行缩减，于是得到2201Y2Y2251C1ELOG1EDYLN22236其中当传输错误概率时，得到的SHANNON极限为B0ESNRLN216DBN237可以看出这与理想AWGN信道的SHANNON极限是完全一致的。我们知道在实际研究中，R是不
43、可能趋近于0的。所以利用式236，再考虑满速率传输的情况RC，就可以得出不同的R下达到信道容量极限时所需的做小信噪比，如图21所示。13图21二进制AWGN的信道容量上图给出了不同编码速率R下二进制AWGN信道的信道容量。可以看出，当评估某一信道编码的性能时，不能直接用它的性能和一般意义下的SHANNON极限（16DB）进行比较，而应该根据它的码率在达到实际信道容量时所需的最小信噪比，并用来和其性能做比较，这样才更合理。下表列举出了一些常见码率下所对应的最小信噪比值。表23不同码率条件下AWGN信道的最小信噪比码率R最低信噪比DB8/930034/520402/310601/201871/30
44、49501614第3章LDPC码表示及编码本章系统地概述了LDPC码的定义及其TANNER图表示，以及二进制LDPC码的编码原理。31LDPC码的定义及其TANNER图表示311LDPC码的定义及其描述一个码长为N、信息位个数为K的线性分组码可以由一个生成矩阵来定义，信息序列通过G被映射到码字。线性分组码也可以由一个一致校验矩阵来等效描述，所有码字均满足。校验矩阵每一行表示一个校验约束，其中所有非零元素对应的码元变量构成一个校验集，用一个校验方程表示；校验矩阵的每一行表示一个码元变量参与的校验约束，当列元素不为零时，表示该码元变量参与了该行的校验约束。码元变量与检验方程之间的关系成为结构。下面
45、主要对二元LDPC码进行讨论。LDPC码是一种线性分组码，它的名字来源于其校验矩阵H的稀疏性，即校验矩阵中只有数量很少的元素为“1”，大部分都是“0”。GALLAGER最早给出了正则LDPC码的定义，具体来讲正则LDPC码的校验矩阵H满足下列三个条件1、H的每行有个“1”；2、H的每列有个“1”，3、与码长和H矩阵的行数相比，和都很小。11110000000000000000000011110000000000000000000011110000000000000000000011110000000000000000000011111000100010001000000001000100010
46、0000010000010001000000100010000010000001000100010000000010001000100011000010000010000010001000010001000010000001000010000100000100001000010000100100000001000010000100001图3120,3,4LDPC码的校验矩阵矩阵H的每列各自包含个“1”，表示每个码元变量受到相同数目的校验约束；每行也各自包含个“1”，表示每个校验方程对相同数目的码元变量进行校验约束；由于和都很小，校验矩阵具有很低的“密度”，因此由校验矩阵所确定的码称为LDPC码
47、。GALLAGER证明了当时，这类码具有很好的汉明距离特性。正则LDPC码通常用来表示，其中N为码长,和的含义不变，图31给出了一个20,3,4正则LDPC码的校验矩阵。15当校验矩阵H各行（列）中“1”的个数不全相同时，就得到了非正则LDPC码。312LDPC码的TANNER图表示设一个正则LDPC码C具有校验矩阵，其对应的TANNER图模型可以表示为一个二部图。其中码字向量表示为一组比特节点，分别对应于校验矩阵的各列，而校验约束则表示为一组校验节点，对应与校验矩阵的各行。仅当时，比特节点与校验节点之间有一条边相连，节点与之间互称邻接节点，其间的连接边称为两个节点的邻接边。对于正则LDPC码
48、，每个比特节点与个个校验节点相连，称该比特节点的度为；每个校验节点与个比特节点相连，称该校验节点的度为，度表示与节点相连的边的数目。图32给出了图31所示校验矩阵对应的TANNER图结构。图3220,3,4LDPC码的TANNER图表示根据比特节点与校验方程之间的约束关系可以得知，TANNER图中中所有比特节点发出的边的数目必然等于所有校验方程所接收的边的总数。那么对于LDPC码N，J，K，若假设M为校验方程的个数，即校验矩阵H的行数，则以下等式必然成立31对于非正则的LDPC码，每个校验方程约束的比特节点数目不一样，同时每个比特节点受约束的校验方程的数目也不一样。反映在TANNER图中就是每
49、个点（比特节点和约束节点）所连接的边的数目是不完全相同的。这样一种不规则的LDPC码在码长很大的时候性能要比正则的LDPC码好，这是由于“波浪效应”（WAVEEFFECT）所致。一部分比特节点受到约束的校验方程数目比较多，即收到的约束度比较高，那么其正确译码的速度也相对比较快；以此同时，这些约束度较高的点也为其他约束度较低的点提供了更为准确的译码外信息，最终使得所有比特节点正确译码的速度更快。又因为校验矩阵H中每行和每列1的个数不同，所以不能再用N,J,K的方式来进行表示。为了准确地表达一个非正则的LDPC码，我们引入如下表达式LRDJ1JJ1DI1II1XXXX32其中表示比特节点的度的分布，表示校验节点的度的分布；满足LDJJ111及16RDII111。正则LDPC码可以看成是非正则LDPC码的特例，对于N,3,4形式的正则LDPC码，相应边的度分布多项式分别退化为。32二进制LDPC码的编码原理321H矩阵的构造由于LDPC码是以校验矩阵H为特征的，不同的校验矩阵H对应了不同的码字集合。因
