毕业设计论文(中国数字电视地面广播标准LDPC码).doc

摘 要纠错编码技术是移动通信、卫星通信、光纤通信和磁盘存储等系统中的关键技术之一。其中，由Gallager在1962年首先提出的低密度奇偶校验码(LDPC)码，在沉寂了多年之后，受到Turbo码的启发，Mackey和Wiberg等人对Gallager码重新进行了研究发Gallager码优异性能，LDPC码再次成为通信技术研究的热点。LDPC码是一种具有稀疏校验矩阵的线性分组码，研究结果表明，采用迭代的概率译码算法，LDPC码可以达到接近香农极限的性能。本论文较为系统的介绍了LDPC码的构造、编码和译码。重点是LDPC码的译码算法和其在数字电视系统中的应用。本文首先研究了LDPC码理论基础，例如图结构、线性分组码。之后介绍了几种构造方法，包括Mackay随机构造、有限几何的EG构造，以及相应的编码算法。并通过Matlab在AWGN信道下对LDPC码进行了仿真，测试其性能。关键字：LDPC码；BP译码；Tanner图；EG码；稀疏矩阵；数字电视地面广播ABSTRACTError-correcting codes are widely used in many fields, such as mobile communication, satellite communication, and so on. Low-Density Parity codes (LDPC), one kind of Error-correction codes, is defined in terms of very sparse matrices, and can be decoded by iteration algorithms. It was first investigated in l962 by Gal1ager, but appeared to have been 1argely forgotten. Mackey and Wiberg rediscovered its excellent property of achieving information rates up to the Shannon limit, after the extreme success of Turbo codes. LDPC code is a kind of sparse calibration matrix linear block code, the results show that the probability of iterative decoding, LDPC code can be achieved close to Shannon Limit performance.This paper has systematic introduced the structure, encoding and decoding of the LDPC code. This paper is focused on the decoding algorithms of the LDPC code and its digital television system applications. Firstly, this paper research on the theoretical foundation of LDPC codes, for example, maps the structure, linear block codes. After several tectonic introduced, including the Mackay random structure, the EG limited geometric structure, and the corresponding coding algorithm. And then, through Matlab in AWGN channel under the LDPC codes for the simulation to test its performance.Keywords: LDPC; BP decoding; Tanner graph; EG-LDPC; sparse matrix; Terrestrial Digital TV目 录南京邮电大学通达学院2008届本科生毕业设计第一章 绪论11.1信道编码11.2 LDPC码的特点和研究情况21.2.1 LDPC码的特点21.2.2 LDPC码的研究现状31.3 中国数字电视地面广播标准41.3.1中国数字电视地面广播标准系统介绍41.3.2 中国数字电视地面广播标准的方案DMB-TH5第二章 LDPC码的理论基础72.1线性分组码72.2 LDPC码的图结构72.2.1 树72.2.2 Tanner图82.3 LDPC码的分类102.3.1 规则码和非规则码102.3.2 二元域和多元域的码11第三章 LDPC码的编码与译码123.1 LDPC码的构造123.1.I Gallager的构造方法123.1.2 Mackay的构造方法123.1.3 PEG(progressive edge-growth)码133.1.4 几何构造方法133.2 编码原理143.2.1 高斯消去法143.3 LDPC码的译码153.3.1 LDPC码的概率译码算法15第四章 AWGH信道下的仿真结果与分析174.1 AWGH信道模型的建立174.2 LDPC码仿真结果及分析17结束语23致 谢24参考文献25第一章 绪论本章首先介绍信道编码理论和LDPC(LOWDensity Parity CODE)码的研究现状，然后概述数字电视标准的发展，最后给出本论文的主要内容和结构。1.1信道编码通信的目的是将载有信息的信号可靠的传送给对方，然而由于在传输过程中数字信号受到干扰，使信号码元波形变坏，接收端可能发生错误判断。信道中乘性干扰引起的码间干扰，通常可以通过均衡技术纠正，而对于加性干扰，除了要选择合适的调制解调方法以及调节发射功率外，纠错编码也是必须考虑的环节。一个基本的数字通信系统如图1-1所示。其中，信道编码器的作用是按某种算法，对信源码适当的添加冗余比特，使得接收端信道译码器根据这些冗余比特尽量多地找出并纠正错码。图 1-1 数字通信系统的基本模型Shannon在其1948年发表的论文“通信的数学理论”中，首次阐明了在任何一种有扰信道中均存在一个确定的信道容量C只要信息以小于此信道容量的速率传输，传输错误概率就可以任意小。Shannon定理的完整表述是：设R信息传输的速率，C是离散无记忆信道信道容量，是一个任意小正数，则只要CR就总存在码字长为N，码字数为的分组码使得译码的平均差错概率P。同时，Shannon推导了波形信道(连续信道)在加性高斯白噪声下的信道容量，即著名的香农公式： （1-1）香农信道编码定理肯定了逼近香农限的编码方案的存在，但并未说明如何找到符合要求的编码方案。香农定理提出以后，寻找能够实际应用的逼近香农极限的编码方案就成了纠错编码理论的目标。到了八十年代和九十年代初，经过几十年的研究和实践，纠错编码理论和技术取得了很大的发展。法国的C.Berrou等人在卷积码和级联码的基础上于1993年提出了一种全新的编码方案Turbo码，在信道编码的理论和应用中取得了突破性的进展。这种编码能够在长码长时逼近香农的理论极限，同时译码复杂度也是可以接受的。它将卷积码和随机交织器结合在一起，实现了随机编码的思想。采用软输入、软输出的的迭代译码算法，其主要译码算法有：MAP、1og-MAP、SOVA算法。在探究Turbo原理的过程中，Gallager2早在1926年提出的低密度奇偶校验(LDPC)码也逐渐引起人们的重视。这种编码由于校验矩阵的稀疏性，使得译码的复杂度只与码长成线性关系，当码长较长时，仍然可以进行有效的译码。D.J.c.Mackay、M.Neal和N.Wiberg等人对Gallager 码重新进行了研究，发现它同样具有逼近香农限的性能。并且发现多元域上的编码性能更好，且域的阶数越高，编码的性能越好。LDPC码和Turbo码有着许多相似的地方，在它们的构造方法中存在许多随机排列的元素，表现出随机码的特性。此外，两者的译码算法也存在着惊人的相似。LDPC码的迭代译码算法是基于可信度传播的，McEliece、Mackay和Cheng3为Turbo码的迭代译码算法可以看作Peal4的可信度传播算法(Belief Propagation)的一个特例。1.2 LDPC码的特点和研究情况随着LDPC码的优点逐渐被重视，这方面的研究开始大量涌现，LDPC码的理论和应用研究取得了进展，下面介绍一下LDPC码的特点和研究现状。1.2.1 LDPC码的特点LDPC码是一种有稀疏校验矩阵的线性分组码，其校验矩阵的结构具有以下四个基本特征：1)校验矩阵的每行有个1；2)每列有个1；3)两列之间在相同位置上都是1的个数不大于1，即交叠部分不超过1；4)与码长相比，行重列重很小，低密度奇偶校验码也因此得名。满足以上定义的称为规则码(regular)，如果行重或列重不是常数，则成为非规则码(irregular)。在Turbo码研究的巨大成功的带动下，Mackay等人重新研究了LDPC码，并发现它具有非常好的特点:逼近香农限的性能，且描述和实现简单，易于进行理论分析和研究，译码简单可实行并行操作，适合硬件实现。近年来LDPC码以其优异的性能、简洁的形式及良好的应用前景日益备受青睐。与Turbo码相比，LDPC码有很多优势。在译码方面，得益于校验矩阵的低密度性，可实现线性时间内译码；LDPC码基于可信度传播的译码算法本质上是并行算法，有利于硬件的并行实现，可以达到很高的译码速度，目前市场上的LDPC码译码器译码速率达到384Mbps；由于校验式的存在，使得LDPC码的译码过程中能够确定码字是否正确，动态终止译码迭代：不易发生“平板效应” (error-floor) ，即译码后的误码率下降速度不会随信噪比的增加而减缓；由于LDPC码码字之间的码距较大，使得译码过程中出现不可检测错误的概率很小：可以采用基于硬判决的迭代算法，虽然性能比软判决差，但实现复杂度很低。在理论分析方面，LDPC码有简单的数学模型二分图，理论分析相对简单。LDPC码有如下缺点：编码复杂度高，虽然最新的研究表明LDPC码可以在线性时间内编码，但相对于卷积码仍然很大，而且在码长很长时由于必须在接收到所有的信息比特后才能够进行编码，这就会给编码带来一定的时延。另外，译码优异的性能通常要在码长较长时才能够体现出来，当采用中、短长度的LDPC码时，由于编码时短长度闭合环路的存在，会在某种程度上降低译码性能。1.2.2 LDPC码的研究现状1.编码方面如果采用普通的编码方法，会带来二次方的复杂度，在长码长时是难以接收的，并且编码时延较长。T.J.Richardson和R.L.Urbanke 在文献5中给出了一种利用校验矩阵的稀疏性对校验矩阵进行一定的预处理后，在线性时间内编码的有效算法，初步解决了LDPC码编码的复杂度问题。Yu Kou和Shu Lin等人对基于有限几何(Finite Geometries)的LDPC码进行研究，它可以表示成循环或半循环的形式，利用生成多项式决定的简单反馈移位寄存器就可以实现编码，编码时间与码长呈线性关系，是比较实用的LDPC码。另外，旋转LDPC码，可以用一个排列向量构成，易于硬件快速实现编码。但是编码前的数据接收过程引入的编码时延仍是LDPC码需要解决的问题。2.译码方面Gallager在他的文章中引入了迭代译码(iterative probabilistic decoding)，是现在被称为置信传播(Belief Propagation，BP) 算法的一种。现在已有很多BP的改进算法，如美国夏威夷大学的Marc P.C.Fosorier研究小组提出的两种BP简化算法UM BP-based和Normalized BP-based，可快速迭代译码，只有实数的加法运算，不需要信道的先验信息，软件和硬件实现都获得好的性能和复杂度的平衡。另外，西安电子大学的贺玉成等提出量化的BP算法，用一个预先计算好的表来简化计算，结果接近甚至超过连续译码算法。除了以上提到的软译码算法，硬判决译码由于低译码复杂度，也引起人们的关注，包括BP、BF、Partial loop-break等算法。3.验证矩阵的构造方面目前对构造好码的研究分为两个方面：一是寻找构造码的分析方法，一是构造综合性能好的码。在构造好码方面，Yu Kou和Shu Lin等人利用几何方法，给出了4种基于欧几里得空间的点和线设计出的码。这些码具有好的最小距离特性。同时几何LDPC码可以用不同的方法扩展或截短得到其他性能非常接近香农限的码。S.J.Johnson和S.R.Weller也给出了一种称为Kirkman Triple系统的组合设计方法构造非随机的LDPC 码，在码长较短时性能好于随机构造的码。而Bane Vasic利用反Pasch仿射几何设计的码，具有很高的码率。在构造综合性能好的码方面，研究者提出了一种比特填充(bit-filling)的方法，可以得到码率最大的码。Xiao.Yu Hu和E.Eleftheriou等人用逐步边增加(Progressive Edge-Growth，PEG)的方法设计出具有最大周长和好的距离特性的码。4.在实现和应用方面目前，基于FPGA和ASCI的LDPC编、解码器，基于DSP的LDPC编、解码器已经研制成功，例如Comtech AHA公司推出了低密度奇偶校验码(LDPC)前向误差修正(FEC)编码器/译码器核；同时，由于性能的优越性，LDPC码有很好的应用前景，将在深空通信、光纤通信、卫星通信、磁/光/全息存储、移动和固定无线通信、电缆调制/解调器和数字用户线(DSL)中得到广泛应用。目前在欧洲数字电视卫星通信标准DVB-S2中采用就是BCH和LDPC级联编码，在第四代移动通信中使用LDPC码的提案也已经提交。而中国数字电视地面广播标准也极有可能采用LDPC信道编码或其级联码。1.3 中国数字电视地面广播标准目前国际上关于数字电视地面传输有三个标准，分别是美国的高级电视系统委员会(Advanced Television systems Committee，ATSC)、欧洲的数字视频地面广播(Digita1 Video Broadcasting-Terrestrial，DVB)和日本的地面综合业务数字广播(Integrated Service Digital Broadcasting-Terrestrial，ISDB)。我国数字电视地面标准是由三个方案最终融合而成，分别是清华大学地面数字多媒体电视广播传输协议(TDS-OFDM based DMB-T)、上海交通大学的高级数字电视广播系统(ADTB-T)和国家广电总局广播科学研究院根据广播应用的不断发展，基于OFDM技术，提出了“地面交互多媒体技术框架” (TiMi) 传输方案。1.3.1中国数字电视地面广播标准系统介绍标准号：GB 20600-2006 标准名称：数字电视地面广播传输系统帧结构、信道编码和调制 批准日期：2006-08-18 实施日期：2007-08-01 标准性质：强制标准国标系统综述：GB20600-2006具有自主创新的特点，提高系统性能的关键技术有：实现快速同步和高效信道估计与均衡的PN序列帧头设计和符号保护间隔填充方法，低密度校验纠错码(LDPC)，时域同步正交频分复用(TDS-OFDM)调制，与自然时间同步的可寻址的多层信道帧结构，系统信息的扩频传输方法等。本标准支持4.813Mbit/s32.486Mbit/s的系统净荷传输数据率。 数字电视地面广播传输系统是广播电视系统的重要组成部分，不但必须具有支持传统电视广播服务的基本功能，而且还要具有适应广播电视服务的可扩展功能。数字电视地面广播传输系统支持固定(含室内，外)接收和移动接收两种模式。在固定接收模式下，可以提供标准清晰度数字电视业务，高清晰度电视业务，数字声音广播业务，多媒体广播和数据服务业务；在移动接收模式下，可以提供标准清晰度数字电视业务，数字声音广播业务，多媒体广播和数据服务业务。 数字电视地面广播传输系统支持多频网和单频网两种组网模式，可根据应用业务的特性和组网环境选择不同的传输模式和参数，并支持多业务的混合模式，达到业务特性与传输模式的匹配，实现业务运营的灵活性和经济性。1.核心技术 TDS-OFDM(Time Domain Synchronous Orthogonal Frequency Division Multiplexing)调制方式频谱效率高，抗多径干扰能力强，适用于宽带信号传输。LDPC(Low Density Parity Check)低密度校验码逼近香农极限的信道纠错编码 Legend Silicon Corp。 PN序列信道估计采用时域伪随机(PN)序列作为参考信号。 2.GB20600-2006具有多项鲜明特点和优势 大容量能够提供更高的数据传输码率，在一个8MHz数字电视频道内可传6-15套标清或1-2套高清数字电视节目。 高可靠传输质量好，很好地解决了各种干扰和高速接收问题，可达到与有线电视同样的收视效果。 兼容性强适合我国国情，与现有模拟电视广播系统兼容，建网成本低，组网快，可以利用现有的微波链路，高山发射站，模拟发射机和闲置的频率(邻频)。 一发三收在同一平台上支持固定，便携，移动和手持接收设备。 高安全性不受非法信号干扰，具有移动性，抗毁坏性的特点，保障安全播出。 高覆盖性能够实现更大的服务覆盖范围。 可扩展性融合无线通信技术，使系统能实现双向多媒体服务，具有进一步发展的潜力。 成熟性从发射设备，接收设备，测试设备到集成电路芯片等产业链成熟。3.国标GB20600-2006系统组成 系统配置主要包括：信源编码器(通常为MPEG-2编码器，H.264/MPEG4编码器)，TS码流复用器，加密机，GB20600-2006数字激励器，单频网适配器，GPS信号接收机，数字电视发射机，天馈系统以及相应的管理软件单元。实际上根据运营模式不同，系统还可以相应简化，数字电视地面广播还可以借用已有的模拟天馈线系统，节约资源和建设时间。 此外，还有所需要的测试设备，不过这些测试设备无需全天候使用，可考虑在需要的时候借用或租用，主要有包括场强仪，功率计，频谱仪，标准接收天线，GPS定位仪等。1.3.2 中国数字电视地面广播标准的方案DMB-THDMB-TH是融合了包括清华、上海交大和广科院等多方研发成果的一个方案，但DMB-TH的主要技术是基于清华方案，也就是拥有自主知识产权的TDS-OFDM(时域同步正交频分复用)调制技术，原有的清华方案的主要技术特点都会体现在DMB-TH标准中，同时，DMB-TH提供了单载波和多载波两种技术选项。在国标制定的过程中，凌讯科技和清华大学共同提出了一种新颖的、适合我国国情的地面数字电视技术方案，称为地面数字多媒体电视广播协议-DMB-T，其核心采用了时域同步正交频分复用（TDS-OFDM）调制技术和独具特色的与自然时间同步的可寻址多层帧结构。DMB-T 此后成为了中国数字电视地面广播传输系统标准-GB20600-2006数字电视地面广播传输系统帧结构、信道编码和调制的基础框架。虽然国标目前尚无一个官方正式的英文代号，由于它的主要核心技术来自于清华大学地面数字电视方案DMB-T，并且清华方案占据了全国三分之二以上的市场份额，DMB-TH作为国标的俗称已在业内逐渐地流行开来。实质上，DMB-TH是从国标的众多调制模式和应用功能中优选出来的技术实现体系，是一套可以独立运行的可扩展技术方案。第二章 LDPC码的理论基础LDPC码是一种线性分组码，由于校验矩阵的稀疏性，它具有Tanner图这样的数学模型，因此理论分析相对简单。20世纪90年代，人们利用定义在Tanner图对LDPC码的译码性能进行分析，目前己经有了一些较为完善的理论，人们还发现基于稀疏图的LDPC码具有非常接近Shannon限的性能。这一章首先介绍线性分组码的原理，然后简介LDPC码的图论基础知识，最后给出LDPC码的分类。2.1线性分组码线性分组码在纠错码中有很重要的地位，它的数学模型简单，较易对其进行性能分析。而LDPC码本质上就是一种线性分组码，它通过一个生成矩阵G将信息序列映射成码字序列。每一个生成矩阵G，都存在一个奇偶校验矩阵H，所有的码字序列C构成了H的零空间。线性分组码的信息位和监督位之间的关系满足一组线形代数方程。一个(N，K)线性分组码的编码就是根据己知的K个信息比特求出N-K个校验比特，因此必须有N-K个线形独立的方程。如果线性分组码的前K位就是原来的信息比特，后N-K位是监督位，则称之为线形系统码。设二进制线性分组码(N，K)的校验矩阵为，码字为z，则H的每一行与它的码字的内积均为零，即式(2-1)成立。 （2-1）线性分组码的最小距离就是码的最小重量(除全“0”码字外)。线性分组码有两个重要的参数，一个是最小码距，它反映了码的检纠错能力，值越大检纠错能力越强。另一个是码率R=K/N ，它表示信息位在码组中所占的比重，体现了编码效率。2.2 LDPC码的图结构在图论中一个图是由顶点和边组成的，其中的树(tree)和二分图(bipartite graph)都可被用来描述和分析LDPC码。二分图中所有的顶点分为两个子集，任何一个子集内部各个顶点之间没有边相连，任意一个顶点都和一个不在同一个子集里的顶点相连。2.2.1 树Gallager 用校验树来表示H矩阵2，用以说明消息在置信传播译码中传播的过程。在这之后，表示LDPC矩阵的树图有了改进，如图2-1所示。一条斜线和与其上端相连的一条横线代表一个校验方程，线上的节点即为构成此校验方程的节点：图2-1中，黑点代表校验节点，白点代表变量节点。图中有两层结构，由上至下，第一层表示为校验方程c，第二层表示参与c的信息节点v，第三层表示v参与的其余校验方程，第四层代表参与上一层校验方程的其它信息节点。如果继续衍生下去，将会出现相同节点。图2-1变量节点v的校验树2.2.2 Tanner图1981年Tanner建立了编码的图模型概念，并证明了和积算法在无环图中译码的最佳性，后来人们将应用于编码领域的二分图称为Tanner 图。LDPC码可以用一个Tanner图来表征，Tanner图和校验矩阵一一对应。图中包含三种元素，变量节点(Variable node) 、校验节点(Check node)和连接它们的边，其中变量节点内部和校验节点内部没有任何边连接，只有在变量节点和校验节点之间才有边相连接，任意一对变量节点和校验节点最多只有一条边相连。Tanner图中的每一条连线对应于校验矩阵中的1。而且对于一个码长为N，码率R=K/N的线性码，它的校验数目是M=N-K。任意一个线性码都可以用一个Tanner图来表示，而LDPC的Tanner图是稀疏的，每一个变量节点只和少数几个校验节点相连，每一个校验节点也只和少数几个变量节点相连。使得图中边的数目几乎正比于码长N，而不是N的二次方。下面以一个(6，3) 线性分组码说明二分图。以(6，3)线性分组码的校验矩阵和其二分图，图中上面的节点是变量节点，下面的节点是校验节点。校验矩阵: (2-2)相应的二分图:图 2-2 (6，3)线性分组码的校验方程和对应的二分图图2-2的第一行节点表示发送的比特(称为变量节点)，第二行是它们满足的校验(称为校验节点)。图中变量节点集合V=()和校验节点集C=()内部不存在相连的边，但两类节点之间存在着连线。变量节点和校验节点之间存在连线意味着该变量比特参加了此校验式，也就是校验矩阵某一行中1的位置。每个节点上的连线数目称为该节点的次数(degree)，图2-2，变量节点的次数都是=2，校验节点的次数都是=3。可以把Tanner图拆成一个一个的子码(subcode) ，例如图23所示：图2-3(6，3)线性分组码的一个子码LDPC码是线性分组码的一种，它的最小汉明距离决定了性能优劣，然而一般情况下，LDPC码的码长较长，无法直接求出一个码的最小距离。而Tanner图中的“环”在一定程度上反映了译码性能。Tanner图中由变量节点、校验节点和边首尾相连组成的闭合环路称为“环”。环的长度就是其中边的数目。从LDPC码的Tanner图中可以看出，每个节点都会存在许多这样的闭合环路，且每个环的周长一定是2的整数倍。在图2-2变量节点就参与了一个长度为6的环，如图中粗线所示，由起，经过，最后返回。环在LDFC码的迭代解码过程中会造成不良影响，形成无效信息的正反馈，使迭代解码无法达到最佳性能，环是如何影响译码性能将在译码章节中详细说明。理论和实践均己证明，Tanner图中的环，特别是短环对迭代解码的性能影响很大。Tanner图中最短环的周长称为最小圈长girth，例如图2-2girth是6。girth的越大，最小距离的下界越大，码的纠错能力越强，Tanner给出了最小距离的下界和girth的关系式： （2-3）其中，D为LDPC码的最小码距，g为LDPC码的girth，y为变量节点的次数，d为二分图中子码(subcode) 的最小码距。如果二分图的girth等于4，将会影响LDPC码的误码率性能，所以在构造LDPC码的校验矩阵时，要尽量避免二分图中出现girth为4的情况。2.3 LDPC码的分类LDPC码有多种分类方法，例如按行重、列重是否是定值划分，可以分为规则码和非规则码；按所在的域划分，分为二元域和多元域的码。下面将分别介绍这两种分类。2.3.1 规则码和非规则码1. 规则(regular)LDPC码如果LDPC码的校验矩阵行列重量固定为，即每个校验方程有比特参与校验，每个变量参与个校验方程，我们称之为规则LDPC码。这也是Gallager最初提出的Gallager码的特点。我们用Gallager对LDPC码的表示方法：将码长为N，行重、列重分别为和的LDPC码称为(N，)LDPC码。从Tanner图的角度来看，这种LDPC码的变量节点次数全部为，而校验节点的次数都为。上例就是一个规则的(6，2，3)LDPC码，相应的图2-2，第一行每个变量节点与3条线相连，第二行校验节点与2条线相连。可以适当放宽上述规则LDPC码的条件，行或列的重量可以不是固定的整数，但行列重量尽量服从均匀分布。另外为了保证LDPC码的Tanner图上不存在长度为4的圈，通常要求行与行以及列与列之间的交叠部分重量不超过1。当校验矩阵H满秩时，规则码的码率R=(N-M)/N=K/M=1-，当校验矩阵H不满秩时，R=(N一rank(H)/N=K/M。Mackay在文献13中证明了在任意信道中，1)规则LDPC码满足了好码(Good codes)定理的要求，即在固定列重，码长N足够长的情况下，存在一个0到信道传输容量之间的值r，在此速率下可以实现无差错传输。2)规则LDPC码满足了更好码(very Good Codes)定理的要求，即如果不固定列重，当/M很小时，此LDPC码可以很接近信道容量。 2. 非规则(irregular)LDPC码在Tanner图中，信息节点希望能参与尽可能多的校验方程，以便更准确的判断自己。而校验节点希望向尽可能少的信息节点传递消息，以确保更准确的判断信息节点。非规则LDPC在此要求下受到人们的重视。Luby12分析了非规则的性能和构造好的非规则码的方法。非规则码的行列重已不再是固定值，即每个变量节点参与的校验式数目或每个校验式中含有的变量节点数目不再保持均匀，而是有意设置部分突出的变量节点和校验节点。在译码过程中，那些参与较多校验式的变量节点迅速得到正确译码信息，然后它们给相邻的校验节点更加有效的概率信息，而这些校验节点又可以给与它们相邻的次数少的变量节点更多的信息。整个译码的过程呈现出一种波状效应，次数越高的变量节点首先获得正确信息，然后是次数较低的节点，然后依次往下，直到次数最低的变量节点。正是这种波浪效应，使得非规则码获得比规则更好的译码性能。2.3.2 二元域和多元域的码Matthew C.Davey和MacKay对上述二元域的LDPC码又进行了推广，将其放到了多元域GF(q)上。假设在域GF(2)和域GF(q)()上构造的LDPC码所对应的校验矩阵分别是和中的元素是0或1，而是由元素0，1，q-1构成，中的每个元素都是中p个元素的组合。从矩阵看将相应GF(2)域中相应的1q向量代入GF(q)域的，得到的二进制形式，调节检验矩阵可以增加与之对应的二进制校验矩阵中列的平均重量，从的Tanner图看，结构并没有改变，不会造成节点之间短圈数目的增加。对于二进制LDPC码来说，如果它的校验矩阵H的列重量增大，那么它的性能也增加，但是如果增加列重量会使得Tanner图中各节点之间的短环数目急剧增加，从而使BP算法的性能下降。而在GF(q)域上构造的LDPC正好可以解决这个矛盾。例如在GF(16)上构造的规则码性能已经和Turbo码相差无几。第三章 LDPC码的编码与译码3.1 LDPC码的构造LDPC码是线性分组码，可以由校验矩阵H等效描述，所以我们只要构造了该码的校验矩阵就完成了LDPC码的构造。3.1.I Gallager的构造方法Gallager 1962年最初的工作中，给出了正则码的构造方法：对码长为N的正则码，他将校验矩阵按行水平地分割为几个大小相同的子矩阵，每个子矩阵的每一列都只含有一个“1”。要构造校验矩阵H，他预先构造了一个子矩阵，例如可以是这样一个子矩阵，矩阵的第i行上，所有的“1都分布在矩阵的第到列上，见(3-1)式。 （3-1）为预先构造的矩阵，令为矩阵的列置换，即为的随机列置换阵。那么矩阵H可以如下构造： （3-2）此即完成了LDPC码的构造。3.1.2 Mackay的构造方法Mackay在LDPC码的校验矩阵中引入了一些重量为2的列，这样由于整个校验矩阵中“1”的数目减少了，对应因子图上边数也就减少了，所以，减少了因子图中环的数量，降低了译码过程中信息的重复利用，减小了环对译码性能的影响。但是，引入重量为2的列会导致低重量码字的出现。需要采取措施减小其出现概率。Mackay给出了如下指导性的构造方法。具体的构造思想有如下四个：构造法1A：这是最基本的构造方法，该方法构造的矩阵每列的重量都为一固定值t，而每两列之间重叠的1的个数不大于1。构造法2A：对于一个MN矩阵，前M/2列的重量都为2， 并且各列重复不超过1，这些重为2的列由两个M/2M/2的单位矩阵构成，一个在上，一个在下。其余如1A。 （a） （b）图 3-1 Mackay 的构造方法 （a）1A；(b) 2A构造法1B，2B：由构造1A或构造2A构造校验矩阵，然后从该矩阵中删除一些仔细选择的列，使得结果矩阵对应的二分图中没有小于某个给定长度的环。上图中的圈代表，圈中的数字3代表此矩形中有该数字个排列矩阵的叠加，对角线表示单位矩阵。3.1.3 PEG(progressive edge-growth)码构造思想是以增加girth为目的；PEG方法的具体操作：给定变量节点的数目、校验节点的数目m和变量节点的分布序列，边选择程序开始放置新的边，选择新边时尽可能对Tanner图的girth有较小的影响;新边放置好后，继续搜索下一个边，直到结束。3.1.4 几何构造方法由于这种构造方法是基于有限几何基础之上的，所以我们首先介绍一下有限几何。设Q是一个有n个点、l条直线的有限几何，而且满足1.每条直线上恰有P个点；2.任意两点之间有且仅有一条直线相连；3.每个点恰好在条直线上；4两条直线要么平行，要么相交且于一点。有两类具有上述结构的有限几何，称为有限域上的射影几何和欧氏几何。在GF(2)构造一个维矩阵，矩阵的每一行对应Q中的一条直线，每一列对应Q中的一点。当且仅当i条直线包含第j个点时，矩阵的每一行的行重为，表示此行对应直线包含p个点；与之对应，矩阵的每一列的列重为，表示此列对应点在条直线上。这样构造的校验矩阵，因为两条直线之间最多只有一个交点，所以任意两行之间没有一个以上的“l”在相同的列出现，同样的原因，任意两列之间也没有一个以上的“l”在相同的行出现。矩阵的密度为，如果和相对于n和l若很小，那么是一个低密度矩阵。以为校验矩阵，其零空间给出了一个LDPC码，码长为n。该码对应的因子图中没有长度为4的环，其汉明距离至少为+1。令为的转置矩阵，即，那么也是一个低密度矩阵，行重为，列重为。以为检验矩阵，其零空间也给出了一个LDPC码，码长为1。同样，该码对应的因子图中也没有长度为4的环，其汉明距离至少为+l。除了上述构造方法，我们还可以利用欧氏几何(EG)和射影几何(PG)分别构造EG-LDPC 码和PG-LDPC码，对应于其中每种几何，均可构造两种LDPC码。可以对校验矩阵按一定规则进行扩展与删减，进而对该码进行扩展或缩短，可以进一步提高其性能。这里不再详细讨论。3.2 编码原理编码就是在给定的条件下，将一个信息序列s映射成编码序列x，使其满足： （3-3）其中x=(s，)，s是信息序列，是校验序列。对于LDPC码来说，一个需要面对的主要问题是看起来的高编码复杂度，LDPC码编码的直接实现具有码长N的二次方的时间复杂度，而Turbo码可在线性时间内编码。为降低复杂度，许多人都针对切LDPC码进行了研究，Sipesr和Spielman提出用级联图而不是二分图以减小编码复杂度，Mackay，Wilson和Davey 建议强制性的使奇偶校验矩阵具有下三角阵的形式。T.J.Richardson和R.L. Urbanke提出具有线性时间复杂度的有效编码，而Lin Shu等人提出的有限几何码，由于具有循环或准循环性，使用循环码的编码方式，编码器设计简单，可实现线性时间的编码复杂度。3.2.1 高斯消去法首先对矩阵作预处理，利用行变换和列变换校验矩阵变成一个下三角矩阵，如图3-2所示：图3-2下三角形形式的校验矩阵矩阵的行变换并不会改变码字的结构，而列变换会改变Tanner图的变量节点的位置，并没有改变码字的最小距离，故不影响码的纠错能力。下例将说明列变换对矩阵和Tanner图的影响。以2.2.2节的例中矩阵为例，如果将第六列和第二列交换，得校验方程： (3-4)相应的Tanner图：图3-3 Tanner图经过上述变化，原矩阵化成了下三角矩阵（）。利用递归法，根据已知信息序列求出校验序列。具体公式是： （3-5）为了得到下三角矩阵，如果用软件实现，预处理部分的复杂度是，具体为次乘法，次加法，而编码的复杂度是，具体为次乘法，次加法。这么高的复杂度，是由于对矩阵作了高斯消去，使得矩阵H已不再是稀疏的。3.3 LDPC码的译码3.3.1 LDPC码的概率译码算法概率译码算法也称软译码算法。它是一种基于消息传递(Message Passing Algorithms)的迭代译码算法(Iterative Algorithms)。通常，用M(j)表示与变量节点j相连的所有校验点所构成的集合，M(j)i 表示M(j)中除去其中的校验节点i后剩下的集合；用N(f)表示与校验节点i相连的所有变量点构成的集合，N（i）j表示N(i)中除去其中的变量节点。j后剩下的集合。则相应的迭代公式可表示为： （3-6）在AWGN信道下，码字序列通常需要经过BPSK调制然后才送入信道，并在接收端得到接收序列Y=， 。根据AWGN信道的特性可以得到：Y = ( i，j=1，2，N1)，其中为服从N(0，)的一维高斯随机变量，因此可以推知： （3-7）AWGN信道下和积译码算法的整个流程如下：1)初始化。对所有变量节点根据(3-7)式计算似然，对所有 赋初值=；2)迭代。水平迭代：根据式(3-6)，对所有校验节点，计算；垂直迭代：根据式(3-6)，对所有变量节点，计算； 3)判决与终止迭代。每次迭代结束后对所有变量节点计算并作硬判决，判决规则为： （3-8）若判决序列满足方程，则停止迭代并输出判决结果，否则继续迭代直到最大迭代次数。第四章 AWGH信道下的仿真结果与分析4.1 AWGH信道模型的建立高斯白噪声是指一阶概率密度函数是高斯型的白噪声。其一阶概率密度函数 （4-1）满足均值为u、方差为的正态分布(4- 1)，即。产生正态分布随机数的方法大致有以下两种：(1)用中心极限定理获得正态分布若随机变量是n个独立的、在(0,1)区间上的均匀分布随机数，则当n充分大时 (4-2)它分布渐进于标准正态分布N0,1。若希望产生均值为m，标准差为s的正态分布随机数，则可把上式改写为：Y=m + sX （4-3）(2) 用直接抽样构造正态随机数 即用一对(0,1)均匀分布的随机数按以下数学式构成一对标准正态分布。 （4-4）直接抽样只要一对(0,1)均匀分布的随机数就可得到一对标准正态随机数，而用中心极限定理则需n个随机数才产生一个正态随机数；但另一方面，直接抽样要进行对数、开方、相乘和三角运算，需要较多的计算时间，这是它的缺点。本文用Matlab中的函数产生(0,1)均匀分布的随机数然后根据直接抽样构造正态随机数的方法得到产生高斯白噪声的函数，由于仿真系统是在Visual C+环境实现的，这里采用Matlab C+数学库中的mex。在命令窗口输入 “mex decode_ldpc_new.cpp”就可以编译成“DLL”文件，然后使用主要脚本模拟了。4.2 LDPC码仿真结果及分析图4-1给出了整个仿真系统的框图，从图中可以看出，整个仿真系统可以分为LDPC码生成模块、系统的输入输出文件和LDPC码仿真模块三个部分，下面将分别对三个部分进行阐述。图 4-1 LDPC 码的仿真系统考虑到搜索LDPC码需要大量的时间而且有失败的可能，而且仿真中可能要多次用到同一个LDPC码进行仿真，因此LDPC码生成部分单独实现，成为了一个独立的模块，它主要用来完成LDPC码校验矩阵和生成矩阵的生成以及将校验矩阵和生成矩阵存储在LDPC码文件中。由于Matlab提供了功能强大的矩阵处理函数以及性能良好随机函数，这里采用Matlab来实现LDPC码生成模块，它是由一系列LDPC码生成函数构成，包括正则LDPC码生成函数、半正则LDPC码生成函数和非正则LDPC码生成函数等。在进行仿真之前必须选择一个LDPC码的生成函数来产生所需要的LDPC码的校验矩阵和生成矩阵，并且将它们保存在特定的LDPC码文件中。进行仿真时，首先考虑信噪比，由信噪比来决定信息帧的数量MsgPackNum和噪声源的方差。信息帧的数量主要参考的是在此信噪比下理论仿真计算出误码率的数量级。在归一化条件下，设每个码字比特功率，则每个消息比特功率，而高斯白噪声中噪声功率,因此仿真的信噪比 (单位为dB)可以表示为： （4-5）方差为： （4-6）接受信号的平均信噪比为： （4-7）由式(4-6)可知式(4-7)计算的噪声源的方差同样适用于这里进行仿真的瑞利信道。运行Matlab仿真程序：1.打开脚本文件的名称“ generic_simulator_nonsys.m ”2. 负载的H （校验）矩阵。3.设置信噪比范围。4.设定的最高数量的解码器迭代，最大数的错误码，以计数为每个信噪比点（必须至少为30个可靠的估计，该文件显示结果为100-200码字的错误。） 5.选择C型或基于MATLAB的LDPC码解码器“decode_ldpc_new ”。6.运行该脚本，等待的结果，生成了“BER”和“FER”图，如图4-3，图4-4。图4-3 LDPC码的误码率图4-4 LDPC码的误帧率由图可以看出信噪比与误码率、误帧率随信噪比的升高而呈稳定地下降趋势，这是它良好的纠错性能的一个表现，具体实