（信号与信息处理专业论文）一种新式ldpc码编译码研究及编码的硬件实现.pdf

i 摘 要 ldpc 码是一种线性分组码，线性分组码的编码是通过生成矩阵得到的，虽然 ldpc 码的 校验矩阵是稀疏校验矩阵，但是它的生成矩阵却并不是稀疏的，使得编码复杂度与码长的平方 成正比，由于 ldpc 码的码长很长，从几千到几十万比特，编码因此会变得很复杂，进而阻碍 了ldpc 码的应用。本文主要对ldpc 码的编码进行研究及硬件实现，在此基础上，对相关译 码进行研究。 由于ldpc码本身具有较强的抗突发差错的特性以及其译码算法能够实现完全并行的操作， 使得 ldpc 码在信道较差的无线移动通信环境中拥有极其广泛的应用前景，适合于在未来的移 动通信系统中实现。ldpc码具有强大的应用潜力，会广泛地应用于光纤通信、卫星通信、无线 通信、电缆调制/解调器以及数字用户环线（dsl）中。 本文首先介绍了 ldpc 码的基本原理，包括ldpc 码的表示、构造原理、编码方法及译码 算法。在编码方法方面详细地讨论了传统的编码算法，然后介绍了一种新型的ldpc编码算法， 此种编码算法与传统方法相比，大大降低了编码复杂度，计算量显著下降。仿真结果表明其误 码率得到了很大改善，且仿真时间大大缩短。在译码算法部分主要介绍了译码性能优良的和积 译码算法的基本原理，并将其运用到图像传输系统中，同时对三种译码算法的仿真结果进行了 比较，最后，以cyclone 系列的ep2c35f484c8芯片为硬件平台，并且使用quartus ii开发工 具， 采用verilog语言在现场可编程门阵列(fpga)上实现了ldpc码编码器的硬件设计及结构实 现，给出了编码器实现的整体结构图，对各个模块的功能和实现做了详尽的说明 关键词：ldpc 码；和积译码算法；verilog；fpga ii abstract ldpc code is a linear block code, the encoding of linear block code is obtained from generated matrices. although the parity check matrix of ldpc code is the sparse matrix, its generated matrix is not sparse, then the encoding complexity is proportional to the square of the code length. since the code length of ldpc is very long, from a few thousand to hundreds of thousands of bits, the encoding becomes complicated, which hinders the application of ldpc codes. the article will discuss the encoding of ldpc codes. ldpc codes have strong anti-burst error properties, and their decoding algorithm are able to achieve with fully parallel operation, which make ldpc codes have a wide range of application in the wireless mobile communication environment, they are suitable to achieve in the future mobile communication systems. ldpc codes have a powerful applicated potential, which will be widely used in optical fiber communications、statellited communications、wireless communications、cable modem and dsl. this paper first introduces the basic principles of ldpc codes, including the expression of ldpc code、the principle of structure、encoding method and decoding algorithm. in the encoding part we discuss the traditional encoding algorithm, then introduce an improved encoding algorithm, which greatly reduce the encoding complexity, the simulation show that its ber has improved, it takes less time to simulate. in the decoding part we mainly introduce the basic principle of sum-product algorithm, which is applied to image transmission system, then we compared the simulation results of three kinds of decoding algorithm. finally, we use the quartus ii development tool and make the ep2c35f484c8 chip of cyclone series as hardware platform , and achieve the encoding hardware implementation of ldpc using verilog language，and give the overall structure of the encoder, making a detailed description of each module. keywords: ldpc codes，spa，verilog，fpga 1 1 绪论 1.1 课题背景 踏入 21 世纪以来，我国的移动通信技术正以一种前所未有的速度突飞猛进地向前发 展。在国家“863”计划的大力支持之下，对“第四代”移动通信技术的研究正轰轰烈烈 地展开。而对高速带宽传输系统的研究是以后研究工作的主题，因此系统的设计应当着眼 于更高的传输效率、更大的容量以及更可靠的传输性能和质量。 在无线移动通信信道中，对高速信息流有着更高的要求，因此在信息进行传输时，其 可靠性的设计面临着更加严峻的挑战。 长时期以来，人类交互信息的基本方式不外乎于文字、语言和图像。19世纪中期，电 报的发明开创了人类运用电子技术传输文字的新纪元。直到 20 世纪末期，有线电话网、 无线电话网、有线电视网、无线电视网依然是图像和语言的主要传输途径，而因特网则是 最主要的文字传输媒体。伴随着数字技术的发展，三大信息网络逐渐融为一体，在世界范 围内进行信息的实时交互已经不再是梦想，并且人们对信息质量和数量的需求日益增长， 更加可靠、有效、高速、安全地传输信息成为人们日益关注的问题。 在数字通信1,2,3的过程中，编码是必不可缺的环节。电报的出现使符号和文字的编码 问题提上了日程，伴随着现代通信技术的迅猛发展，编码也彰显出强大的实力。人们为了 用更短的码表达更多的信息提出压缩代码长度的方法， 同时发明的多种实施方案和压缩方 法统称为信源编码。为了能够及时发现并且纠正信息传输过程中的错误，各种检错和纠错 技术应运而生，信道编码技术由此发展起来，于是通信更加安全可靠。 编码4，实际上就是一种数学映射，通过数学关系的设定，用另外一套编码替换原来 2 的代码。同样信道编码也是用另外一套代码替换原来传输代码的数学变换，或是在原来欲 传输的码流中计划性的插入新的代码从而构成新的码流。 这种替换或者插入按照某种预设 的数学规律进行，因此在接收端能够通过预设的规律判断传输是否有误，甚至于进行自动 纠错找回正确的代码。由于采用信道编码能够使误码率大大下降，因此几乎所有的数字通 信系统中都广泛地使用着信道编码。 在总结了编码理论和通信技术百年成果的基础上，1948 年5香农（shannon）科学地 给信息下了个定义， 并用数学理论证明有噪信道中通过信道编码进行无失真传输的可能性 与必要条件，给出了无失真信源编码的极限码长，创立了信息理论。沿着这条路，经过了 半个多世纪，通信技术取得了日新月异的进步与发展，编码的创新与改进更是层出不穷， 香农的信息理论也得到了人们的空前重视。 在香农编码的正确指引之下，许多接近shannon限的编码被研究出来并得以广泛地应 用。从最初的分组码、rs码6、卷积码7到现在的turbo码8,9、低密度奇偶校验码（low density parity check codes,即ldpc码），码的性能越来越好。 作为一种新型的编码ldpc码是一种性能更加接近shannon限、 译码复杂度低并且纠 错能力强的编码。 在本文中我们提出了一种新式的ldpc码， 实用性很强、 编码复杂度低。 ldpc码作为一种线性纠错编码，它的重现在编码界掀起了一个新的研究热潮。众所 周知， gallager早期提出的ldpc码是规则ldpc码， 即校验矩阵h每行非零元素的个数 相同，每列非零元素的个数也是相同的。随着理论研究的不断深入，关于ldpc码的各种 构造方法不断地涌现出来。 1998年， luby等人把ldpc码的概念加以推广， 不规则ldpc 码得以提出，并且其在性能方面优于规则 ldpc 码。到了 1999 年，richardson 等人发现 了在码长足够长时， awgn信道下的不规则ldpc码的性能与香农限差0.13db10。 在2000 年， chung在awgn信道下对码长为 7 10 bit， 码率为0.5的二元ldpc码做了仿真， 结果 发现其性能与香农限仅差0.01db11。 于是在2001年之后， 人们便开始把目光转移到ldpc 3 码与其他通信技术结合的问题上。 1.2 低密度校验码（ldpc 码）的提出及发展 伴随着移动通信技术的发展，人们对纠错码的要求也越来越高。尽管turbo码已经成 为3g的信道标准编码，但是其译码复杂度很高，时延太长等缺点，使之很难适应“第四 代”移动通信技术的需求。ldpc码是由gallager于1962年发现的基于稀疏校验矩阵h 的一类线性分组码，因此也被称为gallager码12。由于受当时的一些原因，在相当长的一 段时间内ldpc码几乎被人们遗忘了， 其中一个原因就是级联码13的提出， 人们当时普遍 认为级联码在任何方面都会比ldpc码取得更好的效果。 然而经历了几十年的沉寂， 随着 相关理论的发展，ldpc码被重新重视起来，并且证明采用置信传播（bp）迭代译码算法 14ldpc 码的性能逼近shannon限。ldpc码被重新发现是编码领域的一大进展。最近几 年，人们研究发现在莱斯（rice）信道下采用改进的bp译码算法ldpc码同样也具有着 优良的性能15，ldpc码从而受到越来越多的关注。 随着对ldpc码研究的深入， 人们也逐渐开启了ldpc码的实用化进程。 第二代数字 卫星电视广播（dvb-s2）采用了bch码和ldpc码级联方案16达到了高清数字标准。 ldpc码、turbo码一起作为无限城域网ieee802.16e17编码的备选方案， 使ldpc码编码 复杂度高的问题得以解决。dvb-s2、ieee802.16e开启了ldpc码实用化的进程， 相信随 着研究的进一步深入，ldpc码必将广泛地应用到各种通信系统当中。 1.3 ldpc 码的研究现状及意义 ldpc码作为一种线性分组纠错编码， 最初是由麻省理工学院的gallager在1962年提 出来的。在以后的30年里，ldpc码处于一种沉寂状态，一直等到二十世纪九十年代中 4 后期， （1996）neal和mackay重新将其带进了人们的视野。 后来由mackay、luby提出来了不规则ldpc码，urbank、richardson在ldpc码的 发展当中也发挥了不可忽略的作用，他们提出一种新式的编码算法，在编码方面大大减少 了用随机方法构造ldpc码时巨大的存储量和运算量。 kou、lin等运用确定性算法构造出性能优良的ldpc码，这类ldpc码通常是规则 的，尽管与随机构造的规则ldpc码相比，性能上有些许损失，但也是备受关注的。 彭立等研究了ldpc码的一种译码算法位翻转迭代译码算法， 此算法用软判决和 硬判决来实现，算法的复杂度低于置信传播算法的复杂度18。 叶芳等介绍了ldpc码的构造方法扩展比特填充算法， 此种算法的优越性体现在 它能够在低复杂度下构造出大围长的校验矩阵19。 贺玉成等介绍的基于置信传播的ldpc码快速迭代译码量化算法不仅能够降低计算的 复杂度，而且能够降低系统的存储容量，从而增强了ldpc码的实用性20。 工业领域对ldpc码的研究也在如火如荼的进行着，ldpc编译码的芯片已经问世。 例如，flarion公司推出的vertor-ldpc支持的码长可达50000， 迭代次数为10时译码器就 能达到10gbps的吞吐量，它的性能已经相当接近shannon限了，是大多数通信业务的最 佳选择。vocal technologies ltd 推出了ldpc/turbo不对称方案， 并将其运用于wlan， 可以达到实现节能的目的。 ldpc码还成为无线通信系统中信道编码的候选标准之一，如在ieee802.16e中， ldpc码和turbo共同成为编码调制的备选方案， 我国华为公司提出的候选校验矩阵h也 在其中，另外ldpc码还应用在我国的dtmb与cmmb标准中。 总而言之，ldpc码因其结构并行，编码译码器易于硬件实现的特点，广泛地应用于 光纤通信、移动无线通信、调制解调器、数字视频等误码率要求较高的场合，对ldpc码 5 的研究与应用已经成为编码领域中的一个热门焦点。 1.4 论文各个章节的安排 第1 章 阐述了ldpc 码的课题研究背景、提出以及发展、研究现状及意义、论文的 主要工作、以及论文各个章节的安排情况； 第2章 介绍了ldpc码的表示形式以及它的几种构造方法。其中在ldpc码的表示 形式当中，我们主要介绍了ldpc码的矩阵表示方法和tanner图表示方法；在ldpc码 的构造方法中，我们详细地介绍了gallager 构造法、mackay构造法以及几何构造法，并 对三种构造方法作了说明比较； 第3章 首先介绍了ldpc码的基于高斯消元法的传统编码算法， 之后研究了efficient 编码算法，由于前两种编码算法的复杂度高，不具有线性复杂度，因此在最后我们讨论了 一种结构优异的新式efts-ldpc线性复杂度编码，给出了efts-ldpc码的设计修改， 这种线性复杂度的ldpc码的行重列重可以灵活设计。efts-ldpc的编码过程可以在线 性时间内完成，这个过程相比其它编码方案不涉及任何矩阵乘法，编码时间大大缩短并且 具有线性复杂度； 第4章 首先对bp算法作了简单的介绍， 并在此基础上介绍了ldpc码的和积译码算 法(sum- product algorithm )、 对数域的和积译码算法， 以及其在awgn信道下的实现算法， 其次，给出了简化对数域的和积译码算法，最后，将efts-ldpc码与图像传输相结合， 通过图像传输的效果图来观测不同译码算法的效果，并在awgn信道中对这三种译码算 法作了仿真比较； 第5章 本章以cyclone 系列的ep2c35f484c8芯片为硬件平台， 并且使用quartus ii开发工具，用verilog语言编程的方法实现了ldpc码的编码器，给出了编码器实现的 6 整体结构图，主要包括串/并转换模块、编码模块、并/串转换模块和复用模块，对各个模 块的功能和实现做了详尽的说明。 对fpga的结构和功能做了简单的介绍， 并且对我们所 选用的器件做了详细的说明， 给出了fpga硬件设计的基本流程， 最后给出了ldpc码的 编码器的时序仿真并且给出了所消耗fpga的硬件资源； 第6章 对论文进行了简单的总结并对下一步工作进行了展望。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 7 2 ldpc码的基本原理 2.1 ldpc 码的表示 2.1.1 ldpc码的矩阵表示 gf(2)域上的ldpc码c是一种（n,k）线性分组码，码长为n，信息序列长度为k，可 由校验矩阵h唯一定义。h的维数为mn，每一行对应着一个校验方程，每一列对应着码 字的一位。 每行中非零元素的个数称为行重， 每列中非零元素的个数称为列重。 方程 （2-1） 是 一 个5 10的 校 验 矩 阵 及 其 对 应 的 校 验 方 程 ， 其 中 码 字 cccccccccccc=),( 10987654321 ，满足0= t ch。 =+ =+ =+ =+ =+ = 0 0 0 0 0 1101001000 1010100100 0110010010 0001110001 0000001111 10974 10863 9852 7651 4321 cccc cccc cccc cccc cccc h （2-1） ldpc码的命名来源于其校验矩阵是一种稀疏矩阵， 即矩阵当中非零元素的个数远远地 小于零元素的个数，或者矩阵的行重和列重与码长相比是很小的数。正是由于校验矩阵是 低密度矩阵，才能够构造出低复杂度、高性能的ldpc码。 2.1.2 ldpc码的tanner图表示 除了用校验矩阵表示 ldpc 码以外，还可以用双向的图模型表示 ldpc 码21,22，其中 tanner图23表示是比较方便的一种，可以形象地刻画ldpc码的编译码特性。tanner图是 一种双向图，可以用),(evg =表示，其中v是节点的集合， cb vvv=。对维数为m 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 8 n 的校验矩阵，),( 21nb bbbv=称为变量节点（或比特节点、左节点） ，对应校验矩 阵的列，同时对应码字中的位；),( 21mc cccv=是校验节点（check node，函数节点、 右节点） ，对应校验矩阵的行，也就是校验方程。e 是节点之间相连的边的集合， cb vve， 同类节点之间没有边相连， 只有在两类节点之间有边存在。 如果校验矩阵的 第i 行第j 列元素是非零的，则tanner 图的第j 个位节点与第i 个校验节点有一条边相 连，即当1= ij h时，节点 i c与 j b之间有一条边相连，边ebc ji ),(。与节点相连的边数目 称为节点的度（degree） ，从某个节点出发又回到此节点为一循环（cycle） ，所经过的边 的个数称为循环长度，其中最短循环的长度称为图g 的girth。校验矩阵的行重和列重与 节点的度一致， tanner图与校验矩阵一一对应。 上节的校验矩阵对应的tanner图如图2-1 所示，具有10 个变量节点和5 个校验节点，每个变量节点都有2 条边，每个校验节点都 有4条边。 1 c 2 c 9 b 8 b 7 b 5 b 3 b 10 b 5 c 4 c 3 c 1 b 6 b 4 b 2 b 边 校验节点 变量节点 图2-1 校验矩阵的tanner图表示 2.2 ldpc 码的构造 ldpc码是一种线性分组码， 可以把校验矩阵h看成ldpc码的等效描述， 可以这么 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 9 说只要完成校验矩阵的构造，ldpc码的构造也就完成了。 ldpc码构造方法有很多种，从事这方面的研究的人也很多，到目前为止ldpc码的 构造方法主要有图论法、 几何法等， 下面将对ldpc码构造方法的研究现状进行简单地介 绍。 yu kou、shu lin使用有限分析几何构造ldpc码，生成循环或准循环码字24 mackay等人把奇偶校验矩阵变成下三角形式25，虽然使编码具有线性复杂度，但是 会约束变量节点、校验节点以及校验矩阵的围长，从而导致性能下降，因此使ldpc码实 用的关键是在满足围长和次数约束的条件下实现线性时间编码。 sipser 等人用级联图的方法减少编码复杂度26。 这种方法的缺点是级联层的长度远远 小于编码码长，从而导致在相同的码长情况下性能相比标准ldpc码有所下降。 t j richardson等人提出重新排列稀疏校验矩阵的行或列， 得到准下三角结构的校验矩 阵，利用线性时间求解下三角系数线性方程，进行适当的处理便可以实现线性时间编码 27,28。 2.2.1 校验矩阵的随机构造方法 2.2.1.1 gallager的构造方法 gallager在1962年提出的论文中给出了规则ldpc码),(的构造方法29。 将码长为 n的),(规则ldpc码的校验矩阵h按照行水平分割成几个大小一致的子矩阵， 子矩阵 的每列只有一个“1” 。gallager 首先构造了这样一个子矩阵，在矩阵第s行上所有“1”都 分布在矩阵的第1) 1(+i到i列上，如下式（2-2）所示： 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 10 = 321l o 321l 321l 111 111 111 h （2-2） 令w是矩阵 h的列置换矩阵， 也就是), 2 , 1()( l=shws为 h的列置换矩阵。 因 此校验矩阵h构造如下： = )( )( )( 2 1 hw hw hw h m （2-3） 2.2.1.2 mackay 的构造方法 这种构造方法的核心思想是在ldpc码的校验矩阵中引入一些重量为2的列， 于是校 验矩阵h中“1”的数目减少，相对应的因子图的边数便会减少，从而因子图中环的数量也 相应地减少了，这样译码过程中信息不会被重复利用。然而重量为2的列会导致出现低重 量的码字，因此mackay给出了下列构造方法30。 方法1a：这是最基本的构造方法。方法要求固定列重为，行的重量尽可能保持相 同，同时任意两列之间重叠的“1”的个数不超过1。图2-2给出了一个按此方法构造的 ldpc码（3，6）码。 图2-2 构造方法 3 3 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 11 方法2a：在方法1a上做一些变动。将m行校验矩阵分成两块，第一块是前m/2列 m行，余下的为第二块。再把第一块分为两个子矩阵，每个子矩阵为 22 mm 的单位矩阵， 第二块按照方法1a构造。如图2-3所示。 图2-3构造方法 方法1b,2b：从1a、2a方法构造的矩阵中，删除使因子图出现短环的列，重新插入 随机产生的列，使因子图上不存在小于一定长度的环。 2.2.2校验矩阵的结构化构造几何构造法 几何构造法是在有限几何的基础上进行的，我们假设q为有t个点、s条直线的一个 有限几何，并且满足下面阐述的几个条件： （1） 任意一条直线上均有个点； （2） 任意的两个点之间仅有一条直线相连； （3） 每个点刚好在条直线上； （4） 两条直线不是平行就是相交在一点上。 具有上述结构的有限几何有两类， 即有限域上的欧式几何 （eg） 和射影几何(pg)30,31。 在gf(2)上构造了一个ts维矩阵 jiq hh , )1( =， 矩阵的每行与q中的直线相对应， 每 列与q中的一点相对应。矩阵每行的行重是 ，表明此行对应的直线上有个点；与此 3 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 12 类似，矩阵每列的列重是，表明此列对应的点分布在条直线上。用此种方法构造的校 验矩阵任意两行不会有超过一个的“1”出现在相同的列中，同理任意两列也不会有超过 一个的“1”出现在相同的行中。 )1( q h的密度为str/=，假如、相对于t、s 都很小的话， )1( q h就成为低密度矩阵，把 )1( q h作为一个校验矩阵，其零空间给出了一个码 长为t的ldpc码，该码的汉明距离至少是1+。 令 )1( q h的转置矩阵为 )2( q h,也就是 t qq hh )1()2( =,这样 )2( q h作为一个行重是列重是 的低密度校验矩阵， 其零空间同样也给出了一个码长为s的ldpc码，该码的汉明距离 至少是1+ 。 gallager 构造法、mackay构造法的校验矩阵都是随机生成的，尽管它们的纠错性能 好，但因校验矩阵的随机性而无法实现简单编码，同时其译码复杂度很高，从而使系统设 计变得很复杂；而结构化校验矩阵可以通过几何构造法生成，不会生成短循环，具有确定 的结构，生成的ldpc码是循环码或准循环码，能够实现线性时间编码，在硬件实现方面 要比随机结构的码容易得多。 除此之外， 还可以通过pg和eg来构造pg-ldpc码和eg-ldpc码32， 在这里我们 就不详细的讨论了。 2.3 本章小结 本章介绍了ldpc码的表示形式以及它的几种构造方法。 其中在ldpc码的表示形式 当中，我们主要介绍了ldpc码的两种常用的表示方法矩阵表示方法和tanner图表 示方法；在ldpc码的构造方法中，我们详细地介绍了gallager 构造法、mackay构造法 以及几何构造法，并对三种构造方法作了说明比较。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 13 3 ldpc码的编码研究 3.1 ldpc 码的传统编码算法 传统算法，即用高斯消元法直接编码。由于ldpc码是一种线性分组纠错码，因此其 传统编码算法类似于线性分组码， 必须算出其生成矩阵。 已知输入信息向量m其长度为k， nk 的生成矩阵g，很容易计算出码字c：gmc=。 已知校验矩阵h，假设其形式如下： 21c ch =，这里 2 c为mm的稀疏矩阵，如 果在二元域上为非奇异阵，那么g便可以很容易计算出来： = 1 1 2 cc i g k t （3-1） 这里， k i为k阶单位阵。如果在二元域上 2 c为奇异阵（rm 时，end。 3、 倘若该列中还存在着其它不为0的元素，就把此元素所在的行和第i行相加，再将i+1 返回到上一个步骤。 由此种方法得出的h，其前r列是线性独立的，从而可以求解出g。通常来说，如此 得到的生成矩阵g不是稀疏的，编码时的运算复杂度为)( 2 no。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 14 3.2 efficient 编码算法 efficient编码算法33,34，即近似于下三角矩阵的编码算法，它的核心思想是基于保持 矩阵的稀疏性，把矩阵化成近似下三角矩阵的形式，如图3-1所示： 图3-1 近似下三角形式 矩阵被划分成六个稀疏矩阵，其中a矩阵的大小为)()(mngm，b矩阵的大小 为ggm)(，t方阵的大小为)()(gmgm，c矩阵的大小为)(mng，d方阵 的大小为gg，e矩阵的大小为)(gmg，其中t为下三角方阵。 用矩阵 k k iet i 1 0 左乘稀疏矩阵h，得到： 111 0 0 h dbetcaet tba edc tba iet i k k = + = (3-2) 把码字c写成如下形式：),( 21 ppsc =，其中s为输入信息向量，长度为m的校验 位分成g与m-g两部分。因为0 = tt chhc，所以把（3-2）式代入得到： 0 21 =+ ttt tpbpas (3-3) 0)()( 1 11 =+ tt pdbetscaet (3-4) 由（3-3）式可以推出 )( 1 1 2 ttt asbptp+= 由（3-4）式可以推出 tt scaetp)( 11 1 += ，其中dbet+= 1 经过分析我们可以得到 1 p、 2 p的运算量分别为)( 2 gno+、)(no，因此要想简化ldpc 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 15 码的编码复杂度，就要使g尽可能的小，运算量才能保持在线性复杂度内。在下一节中， 我们将构造一种具有线性复杂度的新式efts-ldpc码，此码的编码时间与随机ldpc码 相比大大缩短，更重要的是其编码具有线性复杂度。 3.3 ldpc 码的新式编码方法具有线性复杂度的 efts-ldpc 码 本小节讨论了基本turbo结构的tanner图和大围长的规则ldpc码的编码方案， 这种 构造使我们能够灵活地选择像列重(2j)，行重k和任意围长g这样的参数。turbo结构 的低密度校验码（ts-ldpc）是规则ldpc码，它的tanner图由两棵树交织连接而成。 在ts-ldpc码的tanner图中不需要太多的更改和限制就能达到线性复杂度。仿真结果表 明在低信噪比时efts-ldpc码与随机ldpc码的误比特率性能相似，在高信噪比时 efts-ldpc码有较好的性能并且编码时间大大缩短。 结构化的规则ldpc码，ts-ldpc码可以通过选择合适的码长n 35用任意长的围长g 来设计。ts-ldpc码的特殊类型efts-ldpc码的tanner图结构采用文献36中的编码方 法（来获得线性复杂度） 。 下面我们首先简单介绍一下turbo码的编码结构。 3.3.1 turbo码的编码方法 turbo 码是并行级联卷积码pccc（parallel concatenated convolutional codes）当中的 一种 37。turbo 码编码器是由两个系统卷积码编码器（rsc）经过一个交织器并行连接构 成的，并且对编码后的校验位进行删余，产生码率不同的码字38。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 16 信息序列 u 编码器rsc1 删余 与 复用 编码器rsc2 交织器 xy1 y2u1 图 3-2 turbo码编码器的结构 图3-2所示的是一种典型结构的turbo码编码器框图。 其中 12 , n uu uu=l 为输入 的信息序列，经过交织器，形成新序列u1。u与u1被分别送到两个分量码编码器（rsc1 与rsc2）中，生成序列y1和y2。若想提高码率，则序列y1与y2需要删余，形成校验 序列y(y1和y2)。最后，校验y与未编码序列u经过复用调制后，生成了turbo编码后 序列x39。 3.3.2 ts-ldpc码 这里我们简单讨论一下ts-ldpc码的设计。 文献36中广泛地介绍了ts-ldpc码的设 计，如图3-3所示，ts-ldpc码由三部分构成：两颗重量均衡的树，表示成上树 u t和下 树 l t，用来连接 u t， l t的交织器i， u t的树叶节点是比特节点，而 l t的树叶节点是校 验节点。 u t， l t的层数由h给定保持不变，h应当是一个偶数，因为上树从一个校验节 点开始并且要求树叶节点是比特节点， 同理下树从一个比特节点开始并要求其树叶节点是 校验节点，这两棵树是以类似于turbo的方式成对出现的， u t， l t的树叶节点由许多边 缘连接在一起，如图3-3所示，这种连接 u t和 l t树叶节点的边缘就是交织器i。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 17 v u t l t c rinterleave 图3-3 ts-ldpc码的tanner图：4=h ，3=j，4=k 3.3.3 易于编码的ts-ldpc码（efts-ldpc） efts-ldpc码的tanner图来自于ts-ldpc码的tanner图， 与ts-ldpc码类似它包 含上树 u t下树 l t并由交织器i连接起来。这里对于efts-ldpc的上树 u t没有限制，可 以与标准ts-ldpc码的上树部分相同，efts-ldpc码的下树 l t受限制使它的比特节点 度数为2，除此之外， l t的根从比特节点到校验节点是变化的，如图3-4所示。 文献36中提出的方案对 l t根节点的度数没有任何限制， 如果我们假设下树 l t的所有 校验节点有相同的度数，下树 l t的比特节点为2的限制便不能实现。我们建议在创建 efts-ldpc下树 l t时， l t根（校验节点）的度数为 2 ) 1( h j 而 l t中其它校验节点的度 数均为) 1(k，j，k，h分别为列重，行重， l t的高度，比特节点的度数仍然保持为2。 首先我们建一个规则的ts-ldpc码， 然后根据创建的ts-ldpc码建立相应的efts-ldpc 码，efts-ldpc码的tanner图如图3-4所示，efts-ldpc码是不规则的，这些变化使 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 18 efts-ldpc码可以用线性复杂度编码。 u t l t rinterleave 1 c c 2 c 3 c 4 c 5 c 6 c 7 c 1 x 2 x 3 x 图3-4 efts-ldpc码 3.3.3.1 ts-ldpc码的线性复杂度编码 efts-ldpc码的编码可以用它们的tanner图解释， 因为ldpc码是由tanner图表示 的。为了达到线性复杂度编码，efts-ldpc码的tanner图中下树 l t的根首先可以消除， 校验节点可以消除是因为 l t中它的度数为 2 ) 1( h j 而其它校验节点有相同度数) 1(k并 且 l t的层数与 u t也是相同的，按照引理消除 l t的根不会改变树的基本结构，引理的具 体证明在文献37中给出。 引理1. l t根 （校验节点） 表示的奇偶校验方程是多余的， 可以从奇偶校验矩阵h中 删除而不会改变码的基本结构。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 19 3.3.3.2 efts-ldpc码的编码 efts-ldpc的编码是有步骤地完成的。首先上树 u t被编码，对 l t进行编码首先获 得信息比特然后通过奇偶校验方程计算校验位（例如校验位 1 x由奇偶校验方程 321 :1xxxc=得到） ，下一步，下树 l t基于交织器提供的信息进行编码。从图3-5中 可以看出 l t的所有比特节点代表校验位。 u t l t rinterleave 1 c 8 c 2 c 3 c 4 c 5 c 6 c 7 c 19 c 20 c 21 c 22 c 23 c 1 x 2 x 3 x 4 x 19 x 21 x 22 x 33 x 34 x 35 x 36 x 37 x 图3-5 文献36中efts-ldpc码的tanner图 令h代表 l t的层数， l t中每个比特节点x的度数都为2，比特节点x的值仅仅取决 于低层比特节点的值， 尤其是 l t的1h层比特节点的值仅仅基于 u t树叶节点的值。 因此， l t中比特的值可以从底层，层层计算。在给定层所有比特值都能计算出，也就是说通过 计算第)2(i层，第) 12(i层所有比特值都能计算出，编码过程持续到得知第二层的所有 比特值（第一层已有引理消除） ，用这种方式， l t中所有比特被编码，因此最后的码字是 上树编码比特与下树比特的结合。 3.3.4 计算的复杂性 正如以前的讨论， 通过对h进行gauss-jordan消除法得到的随机ldpc码的编码， 树 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 20 叶需要进行 2 n次运算。 现在让我们估计efts-ldpc编码方案的计算复杂度来弄清楚此方 案性能好的原因。令在第l个奇偶校验方程中获得的比特数量为 l k，ml2 , 1=。校验位 的值通过m个奇偶校验方程获得。需要进行)2( l k次异或运算同时运用第l层的奇偶校 验方程来确定一个校验比特， 因此，m个校验比特的获得需要进行 = m l l k 1 )2(次异或运算。 在m个奇偶校验方程中把比特的平均数表示为 = = m l l k m k 1 1 ，然后编码复杂度可以表示为 )2(kmo，对于有相同行重k的ldpc码，编码复杂度为)2(kmo，因此，很显然 efts-ldpc的编码过程可以在线性时间内完成，这个过程相比其它编码方案不涉及任何 矩阵乘法。 3.3.5 仿真和讨论 我们对efts-ldpc码的ber做了仿真，码的列重为j，行重为k，围长为g，码的 性能在awgn信道环境下测试，采用和积译码算法40。正如文献41中定义 )2(log10 2 10 resnr b =这里r代表码率。和积译码的最大迭代次数为30，这里 efts-ldpc码与（1688，3，8）ts-ldpc码一致，围长为8，列重为3，行重为8。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 21 图3-6 ber性能比较 图3-6是围长8=g的（1688，3，8）efts-ldpc码与（1688，1233）随机ldpc码 ber性能的比较。仿真结果表明efts-ldpc码编码的仿真时间比随机ldpc码少得多， 很显然efts-ldpc码在snr较高的情况下性能优于随机ldpc码，snr较低时二者有 相似的纠错性能。 3.4 本章小结 本章首先介绍了ldpc码的基于高斯消元法的传统编码算法， 之后研究了efficient编 码算法，它是一种近似于下三角矩阵的编码算法，由于前两种编码算法的复杂度高，不具 有线性复杂度， 因此在最后我们讨论了一种结构优异的新式efts-ldpc线性复杂度编码， 给出了efts-ldpc码的设计修改， 这种线性复杂度的ldpc码的行重列重可以灵活设计。 efts-ldpc的编码过程可以在线性时间内完成，这个过程相比其它编码方案不涉及任何 矩阵乘法，编码时间大大缩短并且具有线性复杂度。仿真结果表明efts-ldpc码编码的 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 22 仿真时间比随机ldpc码少得多，很显然efts-ldpc码在snr较高的情况下性能优于 随机ldpc码，snr较低时二者有相似的纠错性能。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 23 4 ldpc码的译码研究 本章首先对bp算法作了简单的介绍，并在此基础上介绍了ldpc码的和积译码算法 (sum- product algorithm )、对数域的和积译码算法，以及其在awgn信道下的实现算法， 其次，给出了简化对数域的和积译码算法，最后，在awgn信道中对这三种译码算法作 了仿真比较。 4.1 bp 算法 迭代译码算法在仿真过程中有着非常优越的性能， 置信传播算法是消息传递算法(mp) 的一种，各个节点之间相互传递的是概率信息，变量节点v向校验节点c传递信息的取值 依赖于v的观测值还有与v连接的校验节点(c除外)在上一轮迭代中传递给v的概率信息， 同样如此校验节点c向变量节点v传递信息的取值依赖于与c连接的变量节点(v除外)在上 一轮迭代中传递给c的概率信息。 4.2 ldpc 码的软判决译码算法和积译码算法 1、 和积译码算法概述 为了能够清楚的表达，我们定义如下符号： m(j): 和变量节点 j v连接的所有校验节点组成的集合； m(j)i: 除了校验节点 i c的m(j)； n(i): 和校验节点 i c连接的所有变量节点组成的集合； n(i)j: 除了变量节点 j v的n(i)； 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 24 ij q: 给定m(j)i校验集合提供信息的情况