第八章LDPC码 8.1研究LDPC码的原因 BCH 码 码 循环码 RS码 线性 信 分 系统卷 码 奇偶 积码 Tu胸 LDPC 非循环 校验 码 码 非系统 非线 码 卷积码 性码 汉明 码 Mackay等人的再发 现 可以看到，信道编码的发展可以简单的归纳为分组码→卷积码→分组 码这样一个过程（在这里按其结构将Tubo码也归入卷积码的范畴）。 其中Tubo码的出现以及迭代译码的思想引入使得信道编解码产生 了前所未有的飞跃，但Tubo码之后卷积码却没有更大的发展，究其 原因就是其没有完备的理论基础，使得人们不能给出其性能上严密的 数学解释。于是在那之后可以说是一种退化或者是返朴归真，Mackay 等人再次发掘了Gallager于1962年提出的一种具有稀疏校验矩阵的 分组纠错码，即LDPC码。 LDC码和传统的分组码最大的区别在于它们的译码。分组码通常是 用最大似然译码，因此，码长一般较短，并用代数方法设计使得复杂 度较低。而LDPC码是迭代译码，校验矩阵用Tanner图表示，码长更 长、围绕着校验矩阵H的特性进行设计是核心。 LDPC码自身的矩阵结构引入了交织特性，而且其采用迭代译码的
第八章 LDPC 码 8.1 研究 LDPC 码的原因 分 组 码 卷 积 码 线性 码 非线 性码 非系统 卷积码 系统卷 积码 循环码 非循环 码 汉明 码 奇偶 校验 码 RS码 BCH 码 Turbo 码 LDPC 码 信 道 编 码 Mackay等人的再发 现 可以看到，信道编码的发展可以简单的归纳为分组码卷积码分组 码这样一个过程（在这里按其结构将 Turbo 码也归入卷积码的范畴）。 其中 Turbo 码的出现以及迭代译码的思想引入使得信道编解码产生 了前所未有的飞跃，但 Turbo 码之后卷积码却没有更大的发展，究其 原因就是其没有完备的理论基础，使得人们不能给出其性能上严密的 数学解释。于是在那之后可以说是一种退化或者是返朴归真，Mackay 等人再次发掘了 Gallager 于 1962 年提出的一种具有稀疏校验矩阵的 分组纠错码，即 LDPC 码。 LDPC 码和传统的分组码最大的区别在于它们的译码。分组码通常是 用最大似然译码，因此，码长一般较短，并用代数方法设计使得复杂 度较低。而 LDPC 码是迭代译码，校验矩阵用 Tanner 图表示，码长更 长、围绕着校验矩阵 H 的特性进行设计是核心。 LDPC 码自身的矩阵结构引入了交织特性，而且其采用迭代译码的
方法，使其性能比以往的线性分组码有很大程度的提高。由于其基本 原理是基于最原始的线性分组码，因此它有强大的数学工具作为其理 论依据，几乎融图论、组合数学、概率论、矩阵论、代数、几何、代 数数论、黎曼几何于一炉。在通信的其它领域，我们很难再找到某个 方向可以有如此深厚的理论基础与之媲美。 但理论上的完备性并不能使其直接应用于实际，因此从码字构造 的方向来说，如何将LDPC码应用于实际工作才是值得深入研究的。 为了保证其实现性，性能上就要有所妥协。 在编码方面，以准循环LDCP码，即QC-LDPC码为例，为了降低 硬件上的存储空间以及易于编码，就要以牺牲LDPC码先天的优势一 一交织特性为代价，这样便做出了性能与实现上的折中。但这种折中 是有意义的，为LDPC码的实际应用开辟了道路。而且，通过某些方 法，可以使设计出的码字在易于存储实现的同时，还能保证一定的性 能。 在译码方面，种种方法都可以归结为和积算法(SPA)的变形，都 是在其基础上做出改进，从而保证译码性能前提下使译码器尽可能的 简单。相对于Tubo码，LDPC码的解码迭代次数还是过高，这样在 实际应用中的竞争力便大打折扣。于是，怎样在保证性能的前提下降 低译码时间是现在译码研究的主要工作。 8.2LDPC码简介 1996年Mackay、Spielman和Wiberg几乎同时发现：Gallager
方法，使其性能比以往的线性分组码有很大程度的提高。由于其基本 原理是基于最原始的线性分组码，因此它有强大的数学工具作为其理 论依据，几乎融图论、组合数学、概率论、矩阵论、代数、几何、代 数数论、黎曼几何于一炉。在通信的其它领域，我们很难再找到某个 方向可以有如此深厚的理论基础与之媲美。 但理论上的完备性并不能使其直接应用于实际，因此从码字构造 的方向来说，如何将 LDPC 码应用于实际工作才是值得深入研究的。 为了保证其实现性，性能上就要有所妥协。 在编码方面，以准循环 LDCP 码，即 QC-LDPC 码为例，为了降低 硬件上的存储空间以及易于编码，就要以牺牲 LDPC 码先天的优势— —交织特性为代价，这样便做出了性能与实现上的折中。但这种折中 是有意义的，为 LDPC 码的实际应用开辟了道路。而且，通过某些方 法，可以使设计出的码字在易于存储实现的同时，还能保证一定的性 能。 在译码方面，种种方法都可以归结为和积算法（SPA）的变形，都 是在其基础上做出改进，从而保证译码性能前提下使译码器尽可能的 简单。相对于 Turbo 码，LDPC 码的解码迭代次数还是过高，这样在 实际应用中的竞争力便大打折扣。于是，怎样在保证性能的前提下降 低译码时间是现在译码研究的主要工作。 8.2 LDPC 码简介 1996 年 Mackay、Spielman 和 Wiberg 几乎同时发现：Gallager
早在1962年提出的低密度校验码（简称LDPc码，也称Gallager码） 也是一个好码，具有更低的线性译码复杂度。Gallager提出LDPc码 后一直没有得到编码界的重视，只有1981年Tanner从图论的角度研 究过LDPC码。 自Mackay等“再发现”LDPC码后，人们的进一步研究表明：给 予非规则双向图的LDPC长码的性能可以优于Tubo码，而且这样的 码的性能可以非常接近Shannon限。一个原因在于LDPC码具有良好 的距离特性、较小的译码错误概率和较低的译码复杂度，且码长大于 200时不存在错误平台，码率容易调整，实验结果中几乎均为可检测 错误，所以LDPC码无论在理论上还是在实际上都具有极其重要的价 值。LDPc码的重新发现是继Tubo码后在纠错码领域又一重大进展。 (1)编码方面的简介 无论Gallager还是Mackay都是用随机的方法构造LDPC码，用 随机法构造的LDPC码的码字参数选释灵活，但对于高码率、中短长 度的DPC码用随机法进行构造，要避免短循环是困难的，其没有一 定的码结构，编码复杂度高，于是人们考虑用代数法构造LDPC码。 LDPC码代数构造可采用几何方法、图论方法、实验设计方法、 置换方法来设计。不同的构造方法都是为了实现以下几个目的：增大 图中最小循环长度，即Gith值。优化非规则码的节点分布，减小编 码复杂度，构造的LDPC码要有好的码性能。 M.G.Luby等指出，非规则H矩阵构造的码字性能优于相应的规 则H矩阵构造的码字。在寻找好的码结构方面，Mackay等提出：能
早在 1962 年提出的低密度校验码（简称 LDPC 码，也称 Gallager 码） 也是一个好码，具有更低的线性译码复杂度。Gallager 提出 LDPC 码 后一直没有得到编码界的重视，只有 1981 年 Tanner 从图论的角度研 究过 LDPC 码。 自 Mackay 等“再发现”LDPC 码后，人们的进一步研究表明：给 予非规则双向图的 LDPC 长码的性能可以优于 Turbo 码，而且这样的 码的性能可以非常接近 Shannon 限。一个原因在于 LDPC 码具有良好 的距离特性、较小的译码错误概率和较低的译码复杂度，且码长大于 200 时不存在错误平台，码率容易调整，实验结果中几乎均为可检测 错误，所以 LDPC 码无论在理论上还是在实际上都具有极其重要的价 值。LDPC码的重新发现是继Turbo码后在纠错码领域又一重大进展。 （1）编码方面的简介 无论 Gallager 还是 Mackay 都是用随机的方法构造 LDPC 码，用 随机法构造的 LDPC 码的码字参数选择灵活，但对于高码率、中短长 度的 LDPC 码用随机法进行构造，要避免短循环是困难的，其没有一 定的码结构，编码复杂度高，于是人们考虑用代数法构造 LDPC 码。 LDPC 码代数构造可采用几何方法、图论方法、实验设计方法、 置换方法来设计。不同的构造方法都是为了实现以下几个目的：增大 图中最小循环长度，即 Girth 值。优化非规则码的节点分布，减小编 码复杂度，构造的 LDPC 码要有好的码性能。 M.G.Luby 等指出，非规则 H 矩阵构造的码字性能优于相应的规 则 H 矩阵构造的码字。在寻找好的码结构方面，Mackay 等提出：能
快速编码的LDPC矩阵通常具有下三角形结构。 TJ.Richardson探讨了如何构造编码矩阵，使编码时间与码块长 度实际上符合线性关系（线形时间编码），而非通常认为的平方关系。 Y.Kou和s.Lin等探讨了基于有限几何学的LDPc码结构。S.Lin研 究团队的B.Ammar等提出用均衡不完全区组设计方法(BlBD)构造 好的LDPC码。 (2)译码方面的简介 Gallager曾给出两种LDPC码的迭代译码算法：硬判决和软判决 算法。后者虽有好的性能，但太复杂，消息传递算法可以认为是二者 的折衷。消息传递算法(MP,Message Passing)有时也称置信传播 (BP,Belief Propagation)算法。在MP译码算法中，节点到节点的 消息是通过Tanner图传递的。 译码算法的改进和优化离不开译码性能的分析。在译码性能分析 的研究方面，TJ.Richardson等开发了一种在码块无限长假设条件下， 跟踪LDPc码Tanner图中消息概率的技术，称为“密度进化”算法的 数值程序，来近似估计噪声门限（在该门限以下可望成功地采用BP 算法)，提出了一种通用方法来确定任何二元输入无记忆信道中采用 MP译码的LDPC码的性能。特别对于BP译码算法，该方法可提供任 何所需精度的性能估计。 s.Y.Chung等将消息离散化，通过计算机迭代搜索寻找最优的节 点次数分布，特别适合于非规则码的分析，在二进制输入AWGN信 道下，设计码率1/2、码张10'的非规则LDP℃码在错误概率106时离
快速编码的 LDPC 矩阵通常具有下三角形结构。 T.J.Richardson 探讨了如何构造编码矩阵，使编码时间与码块长 度实际上符合线性关系（线形时间编码），而非通常认为的平方关系。 Y.Kou 和 S.Lin 等探讨了基于有限几何学的 LDPC 码结构。S.Lin 研 究团队的 B.Ammar 等提出用均衡不完全区组设计方法（BIBD）构造 好的 LDPC 码。 （2）译码方面的简介 Gallager 曾给出两种 LDPC 码的迭代译码算法：硬判决和软判决 算法。后者虽有好的性能，但太复杂，消息传递算法可以认为是二者 的折衷。消息传递算法（MP，Message Passing）有时也称置信传播 （BP，Belief Propagation）算法。在 MP 译码算法中，节点到节点的 消息是通过 Tanner 图传递的。 译码算法的改进和优化离不开译码性能的分析。在译码性能分析 的研究方面， T.J.Richardson 等开发了一种在码块无限长假设条件下， 跟踪 LDPC 码 Tanner 图中消息概率的技术，称为“密度进化”算法的 数值程序，来近似估计噪声门限（在该门限以下可望成功地采用 BP 算法），提出了一种通用方法来确定任何二元输入无记忆信道中采用 MP 译码的 LDPC 码的性能。特别对于 BP 译码算法，该方法可提供任 何所需精度的性能估计。 S.Y.Chung 等将消息离散化，通过计算机迭代搜索寻找最优的节 点次数分布，特别适合于非规则码的分析，在二进制输入 AWGN 信 道下，设计码率 1/2、码长 107的非规则 LDPC 码在错误概率 10-6时离
Shannon限仅0.0045dB。这是迄今为止报道出的性能最接近Shannon 限的信道编码。 8.3LDPC码的基本概念 LDPC码是用一个稀疏的非系统的校验矩阵H定义的线性码。 行重：H矩阵每行中“1”的个数，其值远远小于H矩阵的列数。 列重：H矩阵每列中“1”的个数。 LDPc码可以按照H矩阵分为规则(regular)和非规则(irregular) 两种。规则LDPC码中，各行的行重是一致的，各列的列重也是一致 的，而行重或者列重不一致就称为非规则LDPC码。 下面给出规则LDPC码的定义： 一个（n,j,k)的规则DPC码由它的校验矩阵H定义，校验矩阵 有n列，m行，列重，行重k,钟m=n·j/k,jk,jK<m,k<n。 LDPC码的H矩阵一般都是用非系统形式给出的。例如我们生成一 个6,2,4)的校验矩阵： [110110 0 H=1 1011 011101 如例所示的规则H矩阵行重为4，列重为2。 同一般的线性分组码，H矩阵的码率可以如下计算： R=n-m/n=k-j/k;则图中的矩阵可以用来实现码率1/2的编码。 对于一个非正则(irregular)LDPc码，我们常用度分布（degree distribution)来描述它。H中，列重为i的占比v:和行重为j的占比
Shannon 限仅 0.0045dB。这是迄今为止报道出的性能最接近 Shannon 限的信道编码。 8.3 LDPC 码的基本概念 LDPC 码是用一个稀疏的非系统的校验矩阵 H 定义的线性码。 行重：H 矩阵每行中“1”的个数，其值远远小于 H 矩阵的列数。 列重：H 矩阵每列中“1”的个数。 LDPC 码可以按照 H 矩阵分为规则（regular）和非规则（irregular） 两种。规则 LDPC 码中，各行的行重是一致的，各列的列重也是一致 的，而行重或者列重不一致就称为非规则 LDPC 码。 下面给出规则 LDPC 码的定义： 一个（n, j, k）的规则 LDPC 码由它的校验矩阵 H 定义，校验矩阵 有 n 列，m 行，列重 j，行重 k，其中 m njk = ⋅ / ，j<k，j<<m，k<<n。 LDPC 码的 H 矩阵一般都是用非系统形式给出的。例如我们生成一 个(6,2,4)的校验矩阵： = 0 1 1 1 0 1 1 0 1 0 1 1 1 1 0 1 1 0 H 如例所示的规则 H 矩阵行重为 4，列重为 2。 同一般的线性分组码，H 矩阵的码率可以如下计算： R=(n-m)/n=(k-j)/k；则图中的矩阵可以用来实现码率 1/2 的编码。 对于一个非正则（irregular）LDPC 码，我们常用度分布（degree distribution）来描述它。H 中，列重为 i 的占比 vi和行重为 j 的占比