LDPC码性能研究 说明书.docx

LDPC码性能研究 说明书.docx

《LDPC码性能研究 说明书.docx》由会员分享，可在线阅读，更多相关《LDPC码性能研究 说明书.docx（59页珍藏版）》请在冰点文库上搜索。

LDPC码性能研究说明书

本科毕业设计（论文）

题

目

LDPC码性能研究

摘要

信道编码是数字通信系统的重要组成部分。

LDPC信道编码技术是编码界的重要成果之一。

1/2码率的二元LDPC码在AWGN信道下的性能距信息理论中的Shannon极限仅差0.0045dB，它是目前距Shannon极限最近的纠错码。

Gallagar在1962年提出LDPC码，1996年经过Mackey、Spielman和Wiberg等人的再发现后，LDPC码以其性能优越、全并行迭代译码结构、便于硬件实现等优点，在无线通信、存储工业等领域得到了广泛应用。

校验矩阵的构造是编码的前提，本文采用了随机构造法构造，并对矩阵的多种变换方法进行分析，比较了优缺点。

译码算法是LDPC码的关键，译码复杂度的大小直接影响系统的实现。

主要分硬判决译码、软判决和复合译码。

设计中采用的译码方式是软判决译码。

在性能分析方面，利用matlab仿真码长、列重和迭代次数对LDPC码性能的影响。

仿真结果表明，在一定范围内，LDPC码长码的误码性能优于短码；码长较小时，列重的增加会使性能变差，而对于长码，列重在一定范围内的增大会改善LDPC的误码性能；增加迭代次数会使误码率降低，但当迭代次数大到一定值时，误码率将不会再随着迭代次数的增加而降低。

关键词LDPC码信道编码矩阵变换性能分析

Abstract

Channelcodingisanimportantcomponentfordigitalcommunicationsystems.LDPCchannelcodingtechnologyisoneimportantachievementoftheencodingresults.Theperformanceofhalfofthebinarybit-rateLDPCcodesinAWGNchannelonlyhasatapof0.0045dBtotheShannonLimitthatmakesitbethelatesterror-correctingcodesfromtheShannonLimit.GallagerproposedLDPCcodesin1962,afterMackeyandothersre-discovereditin1996,withbestperformance,completelydecodingalgorithminparallelschemeandeasilyrealizedforhardwaredesign,LDPCcodeshasalreadybeenwidelyusedinmanypracticalsystemssuchaswirelesscommunicationsystemandstoragesystem.

TheconstructionoftheCheckmatrixisapreconditionforcoding;therandomizedmethodwasusedinthispaper.Severalwaystotransformthematrixwasdiscussedandbeingcomparedaboutthemeritsofeachmethod.ThedecodingalgorithmisthekeytoLDPCcodeandthecomplexityofdecodingdirectimpactrealizationofthesystem.Therearethreekindsofdecodingalgorithms:

hard-decisionmethod,soft-decisionmethodsandhybriddecoding.Thehard-decisionmethodwasusedinthisdesign.

BasedonstudyingthebasictheoryofLDPCcodes,theimpactofcodeslength,columnweightanditerationtimesonBERperformanceofLDPCcodesaredemonstratedbycomputersimulationandtheoreticalanalysis.Thesimulationexperimentindicatedthat:

LDPCcodeslong-codeerrorperformanceissuperiortoshort-codeerrorperformance,butwhenthecodelengthreachesacertainvalue,andthenincreasethecodelength,BERofLDPCcodeslowerratewillbesmall.Whenthecodelengthissmall,increasingthecolumnweight,LDPCcodesperformancewilldeteriorate;whencodelengthislargeenough,increasingthecolumnweight,LDPCcodesperformancewillbeimproved,butwhenthecolumnweightreachesacertainvalue,assetoutprioritytoincreasingtheperformanceofLDPCcodeswillbeworse.Toincreasethenumberofdecodingiterations,LDPCcodesperformancewillbeimproved;butwhenthenumberofiterationsislargeenough,thenincreasethenumberofiterations,LDPCcodeswillnolongerreducetheerrorrate.

keywordsLDPCcodeschannelcodingmatrixtransformationperformanceanalysis

第1章绪论

本章简要介绍了数字通信系统，并对系统中的每一部分进行了功能性说明，介绍了信道编码理论及其发展历程，最后概述了低密度奇偶校验码的提出、发展和现状。

1.1数字通信系统

通信系统的基本目的在于将信息由信源高效、可靠、安全地传送到信宿。

在信息传输的过程中，信道中的噪声会不可避免地对传输信息产生干扰，从而导致了可靠性的降低。

所以，通信系统设计的核心问题在于如何克服信道中随机噪声对信号的干扰，减小信息传输产生的差错，同时在最大程度上保证信息传输的效率，即如何解决系统有效性和可靠性的矛盾。

一般地，通信系统的可靠性用误比特率（BER）来衡量，其有效性则用信息传输速率R比特/信道符号来衡量。

早期的人们普遍认为：

通信系统的可靠性与有效性之间存在不可调和的矛盾，一方的改善总是以牺牲另一方为代价，并指出当功率受限时，在有扰通信信道上实现任意小错误概率的信息传输的唯一途径就是把信息传输速率降低至零。

Shannon信息和编码理论的奠基性论文“通信的数学理论”于1948年发表之后，改变了这一观点。

他首次阐明了在有扰信道上实现可靠通信的方法，指出实现有效而可靠地信息传输的途径就是通过编码。

根据Shannon的信息理论，数字通信系统的基本组成如图1.1所示：

图1.1数字通信系统的基本组成

图中，信源的作用为产生需要传送的信息，信息可以是模拟信号也可以是数字信号。

如果是模拟信号，在进入数字通信系统之前需要进行采样和量化处理。

信源编码器的主要作用是将信源发出的信息，例如语音、图像或者是文字等原始的数据进行转化，在保证通信质量的前提下，尽可能的通过对信号的压缩，提高通信系统的有效性。

以更少的符号来表示原始信息，使信息能够更好的在传输媒介中进行传输。

信道编码是在发送器和接收器之间实现信号可靠传输的必要手段之一。

传输信道中存在的噪声必然会对传输的信息引入失真和信号判决错误，因此需要采用差错控制码来检测和纠正这些比特错误。

信道编码器的主要作用是通过对信源编码后的信息加入冗余信息，使得接收方在收到信号后，可以通过信道编码中的冗余信息进行前向纠错，以保证通信系统的可靠性。

数字调制器的作用是使信息变成能够适应信道传输的信号。

信号经过调制器后进入物理信道进行传输。

典型的物理信道包括有线信道、无线信道、光纤信道、卫星信道等，针对不同的信道设计通信系统时要有不同的考虑，如无线信道会收到多径的影响而产生衰落，而卫星信道会受到信号功率衰减的影响等。

信号到达接收端后，通过数字解调器对接收到的调制信号序列或传输码字进行最优估计，然后输出数字编码序列送到信道译码器。

信道译码器对信息进行估计和判决，估计准则是根据编码准则和信道特性而确定的，目的是最小化信道噪声的影响。

最后信源译码器根据信源编码准则将得到的信道编码器输出的编码信息序列经过相应的信源译码后，得到对原始信息序列的估计。

1.2信道编码理论及其发展

图1.1中的信道编译码部分是以特定的控制手段，引入适量冗余比特，以克服信息在传输过程中受到的噪声和干扰影响。

根据Shannon提出的信道编码定理，对任意一个平稳离散无记忆有噪声信源，都有一个固定的量，称之为信道容量，记做C。

只要信息的传输速率低于信道容量，就必然存在一种编码方法，使得信息出现差错的概率随码长的增加趋于任意小；反之，当信息传输速率超过信道容量时，则不存在这样的编码方法。

这就是著名的信道编码定理，它给出了特定信道上信息传输速率的上确界。

信道编码定理：

任意离散输入无记忆平稳信道存在信道容量，对预期的任一数据速率和任一错误概率，有可能设计一对编译码器，以保证该信道中速率为R的数据传输具有小于p的译码错误概率。

信道编码定理指出，在有扰信道中，只要信息传输速率小于信道容量，就有可能实现任意可靠的信息传输。

这个存在性定理提醒我们可以实现以接近信道容量的传输速率进行通信。

但遗憾的是该定理采用的是非构造性的证明方法，其中并没有给出逼近信道容量的码的具体编译码方法。

Shannon在信道编码定理的证明中引用了三个基本条件，即：

（1）、采用随机的编码方式；

（2）、码字长度趋近于无穷大；

（3）、译码采用最佳的最大似然译码。

一般可将信道编译码器所使用的纠错码从性能上分为坏码和好码。

所谓坏码是指只有将码率降至零才能使误码率为任意小的编码方式；而好码又可以分为当误码率任意小时，码率逼近信道容量限的非常好码和码率可达到的非零最大值小于信道容量限的一般好码。

虽然Shannon指出一个随机选择的码以很高的概率为好码，但随机码的最大似然译码的复杂度往往与码长呈指数关系，即在误码率随码长趋于无穷而趋向于零的同时，译码复杂度以指数增长，而在实际应用中，只能够使用以码长多项式的时间和空间复杂度内完成编译码的纠错码，因而尽管一般的随机码是好码，但不能看作是实用码。

自信道编码定理提出以来，如何构造一个逼近信道容量限的实用好码成了众多研究学者竟相研究的课题，并逐渐形成信息论的一个重要分支——信道编码理论。

五十多年来，人们构造实用好码的探索基本上是按照Shannon所引用的基本条件的后两条为主线展开的。

虽然从理论上讲，除了目前已知的码外，几乎所有的码都是好码，但到目前为止，构造出真正意义上的实用好码还有较长的距离。

虽然如此，通过众多学者，特别是有关数学和信息论学术界的研究人员五十多年的共同努力，目前已经取得了很多成果。

下面对其进行简要概述。

纠错码从构造方法上可分为分组码（BlockCodes）和卷积码（ConvolutionalCodes）两大部分。

在分组码方面，第一个分组码是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码的特例。

其后发现的分组码主要有1970年的Goppa码和1982年发现的代数几何码。

在所有这些分组码中，除了Goppa码和代数几何码中存在个别达到GV限的渐进好码外，其它均不是好码。

分组码的译码主要采用基于代数的硬判决译码。

卷积码最早由Elias提出，早期被称为树码（TreeCodes），现在称为格图码（TrellisCodes）或卷积码。

卷积码具有动态格图结构，可用有限状态机来描述其状态。

由于缺乏有效的理论研究工具，对卷积码的有效研究成果不是很多，目前性能好的卷积码的构造方法主要借助于计算机搜索来获得。

卷积码的译码一般采用概率译码，由于译码算法的简单、实用和易于实现，卷积码被广泛应用于实际中。

1966年，Forney将分组码和卷积码结合起来，提出了级联码（ConcatenatedCodes）的概念。

级联码一般采用RS码作为外码，卷积码作为内码。

Forney的研究表明，级联码在性能得到较大改善的情况下，其译码复杂度并不显著增加。

根据对接收信号处理方式的不同，纠错码的译码可以分为硬判决译码和软判决译码。

硬判决译码是基于传统纠错码观点的译码方法，解调器首先对信道输出值进行最佳硬判决，再将判决结果送入译码器，译码器根据解调器的判决结果，利用码字的代数结构来纠正其中的错误。

而软判决译码则充分利用了信道输出的波形信息，解调器将匹配滤波器输出的一个实数值送入译码器，由于实数值包含了比硬判决更多的信道信息，译码器能够通过概率译码充分利用这些信息，从而获得比硬判决译码更大的编码增益。

总之，尽管随机码是理论上的好码，但由于其编码实现的困难性和无法承受的译码复杂度而只被用做理论分析的工具，在信道编码定理和后来的许多编码理论成果中，代数编码理论始终占据了主导地位，使得传统的信道编码技术受到临界速率（CriticalRate），也称做截止速率（CutoffRate）的限制。

1993年Turbo码的提出被看作是信道编码理论研究的重要里程碑。

Berrou等人将卷积码和随机交织器相结合，同时采用软输出迭代译码来逼近最大似然译码，取得了超乎寻常的优异性能，并一举超越了截止速率，直接逼近Shannon提出的信道容量限。

Turbo码是一种信道编码理论界梦寐以求的可实用非常好码，它的出现标志着信道编码理论研究进入了一个崭新的阶段。

Turbo码成功的根本原因在于其实现方案中长码构造的伪随机性是核心，它通过随机交织器对信息序列的伪随机置换实现了随机编码的思想，从而为Shannon随机编码理论的应用研究奠定了基础。

随着Turbo码的深入研究，人们重新发现Gallager早在1962年提出的低密度校验码（LowDensityParity-CheckCodes，简称LDPC码）也是一种具有渐进特性的非常好码，它的译码性能同样可以逼近Shannon信道容量限。

由于LDPC码具有在中长码长时超过Turbo码的性能，并且具有译码复杂度更低，能够并行译码及译码错误可检测等特点，成为目前信道编码理论的研究热点。

研究表明，Turbo码只是LDPC码的一个特例，两者都是基于图构造的低密度码，译码算法具有等价性，从而使两者在基于图模型的编译码研究中得到了统一。

1.3低密度奇偶校验码的提出、发展和现状

1962年，Gallager在他的博士论文中提出了二元正则LDPC码，也被称做Gallager码。

Gallager证明了这类码具有很好的汉明距离特性，是满足GV限的渐进好码，在计算树上进行（N为码长）次后验概率迭代译码可以获得依码字长度指数降低的比特错误概率，但限于当时的计算能力，缺少可行的译码算法，LDPC码被认为不是实用码，在很长一段时间内没有受到人们的重视。

1981年，Tanner在他的一篇奠基性的文章中正式提出了用图模型来描述码字的概念，从而将LDPC码的校验矩阵对应到被称为Tanner图的双向二部图上。

采用Tanner图构造的LDPC码，通过并行译码可以显著地降低译码复杂度。

Tanner还仔细分析了最小和算法（Min-SumAlgorithm）与和积算法（Sum-ProductAlgorithm）两种信息传递算法，证明了基于有限无环Tanner图的最小和译码算法与和积译码算法的最优性。

但Tanner图在实际当中是采用随机图构造的，其中不可避免地存在小环路现象，这些小的环路会造成译码信息的重复传递，使译码过程中的消息之间不满足独立性假设，影响了迭代译码算法的收敛性。

Turbo码的发现重新引发了众多学者对LDPC码的研究兴趣。

MacKay和Neal利用随机构造的Tanner图研究了LDPC码的性能，发现采用和积译码算法的正则LDPC码具有和Turbo码相似的译码性能，在长码时甚至超过了Turbo码，这一结果引起了信道编码界的极大关注。

此后，Davey和MacKay从减少Tanner图上小环路的概念出发提出了基于的LDPC码，进一步提高了LDPC码的译码性能。

在MacKay和Neal重新发现LDPC码优异性能的同时，Spielman和Sipser提出了基于二部扩展图的扩展码。

在对扩展码的研究中，他们证明了一个随机构造的Tanner图以很大的概率为好的扩展图，而由好的扩展图构造的线性纠错码是渐进好码，从而证明了采用随机Tanner图构造的LDPC码以很大概率是渐进好码。

Luby等人将采用非正则Tanner图构造的扩展图用于删除信道，称之为Tornado码。

由于采用了非正则的Tanner图，Tornado码具有更大的扩展性和更好的收敛性，纠删性能更强。

此后，采用优化度序列设计的非正则Tanner图被用于构造LDPC码，称为非正则LDPC码，与正则LDPC码相比，非正则LDPC码的性能得到显著的提高。

同时，Wiberg结合Turbo码和网格图的研究，将Tanner图推广到包含隐含状态变量的因子图（FactorGraph），对Turbo码和LDPC码的研究在因子图的基础上得到统一。

Wiberg对因子图的研究发现，对任意给定系统，无环图的状态复杂度是最大的，有环图的状态复杂度则会大大降低，从而证明了基于有环Tanner图的LDPC码具有较低的译码复杂度。

Wiberg同时还证明了最小和算法和和积算法在本质上的同一性，在格图译码中，最小和算法退化为Viterbi译码算法，和积算法退化为BCJR译码算法。

近两年，Richardson等人应用密度进化理论来测度LDPC码的性能。

Richardson等人在对LDPC码的研究中发现，译码信息的迭代传递过程中存在着译码阈值现象，即当信噪比大于译码阈值时，迭代译码可使误码率趋于零，反之无论采用多长的LDPC码，经过多少次迭代译码，总存在一定的错误概率。

应用中心极限定理，Richardson等人证明了有限随机有环图的译码阈值可以逼近无环图的译码阈值。

通过建立在无环图上的密度进化理论，可以精确地计算无环图上LDPC码的译码阈值，分析其译码收敛条件，从而近似估算有环Tanner图上LDPC码的性能。

研究表明，译码阈值的大小与LDPC码的构造参数密切相关，采用优化度序列设计的非正则LDPC码可以有效地改善阈值，因此密度进化理论可以用于指导LDPC码的优化设计。

Chung等通过对密度进化理论的研究，进一步提出了应用高斯逼近原理来简化译码阈值计算和收敛性分析，从而使测度LDPC码性能的模型由多参数动态系统的密度进化理论模型简化为单一参数动态系统的高斯逼近模型。

第2章预备知识

本章以汉明码为例，介绍了线性分组码的一般原理，并以此为后文中LDPC码的编码原理及程序中编码算法设计打下理论基础，同时通过对线性分组码的分析介绍，形象地表现了信道编解码过程中的纠错检错过程。

此外，还对信道容量以及香农极限进行了说明。

2.1线性分组码

在第一章中已经提到，信道编码的目的是提高信号传输的可靠性。

信道编码是在经过信源编码的码元中增加一些多余的比特，目的在于利用这些特殊的多余比特去发现或纠正传输中发现的错误。

在信道编码只有发现错码能力而无纠错能力时，必须结合其他的措施来纠正错码，否则只能将发现为错码的码元删除，以求避免错码带来的负面影响。

在线性分组码中，使用线性代数方程来决定监督位与信息位之间的关系，所谓监督位即在码元中添加的冗余比特。

线性分组码的构造方式较为简单、理论较为成熟。

本章以汉明码为例介绍线性分组码的一般原理。

这种编码方法是由汉明（R.W.Hamming）与1950年提出的。

汉明码是一种能够纠正一个错码的效率较高的线性分组码。

对于偶数监督码而言，在接收端解码时，实际上就是在计算下式：

（2-1）

若计算出的S=0，就认为无错码；若计算出的S=1，就认为有错码。

现在将式（2-1）成为监督关系式，S为校正子。

由于校正子是一个二进制数字，他只有两种取值，故只能表示有错和无错，而不能进一步的指明错码的位置。

不难推想，若此码长增加一位，即有两个监督位，则能增加一个类似式（2-1）的监督关系式。

这样就能得到两个校正子。

两个校正子的可能取值有4种组合，即00，01，10，11，故能表示4种不同的信息。

若用其中一种组合表示无错码，则还有其他3种组合可以用于指明一个错码的3个不同位置。

因此，若有r个监督关系式，则r个校正子可以指明一个错码的（）个不同的位置。

只有当校正子可以指明的错码位置数目等于或大于码组长度n时，才能够纠正码组中任何一个位置上的错码，即要求：

（2-2）

下面通过一个例子来说明如何具体构造监督关系式。

要求设计一个能够纠正1个错码的分组码（n,k），给定的码组中有4个监督位，即k=4.由式（2-2）可知，这时要求监督位数。

若取，则。

现在用表示这7个码元，用表示校正子，这三个校正子恰好能够指明个错码的位置。

例如，可以按照表2.1所示规定校正子和错码位置的关系。

当然，也可以做其他的规定，这不影响讨论的一般性。

表2.1校正子和错码位置关系

错码位置

错码位置

001

101

010

110

100

111

011

000

无错码

由此表可见，仅当在位置上有错码时，校正子的值才等于1；否则的值等于0。

这意味着4个码元构成偶数监督关系：

（2-3）

同理，构成如下偶数监督关系：

（2-4）

以及构成如下偶数监督关系：

（2-5）

在编码时，信息位的决定于输入信号，他们是随机的。

监督位是按照监督关系决定的，应该保证上列3个式子中的校正子等于0，即有：

（2-6）

上式可改写为：

（2-7）

若信息位的值给定，则可以根据上式计算出监督位的值。

这样计算出的结果见表2.2。

表2.2监督位计算结果

0000

000

1000

111

0001