LDPC码性能研究与算法优化

I 摘要 信道编码是数字通信系统的不可或缺的组成部分 , 其中 (一种采用矩阵构造进行编码，使用迭代方法进行译码的新型信道编码方案，它的译码复杂度很低，并且拥有逼近香农极限的优异性能。 本文首先介绍信道编码的发展历程、 的基本概念和基本原理，然后从 验矩阵）的构造方法以和性能分析方面对 进行了讨论，并针对每种方法提出了自己的结论和看法。介绍了 序的整体框架，分析了程序的 运行过程以及程序中的注意事项。 在理论研究方面，本文首先研究了 的码结构的构造方法。然后详细分析了传统的 码算法和基于下三角的有效编码算法。然后利用 行仿真，将矩阵进行了多次的下三角变换，观察仿真结果中信噪比和误码率的折线图，得出结论。信噪比不同，分成的最佳下三角个数不同。同一信噪比下，分割的下三角的个数不同，对应的误码率也是不相同的。 关键词 ： 矩阵变换 信道编码 性能分析 is an of is of of is a of on It as as of of is of in of In in in of on a of NR ER a NR is of is of is is 目录 第 1 章 绪论 . 1 字通信系统 . 1 道模型 . 3 密度校验码的研究与发展 . 3 文框架结构 . 4 第 2 章 的定义和编码的原理 . 6 . 6 . 6 阵的表示方法 . 6 表示法 . 7 . 8 第 3 章 译码算法 . 12 . 12 判决译码算法原理 . 13 . 16 第 4 章 的设计 . 18 的校验矩阵的设计 . 19 计 H 矩阵的整体结构 . 19 除四环 . 20 和译码流程 . 20 的 生成 . 21 的编码 . 22 的译码 . 23 第 5 章 研究不同校验矩阵对 性能的影响 . 25 验矩阵 . 25 同的下三角 个数对 性能的影响 . 26 三角校验 矩阵对性能的影响分析 . 26 第 6 章 总结与展望 . 33 结 . 33 望 . 33 参考文献 . 34 b 致谢 . 36 附录 . 37 1 第 1 章 绪论 本章主要介绍了数字通信系统的构成和通信系统的工作流程，简单地介绍了数字通信系统的工作原理。同时也介绍 了信道编码技术的发展历程，简单的阐述了信道编码技术的提出和各个发展阶段中的代表事件，以及取得的成果 。 字通信系统 通信系统的基本目的是将所要传递的信息由信源高效、可靠、安全地传递给信宿。在信息传输时，信道中的噪声必然会对传输信息产生干扰，从而使可靠性降低。所以，设计通信系统的核心问题在于如何减小信道中随机噪声对传输信号的干扰，在减小信息传输产生错误的同时，还要尽可能地保证信息传输的效率，即解决通信系统中，有效性和可靠性之间的矛盾。一般地，用误码率（ 衡量通信系统的可靠性，用信息传输速率 R（比特 /信道）符号来衡量系统的有效性。早期，人们普遍认为在通信系统中有效性与可靠性之间存在着不可协调的矛盾，一方的改善必定会引起另一方的恶化，并且指出，当功率受限时，在有扰信道上，实现任意小的错误概率的信息传输的唯一方法就是让信息传输速率为零。这个观点直到 息编码理论的奠基性论文“通信的数学理论”于 1948 年发表之后才被改变。他第一次阐明了在有扰信道中实现可靠通信的方法，并且指出，要想实现可靠而有效地传输信息，就要通过编码。根据 息理论，数字通信系统的基本组成如图 示。 通信系统一般情况下被分为数字通信系统和模拟通信系统两种。模拟通信系统所发送的信号一般为电信号的参量连续值，例如，普通电话机输出的信号就是模拟信号，但是，数字通信系统在发送信号前，先要将连续的模拟信号变成数字信号，经由数字通信方式传播之后在接收端通过相反的变换，来还原原始的模拟信号。 通常数字通信系统的构成如图 示。 图 信系统的简化模型 发送设备 信道 信源 接收设备 信宿 噪声源 信道 2 如图 示，信源产生的信号经信源编码器编码之后，被转换成二进制数字序列。为了使序列中的冗余尽可能小，信源编码器要用尽可能少的二进制数字来表示信源输出，这个过程也被称为数据压缩。假设信源编码器每秒钟发送 么， 被称为数据率。 在数据传输 的过程中，信道会引入干扰从而导致信息的接收错误，信道编码器通过给要发送的信息序列中加入一定的冗余，从而将信道引入的差错最小化。假设信道编码器输入 k 个信息单元，输出 n，我们定义 R=k/n 为该信道编码方式的码率，并且称 n 为一个码字。编码器的任务就是产生差别很大的码字，因为差别越大，出现错误判决的可能性就越小。因此，经信道编码后产生的传输速率为每秒 错误 !未找到引用源。 =错误 !未找到引用源。 /R 比特。 R 是小于 1 的数，所以经信道编码之后，数据的传输速率变高，也就是占用了更多的带宽，即引入冗余。信道编码器的 意义就是在发射功率，系统带宽和设备复杂性的共同约束下提高系统传输的可靠性。 经过信道编码器编码产生的数字信号一般不适合直接在信道中进行传输，因此数字信号会经过调制器转换为适合在信道中传输的模拟信号。此外，还能通过多进制的调制方法提来高频带利用率。例如一个 M 进制的调制器，将 L 个数字比特映射到 有 M=2L,再假设符号周期为 T，则定义 ，且 错误 !未找到引用源。 满足关系式 错误 !未找到引用源。 =错误 !未找到引用源。 / 调制后的信号进入信道进行传输，无可避免 得要受到外界噪声的干扰。信道包括从调制器到解调器的所有硬件设备，存储媒介，和传输媒质。在实际的信道中，信道要受到信道带宽和热噪声的约束，对于无线信道还存在多径衰落。 在接收端，系统采用与发射端相反的操作来恢复信号。首先，解调器对接受的信号进行解调，如果输出的是数字比特，并且直接对数字比特进行译码，那么这种译码方式就被称为软译码，使用软译码能够充分利用信道信息，从而提高译码准确性，但计算复杂度则比较高。 信源 信源编码器 信道编码器 调制器 信道 信宿 信源译码器 信道译码器 解调器 噪声源 图 字通信系统的基本模型 3 道模型 图 示信道部分只是对息传输所通过的介的一种抽象，而实际的信道则是多种多样的，比 如电缆、光缆、存储设备、甚至连我们所处的空间和宇宙都可以是信道。对通信系统的设计者们来说，必需要了解通信系统中信道的特性。根据信道的统计特性是否随着时间的变化而改变，可以将信道分为平稳信道和非平稳信道；根据信道的输入和输出的取值是否是连续的，可以将信道分为离散信道、连续信道和离散输入 /连续输出信道；根据信道的特性对输入端是否具有对称性可以将其分为对称信道和非对称信道；根据信道的输出之间是否具有相关性，可将信道分为记忆信道和非记忆信道。在实际应用中用到的信道，大多都是离散输入的平稳无记忆对称信道，下面给出几种 经常用到的信道编码模型。 二进制对称信道（ ：输入为二进制变量 0 和 1 ，输出也是二进制变量 0 和 1 ，而且，传输过程中发生错误（输入为 1 输出为 0 或输入为 0 输出为 1）的概率与输入没有关系。 二进制删除信道（ ：输入为进制变量 0 和 1 ，输出要么是输入的二进制变量 0 和 1，要么是删除 E ，而且，通常情况下传输过程中不同的输入被删除的概率是相同的。 二进制输入高斯信道（ ：输入为二进制变量，输出为连续变量，而且信道中的加性噪声是服从 N(0, ) 的高斯随机 变量。 密度校验码的研究与发展 是一种校验矩阵为稀疏矩阵的线性分组码，它是由 1962 年提出， 1963 年 表的 文标志着 的诞生， 校验矩阵对应到计算树上，校验矩阵中每列对应于图中的一个变量节点，每行对应于一个校验节点，校验矩阵中的非零元素所在的行和列对应的变量节点和校验节点之间有边相连。 明 的最小汉明距离随着码长的增 加而线性增加，并且在计算树上进行后验概率迭代译码可获得随码字长度增加而降低的比特错误概率。虽然 经证明了 是具有渐近特性的好码，但由于当时计算能力有限，所以 一度被认为是一种不实用码，在很长的一段时间内不被人们所重视。 1981 年 广泛研究图码的基础上提出了规范图码的表示方法 称二分图），这种方法是把校验约束建立在局部码元集合上。从 上可以直观地理解 到 1996年 是一种好码，并且，推广了 概率迭代译码算法，论述了和积算法（也称信传播）算法）的详细方案，极大地推动了 的发展，成为 的发展的里程碑。 1997 年 人首先提出了非规则 ，并证明了非规则比规则 有更好的性能。 实际上在构造 时，其 必定存在小环，这样就会造成译码性能的下降。要想构造好的 ，可以从两个方面进行研究：其一，构造综合性能更好的码，其二，寻找构造码的分析方法。 A. H. 据码性能提出根据围长（ 分布来设计 ， 人提出了渐进边增长（ 构造码算法，适用于随机构造 ，通过对围长进行优化，可以消除小环。 人用循环矩阵构造的 校验矩阵，围长很大。 i 和 人利用有限几何法构造 ，给出了 4 种基于 是 过对因子图的研究发现，对任意给定的系统，无环图的状态复杂度是最大的，有环图的 状态复杂度则很小，证明基于有环 具有较低的译码复杂度。 人指出消除 4 环对码的性能将会有很大的提高，但是，继续消环对于码的性能提高的影响则越来越不明显。 人总结发展了 分析方法，提出了密度进化（ 法，分析了消息快递译码下的 的容量，设计出非规则 ，这种非规则码非常接近香农极限，论述了快速 的编码方法，对 的研究和发展做出了极大贡献。 在以上工作的基础上， 的研究在译码算法上的简化，密度进化的改进，非规则码度数设计，校验矩阵的构造，距离特性和性能界限的分析，通信和数据存储的应用， 的实现等方面展开，已取得非常多有价值的成果，并在实际系统中得到应用。 文框架结构 本文对 进行了深入研究，通过查阅大量的中外文资料，对 的发展变化、工作过程以及工作原理等方面进行了详细的阐述。本论文主要研究了通过对 H 矩阵进行不同个数的下三角变换，对 编码解码后误码率的影响，通过行仿真。 第一章，绪论。本章主要介绍了 基础 知识，介绍了数字通信系统的构成以及信道编码技术的发展历程。 5 第二章， 的定义和编码原理。本章主要介绍了 的定义，介绍了矩阵表示和 表示这两种基本表示方法。同时也详细讲述了 编码的思想。 第三章， 译码算法。主要介绍了 的译码思想，简要介绍了软判决算法和硬判决算法的发展历史。举例介绍了 判决译码算法和 的码算法的原理和工作过程。 第四章， 的设计。本章主要介绍了校验矩阵 H 的生成过程框架，需要注意的事项以及消除四环的原因。 同时也详细介绍了 的译码流程图，以及运行程序的介绍。 第五章，就不同校验矩阵对 性能的影响。本章主要是提出了把原矩阵 性能的影响问题。然后对此次猜想进行真，探究 H 矩阵经过不同处理后信息传输的误码率之间的关系，画出折线图以及表格，得出结论。 第六章，简要概述了本文介绍的内容，对本论文进行了总结。并且对 进行了阐述，展望了 的发展前景和发展方向。在一定时间段里 仍然会是比较热门的信息传输方法。 6 第 2 章 的 定义和编码的原理 本章介绍了 的定义，简单阐述了 元的基本的原理。同时介绍了矩阵的表示方法和 表示方法这两种 基本表示方法，举例描述了这两种表示方法。同时也详细描述了 的编码思想，为以后的 序仿真打下基础。 的基本原理 又叫做低密度奇偶校验码，是一种校验矩阵非常稀疏的线性分组码，也就是说它的校验矩阵 H 中非零元素的个数远远要比零元素的个数要小，或者矩阵的行重和列重与码 长相比很小。由于 的这些特性，使其可以构造出高性能、低复杂度的编码。 的表示方法 的表示方法一般分为两种，即矩阵的表示方法和 表示方法。 阵的表示方法 是一种线性分组码， 的码字由校验序列和信息序列两部分组成，令码长度为 n，信息序列长为 k。我们可以使用 m n 维的校验矩阵来唯一地表示一个码字。校验矩阵的每一行可以看成是一个奇偶校验方程，每一列是该码字的一位。每一行非零元素的个数称之为行重，我们用 一列非零元素的个数称为列重，我们用 表示。校验矩阵 H 的行数 m 的值等于码字要满足校验等式的个数，码字的每个比特都参与了 每个校验等式包含了码字中 不同比特位。以下面的一个例子来具体说明 的矩阵表示： 设一个规则的 的校验矩阵 H 如下： 7 H=100110110001011100001011(公式 2 由式 (2，该规则 的行重 ，列重 错误 !未找到引用源。 为 2，设 c=(错误 !未找到引用源。 错误 !未找到引用源。 错误 !未找到引用源。 )满足该校验方程的一个码字，则有 H 错误 !未找到引用源。 =0，即要满足下面的关系式。 (公式 2 上式中的加号是二进制加法，经过验证， c=1 0 0 1 1 0是符合以上校验方程的一个码字。 表示法 除了用校验矩阵 H 来表示外，还可以用 表示。 表示法是一种非常形象的表示方法，为我们理解和分析 的译码过程提供了很大的方便。 是双向图，它将节点分成两个不同的集合，任何一个集合的内部节点没有连线，只有不同的节点间才有连线。 我们令 E 表示各边的集合 ,V 表示各节点的集合，那么，一个由节点和节点之间的连线所构成的 ，就可以 表示成 G=(V， E)。节点集合（ V）又分为两个不相交的子集，假设校验矩阵 H 是 m n 维的，那么，变量节点集合就可以表示为 错误 !未找到引用源。 =(错误 !未找到引用源。 , 错误 !未找到引用源。 , 错误 !未找到引用源。 )，校验节点表示为 错误 !未找到引用源。 =( 且满足关系 V=错误 !未找到引用源。 错误 !未找到引用源。 ,错误 !未找到引用源。 错误 !未 找到引用源。= 错误 !未找到引用源。 。以上式 (2的校验矩阵 为例，它的 如图 示。 b1 b2 b3 b4 b5 b6 c1 c2 c3 验矩阵的 表示 8 如图 示，校验矩阵的每一行对应一个校验节点，每一列对应一个变量节点。如果校验矩阵的第 i 行，第 j 列是非零元素，则在 上，第 j 个变量节点和第i 个校验节点之间有一条边相连，即节点 错误 !未找到引用源。 与 错误 !未找到引用源。之间有一条边相连， 边 (错误 !未找到引用源。 ， 错误 !未找到引用源。 )错误 !未找到引用源。 E。与节点相连的边的数目为节点的度 (校验矩阵的行重，列重与 量节点的度是相对应的。我们定义，从某个节点出发到再次回到该节点为一个循环 (所经过边的个数称为循环长度 (在上面的 们可以看到 6 条粗线构成一个有向闭合环路，它由 发，经过 6 条边后又回到了 的循环长度为 6。我们把 中最短的循环长度称为最小围长。 的编码思想 的编码步骤如下： 1低密度校验矩阵构造 ， 完全由其校验矩阵来确定，因此，要对 先要构造一个校验矩阵。如今，低密度校验矩阵的构造方法已经有很多了，假设已经构造了一个校验矩阵 H,那么，就可以从码字空间中选出一组可用码字，作为所需构造的 。 2为了方便在译码的时候确定信息比特的位置，需要用到高斯消元，将非系统形式的校验矩阵 H，转化为系统形式： H=错误 !未找到引用源。 ,I ，其中 I 为单位矩阵。 3利用校验矩阵来得到生成矩阵 G=I,P 。 4用生成矩阵 G 与信息序列 u 相乘，得到编码输出码字 ： C=u 错误 !未找到引用源。 G=u,u 错误 !未找到引用源。 p (公式 2目前，过长的编码时延和过高的编码复杂度，是阻碍 的应用的主要因素。上面介绍的 的编码方法的编码复杂度为码长的二次方，码长很长情况下的编码复杂度过高将成为 应用的瓶颈。 上述 的编码方法的复杂度之所以高，是因为，在构造生成矩阵的时候，对校验矩阵进行了高斯消元处理，从而，破坏了原校验矩阵的稀疏性，使得生成矩阵包含大量的“ 1”元素 。一种改进的法是 出的矩阵变换法，该方法的编码处理过程分为两步：即预处理过程和实际编码过程。预处理过程是一个9 离线计算过程，针对一个给定的码字，只需要作一次计算，而实际编码过程是对传输数据的处理。 在 人的矩阵变换算法中，设输入的信息的系统比特部分为 s，通过编码得到的校验比特部分为 错误 !未找到引用源。 和 错误 !未找到引用源。 ，则码字 c = ( s ,错误 !未找到引用源。 ,错误 !未找到引用源。 )，满足 H 错误 !未找到引用源。 =0。对校验矩阵进行行和列的变换，如果能够化成下三角矩阵的形式，则编码的复杂度是线性的。一般来说，通过行列变换是能够将校验矩阵化成如下的近似下三角矩阵的： H= (公式 2该矩阵形状如图 示。 A B O T C D E 将校验矩阵左乘如下矩阵 (公式 2可得到： 0DA (公式 2那么 H 错误 !未找到引用源。 =0 可以分解成如下的两个表达式： T 0 (公式 2( C1A ) D1B )0 (公式 2定义 = D1B ，并且假设非奇异，则求解上面两表达式可得： 错误 !未找到引用源。 = ) (公 式 2图 似下三角校验矩阵形状 10 错误 !未找到引用源。 = T 1( (公式 2通过以上两个公式可以计算校验信息 而得到码字。下面对这种矩阵变换的编码方法的复杂度进行了简单分析，由前面的推导可知，因为系统的信息比特可以直接获得，所以复杂度就集中在了 两个公式的计算上面。 根据 复杂度计算的描述，对于 算的复杂度 估计分别如表 2表 2示。 表 验信息 计算复杂度分析 操作 解释 复杂度 疏矩阵与向量的乘法 O(n) 令 杂度同上 O(n) 令 杂度同上 O(n) 疏矩阵与向量的乘法 O(n) (两个向量的加法运算 O(n) g O(表 验信息 计算复杂度分析 操作 解释 复杂度 稀疏矩阵与向量的乘法 O(n) 稀疏矩阵与向量的乘法 O(n) (+( 两个向量的加法 O(n) (,则得 然是稀疏矩阵与向量的乘法 O(n) 统计两个计算校验信息 复杂度分析表的数据，可以获得矩阵变换方法的编码复杂度 O(n+要想降低编码的复杂度，应该让 g 尽量的小。 11 人在文章中提出三种 法对矩阵的下三角化变换进行了讨论，它们分别是法 A， 法 B 与 法 C，其中， 法 法 法 别表示直接作用于算法 A、 B 和 C 的校验矩阵，而 法 法 表示作用于三种算法的校验矩阵的转置。三种 法可以让 g 尽量减小，从而降低 码的复杂度。 矩阵变换算法的编码过程总结如下： 第一步：预处理过程，输入非奇异校验矩阵，输出形如 等价矩阵，并且保证 为非奇异矩阵。预处理过程中 ,包括矩阵的近似下三角转换和矩阵的秩校验。通过行和列的置换将校验矩阵变换成形如 近似下三角矩阵形式，并通过运用 法让 g 尽量的减小。矩阵的秩校验是利用高斯消完成如下矩阵的运算： 0DA (公式 2 关键是检验矩阵 是否为奇异矩阵，如果是奇异的，那么需要再次进行列置换最终将其变成非奇异形式。 第二步：实际编码过程，当校验矩阵已经化成了形如 非奇异矩阵时，对于给定的输入信息序列 s，只需要通过（公式 2和 (公式 2计算校验信息 可以得到编码输出码字 c=(s, 错误 !未找到引用源。 ,错误 !未找到引用源。 )。 校验矩阵变换编码算法虽然可以使编码复杂度近似呈线性，但是对编码矩阵的原始结构要求比较高，许多矩阵只通过简单的行列置换满足不了该方法的诸多限制条件，因此，应用起来也遇到一定的困难。降低编码复杂度的另外一个有效的方法是设计拥有特殊结构的校验矩阵，比如循环码与准循环码，只通过信息位或校验位数量的移位寄存器就 可以实现此类编码，复杂度低，没有大的编码延迟，与分组长度成线性关系，而且硬件实现也很简单。类循环码已经成为当前研究的一个热点。 12 第 3 章 译码算法 的编码性能以及应用前景取决于信道编码的译码算法。特别是在码长较长的情况下，译码算法的复杂度决定了编码的应用前景。根据线性分组码的基本原理我们知道，译码复杂度与码长呈指数关系，随着码字的增长，译码复杂度将按照指数方式增长。当码长到达一定的长度后，译码的复杂程度就趋于无穷大。但是， 以它的译码复杂度 大大地降低，译码复杂度与码长近似于线性的关系。因此，克服了码字较长时译码算法复杂度高的缺点，使较长码字的应用前景更加宽广。 译码算法简介 在差错控制编码领域的第一个量化飞跃在于意识到了将译码和解调分离开来会带来损失。为了补偿由解调器引入的差错，差错控制编码理论才被提出。在这个思想的指引下，调制解调器首先要判断调制器的输入是什么，然后，将判决结果输入到译码器中；再使用已知的码字结构来判断编码器输入端的码字是什么。这个过程称为“硬”判决译码；但是，它不是最佳的译码方法，因为每执行一次硬判决，解 调器都会丢掉一些可能会有用的信息，而且我们知道，不能在执行完与这个信息有关的所有判决之前，将信息提前丢弃。 将编码和调制相结合，解调器就不会把一些错误传递给译码器。解调器仅仅对各种符号进行短暂的估计，通常被称为“软 判决，这样就不会丢掉一些对译码器来说有用的信息了。“最佳”译码器可以采用 最大后验概率 ) 算法，将误码率 (小化。软判决译码与硬判决译码相比，在性能上，有一定程度的提高。如果采用软判决译码方法，信号的 噪比）相对于硬判决将具有 2优势。 硬判决译码时，采用码字间的 汉明距离最大化原则；而软判决译码，则采用几何距离 ( 欧式距离 ) 最大化的准则。因此，在执行软判决译码时，我们常说针对“信号空间”进行译码。 提出 的同时，也给出了两种迭代译码算法 ：硬判决译码 (法和软判决译码算法。前者的计算复杂度很低，只需要用到模二运算，但是它的译码性能不理想，后者虽然译码性能更好，但它的复杂度太高。对硬判决算法来说，采用信道的软信息对比特翻转的判据进行加权的方法，可以在译码复杂度增加不是很大的情况下，提高译码的性能。 码算法 缩小了与软判决算法之间的差13 距，它的译码性能有了很大的提高。 1996 年， 出了 算法，也叫做 法，它的译码性能要比硬判决译码算法的性能好很多，但它的运算复杂度却不大。 低复杂度情况下的的 码算法作了进一步的研究，提出 码算法，将 码算法进行了简化。为了改善 码算法对校验节点上的简化处理而造成性能上的损失， 出了两种改进算法，第一种：采用归一化的，近 似最佳 法 ( 也叫做 P 法 )； 另一种：以损失可靠性来换取外附信息精度的 小和 ( 译码算法是根据对数域 法而提出的一种近似地简化算法，它用求最小值的运算的方法简化了函数运算，从而，大大降低了运算复杂度，而不需要对信道噪声进行估计，但是它的性能也有一定程度上的降低。 判决译码算法原理 出的 是一种基于规则的稀疏二分图的信道纠错码。一个具有n 个变量节点和 r 个 校验节点的二分图，可以用如下方法，生成对应的维数 k n一 r 的长为 n 的线性码 ：将码字的比特位和变量节点一一对应。二进制域上的矢量x=( ， 满足方程 H*x=0 时，为一个码字，这里的 H 为二分图 r*n 维的关联矩阵，它的列对应于二分图的变量节点，行对应于二分图的校验节点 。也可以说，当每一个校验节点的相连变量节点值的异或为 0 时，其对应的二进矢量 ( ， 为一个码字。 下面，只从二分图的角度来讨论，并且，假设变量节点产生了某种错误。考虑 到变量节点的度为 验节点的度为 量节点，接收到错误的信息比特的概率是 P。采用循环迭代的译码算法，每次进行迭代的时候，首先，由变量节点发送一比特的信息到与其相连的校验节点，然后，校验节点发送一比特的信息到与其相连的变量节点。为了更好地描述译码过程，对于变量节点与校验节点 相连的边 ( , )，图 出了一个描述的相连节点的树。其中，用表示根节点，用的校验节点 ( 除 以外 ) 表示分支节点。以下的译码算法中，我们假设，对小于某一最大次数的迭代来说，的深度是迭代次数的两倍时 ，其相连节点可以用一树描述。即图 的循环的长度没有比迭代次数的两倍要小的。每一个变量节点，存储一个接收比特的硬判决信息 ( 错误概率为 p ) ，每一条边 ( , ) 存储一比特节点的正确信息的猜测值 。这个猜测信息在译码迭代中逐次更新。在每次迭代循环过程中，边 ( , ) 都要双向传递信息。其迭代过程如下所示： （ 1）对所有的边 ( , ) 并行地执行如下操作：如果是第一次进行迭代，令 =则，按照如下方法来计算 ：如果上一次迭代过程中，和节点14 相连 ( 除 以 外 ) 的所有的校验节点发送给 的信息比特都相同的话，那么，就将该值赋给 ，否则的话 =两种情况下，变量节点都把值 发送给校验节点 。 （ 2）对所有边 ( , ) 并行地执行以下操作： 校验节点 ，将其在本次迭代过程中从除之外的其他相连节点收到的信息的异或值发送给变量节点。如果图 没有循环，那么，上述算法在所有的校验都得到满足的时候结束，否则的话，继续进行迭代，一直迭代到超过某一预设的最大迭代次数时才停止，各节点如图 示。 下面直观地解释一下上述算法。节点的某个校验节点 ，将除之外的所有与之相连校验的节点的异或值发送给，这相当于校验节点 ，根据除节点之外的相连节点提供的参与校验的信息，向节点提出要求。为了使该校验约束得到满足，在假设其它节点所提供的信息是正确的条件下，节点应该取它的异或值。但是节点不一定会响应该要求。如果，除 以外所有的校验节点都向节点提出相同的要求，那么，会响应该 要求，并将这个要求的值作为的猜测信息，发送给节点 ，参与到节点 的校验检查中，节点 将利用这条信息和从其它变量节点