毕业设计(论文)-华侨大学.docx

毕业设计(论文)-华侨大学.docx

《毕业设计(论文)-华侨大学.docx》由会员分享，可在线阅读，更多相关《毕业设计(论文)-华侨大学.docx（62页珍藏版）》请在冰点文库上搜索。

2013届本科毕业设计论文

摘 要

LDPC码的优异性能及其在信息可靠传输中的良好应用前景（例如光通信、卫星通信、深空通信、移动通信等），已引起世界各国学术界和IT业界的高度重视，成为当今信道编译码领域最瞩目的研究热点。

在现代数字通信系统中，为保证各种数据能够可靠、有效的传输，往往要利用纠错编码技术。

近年来，随着无线数字通信发展及各种高速率，突发性强的新业务的出现，研究并利用好纠错编码技术就越来越显得必要。

LDPC码是

Gallager最早于1963年提出的一种具有稀疏校验矩阵的分组码。

之后，在Turbo码巨大成功的带动下，Mackay等人重新研究了它，并发现LDPC码具有逼近香农限的特性，同时具有低译码复杂度，因此必将在CDMA系统中得到广泛的应用。

本文首先在讨论了LDPC码的基本概念及编码算法基础上，重点对硬判决译码算法

（比特翻转译码、加权比特翻转译码）、软判决译码算法（概率域和积译码、Log域和积译码、最小和译码）进行了详细地分析和一些基础的比较。

最后主要介绍了BF、BP译码算法的LDPC码仿真和分析。

关键词：

CDMA系统；LDPC码；信道译码

ABSTRACT

4

LDPCcodeshavegoodperformanceandreliabletransmissionofinformationinthegoodprospectofapplication（suchasopticalcommunications,satellitecommunications,deepspacecommunication,mobilecommunication）,hasattractedgreatattentionofacademiccircleandITindustry,becomeahotresearchtopicinthefieldofattentionmostchannelcoding.Inmoderndigitalcommunicationsystem,inordertoensurethereliabletransmissionofdata,effective,oftenmakeuseoferrorcorrectioncodingtechnology.Inrecentyears,withthedevelopmentofwirelessdigitalcommunicationandhighspeed,strongburstofnewbusiness,studyandusetheerrorcorrectioncodingtechnologybecomesmoreandmorenecessary.LDPCcodeisaGallagerfirstproposedin1963blockcodeswithsparseparitycheckmatrix.Afterthehugesuccess,intheTurbocodeunderthedrive,Mackayetal.Tostudyit,anditisfoundthattheLDPCcodehastheapproximationpropertyoftheShannonlimit,alsohaslowdecodingcomplexity,soitwillbewidelyappliedinCDMAsystem.

ThispaperfirstdiscussesthebasicconceptofLDPCcodeandthecodingalgorithm,keydecodingtotheharddecisionalgorithm（bitflippingdecoding,weightedbitflippingdecoding）,softdecisiondecodingalgorithm（probabilisticdomain,Logdomainandsum-productdecoding,min-sumdecoding）isanalyzedandsomebasic.

FinallyintroducestheLDPCcodesimulationandanalysisofBF,BPdecodingalgorithm.

Keywords:

CDMA;LDPCcode;decoding

目 录

第一章 绪论 1

1.1研究背景和意义 1

1.2数字通信系统模型 3

1.3纠错码的发展 4

第二章 LDPC码的理论基础及编码算法 6

2.1LDPC码的相关概念 6

2.1.1线性分组码 6

2.1.2LDPC码定义 7

2.2LDPC码的图结构 7

2．2．1树 8

2．2．2 Tanner图 8

2.3LDPC码的分类 10

2.4LDPC码的编码算法 10

第三章LDPC码的信道译码 13

3.1LDPC码的译码原理 13

3.2硬判决译码 14

3.2.1比特（BF）翻转译码算法 14

3.2.2加权比特翻转译码算法 16

3.3软判决译码 17

3.3.1和积（BP）译码算法 17

3.3.2Log-BP算法 20

3.3.3最小和译码算法 21

3.3.4三种译码算法性能比较 21

第四章LDPC信道译码设计及仿真 23

4.1BF译码算法仿真及分析 23

4.2BP译码算法仿真及分析 25

结 论 28

参考文献 29

致 谢 30

附 录 31

附录1:

[BF译码算法程序] 31

附录2:

[BP译码算法程序] 36

附录3:

[外文翻译] 40

第一章 绪论

1.1研究背景和意义

CDMA技术早已在军用抗干扰通信研究中得到广泛应用，1989年11月，

Qualcomm在美国的现场试验证明CDMA用于蜂窝移动通信的容量大，并经理论推导其为AMPS容量的20倍。

这一振奋人心的结果很快使CDMA成为全球的热门课题。

如今，

3G走上了通信舞台的前沿，3G系统采用CDMA技术和分组交换技术，3G将支持更多用户，实现更高的传输速率。

无线通信在当今通信中起着越来越重要的作用，CDMA技术也已成为本世纪主要的无线接入技术。

3G能够将语音通信和多媒体通信相结合，其增值服务将包括图像、新技术的应用，会为公众提供更好的服务，新技术主要体现在上网速度增长带来的一系列音乐、网页浏览、视频会议以及其它一些信息服务。

因此，对

CDMA通信系统的研究能够加快3G的发展，给用户带来更多的服务。

扩频通信技术作为抗干扰通信技术，长期以来一直为军方所用。

CDMA技术的民用化，特别是与数字蜂窝技术相结合，构成了CDMA数字蜂窝移动通信系统，对移动通信的发展产生了十分巨大和深远的影响。

由于CDMA体制具有抗人为干扰、抗窄带干扰、抗衰落、抗多径扩展，并可提供十分巨大的系统容量和便于与模拟或数字体制共存的优

点，使得CDMA数字蜂窝移动系统很快成为TDMA数字蜂窝移动系统强有力的竞争对手，收到世人瞩目，成为第三代移动通信的主要技术手段。

CDMA系统的发展历程如下：

在大量蜂窝移动通信工业部门的支持下，美国圣地亚哥Qualcomm公司设计、开发并试验了CDMA蜂窝网，于1991年12月做了现场试验并取得了一致好评，当时进行了5

个基站、70个移动太参加组网的试验。

现场试验结果表明：

1、CDMA理论分析的愉悦性，在实际通信条件下是存在的，并有实际测试数据证明了系统容量和性能改善了多少；

2、CDMA蜂窝网的关键技术已经过关，可向实用化方向发展；3、CDMA双模式公共空中接口方案是可行的；4、基站和移动台的专用集成电路是可靠的，便于向工业化方向发展。

从1993年4月开始，世界上许多著名电信公司均根据标准生产CDMA系统的设备。

1993年4月，我国开始引入CDMA实验网。

IS-95系统以其高语音质量、稳定的系能以及空中接口的大容量而在世界各地广泛使用，因此，很自然下一代的移动通信空中接口将建立在这一已被证明了的具有优良性能的第二代CDMA接口之上，并且向后兼容现有的IS-95网络。

IS-95向第三代，即CDMA

42

2000的演进，可通过使用宽带CDMA技术来适应IMT-2000的要求。

CDMA2000提供了从第二代IS-95的平稳过渡，业务供应商可以在有附加容量和高级业务需求的区域有选择性、无缝地建立CDMA2000网络。

中国CDMA的发展并不迟，也有长期军用研究的技术积累，93年国家863计划已开展CDMA蜂窝技术研究。

目前各国上报给国际电联审批的所有3G提案中，绝大多数方案都是基于与IS-95CDMA相近的CDMA技术。

纠错码也即信道编译码，是通信系统的关键技术之一，可以大大提高通信系统的性能。

从1948年香农在他的开创性论文《通信的数学理论》中首次提出在有扰信道中实现可靠通信到目前为止，纠错码已有五十多年的历史，由最初的BCH码逐步发展到目前越来越受关注和应用的Turbo码和LDPC码。

LDPC码虽早在1963年就由Gallager发明的，但是由于当时条件的限制，LDPC码一度被人们所忽略，直到Turbo码的发明才让人们重新意识到了LDPC码。

和Turbo码一样，

LDPC码也具有逼近香农限的性质，并且非正则LDPC码性能甚至优于Turbo码。

因此，熟悉和了解LDPC码的编译码原理及其性能分析对设计更适合于通信系统，性能更优的码型起到了积极的指导作用。

LDPC码是一种具有稀疏校验矩阵的线性分组码，具有能够逼近香农限的性能特性，在许多场合下性能优于Turbo码，而且由于校验矩阵的稀疏性，译码的复杂度低，并可实现完全的并行操作，便于硬件实现；具有较大的灵活性和较低的差错平层特性；描述简单，对严格的理论分析具有可验证性；另外，置信传播算法存在一种译码门限效应，当信道噪声方差低于门限值时，译码后的误码率可以趋于零；在编码的数学模型上，LDPC码具有简单的二分图数学模型。

由于LDPC码属于线性分组码，其编码过程一般采用线性分组码的通用编码方法，即由信息序列根据码的生成矩阵来求相应的码字序列，尽管

LDPC码的校验矩阵是非常稀疏的，但它的生成矩阵却并不稀疏，这使得其编码复杂度往往与其码长的平方成正比。

因此，LDPC码的缺点主要就是编码的复杂度较高，虽然有研究表明它可以在线性时间内编码，但是其复杂度相对于卷积码的即时编码来说，编码复杂度仍然过大。

同时在码长较长时，由于必须在接收到所有的信息比特后才能进行编码，这就会给编码带来一定的延时。

另外，LDPC码性能的优越性通常要在码长较长时才能体现出来，当码长为中短长度时，由于编码中短长度圈即环的存在，会在某种程度上降低编码的性能。

那么，今后LDPC码的研究方向主要有：

（1）码的设计；

（2）选择合适的硬件以降低编译码的运算复杂度；（3）LDPC码应用于各种通信中。

目前，LDPC码已成为通信技术的首选。

1.2数字通信系统模型

如下图为数字通信系统模型：

信源

信源编码

信道编码

调制

信道

噪声

信源解码

信道编码

解调

信宿

图1.1数字通信系统模型

其中，信源编码是把发出的消息如文字、图像、视频等转换成二进制或者多进制形式的信息序列，目的是消除信源信息中的冗余度，以提高传输效率。

信道编码与信源编码正好相反，它是按一定规则在有效信息后增加一些冗余，提高信息序列之间的相关性，并且利用这种相关性在接收端检错和纠错，使译码后的信息错误概率尽可能小。

调制则是将数字信号频谱从低频到高频处，以适应在信道中作长距离传输的要求。

消息通过信道传输，在信道中收噪声的干扰。

仿真时常用的几种离散无记忆信道包括：

二进制可擦除信道、二进制输入对称信道、二进制输入加性高斯白噪声信道等。

在接收端，从信道接收到的信号依次通过解调、信道译码、信源译码，最后到恢复出的信源信息。

信息如何被更加有效地、可靠地传输室数字通信系统设计的中心问题。

信息传输的有效性通过信源编码来实现，而可靠性则通过信道编码来实现。

1948年，香农提出的信道编码定理指出，任意给定的信道都存在称之为信道容量的信息传递速率上确界。

只要传输速率低于信道容量，就可以通过适当的编码方式，是译码错误概率任意小。

不同的信道有不同的信道容量。

对于带限的加性高斯白噪声（AWGN）信道，信道容量C由下式确定：

C=Wlog2（1+Ps/WN0）

（1.1）

（bits/s）

该式通常称为香农公式，其中W是信道带宽，Ps是信号功率，N0为噪声的双边功率谱密度。

如果信道带宽W→∞时，信道容量C会趋于一个极限值：

P

C¥= s

N

log2e=

Ps

Nln2



（bit/s）

0 0

（1.2）

也就是说，无论信道带宽多大，为了达到需要的信道传输速率，信道比Ps/N0都不可能无限制的小。

在无限带宽的AWGN信道中进行可靠传输时，信噪比的下限（即实现无错误传输的最小信噪比）就是香农限。

如何构造出达到香农限的信道纠错码，成为之后信道编码领域的主要任务。

1.3纠错码的发展

纠错码是数字通信系统中的一个重要环节，其目的在于提高通信的可靠性降低低差错率。

而所谓通信系统就是完成信息传递所需的所有设备的总和，如图1．1所示，由于数字通信具有抗干扰能力强、便于差错控制、便于使用现代数字信号处理、易于加密、可以综合传递各种信息等优点，因此数字通信系统更适应于现代通信的要求。

而纠错码是深空通信中的重要环节，在香农的信息论建立以后，汉明（Hammin曲、斯列宾（Slepian）、普兰奇（Prange）等人在50年代初，根据Shannon的思想，给出了一系列设计好码和有效译码的方法。

随后，纠错码受到了越来越多的通信和数学工作者的重视，使纠错码无论在理论上还是在实际中都得到了飞速的发展。

五十年代至七十年代，主要研究各种有效的编译码方法，奠定了线性分组码的理论基础。

所以，在此基础上人们利用代数中的一些理论，通过代数的方法构造了许多纠错码，并研究了与之相适应的译码算法。

这些码字大部分都是线性分组码，比如戈雷码、汉明码、循环码和BCH码，它们的译码算法主要采用大数逻辑译码和捕错泽码。

但是这些码字都是短码，其纠错译码算法的复杂度是随着码长的增加成指数级增长，长码的实现十分困难，投入实际使用的主要是短码，而这些短码的性能距离香农限很远。

要达到香农限，必须要码长较长的编码，Gallager在1962年提出了一种码字，这种编码因为校验矩阵的稀疏性，使得译码的复杂度与码长保持线性的关系，码长较长时依然可以有效地译码。

然而当时人们普遍认为级联码更容易实现，以及一些技术条件的限制，导致人们忽视了这种编码的存在。

卷积码也是在同一时期提出的另一类重要的纠错码，它在编码过程中引入了寄存器，增加了码元之间的相关性。

在相同复杂度的条件下可以获得比线性分组码更高的编码增益，但是这种相关性同时也增加了分析和设计卷积码的复杂性。

纠错码主要就分为如上所述的线性分组码和卷积码两类，它们各有优缺点。

此外由于在实际应用中短码的性能有限，只有长码才能得到优秀的性能，于是人们设想是否能够在短码的基础上构造长码，由此提出了短码的级联或乘积来得到长码，在提高编码性能的同时，能够在短码的基础上具有较低的译码复杂度。

到八十年代和九十年代初，法国的C．Berrou等人在卷积码和级联码的基础上，于1993年提出了一种全新的编码方案Turbo码，在信道编码理论和应用中取得了突破性的进展。

这种编码能够在码长较长时逼近香农的理论

极限，同时译码复杂度也是可以接受的。

Turbo码采用并行级联递归的编码器结构，是一种系统的卷积码，其译码算法主要有MAP算法、Log．MAP算法和SOVA算法等。

Turbo码之所以具有逼近香农限的性能，是因为其独特的编码结构和新的译码思想，其关键技术是交织器的使用。

在Turbo码获得巨大成功的启发下，另一类具有相似特征和性能的编码复活了，这就是LDPC码。

LDPC码是Gallager提出的，D．J．C．Mackay、M．Neal和N．Wiberg等人对LDPC码重新进行了研究，发现LDPC码同样具有逼近香农限的性能。

M．G．Luby和

M．Mitzenmacher等人对LDPC码进行了推广，提出非正则的LDPC码，这种码型的性能能够赶上甚至超过Turbo码的性能。

同时，与Turbo码的译码算法相比，LDPC码的译码复杂度有很大的降低。

第二章 LDPC码的理论基础及编码算法

LDPC码揭示了一种新的具有低密度校验矩阵的线性分组码。

它利用校验矩阵的稀疏性解决长码的译码问题，可以在线性时间内译码，同时又近似于香农提出的随机编码，获得了优秀的编码性能，并经过近几年的研究，人们在正则码的基础上进行推广提出了

性能更好的非正则LDPC码。

但是，对LDPC码来说，在不考虑码长和度分布对的情况下，编码校验矩阵的结构就成了影响其性能的重要因素，反映在二分图上对编码性能有重要影响的就是图中环的大小，由此，需要采用一定的方法对校验矩阵进行构造，获得好的编码。

本章首先介绍了LDPC码的基本概念及其表示方法和分类，然后根据现有各种校验矩阵构造方法和编码算法介绍通信系统中所采用的校验矩阵构造方法和编码算法。

LDPC码是一种线性分组码，由于校验矩阵的稀疏性，它具有Tanner图这样的数学模型，因此理论分析相对简单。

20世纪90年代，人们利用定义在Tanner图对LDPC码的译码性能进行分析，目前己经有了一些较为完善的理论，人们还发现基于稀疏图的LDPC码具有非常接近Shannon限的性能。

这一章首先介绍线性分组码的原理，然后简介LDPC码的图论基础知识，最后给出LDPC码的分类。

2.1LDPC码的相关概念

2.1.1线性分组码

线性分组码在纠错码中有很重要的地位，它的数学模型简单，较易对其进行性能分析。

而LDPC码本质上就是一种线性分组码，它通过一个生成矩阵G将信息序列映射成码字序列。

每一个生成矩阵G，都存在一个奇偶校验矩阵H，所有的码字序列C构成了H的零空间。

线性分组码的信息位和监督位之间的关系满足一组线形代数方程。

一个（N，K）线性分组码的编码就是根据己知的K个信息比特求出N-K个校验比特，因此必须有N-K个线形独立的方程。

如果线性分组码的前K位就是原来的信息比特，后N-K位是监督位，则称之为线形系统码。

设二进制线性分组码（N，K）的校验矩阵为H（N-K）´N，码字为z，则H的每一行与它的码字的内积均为零，即式（2-1）成立。

HgzT=0T或者zTgH=0

（2.1）

线性分组码的最小距离就是码的最小重量（除全“0”码字外）。

线性分组码有两个重要的参数，一个是最小码距d0，它反映了码的检纠错能力，值越大检纠错能力越强。

另一个是码率R=K/N，它表示信息位在码组中所占的比重，体现了编码效率。

2.1.2LDPC码定义

定义：

LDPC码是一种校验矩阵H中只有很少的元素为“1”，大部分元素都是“0”的一种线性分组码。

主要参数：

n：

编码后长度，也是校验矩阵的列数。

m：

编码后校验位的长度，校验矩阵的行数。

j：

校验矩阵的列重量，即校验矩阵每列“1”的个数。

k：

校验矩阵的行重量，即校验矩阵每行“1”的个数。

1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1

1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0

0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0

0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0

0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0

0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1

0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1

0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0

0 0图2.1参数为（20,15,3,4）的LDPC码校验矩阵H

0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0

LDPC码是0一1种特0殊0的线0性0分1组码0,特0殊0之处0就1在于0它0的0奇偶0校1验矩0阵0H中0非零元素的

1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0

个数非常少，远远小于零元素的个数，所以LDPC码可以由其校验矩阵来定义。

这样的

LDPC码长为n，校验位长度大约为m，信息位长度为k=n-m。

校验矩阵H每行中“1”的个数称为行重，每列中“1”的个数称为列重。

2.2LDPC码的图结构

在图论中一个图是由顶点和边组成的，其中的树（tree）和二分图（bipartitegraph）都可被用来描述和分析LDPC码。

二分图中所有的顶点分为两个子集，任何一个子集内部各个顶点之间没有边相连，任意一个顶点都和一个不在同一个子集里的顶点相连。

2.2.1树

Gallager用校验树来表示H矩阵，用以说明消息在置信传播译码中传播的过程。

在这之后，表示LDPC矩阵的树图有了改进，如图2-2所示。

一条斜线和与其上端相连的一条横线代表一个校验方程，线上的节点即为构成此校验方程的节点：

图2-2中，黑点代表校验节点，白点代表变量节点。

图中有两层结构，由上至下，第一层表示为校验方程c，第二层表示参与c的信息节点v，第三层表示v参与的其余校验方程，第四层代表参与上一层校验方程的其它信息节点。

如果继续衍生下去，将会出现相同节点。

信息节点 v

校验节点

信息节点

图2.2变量节点v的校验树

2.2.2Tanner图

1981年Tanner建立了编码的图模型概念，并证明了和积算法在无环图中译码的最佳性，后来人们将应用于编码领域的二分图称为Tanner图。

LDPC码可以用一个Tanner图来表征，

Tanner图和校验矩