（信号与信息处理专业论文）ldpc码译码算法的研究及其硬件实现.pdf

烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 i 摘要 ldpc 码（low-density-parity-check code，低密度奇偶校验码）是一种译码性能 逼近香农极限且具有较强纠错能力的差错控制能力的编码技术。 研究表明当码长足够长的时 候，ldpc 码与 turbo 码相比更具优良性能，极有可能被确定为第四代移动通信中的纠错编 码方案。因此，ldpc码译码算法的硬件测试已经成为当今纠错码领域的研究热点之一。 本论文主要对 ldpc 码的译码算法进行了研究，针对最优译码置信传播算法的复杂度较 高而最小和译码算法性能较低的问题， 研究了分层最小和译码算法可认为是二者的折中， 并 通过仿真进行了验证。本文对ldpc码的研究工作主要在以下方面： 1. 研究了构造ldpc 码的gallager、mackay、peg 三种方法，并分析了它们对ldpc 译 码性能的影响。 2. 研究了ldpc 码的基于高斯消去和ru 快速两种编码算法，对这两种编码算法进行了 分析与比较，讨论了 ru 快速编码算法在保持良好译码性能的前提下大大减少了编码的复杂 度，具有广阔的工程应用价值。 3. 分析了 ldpc 码的各种译码算法：概率 bp、llr-bp、最小和、归一化最小和、分层 最小和译码算法， 对各种算法的优缺点进行了理论分析和比较， 分析了它们的性能差异。 通 过搭建高斯白噪声（awgn）信道，对 ldpc 码进行了仿真，分析了各种不同配置参数（如不 同码长、不同码率、不同译码算法、不同迭代次数等）对译码性能的影响，讨论了译码算法 中的噪声门限、密度演变算法及 awgn 信道下的初始信息，仿真结果表明了改进分层最小和 译码算法的可行性与实用性， 确定分层最小和译码算法在译码性能上完全适合作为硬件实现 的译码算法。 4. 使用verlilog硬件描述语言， 采取部分并行译码的结构， 采用自顶而下的设计方法 来设计ldpc码的译码器，在quartus 环境中将各个模块合并为完整的译码器电路，对译 码器进行功能、时序仿真，下载译码算法进行相应的测试。 5. 对ldpc码的算法和硬件实现的发展和改进做了展望。 关键词：ldpc码；fpga；分层最小和；置信传播 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 ii abstract ldpc code (low-density-parity-check code) is a powerful error correcting technique. research shows the decoding performance of ldpc code is close to shannon limit and is more excellent than turbo code with sufficiently long block lengths. considering the advantage of ldpc code, it is great possibility to be identified as error correction coding scheme for the forth-generation mobile communication. so, the decoding algorithm of ldpc code has become one of the hot areas of error-correcting codes research. for belief propagation algorithm is high complexity and the performance of min-sum algorithm is so poor, layered decoding with min-sum algorithm is proposed which verified by simulation. in the paper, the mainly research of ldpc code is following: firstly, researching gallager, mackay, peg three methods for constructing ldpc code and analyzing their impact on the decoding performance for ldpc code. secondly, researching based on gaussian elimination and the ru fast encoding algorithms which are compared with each other, result shows the application of ru fast encoding algorithm which remains better decoding performance significantly is extensive. thirdly, analyzing the performance difference of various decoding algorithms of ldpc code, for example the probability of bp, llr-bp, min-sum, normalized min-sum and layered decoding with min-sum algorithm, identifying layered decoding with min-sum algorithm is completely suitable as hardware decoding by simulation in awgn channel with different configuration (such as different code length, different bit rates, different decoding algorithms and different number of iterations, etc.). the layered decoding with min-sum algorithm are discussed in the noise threshold, the density evolution algorithm and the initial information of awgn channel.the simulation results show that layered decoding with min-sum algorithm is completely suitable as hardware decoding. fourthly, taking part of the parallel decoding structure, using top-down methodology to design the ldpc decoder, in the quartus environment, all modules will be merged into a complete decoder circuit. we got the test result by downloading layered decoding with min-sum algorithm in decoder circuit with functional, timing simulation. keywords: ldpc code; fpga; layered decoding with min-sum; believe-propagation 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 1 1 绪论 1.1 研究背景及意义 近十年来， 无线移动通信的飞速发展， 使人类实现了无处不在的通信理想向前迈了一大 步。随着经济的增长、社会的发展及人们物质精神生活的提高，人们对通信提出了更新、更 高的要求。 纠错码作为信道编码是提高通信质量的渠道之一。 当今的纠错码不再是仅仅停留 在理论方面，它已经是一门标准的技术被广泛应用。在移动通信中，纠错码被广泛应用于模 拟及数字体制的传输来提高传输的可靠性和节省珍贵的频谱资源； 在卫星通信中， 纠错码技 术已经成为降低对高功放的要求和减少地球站天线孔径的经济可靠的方法。 turbo码作为一种纠错码，已经成为第三代移动通信（3g）信道编码的标准，但其译码 复杂度较高，时延长的特性，难以适应有更高数据传输的未来移动通信中（超3g或4g） 。 ldpc信道编码技术是近年来全球的热点研究的新技术，研究证明“它在采取基于置信传播 （believe-propagation， bp） 迭代译码算法的条件下是目前最接近香农限的纠错码， 因此ldpc 码的重大发现是继turbo码之后在纠错码领域的又一重大发现。 ldpc码与高效调制相结合， 能够满足下一代移动通信中高速数据大容量传输的要求。ldpc码具有较低的差错平底，可 实现完全的并行操作，译码复杂度低于turbo 码，适合硬件实现，吞吐量大，极有可能取代 turbo 码而成为第四代移动通信的首选编码方案。 ldpc 码与turbo 码的比较主要体现的优 点： 在纠错性能比较方面： 由于turbo 码的最小欧氏距比较小， 其在低信噪比的条件下性能 优越，而在高信噪比时性能却有所下降，即具有较高的差错平底” 。ldpc 码却很好的克服 了这一缺点，正则的 ldpc 码的码字间的最小距离随着码长的增加呈线性增加，具有优异 的码长渐进性能，即具有很低的差错平底（error floor） 。 在实现的复杂度方面，turbo 码的map 译码算法复杂度非常高，要降低其复杂度可以 用 sova 算法译码，但这样会使其译码性能有所下降。ldpc 码的置信传播算法译码算法 复杂度相对较低，且可以实现完全的并行操作。ldpc 码的编码器一般比 turbo 码复杂一 些，特别是对于非正则ldpc 码，其数据流的写入与设计较困难，但ldpc 码编译码不用 交织器，因而总的来说具有更低的硬件实现复杂度。综上，ldpc码比turbo码在技术上更 具有优势，更能适应未来系统高速数据传输和高性能的要求。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 2 1.2 纠错码的历程发展 有扰信道编码定理是香农1948年在 “通信的数学理论”论文中提出的， 简称shannon定 理1。shannon 定理明确的提出对于任何一个有扰信道都会存在一个确定的信道容量 c，当 信息传输数率小于此信道容量， 就会存在一种编码方法在码长趋于无限长的条件下， 那么译 码错误概率将会趋于零。 自香农信息论建立之后， 人们利用代数中的一些理论构造了许多的纠错码， 并研究了与 之相关的译码方法。这些纠错码可以分为两大类：线性分组码和卷积码，但在实际应用中这 两大类码字大多采用短码，因其译码复杂度与码长成指数关系，随着码长的增加，译码的复 杂度增速非常快， 所以这些码均不能逼近香农限的目标， 于是人们设想是否能够在短码的基 础上构造出长码， 通过短码的级联或乘积得到的长码， 在提高编码性能的同时也降低了译码 的复杂度23。 “1962 年gallager4在中描述了一种编码方法，这种编码方法因为校验矩阵的稀疏性， 使得译码复杂度与码长成线性的关系， 在较长码长时仍然得可以有效的译码。 但是在当时人 们一致认为级联码可以更加容易的实现以及那个年代技术条件的种种限制， 人们忽视了这种 编码方法。在八十年代与九十年代初，c.berrou 等人在级联码和卷积码的理论基础上提出 turbo 码，这在信道编码理论和应用中取得了突破性的进展。这种编码方案在码长较长的时 候逼近香农定理的极限，且译码的复杂度相对可以接受。 “通过 turbo 码获得的成功启示， 另外一种具有相似性能编码与特征的方案复活了， 它就是ldpc （low-density-parity-check） 码。ldpc码是由gallager码的发展过来的，由d.j.c.mackay2、m.neal3和n.wicvbgberg4 通过对gallager码的深入的分析，研究表明gallager码的性能与turbo码相对比有一定的差 距，但是他们都具有逼近香农限的性能。他们进一步研究的多元域 gallager 码与二元域的 gallager 码相比性能上有很大的提高且域的阶数越高编码的性能就越好，由此提出了非正则 的ldpc码， 其编码性能能够赶上甚至超过了turbo码的性能5。 ldpc码的译码算法与turbo 码的译码算法相似是一种并行的迭代译码算法”6。 1.2 ldpc 码的发展和研究现状 在当前ldpc码在编码方面面临较高的编码复杂度与编码延时的问题。 ldpc码具有二 次方的编码复杂度，运算量会大大增加，如果码长在较长的情况下是难以承受的。当前人们 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 3 对ldpc码编码的主要研究方向就是将原始的二进制推广到多进制。luby，mitzenmacher， shokrollahi和spielman等人发现非正则的ldpc码与正则的ldpc码相比可以得到更好的性 能。北京邮电大学杨大成教授提出的“关于非正则ldpc码基于度分布的harq性能研究”在 编码时在考虑节点度的分布影响同时又考虑到码字自身不均等的错误保护性能， 在误比特率 和吞吐量指标上有明显的改进。 在ldpc码译码方面，现在的主要的研究方向是mackay和neal提出的bp45（believe _propagation）迭代译码算法及其改进的最小和译码算法。j.-h. kim, m.-y. nam and h.-y. song提出的“variable-to-check residual belief propagation for ldpc codes”是一种利用节点间 残余信息动态调度的置信传播算法， 有着译码速度快， 误码率性能优良， 复杂度较低的优点。 清华大学王京教授提出的“基于ldpc码校验节点度的分类修正最小和译码算法”是根据外 信息绝对值的最小值和次小值分类，由该节点度计算与bp算法偏移量来选择不同阀值和修 正因子，从而能够更好的实现性能与硬件实现的平衡。 ldpc码相对于turbo码来说尽管有很多的优势但它也不是完美的，ldpc码有待解决 的问题如下： 1、ldpc 码编码复杂度有待降低。最新研究表明，尽管 ldpc 码能够在线性时间内编 码，但编码复杂度相对于turbo码仍然繁琐。 2、中短码长的 ldpc 码性能不理想。ldpc 码的优越性表现在码长较长时，中短长度 的ldpc码编码时短长度闭合环路的存在会降低译码性能。 3、ldpc 码译码器为完全并行结构的时候，虽然译码速率非常的高，但硬件消耗资源 太大， 在实际应用中可行的方案是采取部分并行译码结构。 目前， 适应于部分译码结构ldpc 码的构造方法还不完善。 1.3 论文的各章节的安排 本文中各章节的安排如下: 第一章介绍了本课题的研究背景以及与内容相关的现阶段ldpc码的研究现状， 并对现 阶段ldpc码有待解决的问题进行了概括。 第二章从描述 ldpc 码的定义入手，介绍了 ldpc 码的理论基础及有利于译码性能的 三种构造方法和两种编码算法，并分析了构造方法和编码算法各自的优缺点。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 4 第三章主要讨论了 ldpc 码的各种译码算法，并通过仿真实验得出了不同配置参数对 ldpc译码性能的影响，确定了分层最小和译码算法作为硬件实现的选择。 第四章以fpga为硬件实现平台， 利用verilog hdl语言编程设计， 采用模块设计方法， 实现了译码器的各个功能模块，并对仿真结果作详细的分析。 第五章对全文的工作进行了总结以及提出了进一步的研究方向。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 5 2 ldpc码的构造方法与编码算法 ldpc码是一种基于稀疏校验矩阵h的线性分组码， 有很多的学者对其编码问题进行了 研究。相对于turbo码来说，ldpc码的优势在于其译码硬件实现的复杂度较低，但其编码 复杂度要比turbo码高很多。 根据校验矩阵h的不同特点， ldpc码可以分为正规ldpc码 和非正规ldpc 码。本文中主要以正规 ldpc 码为研究对象，文中讨论的ldpc 码均指的 是正规ldpc码，对于非正规ldpc码会特别指出。 本文中的编码方法是thomas j.richardson与rudiger l.urbanke提出的ru算法7， 讨论 了ru快速编码算法在保持良好译码性能的前提下大大减少了编码的复杂度， 具有广阔的工 程应用价值。 这种编码算法只是仅对校验矩阵进行重排的预处理， 这使得编码时间复杂度在 多数情况下相对可控，甚至具有线性特点8。 2.1 ldpc 码的定义及相关知识 （1）行重：校验矩阵的一行中非零元的个数，记为。 （2）列重：校验矩阵的一列中非零元的个数，记为。 （3）校验矩阵：一个二进制的线性分组码( , ) n k的校验矩阵h可以表示为 1,11,21,0 2,12,22,0 ,1,2,0 . . . . . . . . . . nn nn n k nn k nn k hhh hhh h hhh = （2-1） 码字 011 ,., n cc cc = 的线性方程组可以表示为0 t hc=。 （4）矩阵密度：矩阵h 中元素“1”的个数与矩阵所有元素的个数之比称作矩阵h 的密 度。 （5） 正规ldpc码： 校验矩阵h 中每行的“1”的个数相等， 每列的“1”的个数相等的ldpc 码为正规ldpc码。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 6 2.1.1 ldpc码的定义 ldpc码是一种线性分组码， 其校验矩阵h 中元素“1”的个数大大于元素“0”的个数， 即 其校验矩阵h 具有稀疏性。一个码长为n与信息位个数为k的线性分组码可以由一个生成 矩阵 k n g 来定义，信息序列1k m通过g映射成发送序列即码字cm g= 。线性分组码也可 以有一个一致校验矩阵h 来描述，所有的码字都满足0 t hc=。正规ldpc码的定义是由 gallage最早提出，具体来说ldpc码的校验矩阵h满足以下三个条件： 1. h 的每一行有个“1”； 2. h 的每一列有个“1”，且3（gallage证明当3时，ldpc码具有很好的汉明 距离特性） ； 3. 与码长n和h 矩阵的行数相比，和都很小； 2.1.2 ldpc码的校验矩阵 设( , , )n 表示一个ldpc码，其中n代表码长，与表示校验矩阵的行重和列重。 码字中每个比特位都参与了个校验等式的检验， 每个校验等式包含了码字中个不同的比 特位，其校验等式的个数为:()/mn=。 h 是满秩时的编码效率 ()/1/rnmn = 。假设我们希望得到的码率为r，当 与m个校验等式相关时（即() m n rank hm ） ，这样得到的码率()/rnrank hn=，高 于我们希望得到的码率r。 例2.1 ldpc码的校验矩阵(20,3,4)h如下图所示： 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 7 图2-1 ldpc码的校验矩阵(20,3,4)h 该校验矩阵中每列有3个“1”，每行中有4个“1”，共有20*3/4=15行，即有15个校验等 式，ldpc码(20,3,4)的任何一个码字c都必须满足0 t hc=。 2.1.3 ldpc码的生成矩阵 ldpc码的生成过程可以描述为一个信息矢量和一个矩阵相乘的结果：cm g=，其 中g是由k个n维矢量 0123,1 ,., k gg ggg 构成的矩阵，m是信息序列分组 0123,1 ,., k m m m mm ，c是n维编码输出 0123,1 ,., n c c c cc ，其中信息矢量和矩阵是在 二元域(2)gf上进行的，根据（2-1）式，码字c的表示为： 0000101 , ., kk cmgmgmg =+ （2-2） 则矩阵g称为编码生成矩阵，其形式为： 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 8 0,00,10,1 0 1,01,11,11 11,01,11,1 . . . . . . . . . . n n kkkkn ggg g gggg g gggg = （2-3） 例2.2对于一个二元(7,3)线性分组码，其生成矩阵可以表示为： 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 1 1 0 1 g = （2-4） 如果编码信息矢量为001m =，则得到的码字 1 0 0 1 1 1 0 0 0 10 1 0 0 1 1 10 0 1 1 1 0 1 0 0 1 1 1 0 1 cm g = （2-5） 表2-1 2.2 ldpc 码的二分图表示方法 ldpc码的二分图又称tanner图最早是由tanner在1981年提出的910， 其校验矩阵h 信息序列分组m 码字 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 1 0 0 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 9 的特殊规律性是可以由二分图表示的。 将图中顶点可以分为两个集合， 在这两个子集中各个 顶点之间没有边相连，任意一个顶点都要和另一个子集中的顶点相连。ldpc码的二分图可 以分为两组不同类型的结点：变量节点（variable node）和校验节点（check node） ，分别对 应的是校验矩阵h中的n列和m行。 在已经知道ldpc码校验矩阵的情况下， 其二分图可 以这样画出来9： 假定校验矩阵中的某一个元素为1 ji h=， 则校验节点j与变量节点i可以 用无向线段连接，校验矩阵中其他元素1 ji h= 都做同样的处理。 例2.2 设一个ldpc码的校验矩阵(12,3,6)h如下， 1 1 1 0 0 1 1 0 0 0 1 0 1 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 1 1 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 1 0 1 1 1 0 0 0 0 0 1 0 1 1 0 0 1 1 1 0 h = （2-6） 1236711 1234512 678101112 14891012 245789 35691011 0 0 0 0 0 0 vvvvvv vvvvvv vvvvvv vvvvvv vvvvvv vvvvvv = = = = = = （2-7） (12,3,6)h 对应的tanner图如（2-2）所示，图中有12变量节点 1212 ,.v vv ，6校验 节点 126 ,.c cc 。tanner中的边代表变量节点与校验节点之间的联系， 只有当变量包含于 某个校验等式的时候，对应的变量节点与校验节点之间才会存在边。这样我们就可以得知， tanner图中边的条数与校验矩阵h中非零元的个数是相等的。在包含边与节点的一个图形 中，节点次数的分布很大程度上决定了该图形的一些基本的性质。 图2-2 (12,3,6)h 对应的tanner图 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 10 “在tanner图结构当中，由四条粗连线组成了一个有向的闭合回路，由 1 v开始，最后 又返回 1 v，长度为4。在ldpc码的编码tanner图中，会存在很多这样的闭合回路，其中最 短的闭合回路的长度称为最小环()girth，例2.2中tanner图中的最小环为4。从tanner图 中我们可以显然看出，对校验矩阵h作行或列的简单的交换，这样不会改变对应的tanner 图结构和最小环的分布。 造校验矩阵被我们按照某种规则构， 在化成生成矩阵之时可能存在 冗余的行或应该交换列的情况。在这时我们交换校验矩阵h的部分行列的顺序，得到符合 条件的新的校验矩阵 h，tanner图结构是相同可以构造出相应的生成矩阵”15。 “ldpc码的tanner图中闭合回路的分布以及最小环的大小对译码性能有着很大的影 响。tanner图在9中证明，ldpc码tanner图结构最小环的大小决定了该码字的最小码间距 的上界。我们设置ldpc码tanner图的最小环是4，这样的得到的ldpc码误码率性能可 能很差。 在下图中2-2中有一个最小环是4的闭合回路用粗线来表示。 假如图中的 1612 ,v v v3 个信息比特出现错误， 则它相关的 12346 ,c c c c c5个校验约束中， 仅有 6 c可以检测出发 生错误。 这样三个错误的检测要从一个错误校验约束是比较困难的。 设某一个度为6的tanner 图，如图（2-3）所示”12： 图2-3 某个度为6的tanner图 如果某个码字取值为1010，当这4个信息比特取反变为0101时，所有校验约束仍然满 足， 但这么小的码距会使编码的性能非常差。 这样我们可以得到构造ldpc码校验矩阵的时 候应该避免tanner出现最小环是4的情况，并且使得度较小的闭合回路的数目尽可能的少。 迭代译码算法是ldpc码的主要译码算法， 如果迭代次数很多， 有一些节点有闭合回路， 信息可能被重复更新， 信息到达这些节点的时候将不会再满足统计独立的特性。 即便tanner 图中存在这样的闭合回路，如果最小环大于4，那么ldpc码的译码性能仍满会比较令人满 意。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 11 2.3 正规 ldpc 码与非正规 ldpc 码 根据tanner图的分布可以将ldpc码分为正规ldpc码和非正规ldpc码11。正规 ldpc码对应着正规tanner图，非正规ldpc码对应非正规tanner图。正规ldpc码是 gallager最初定义的ldpc码4，其校验矩阵的列重、行重是一个固定的常数，码率为 1/r = 。 由于正规ldpc码校验矩阵的行重和列重保持固定， 所以校验矩阵中“1”个数 随着码长的增加而呈线性增长， 校验矩阵元素的总个数呈平方增长， 这样的规定限制了编码 性能的提高4。如果允许校验矩阵中的行重或列重发生变化，同时保持校验矩阵的稀疏性， 编码与译码算法同样适用， 并能使编码性能得到极大提高， 因为这种编码使得对应的tanner 图中变量节点和校验节点有合适的次数分布，这就是非正规ldpc码。非正规ldpc码对 应的tanner图中变量节点或校验节点的度不同，通常用序列 12 ,., k 与 12 ,., j 来表示边的度分布， 其中 m 表示与度为m的变量节点相连的边占总边数的比例， n 表示与 度为n的校验节点相连的边占总边数的比例。k与j分别表示变量节点与校验节点最大的度 数，于是有： 1 1 k m m = = ， 1 1 j n n = = （2-8） 边的度分布序列可以用以下多项式来表示： 1 1 ( ) k m m m xx = =， 1 1 ( ) j n n n xx = = （2-9） 此时，码率r满足： 11 00 1( )/( )rx dxx dx= ，当校验矩阵不满秩时，实际码率要 比r略高。显而易见，非正规ldpc码要比正规ldpc码性能更加优越，因为对应每个变 量节点度数越大越好，可以从相关联的校验节点得到更多的信息，更能准确的判定正确值。 对于校验节点来说度数越小越好， 这样反馈给与其关联变量节点的信息越有价值。 对于非正 规ldpc码的总度数是一定的， 度数较大的变量节点从相关校验节点中得到的信息较多， 能 够很快的被译码得到正确值， 这样反馈给校验节点更加正确的概率信息， 从而使得度数较小 的变量节点的信息更好的被正确译码1238。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 12 2.4 ldpc 码的构造方法 构造ldpc码的关键在于校验矩阵， 只要校验矩阵确定了， 编码也就可以确定。 文献中 给出了很多的构造与设计的方法，本节中简要概述最著名的几种。根据达到目的的不同（如 高效率的编译码，低误码率性能等） ，不同的构造方法遵从不同的标准。总的来讲，关键就 是构造出没有短长度的闭合回路或闭合回路的平均长度尽可能大的校验矩阵。 2.4.1 gallager 的构造方法 在文献411中，gallager提出利用简单稀疏校验矩阵的随机置换和级联来模拟随机码， 简单概述为：由确定的方式构造出一个矩阵（例如单位矩阵） ，再将该矩阵所有列作随机的 排列组合之后生成一系列规则的子矩阵， 再将这些规则的子矩阵组合成需要的矩阵。 假设构 造出列重为，行重为的校验矩阵h，gallager将其分为大小相等的子矩阵 123 (,.,)th hhh，每个子矩阵的行重为，列重为1。 23 ,.,hhh都是通过对 1 h所 有列作随机排列组合而成。 设 1123 ,.,he e ee=，其中 1 1 0 .0 0 1 .0 0 .0 0 .1 e= （2-10） 1 21 1 () . . . () h h h h = （2-11） 1 h为校验矩阵h的第一个子矩阵， 1 ()h为 1 h的随机列置换。 利用这种规则构造出的 校验矩阵可以保证固定的行重和列重，其最大优势在于1是随机产生的，保证了ldpc码 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 13 的优越性能，但在构造中短码的时候，编码tanner图中会出现较短的闭合回路。随着码长 的增加，这种较短闭合回路出现的几率很小。tanner等人在1981年总结了这种构造ldpc 码校验矩阵的方法，之后几年mackay等人又对这种方法进行了改进56。 2.4.2 mackay的构造方法 gallager的构造方法610，在构造中短码的时候会出现girth为4的闭合回路，将会影响 ldpc码的译码性能。mackay提出的构造方法使得girth为4的闭合回路不存在，其构造方 法如下： 构造方法之一：固定行重，随机产生列重为的列，要求此列重尽可能的接近。 构造方法之二：列重固定为，行重尽可能的保持为，同时任意两列之间交叠1的个 数不超过1个。 构造方法三：在方法二的基础上，去除较短的闭合回路。 构造方法四：在方法三的基础上，保证校验矩阵h满秩。 2.4.3 peg（progressive edge_growth）构造方法 从理论上讲，码长趋于无穷时采用最优译码器，正规ldpc码的性能能够逼近香农限， 但码长太长最优译码的复杂度太高，无法实际应用14。xiao-yu hu提出了一种peg（progr es-sive edge_growth）构造方法。这种构造方法使得变量节点的围长（从某一变量节点出发 又回到该变量节点所经历的最小边数） 最大， 构造的中短码是目前具有相同参数最好的码之 一151617。 非正规ldpc码和正规ldpc码都可以通过tanner图来表示。 设变量节点度为i的个数 为 i ，校验节点度为j的个数为 j ，记码长为n非正规ldpc码的码率为r，则有： i i n=，(1) j j nr= 根据tanner图可得： ij ij ij= 根据变量节点度的分布序列 i 与校验节点度的分布序列 j ，可得多项式： ( ) i i i xix=，( ) j j j xjx= 由上式 可得( )1n=，( )()11nr=，码率( )( )11 /1r= ，对( )x与( )x求 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 14 导可得：( ) 1i i i xix =，( ) 1j j j xjx =。令1x =，( )( ) 11=总边数 再从边的角度考虑， 记 i 为与度为i的变量节点相连的边的个数占总边数的比例， j 为 与度为j的校验节点相连的边的个数占总边数的比例，可得： ( ) 1i i i xx = （2-12） ( ) 1j j j xx = （2-13） ( )( )( ) /1xx= （2-14） ( )( )( ) /1xx= （2-15） peg构造方法是通过预先计算得到的变量节点与校验节点在tanner图中的重量而获得 的16。在预知( )x与( )x的基础上，构建出一个采用迭代边到边的方法增大局域环长的 图。无论正规ldpc码和非正规ldpc码都可以采用这种方法制图，主要取决于重量的分 布。 记ldpc码n个变量节点的集合 011 ,., vn vv vv =，m个校验节点集合 011 ,., cm vc cc =，(),v e表示tanner图，v为节点集合，e为边的集合，变量节点度序 列为 01(1) ,., vvvv n dddd =，其中 vj d是变量节点 j v的度，校验节点度序列为 01(1) ,., cccc n dddd =，其中 cj d是校验节点 j c的度。 2.5 ldpc 码的编码 尽管ldpc码有着良好的译码性能， 但其编码面临着复杂度高和时延问题。 如果采用直 接编码的形式，将会有二次方的复杂度，当码长较长的时候令人无法接受，而校验矩阵的稀 疏性决定了使其线性编码成为可能39。 2.5.1 基于高斯消去直接编码算法 我们一般采取基于校验矩阵 m n h 的高斯消去进行ldpc码的编码，对应的码字c，则 满足0 t m n hc =。 编码时的信息序列为 12 ,., n m mm mm =， 将 m n h 经过高斯消去得 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 15 到等价的下三角形式，然后再经过初等变换得到右边为单位矩阵形式|hp i=,（p为 ()mnm维矩阵，i为mm维满秩矩阵）生成矩阵| t gi p= ，码字cm g=直 接编码。 高斯消去的具体步骤： 1设 h=h，整数1i = 。 2 将 h第i行的第一个1所在的列移动到第i列， 假如第i行的所有元素都为0， 则1i+ 后重新执行第（2）步，当im时结束，另h作同样的调整。 3假如该列中还有其他不为0的元素，那么将该元素所在的行与第i相加，然后1i+， 重新执行步骤（2）19。 行的变化只能改变校验时候的秩序，并没有改变码字的结构。列的变化反映在tanner 图上只能改变变量节点的分布次序，此时产生的码字就是满足经过初等变换后的校验矩阵 h，当将编码输出后的码字位置还原，仍然受原校验矩阵的监督。 图2-5 ldpc码校验矩阵下三角形式 此时的校验矩阵 h一般都不是稀疏的，将此时的n维向量分为两个部分：信息位s和 校验位p， 12 ,., n m ss ss =与 12 ,., m pp pp=分别为nm维与m维，则产生系统 码的步骤如下42： 任意设置nm维信息比特， 得到第一位校验比特 11, 1 n m jj j phs = = （2-16） 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 16 根据下三角矩阵递推的方法可得其他的校验位比特 1 , 11 n mi ii jji j n mj ij phshp + = =+ （2-17） 这样编码方法的复杂度大约是 2 ()o n。 2.5.2 ru快速编码算法 上述我们讨论了基于高斯消去编码算法， 经过一系列的初等变换， 很可能破坏了校验矩 阵的稀疏性，其复杂度大约是 2 ()o n，为了较好的利用校验矩阵的稀疏性能，t.j.richardson 与r.l.urbanke在文献910中提出了对校验矩阵进行一定的预处理，得到近似下三角的结构 的矩阵， 利用下三角系数方程可以在线性时间内求解的特点， 经过适当的处理就可以实现在 线性时间编码。这种方法称为ru算法，其核心思想就是利用校验矩阵的稀疏性减少编码的 复杂度36。 下面我们讨论一下ru编码算法的步骤： 首先对校验矩阵行或列做重新排列得到一个近 似下三角的矩阵,如图2-6所示， 这种转换称为校验矩阵的近似三角化。 把校验矩阵分为六个 部分：a,b,t,c,d,e,其中a是() ()mgnm维矩阵，b是()mgg维矩阵，t是 () ()mgmg维矩阵，c是()gnm维矩阵，d是gg维矩阵，e是()gmg 维矩阵，t为下三角矩阵，从左上到右下对角线上的元素都是1。校验矩阵的三角化并没有 改变校验矩阵的稀疏性， 因为其六个部分的小矩阵仍然保持着稀疏性， 这就是保证了低复杂 度编码的前提条件32。将校验矩阵h左乘 1 0i eti ,则得： 111 0 0 iabt h etietacet bd = + （2-18） 得到了这样的校验矩阵 11 0 abt h etacet bd = + （2-19） 设码字 12 ,cm p p=，其中m为信息比特， 1 p与 2 p合起来为校验部分，两者的长度分别 为g与mg。因0 t hc=，并定义 1 et bd = +， 1 p与 2 p得计算过程如下表所示： 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 17 表2-1 表2-2 图2-6 ldpc码校验矩阵近似下三角形式 由表可得采用ru算法，编码的复杂度为( ) 2 o ng+，要进一步降低其复杂度必须使得 g尽量很小，可能使编码大约在线性复杂度。 运算操作 备注说明 复杂度 t ac 与稀疏矩阵相乘 ()o n 1t tac 1tttt tacact = = ()o n 1t e tac 与稀疏矩阵相乘 ()o n t cc 与稀疏矩阵相乘 ()o n 1tt etaccc + 矩阵相加 ()o n 11tt etaccc + g g非稀疏矩阵相乘 () 2 o g 运算操作 备注说明 复杂度 t ac 与稀疏矩阵相乘 () o n 1 t bp 与稀疏矩阵相乘 ()o n 1 tt acbp+ 矩阵相加 ()o n 1 1 tt tacbp + 1 11 tttttt tacbpacbpt += += ()o n 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 18 对于一个长