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

烟台大学硕士学位论文 烟台大学硕士学位论文 i 摘要 低密度奇偶校验码（low-density parity-check codes，ldpc）是 1962 年由 gallager 提出的基于稀疏校验矩阵的一种线性分组码，它以其接近于香农限的出色 性能引起了通信领域的轰动，它是继 turbo 码之后在纠错码史上的又一重大飞跃， 且当前 ldpc 码极有可能被确定为第四代移动通信的纠错码编码方案，因此它已经成 为当今通信领域专家和学者的研究热点。 本文主要研究迭代译码算法， 针对影响通信性能的有效性和可靠性， 分别对 ldpc 码的硬判决算法和软判决算法进行了详尽的分析，并且找到了一种适于硬件实现的 译码算法算法。本文大致可分为理论分析和硬件设计两大层面： 理论研究方面，本文首先介绍了信道编码和 ldpc 码的背景知识，接着对 ldpc 码基本原理以及常用的构造方法和编码算法进行了讨论，重点对 ldpc 码的基于硬判 决和软判决的两大类迭代译码算法，分别在译码复杂度和误码率两方面进行了深入 剖析，文中介绍了一种通过减少迭代次数的方法来提高译码速度的译码算法，这种 算法适合应用于对时间要求比较严格的实时系统中。最后通过搭建 awgn 信道仿真平 台，分析了各种算法的性能差异和各种不同的设置参数对译码性能的影响。通过仿 真分析，找到了一种能够达到译码复杂度和可靠性的良好折衷的算法，基于这种算 法我们对它进行了硬件设计。 硬件设计方面，本文基于 fpga 实现 ldpc 码译码器的设计为研究目标，以 normalized bp-based 译码算法为理论支持，利用 verilog hdl 硬件描述语言，采取 自顶向下的设计方法对 ldpc 码译码器进行了设计，较为详细地给出了译码器的整体 结构框图以及各个译码功能模块的实现方式，在 quartus ii 软件环境中将各个模块 整合为一个完整的译码器，并对译码器进行综合编译、功能时序仿真，验证对译码 器的设计。 关键词： ldpc 码，迭代译码，软判决译码，硬判决译码，fpga 烟台大学硕士学位论文 烟台大学硕士学位论文 ii abstract ldpc codes(low-density parity-check codes) proposed by gallager in 1962 is a kind of the linear block code based on the sparse parity check matrix. its close to shannon limit for the outstanding performance caused a sensation in the field of communication, and it is the second major leap after the turbo codes in the history of the error-correcting codes. at present ldpc codes will most likely to be identified as the fourth generation mobile communication error correction coding scheme. it is thus clear that ldpc codes have become the research hotspot which the experts and the scholars are focused on in the field of communication. this paper studies iterative decoding algorithms, and does a detailed analysis about hard decision and soft decision algorithms based on the validity and the reliability for the communication performance of the ldpc codes. then we found a suitable decoding algorithm for hardware implementation. the paper can be devided into two major aspects: the theoretical analysis aspect and the hardware design aspect: in the theoretical research aspect, this article studied some background knowledge of the channel coding and the ldpc codes, then described the basic principle of the ldpc codes, the constructing methods and the encoded algorithms. two kinds of iterative decoding algorithms in hard decision and soft decision were studied in depth on the aspects of decoding complexity and error rate. in particular, one kind of decoding algorithm to reduce the number of iterations was introduced, and this algorithm is suitable for the real-time system which is more strictly for the time. through building awgn channel simulation platform, the performance of different algorithms and a variety of different settings of parameters about decoding performance are studied. through simulation analysis one algorithm of having good compromised between decoding complexity and reliability was found, and the article carried out its hardware design based on this algorithm. in the hardware design aspect, the goal for this article is to design ldpc decoder based fpga, and the theoretical support is the normalized bp-based algorithm. a more detailed block diagram of the overall decoder and the various functional modules of the ldpc codes decoder were designed with the verilog hdl hardware description language in using of top-down design method, then in the quartus ii software environment each 烟台大学硕士学位论文 烟台大学硕士学位论文 iii module will be integrated into a complete decoder. finally the decoders design was verified through comprehensive compilation, functional and timing simulation. keywords: ldpc codes ， iterative decoding ， soft-decision decoding ， hard-decision decoding， fpga 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 1 1 绪论 1.1 数字通信系统 可以说自有了人类开始， 就伴随着人类的通信。 通信指的是人与自然之间或者是 人与人之间通过某个行为或者媒介进行的信息交流和信息传递，通信之目标就是信 息传递，即信息传输。它要求对信息进行高效率、无失真的传输，同时要求在传输 的过程中抑制掉无用、有害的信息。 “光通信”或者“电通信”是近代通信的主要方 式，它是借助于光信号或者电信号及其相关的设备来达到通信的目的的。 信源、信道以及信宿组成了最简单的通信系统。一般而言，信源指的是发出信 息的源，起提供消息的作用；信宿是相对于信源来说的，它的功能是接受信息；信 道指的是由信源到信宿之间传递信号的传输介质或设备，它是传递信息的通道，通 常将其分为编码信道与调制信道，结构框图如图 1.1 所示。该结构框图是典型的点 对点单向通信系统方框图，在此基础上容易构成点对点双向通信系统、点到多点的 单向广播系统和多点对多点的单向通信系统（mimo）等 1。 信 源 调 制 器 信 道 编 码 发 送 设 备 介 质 接 收 设 备 解 调 器 信 道 译 码 信 宿 噪声源 调制信道 编码信道 消息 消息 图 1.1 通信系统结构框图 由图 1.1 可知，调制信道是编码信道的一部分，编码信道的特性与调制信道的特性 紧密相关，依赖于调制信道。更精确的来说，编码信道的输入、输出码字符号数目 和转移概率是由调制信道来决定的 1。 调制信道的输入端与输出端通常是用连续函数 来表示的模拟波形信号，即通信系统的信道如果是调制信道，则这个通信系统就是 模拟通信系统。而编码信道的输入端与输出端一般都是数字信号，即如果通信系统 的信道是编码信道，则这个通信系统就是数字通信系统。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 2 有效性和可靠性通常是评价一个通信系统优劣的主要性能指标。有效性反映的 是通过信源编码技术进行去粗取精，尽可能地消除冗余，提高编码效率，相当于传 输的“速度”的问题，可靠性则反映的是通过在信道编码中加入冗余以减小误码率 或者是误比特率，从而提高接收到的信息的准确程度，相当于传输的“质量”问题， 它是通信系统中信道编码的主要任务。有效性通常用码元传输速率来描述，而可靠 性通常可以用误码率或者误比特率来描述。尽量地减小误码率或者误比特率就是信 道编码技术的主要目的。因此，通信系统中的有效性和可靠性既是相互矛盾的，又 是相对统一的 2。一般而言，信道编码的有效性越高，则码的可靠性就越低，因此， 要在有效性和可靠性之间寻找一个折衷，使得在差错可以允许的范围内，尽量提高 传输的有效性。 1.2 信道编码理论及其发展简史 1.2.1 信道编码理论 1948 年，c.e.shannon 以其通信的数学理论 3的经典论文开创了信道编码领 域的先驱，在这篇论文中他提出了著名的信道编码定理香农第二定理，它是一 个存在性定理，是纠错编码理论的基础。该定理指出，在有噪信道中，当信道编码 的码长n足够长时，总能存在一种编码方法，使得传输的差错率达到足够的小，并 且信道的信息传输的速率r无限接近于信道容量c。这一定理在理论上明确地指出 了平均译码错误概率 e p趋近于 0， 存在信道的信息传输速率r无限接近于信道容量 c 的抗干扰信道编码技术，信息可以在有噪信道中进行可靠地传输。香农第二定理表 明了好码的存在，为整个编码领域奠定了理论基础。但如果从实际应用的角度看， 由于在理论的证明过程中是完全采用随机选择的码，就具体而言无法实际构造这种 码，因此也就无法给予实现和应用。 shannon 在其香农第二定理中运用的三个前提条件如下： 1）使用随机编码的方法 2）信道编码的码长n趋于无穷大 3）译码算法采用最佳的最大似然译码准则 信道的香农容量公式是在无记忆信道中加入加性高斯白噪声（awgn）的基础上 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 3 推导而来的，加性高斯白噪声的平均功率为n，信道输出信号的有效带宽 b（hz）受 限，输出信号的功率为s w（），输出噪声的平均功率为wn（），则信道容量c可以 表示为： 2 log (1) s cb n =+ （1.1） 式（1.1）就是香农（shannon）信道容量公式，其中/sn代表信噪比，单位是比特 每秒。 它表达了信息的最大传输速率。 当加性高斯白噪声的单边功率谱密度为 0 n时， 噪声的平均功率为 0 nn b=，这时信道的容量公式可以变换为： 2 0 log (1) s cb n b =+ （1.2） 假设通信系统以最大的传输速率 b r即信道容量c进行无差错传输，此时的最大 频谱效率可以表示为 max /c b=，综上可以得到： max 0 b es nn = （1.3） 其中 b e表示每比特的能量， 0 / b en表示的是功率效率。 当信道有效带宽b 时，此时最大频谱效率 max ，通过代换可以得到无差错传输的最小的 0 / b en： max max2 0 log (1) b ec bn =+ max max 0 21 b e n = + max 0max 21 b e n = max maxmax 00 0max 21 limlimln21.6 b e db n = (1.4) 由（1.4）可得， awgn 信道在带宽趋于无穷大的理想状况下实现无差错传输的 最小信噪比为1.6db，这就是香农限。在实际的编码算法当中，算法的性能可以用 与香农限的距离来衡量。因此可以说，如果能够构造出性能接近香农限、有效性较 好的码就是可以实用的好码。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 4 1.2.2 信道编码发展简史 自 1948 年 shannon 提出信道编码理论的 60 多年以来，探索逼近信道容量限的、 复杂度低的、实际可译的非常好码，成为通信信道编码理论界竞相研究的关键热点 课题。经过众多专家学者 60 多年来不懈的努力，信道编码在理论和实际应用中都得 到了快速的发展。根据香农所指出的目标与方向，就目前来说，纠错码的种类基于 构造方法可以分为卷积码和分组码两类。 分组码方面，第一种分组码是 hamming 码，它是于 1950 年发现的能够纠正单个 错误的码字，在 50 年代中，基于代数理论多个短码长的分组码又被陆续发现，例如 golay 提出的 golay 码、muller 和 reed 提出的 rm 码以及 prange 提出的循环码等。 到了 20 世纪 60 年代，信道编码领域迎来了快速发展的阶段。在 1960 年，bose 等人 提出了构造简单且能够纠正多个错误的 bch 码以及 reed、solomon 构造出了多进制 结构的 rs 码。1962 年，gallager 在他的论文中提出了著名的迭代译码算法的低密 度奇偶校验码（low-density parity-check codes,ldpc）码 4，但由于当时计算机 水平和图理论水平的限制，ldpc 码没有发展起来。1970 年，goppa 提出了一种线性 循环码，其子类能够达到信道编码定理中对好码要求的标准。 另一类重要的信道编码是卷积码，它是由伊莱亚斯（elias）在 1955 年提出来 的，其与线性分组码的不同之处在于卷积码是有记忆的，在卷积码的约束长度内， 前后组的关系是相互联系的，因此卷积码的性能优于分组码，但是其设计的复杂度 也相应较高。 1963 年， fano 提出了 fano 算法序列解码算法； 1966 年， ziganzirov 等人构造出了堆栈算法；1967 年，一种性能良好且复杂度适中的 viterbi 算法极大 地推动了卷积码的发展和卷积码信道编码的实用化。 1993 年的 icc 国际会议上， c.berrou 等人提出了更加接近香农限、 误码率小的、 实用的编码方法turbo 码，turbo 码的提出对信道编码理论的研究产生了深远的 影响，成为信道编码的里程碑。它在编码方案中实现了构造长码的伪随机性，使用 随机交织器将信息序列进行伪随机置换，以此实现随机编码的思想，奠定了 shannon 随机编码理论的基础。1996 年，ldpc 码接近于 shannon 限的优越性能终于被 mackay 和 neal 重新发现，并且其具有较低的译码复杂度，在码长较长的情况下，性能甚至 优于 turbo 码，是一种实用的好码。turbo 和 ldpc 码的出现从此揭开了信道编码理 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 5 论的新篇章。 1.3 ldpc码的研究价值及发展简史 1.3.1 ldpc码的研究价值 ldpc 码以其自身的诸多特点成为编码领域的一个新的研究热点。1962 年， gallager 在其博士论文中提出了两个创造性的观点： 1）应用比较简单的稀疏校验矩阵的随机置换以及级联模拟随机码。 2）使用当信道特性以及信息的先验概率已知的情况下的迭代译码算法。 ldpc码正是应用了上述两种观点。 ldpc码具有很大的灵活性和较强的纠错能力， 并且可以几乎适用于各种信道。另外，由于 ldpc 码也是一种线性分组码，实现起来 简单，但其性能可以与 turbo 码相差不大甚至优于 turbo 码，相较之下： ldpc 码具 有如下优势： 1）ldpc 码的译码的复杂度低，复杂度随着码长的增长呈线性增加，使长码编码 的应用成为可能。turbo 相当于卷积码级联而成，当分组较长时，复杂度不是线性增 加。 2）ldpc 码相对于 turbo 而言，译码速度快。因为 ldpc 码应用迭代译码的思想， 可以并行操作，更有利于硬件的并行实现，能够达到高速的译码速度。 3）ldpc 码因其并行迭代的复杂度与码长呈线性增长的关系，吞吐量可以优于 turbo 码 10 倍，能够改善传输效率，便于硬件实现。 4）抗突发差错的性能好。ldpc 码校验矩阵具有稀疏特性，当码长比较长时，距 离很远的信息位都统一参与校验，从而能够减小连续的突发差错对译码性能的影响， 其编码本身就有抗突发差错的性能。 5）ldpc 码的理论分析相对简单。ldpc 码是线性分组码，数学模型简单。目前， 在译码的性能分析上 ldpc 码已有了较为完备的理论体系，然而 turbo 码尚缺乏可靠 的理论解释。 6）ldpc 码有更低的错误平层，可以应用于对误码率要求较为严格的深空通信等 领域。而 turbo 码的错误平层相对较高，一般在 6 10量级上，必须和外码级联才能 达到这类场合的使用要求。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 6 当然，我们在看到 ldpc 码诸多优点的同时，也应该关注 ldpc 码存在的一些问 题，正是这些问题制约了 ldpc 码的发展。为了使 ldpc 码理论尽快得以完备完善而 广泛应用起来，专家学者们正在对这些问题进行深入的研究： 1）当 ldpc 码的码率较低时，其性能不甚理想。由于抗衰落性能较好的码的码 率通常较低，从而被大多通信系统所采用，然而低码率的 ldpc 码的性能差于 turbo 码。 2）ldpc 码的编码复杂度比较高。尽管 ldpc 码的译码算法可以在线性时间内完 成，但其编码复杂度仍然大大地高于 turbo，更无法与卷积码等即时编码算法的复杂 度相比。 3）中短码长的 ldpc 码的性能不甚理想。当 ldpc 码长处于中、短长度时，由于 编码时环的存在，使得译码性能受到影响。 4）在实现方面，如果 ldpc 码译码器使用全并行结构，虽然译码速率得到很大 提高，但是其硬件资源的消耗过大，而目前适用于部分并行结构的 ldpc 码的构造方 法还不够完善。 总而言之，ldpc 码有着各种优异的性能，但也存在着许多有待解决的问题。研 究好并解决好 ldpc 码的课题对通信界的发展将有十分重要的理论价值和应用价值。 1.3.2 ldpc码的发展简史 一、ldpc 码在理论上的发展： 1962 年，gallager 在他的博士论文中首次提出了低密度校验矩阵的纠错码，即 ldpc 码，并且给出了简单的构造方法和硬判决译码算法。然而由于当时图理论水平 及计算机水平的限制，ldpc 码在很长的时间里被人们遗忘，一直持续到 20 世纪 90 年代才重新被人们重视。 1981 年，tanner 5提出了从图模型的角度来描述码字，将 ldpc 码的校验矩阵的 校验节点和变量节点分别对应到tanner图的二分图上。 通过用tanner图构造的ldpc 码采用并行译码算法，可以有效降低译码的复杂度。另外，tanner 证实了和积译码 算法（sum-product algorithm）以及最小和译码算法（min-sum algorithm）基于 有限无环 tanner 图译码的最佳性。 1996 年，mackay 6和 neal 重现发现了 ldpc 码有着优越的性能，在码长较长时 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 7 性能甚至优于 turbo 码，从此 ldpc 码重新得到了人们的重视与研究。 1998 年， m.g.luby 7和 m.mitzenmacher 构造了非正则的 ldpc 码， 使其行重 （列 重）不再要求相同，其性能优于规则的 ldpc 码，改进了 ldpc 码的译码性能。同年， davey 与 mackay 8构造出了基于 ( )gf q域的 ldpc 码。 密度进化理论：2001 年，t.j.richardson 和 r.l.urbank 91011等在前人研究的 基础上，提出了密度进化方法（density evolution） ，分析了当使用消息传递译码 时 ldpc 码的容量，构造出了逼近于香农限的非正则的 ldpc 码，并阐述了 ldpc 码行 之有效的编码方式。s.y.chung 与 richardson 121314通过将消息离散化的方法又提 出了离散的密度进化方法，这种方法通过利用计算机进行迭代搜索，从而寻找到最 优的节点次数分布，它较适合应用于对非正则码的分析。为了达到提高计算速度的 要求，s.y.chung 与 richardson 13又将信息的无穷维概率密度函数采用高斯近似的 方式，达到了用更新高斯密度均值的一维问题来替换迭代计算的多维问题的目的， 采用这种方式更利于分析信道参数的门限值，能够使用计算机快速地进行线性规划 寻且优化非正则码。 针对于码界和距离分布理论的研究分析：为了便于给仿真和实际应用提供相应 的理论指导，对 ldpc 码界和最小距离分布的分析成为了许多专家学者致力于研究的 热点问题。i.sason 与 s.shamai 15在研究 gallager 的 ldpc 码距离分布的基础之上， 且通过与错误概率的切线球（tangential sphere）相融合，获得了二进制输入加性 高斯白噪声信道（biawgn）的最佳之译码上界，且利用此上界分析讨论了对不同码 率和码长的码集合的性能；g.miller 与 d.burshtein 16利用集合平均分布的表达式 推出了当采用最大似然译码时，ldpc 码通过任何二进制输入对称输出信道的译码后 的错误概率的上下界；d.burshtein 与 m.krivelevich 17等将码率之下界推广到二进 制输入对称输出信道中，获得了一个更紧的码率的下界，且通过研究给出了达到可 靠通信的码率的上界；d.burshtein,s.litsyn,g.mille 18等人分别用 8 种不同的方 法产生了 gallager,mackay,richardson 给出的规则 ldpc 码的校验矩阵，在理论上 分析比较了采用不同方法构造校验矩阵时的差异。 二、ldpc 码在应用上的发展 ldpc 码的优异的性能使其拥有无比广阔的应用前景，甚至在许多领域都可以代 替 turbo 码，ldpc 码已经被第四代移动通信系统列为关键技术。下一代卫星数字数 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 8 字视频广播标准（dvb-s2）也已经采纳了 ldpc 码的编码方案。在我国广电总局广科 院的 timi 也以其良好的性能成为我国地面数字电视传输标准建设备选方案，其最大 的技术亮点便是应用了 ldpc 码信道编码技术。依据日经 bp 社，日本产业技术综合 研究所利用群集计算机验证了 ldpc 码不存在错误平层（error floor） ，具有良好的 有效性。 由此， ieee802.3an通过了在面向双绞线的10gbit/s以太网标准 “10gbase-t” 草案中采用 ldpc 码的编码方案。2001 年以来，ldpc 码与通信领域中的其他技术的 结合应用成为了一个新的研究热点，ben lu 等人结合了选择性衰落分集 （selective-fading diversity） 和空间分集， 提出了基于 ldpc 码的 stc （space-time coded）ofdm 系统，这种系统可以以较低的计算复杂度实现较高的性能。 芯片方面，由 comtech aha 公司推出了一种 ldpc 码的前向纠错编译码器内核， 它可为适应信道条件的变化而相应地进行动态改变，并能够支持多种编码、数据率 以及调制格式。comtech aha 推出的这个内核是用 fpga 来实现的，能够支持高达 30mbit/s 的数据率，输入量化最多可达 6 位，块大小最高可达 30kbit/s，每一块编 程反复能够达到 256 次。alberta 大学的研究人员利用 fpga 实现了比区块编码更灵 活的一种 ldpc 码卷积编码排列，这种方法可使得在典型的无线以及有线的协议框架 下能够适应现实世界的多样性。 虽然 ldpc 码的硬件译码方面也取得了较大的进展，并且译码速度也比较令人满 意，但是我们也必须清醒地看到，高速全并行的 ldpc 码译码器对硬件资源的要求非 常高，研发的成本会非常的大，投入应用会有很大的开发风险，这样就不利于 ldpc 码的发展和使用。可使就目前的状况来看，这个难题还没有得到让人满意的改善。 所以，现阶段需要克服的译码器实现的瓶颈难题就是如何解决译码器的高效率与降 低译码器对硬件资源的高消耗难题。 1.4 论文章节安排 论文共分五章，本章为绪论，简要介绍了 ldpc 码的背景知识、研究意义及其发 展简史。 第二章详细阐述了 ldpc 码的基础理论， 包括 ldpc 码的定义以及表示方法， 基于 正则 ldpc 码和非正则 ldpc 码的不同构造方法，以及两种编码方法，并简要分析了 它们各自的优缺点。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 9 第三章主要基于译码复杂度和可靠性对硬判决译码和软判决译码两大类译码算 法进行了分析，寻求能达到这两者良好的折衷的译码算法，并确定为译码器硬件实 现的理论基础。在此基础上通过仿真对影响译码性能的各种设置参数进行了分析讨 论。 第四章以利用 verilog hdl 语言和 quartus ii 仿真软件，采用自顶向下的模块 化设计方法，对基于 fpga 译码器各个功能模块和实现方法都做了详细的介绍。 第五章总结全文，提出需要解决的问题和下一步工作的研究方向。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 10 2 ldpc码基本原理 早在 1962 年 gallager 就提出了 ldpc 码，它是一种用非常稀疏的校验矩阵 （parity-check matrix）来表示的线性分组纠错码，ldpc 码性能优异，是一种能够 逼近香农限的渐进好码，当码长较长时其性能甚至能够超过 turbo 码，具有译码复 杂度低、结构简单、错误平层低等诸多优点，因而受到了专家学者们的广泛青睐。 本章介绍并讨论了 ldpc 码的定义、ldpc 码的两种表示方法、正则与非正则 ldpc 码 构造方法以及两种编码方法。 2.1 ldpc码的定义 从本质上讲，ldpc 码是一类特殊的线性分组码，可以用校验矩阵和二分图来描 述。ldpc 码的校验矩阵h非常稀疏，校验矩阵h的每行有q个 1，表示的是每个校 验方程对q个变量节点进行校验约束；同样的校验矩阵h的每列有p个 1，表示每 个变量节点受到p个校验方程的校验约束。通常校验矩阵中的p和q都很小，即校 验矩阵每行（列）的重量很小，具有很强的稀疏特性，因此校验矩阵的密度会非常 低，这也就是为什么称为低密度奇偶校验码（ldpc）码的原因了。 gallager 通过 ldpc 码的校验矩阵最早给出了正则 ldpc 码的定义，其校验矩阵 中每一行和每一列的“1”的个数是相同的，分别用q和p来表示，则其校验矩阵表 示为( , , )n p q，n代表码长。它的定义需要满足三个条件： 1）校验矩阵h的每行有q个 1； 2）校验矩阵h的每列有p个 1，并且3qp； 3）p和q与校验矩阵h的行数和码长相比，都很小。 gallager 给出了当3p 时，码具有良好的汉明距离特性的证明。同时在他的博 士论文中给出了正则 ldpc 码的校验矩阵(20,3,4)h，如图 2.1。 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 11 图 2.1 gallager 博士论文中的校验矩阵(20,3,4)h 2.2 ldpc码的表示方法 2.2.1 ldpc码的校验矩阵表示方法 一个 ldpc 码可以用校验矩阵( , , )h n p q来描述，可以表述为每个变量节点参加 了p个校验方程的检验，而每个校验节点则对q个变量节点进行了校验。其中校验 方程的个数有： ()/mnpq= (2.1) 当校验矩阵h满秩时得到的编码效率为： ()/1/rnmnp q= (2.2) 假设我们希望得到 ldpc 码的码率为r，当() m n rank hm ，也就是说m个校验 方程相关时，这时得到的实际的码率为()/ m n rnrank hn =，它高于我们所希望 得到的码率r。 例 2.1 假设一个 ldpc 码的校验矩阵(12,2,3)h如下所示： 8 12 111000000000 000111000000 000000111000 000000000111 000001110000 010100000100 100000001010 001010000001 h = 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 12 在这个校验矩阵中，列重为 2，行重为 3，每一行代表了一个校验方程，总共有 /122/38np q=行，即总共有 8 个校验方程。每个校验方程中相对位置为 1 的表示该位是校验方程的一个因子，校验矩阵的非 0 元素组成了校验方程组如式 （2.3）所示： 123 456 789 1 01 11 2 678 241 0 191 1 351 2 0 0 0 0 0 0 0 0 xxx xxx xxx xxx xxx xxx xxx xxx += += += += += += += += (2.3) ldpc 码的任意码字c都应该满足0 t hc=的限制，如果码字c能使0 t hc=成 立，则c可成为对应于校验矩阵(12,2,3)h的一个码字。 2.2.2 ldpc码的二分图表示方法 ldpc 码除了可以使用稀疏校验矩阵h来表示之外，由于其校验矩阵具有特殊的 规律性，还可以用 wiberg 的因子图（factor graph） 19与 tanner 的 tanner 图5来 达到更为直观的描述的目的。然而 tanner 图相对于因子图来说能够更加直观生动地 表述 ldpc 码的编译码特性，使用起来也更为灵活方便，因此便得到了广泛的应 用,tanner 图也叫做二分图、双向图。 ldpc 码的二分图是由一组顶点和连接它们的一组边组成。这一组顶点又分成了 两个子集对应于校验矩阵 m n h 的每行的顶点叫做校验节点，这样的校验节点共 有m个，组成一个子集；对应于校验矩阵 m n h 的每列的顶点叫做变量节点，这样的 变量节点共有n个， 组成一个子集。 一个子集里的任何一个顶点与另一个子集里的顶 点有边相连，同一个子集里面的顶点之间没有边相连，校验节点与变量节点之间的 每一条连线对应于校验矩阵中的每个“1” 。对于每一个校验方程来说，就是在一个 校验方程中对应着多少个变量节点参加了这个校验方程的校验，即为校验矩阵的每 行中含有“1”的个数。换言之，当变量节点参加了某一个校验方程的校验，则这个 变量节点与该校验节点之间就有一条边相连，对应与校验矩阵中“1”的位置，由此 可见，校验矩阵中“1”元素的个数与二分图中的边的条数是相等的。每个节点上的 边的数目称为这个节点的度（degree） 。由此可见，ldpc 码的校验矩阵与 tanner 图 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 13 构成了一一对应的关系，如图 2.2 所示直观地描述了校验矩阵与二分图之间的关系。 例 2.2 正则校验矩阵(6,2,3)h与其对应的二分图的说明。 c1 c2 c3 c4 v1v2v3v4v5v6 1 1 1 0 0 0 0 0 0 1 1 1 0 1 0 1 1 0 1 0 1 0 0 1 h = c1c2c3c4 v1v2v3v4v5v6 校验节点 变量节点 图 2.2 正则校验矩阵(6,2,3)h及其对应的二分图 如上图 2.2 所示，校验矩阵(6,2,3)h的每一行对应着二分图中的一个校验节点 i c，每一列对应着二分图中的一个变量节点 j v，这样共有 4 个校验节点，6 个变量节 点，分别如图所示。就校验矩阵(6,2,3)h的第一行即校验节点 1 c来说，由校验矩阵 可以看出， 共有 3 个变量节点参与了校验方程 1 c的校验， 对应于二分图中校验节点 1 c 的三条边；同理就校验矩阵(6,2,3)h的第一列即变量节点 1 v来说，它参与了两个校 验方程 1 c和 4 c的校验，对应着二分图中 1 v的两条边。每个校验节点有 3 条边相连， 即校验节点的度为 3；每个变量节点有两条边相连，即变量节点的度为 2。由此可见 当校验节点和变量节点之间存在边时，才存在着两者之间的联系，即边的位置在很 大程度上影响着校验矩阵的性能。 如图 2.2 所示的二分图，在连接校验节点和变量节点的边中有四条加粗的线： 42534 vcvcv，这四条边使得信息的传输形成一个闭合的回路，我们称之 为环，构成环的边的条数称之为环长。在二分图的所有节点中，长度最小的环长称 之为最小环长（girth） 。图 2.2 的校验矩阵的最小环长是 4。由于 ldpc 码的译码算 法主要采用的是迭代译码算法，当其二分图中存在闭合的回路时，在进行译码的过 程中，经过多次迭代从而使得到达存在环的这些节点的信息不再满足相互独立的特 性，也就自然使译码的性能大打折扣，可见 ldpc 码的校验矩阵所对应的二分图中， 闭合回路的存在将会影响到译码的可靠性。前人的仿真结果表明，如果二分图中存 在最小环长为 4 的环， 会对译码的可靠性造成非常大的影响。 从另一个角度说， ldpc 码的二分图中最小环长的长度也会影响到码的最小距离，tanner 对此问题进行了深 入研究并且给出了两者之间的关系式： 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 14 (2)/4 (2)/4 /4 (1)(1)1 (1)(1)/2 (1)(1) 1 (1)(1)1 /2 (1)(1) 1 g g g dd dddg d d ddg d + 为奇数 为偶数 (2.4) 式 2.4 中g为 ldpc 码的最小环长，d是二分图中子码的最小码距，是变量节点的 度，d是码的最小码距，由式 2.4 可以看出，ldpc 码的二分图中 girth 长度越长， 码的最小距离会越大， 从而促使 ldpc 码的译码的可靠性越好。 综上所述， 在构造 ldpc 码的校验矩阵时，要尽量保证在避免出现长度为 4 的环的出现的同时，使得其它节 点的的最小环长要尽量地大。 然而让人吃惊的是，只要最小环长的长度大于 4，尽管二分图中的许多节点存在 着很多闭合回路，通过迭代译码算法之后却对 ldpc 码的译码性能的影响不大。 gallager 对这种现象做出了解释，他认为：随着译码算法迭代次数的不断增加，信 息之间的独立性所产生的影响逐渐减小且趋近于互相抵消，当迭代次数达到一定的 数值时，环的存在对译码结果产生影响的可能性就会变得很小。 2.3 正则 ldpc码与非正则 ldpc码 正则 ldpc 码与非正则 ldpc 码的定义是根据其校验矩阵而来的，正则 ldpc 码的 校验矩阵需要满足以下特性： 1）严格地来说，正则 ldpc 码的校验矩阵的每列要有固定列重p，每行有固定 的行重q。但在实际的应用中由于现实的需要，可以对 ldpc 码的行重和列重适当地 放宽要求，不必固定为一个整数，但其行（列）重要尽量地服从于均匀分布。 2） 要满足 ldpc 码的校验矩阵非常稀疏的特性， 因此要求其校验矩阵的行重q和 列重p相对于校验矩阵的行数m和列数n而言，要非常小。 3）校验矩阵的二分图中要尽量保证不产生最小环长为 4 的环，这就要求校验矩 阵中任意的两行或两列相同位置上的“1”的个数最多为 1。 4）正则 ldpc 码最小码率r有如下计算公式： ()/1/1/rnmnm np q= = (2.5) 当正则ldpc码的码长足够长并且使用最优译码算法的情况下， 从理论上讲， 正则ldpc 码的性能可以逼近香农限。但是在实际中，当码长趋近于无穷长时，最优译码算法 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 15 的计算复杂度会太高，对硬件资源的要求更加不可想象，因此逼近于香农限的正则 ldpc 码在现实中很难得到实际的应用。 mackay 20曾经对正则的 ldpc 码做出了两条重 要的结论： 1.当 ldpc 码的列重可以根据传输的速率和信道的特性来匹配，而不再是一个固 定的值时，这时肯定能够找到一个最佳好码，使之能够实现在小于信道容量的速率 内进行无差错的传输。 2.当给定的 ldpc 码的列重大于 3，并且其码长趋近于无穷大时，能够找到一个 大于零并且小于某信道容量的速率r， 使之以大于零且小于速率r的速率在信道中进 行无差错的传输。 从上述结论反应出一对不可相容的矛盾。从理论上来说，针对 ldpc 码的每一个 校验节点而言，其度越小，即参与到这个校验方程的变量节点越少，对这个校验节 点的准确判断的影响性就越小；而对于每一个变量节点而言正是一种相反的情况， 其度越大，即每个变量节点参与到的校验方程的个数越多，它获得的信息量就越多， 从而判断出变量节点的准确值的可能性就越大。 针对这种不可调和的情况，luby,mitzenmacher 21等人研究出了非正则 ldpc 码， 它克服了在正则 ldpc 码中的一些缺陷。非正则 ldpc 码不再对校验矩阵中的行重与 列重做固定的数目限制，对应到二分图中来说，也就是对每个集合中的校验节点的 度以及变量节点的度不再要求相等或均匀，每个变量节点参与的校验方程的个数， 以及每个校验节点含有的变量节点的个数不再要求必须相等或均匀。如图 2.3 所示 就是一个非正则ldpc码二分图， 它直观的反应出了变量节点与校验节点之间的关系， 校验节点集合中各个节点的度不一定互相相等，变量节点集合中各个节点的度也不 一定互相相等。 校验节点 变量节点 图 2.3 非正则 ldpc 码的二分图 非正则 ldpc 码可以对其进行有目的的强化某些变量节点和校验节点，由于这种 设置，使得非正则 ldpc 码在译码过程中充分利用了一种“波状相应” ，正是这种方 烟 台 大 学 硕 士 学 位 论 文 烟 台 大 学 硕 士 学 位 论 文 16 式使得非正则 ldpc 码的译码性能明显优于正则的 ldpc 码。具体而言，波状效应表 现为：在 ldpc 码译码的过程中，首先是那些度比较大的，即参与校验方程的个数比 较多的变量节点先获取正确的译码信息，从而这些变量节点就可以给与它们相邻的 校验节点更加有效可靠的参考信息，然后，这些校验节点就可以给度稍小一些的变 量节点以更加多且准确的信息，以使得它们译码正确的概率大大增加。由此可见， 这种波状效应的