第 33 卷 第 9 期 Vol.33 No.9 ·软件技术与数据库· 计 算 机 工 程 Computer Engineering 文章编号：1000—3428(2007)09—0064—02 2007 年 5 月 May 2007 文献标识码：A 中图分类号：TP311 LDPC 码的树图理论 张焕明，叶 梧，冯穗力 （华南理工大学电子与信息学院，广州 510640） 摘 要：LDPC 码译码采用的是 BP 算法，但由于回路的存在，使译码重复迭代，特别是短长度的回路使 LDPC 码的性能下降，因此用树 图法分析了 LDPC 码的回路及其特性，给出了码回路的求解方法，非常适合于计算机进行求解，同时也给出了 LDPC 码回路所经过的节点 及长度。 关键词：LDPC 码；Tanner 图；回路；度 Theory of LDPC Code’s Tree Graph ZHANG Huanming, YE Wu, FENG Suili (School of Electronic & Information, South China University of Technology, Guangzhou 510640) 【Abstract】Belief-propagation algorithm is taken in LDPC code’s decoding method, but small loops degrade the code’s performance. This paper analyzes the theory of LDPC code’s loop by tree graph and gives out the method to calculate all loops. 【Key words】LDPC code; Tanner graph; Loop; Degree 1 LDPC 码简介 LDPC(Low Density Parity Check)码[1]是一种具有稀疏校 验矩阵的分组纠错码，其性能逼近香农限，描述和实现简单， 易于进行理论分析，译码简单且可实行并行操作，适合硬件 实现[3]。 LDPC 码可以用奇偶校验矩阵 H 来表示，和所有的线性 分组码一样，域 F 上的 N、K 维的编码 C 可用(N-K)*N 的校 验矩阵 H 来描述：C={ｘ∈Fn|ｘHT=0}。因 H 稀疏，能实现 低复杂度的编译码。同时也可以用二分图来表示，一个二分 图是一个包括两个顶点集合的图，分别是信息节点集合和校 验节点集合。若某个校验约束方程中出现了某个码字比特， 则在相应的的信息节点和校验节点之间出现了连边，也对应 着相应的 H 阵中的元素 1。 LDPC 码的译码方法为 BP(可信度传播)算法，也叫和积 算法(SPA)，和 Turbo 码的译码方法一样，也是一种迭代算法。 影响 LDPC 码译码性能的因素有 2 个：(1)校验矩阵的稀疏度； (2)校验矩阵对应 Tanner 图中回路的长度和数量，回路的长度 越短，短回路的数量越多，那么 LDPC 码的性能越差[2]。 2 LDPC 码回路的树图法描述 Tanner 采用二部图表示 LDPC 码，这种二部图称作 Tanner 图。比如对于校验矩阵为 1 0 1 0 11 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 1 1 ⎡ ⎢ 1 ⎢ 0 ⎢ ⎢ 0 ⎣ H = 0 1 0 1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ (1) 的 LDPC 码，则其对应的 Tanner 图如图 1 所示。 Z1 Z2 Z3 Z4 x1 x2 x3 x4 x5 x6 x7 图 1 低密度校验码的 Tanner 图 x8 把 和 节 点 相连 的边 的数 目 称 为 节 点的 度(degree)， 而 —64— Tanner 图中节点的度的分布可以用度分布多项式 λ(x)和 ρ(x) 来描述： ( ) ∑ x λ (2) d x 1λ − = vd d 1 d = cd ( ) ∑ x ρ = d 1 = (3) d d x 1ρ − 其中，λ(d)、ρ(d)分别为度为 d 的码字节点和校验节点所占总 节点的比例，dv、dc 分别为码字节点合校验节点度数最大值。 为了求解 Tanner 图中的回路，可以用树[7]进行分析，其 原理是这样的：(1)选定一个码字节点或校验节点为根节点， 如节点 Z1；(2)从这个根节点 Z1 出发，选取和其连接的节点 并用边相连接，如上图为 X1、X3、X5、X7；(3)再从这些节点 出发，选取和它们连接的节点；(4)如果节点不能再生长出新 的节点或者在以前的树枝中出现过，则终止生长，统称之为 端节点，并把这两类节点分别称为叶和截断节点；(5)否则， 继续(3)；(6)直到所有的节点都终止。 按上述方法，可画出上例以 Z1 为根节点的树图如图 2。 Z1 x3 Z3 x6 x7 x2 x5 Z4 x4 x8 x1 Z2 x6 Z3 x4 Z4 x8 Z4 x2 Z4 图 2 回路计算的树图法原理 x7 Z3 这样，把最先选择的节点称为根节点，如图 2 中的节点 Z1，从根节点长出的树枝的端点称为 1 级节点，也称为根节 点的子节点，而 1 级节点也称为 2 级节点的父节点，依次类 作者简介：张焕明(1970－)，男，讲师、博士生，主研方向：通信与 信息系统中的纠错编码；叶 梧、冯穗力，博导、教授 收稿日期：2006-06-11 E-mail：huanmingzhang@tom.com 

推，直到端节点，如果两个节点是由同一个节点所生成，那 么称此节点为干节点。并且，按照标号由小到大的顺序定义 节点的级别。由级别高到低的顺序，选择节点，凡在树中出 现至少两次的节点即为 Tanner 图中的一个回路，这样按照上 述办法可以得到上例中的回路为 9 个。 也就是说，在节点 Z1 为根节点的树图中，有 9 个不同的 回路。按照相同的原理，可以求出把其他节点作为根节点的 回路，再按节点级别排列这些环，并除去相同的环，那么就 可以得到 LDPC 码 Tanner 图中的所有回路。上面的树图中， 包含了所有的节点，称这样的图为连通图。下面凡未特别提 及，只讨论连通的情况。由上作树图方法可以看出以下公理： (1)除根节点外，一个节点有且只有一个父节点。(2)端节点全 为叶的树没有回路。(3)在树图中，除截断节点外，每个节点 连接的边数即为节点的度。 引理 由树图可恢复出 Tanner 图，从而可以得到校验矩 阵 H。 证明 根据上面作树图的方法知道，所有节点都将出现一 次(除非它还是截断节点)，同时它也表示除了它的度和它的 邻节点，如果按照 Tanner 图的方式重新描述，将恢复出原来 的图，并可以得到 H。 定理 1 回路中包含至少一个截断节点。 证明 截断端点的出现必然意味着节点的重复出现，又因 为它们是树上的不同的分支，所以必定有回路的出现。 定理 2 对于连通图，树图中包含了 Tanner 图中的所有回 路。由引理很容易得到定理的结果，证明在此略去。 定理 3 如果一个节点在树图中总共出现 n 次，那么此节 点出现在 2 nC 个不同的回路中。 C 2 n 方向，每个节点都将重复一次，显然不同回路的数目是 = P 2 2/ n 如果一个节点两次出现，并且它们有相同的干节点，一 个距离干节点为 h1，另一个为 h2，则存在一个长度为 h= h1+h2 的回路，并且干节点也为回路的一个节点，h 为偶数，h1、h2 同为奇数或同为偶数。 3 结论 回路的多少和最短回路长度是影响 LDPC 码性能的重要 因素，本文分析了回路的特点，利用树图方法，可以得到 LDPC 码的全部回路，包括回路的长度和路径。树图分析方 法对 LDPC 码的研究和发展有重要的理论意义。 参考文献 1 Gallager R G. Low Density Parity Check Codes[M]. MA: MIT Press, 1963. 2 Gowan J A, Williamson R C. Loop Removal from LDPC Codes[C]//Proc. of Information Theory Workshop. 2003: 230. 3 Kay D J C. Good Error-correcting Codes Based on Very Sparse Matrices[J]. IEEE Transactions on Information Theory, 1999, 45(2) 399-431. 4 Luby M G, Amin S M, Mizenmacher M, et al. Improved low-density Parity-check Codes Using Irregular Graphs and Belief Propagation[C] //Proceedings of IEEE International Symposium on Information Theory. 1998-08-16: 117. 5 Kay D J C, Neal R M. Near Shannon Limit Performance of Low Density Parity Check Codes[J]. Electronics Letters, 1997, 33(6): 457. 6 Richardson T J, Shokrollahi M A, Urbanke R L. Design of Capacity-approaching Irregular Low-density Parity-check Codes[J]. IEEE Transactions on Information Theory, 2001, 47(2): 619-637. 7 Reinhard D. Graph Theory[M]. New York: Springer-Verlag, 证明 n 中选取 2 个，总共有 2 nP 种选法，由于回路没有 1997. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ （上接第 24 页） 表 4 函数 f2 的比较结果 EGA AGA 极值点 最优值 阻滞 次数 全局解 最优值 阻滞 次数 -1.008, -1.211, -19.868, 19.963, -19.327 -1.249, 0.938, 19.617, -19.264, 19.592 1.025,-1.186, -19.639, 19.452, 19.644 0.606, 1.456, -19.919, 19.783, -19.267 1.007 2 0 -0.033,-1.568, -19.744,18.926,-1 9.996 1.007 0 1.007 1 1.007 2 0 0 0 -1.408, 0.686, 18.647,18.900, 18.234 0.109, -1.563, 19.117,19.422, 19.917 0.980, 1.250, 17.489,19.657, -19.960 1.007 1 1.006 2 1.007 0 1.006 4 0 0 0 0 全 局 解 集 1 2 3 4 3.2 收敛速度和效果的理论分析 实验表明 EGA 往往能在相同的搜索时间内获得比其他 次数内保证了对重点区域的搜索，提高了搜索效率和精度， 进一步缩短了整体的搜索时间。 (3)对搜索空间的划分排除了不必要的干扰，使适应值高 的解更容易被重复搜索，提高了算法的搜索能力。 4 结论 根据相关理论(见第 1 节)，本文提出了基于搜索空间探 索信息的遗传算法 EGA，实验证明在同等计算量的情况下， 本算法确能提高对全局最优解和好的局部最优解的搜寻效率 和精度，还能尽可能多地得到全局和局部最优解以及其它搜 索空间的有效信息。同时，对算法的优势进行了理论分析和 实验验证。 参考文献 1 李敏强, 寇纪淞, 林 丹, 等. 遗传算法的基本理论与应用[M]. 北京: 科学出版社, 2002. 2 张文修, 梁 怡. 遗传算法的数学基础[M]. 西安: 西安交通大学 遗传算法更好的结果。分析其原因如下： 出版社, 2000. (1)搜索子空间成倍的减小，导致每次搜索的收敛时间减 3 Alden H W, Christopher R S. Bistability in a Gene Pool GA with 少，部分抵消了搜索空间数目增加的影响。 (2)由于采用依概率的方式选取待搜索子空间，在有限的 Mutation[M]. Morgan Kaufmann, 2003. 4 姬振豫. 正交设计的方法与理论[M]. 香港: 世界科技出版社, 2001. —65—