【 摘 要 】 LDPC码是性能限与香农限仅差0.0045dB的一种差错控制码，译码采用SPA（和积算法），其性能受Tanner图中回路长度和回路数目的影响，回路的存在使译码信息重复迭代，性能下降。论文通过计算机仿真，采用Matlab元胞数组，将二元校验矩阵转换为截断树矩阵，实现了求解LDPC码回路的算法，既给出回路的长度，又能得出回路的分支路径，并且能够对所有回路作整体性的描述。
【 关键词 】 LDPC；截断；树；回路
【 Abstract 】 LDPC codes are defined by their sparse parity-check matrices and can be described by bipartite graphs called Tanner graphs. Loops in Tanner graph prevent the sum-product algorithm from converging. Further， loops， especially short loops， degrade the performance of LDPC decoder， because they affect the independence of the extrinsic information exchanged in the iterative decoding. This paper， by graph theory， deduces cut-node tree graph of LDPC code， and depicts it with matrix. On the basis of tree matrix algorithm， whole depictions of loops can be figured out， providing of foundation for further research of relations between loops and LDPC codes’ performance.
【 Keywords 】 ldpc； graph； loop； cycle
1 引言
LDPC （Low-density Parity-check，低密度奇偶校验）码是由 Gallager 在1963 年提出的一类具有稀疏校验矩阵的线性分组码 （Linear Block Codes），然而在接下来的 30 年来由于计算能力的不足，它一直被人们忽视。1993年，D MacKay、M Neal 等人对它重新进行了研究，发现 LDPC 码具有逼近香农限的优异性能，并且具有译码复杂度低、可并行译码以及译码错误的可检测性等特点，从而成为了信道编码理论新的研究热点。
好的图码模型具有实际上可以实现的复杂度的近优译码算法。性能好的LDPC码的Tanner图中没有太多的回路，只是具有较长的最短回路并不一定是好的LDPC码。码的正则性也是影响LDPC码的一个重要因素，不规则的LDPC码一般相比规则的LDPC有较好的性能。
因LDPC码的译码采用迭代译码，其原理是节点间传递的信息统计独立，当LDPC码的校验矩阵对应的Tanner图有回路存在时，某一节点发出的信息经过回路后会被传回本身，从而造成自身信息的重复，影响算法的收敛性，也影响译码的准确性。
2 图论基础知识
无向图G（V，E），其中有限非空子集V是顶点集，有限非空子集E是边集，且E是有成对的子集{{u，v}：u，v∈V，u≠v}
V = { 1， 2， 3， 4， 5， 6}
E = { {1，2}， {1，5}，{3，4}， {2，5}， {5，6} }
n = 6
m = 5
图G（V，E）中一条长度为n的路径就是一个节点序列v1，v2，…，vn，vn+1，vi∈V，i=1，2，…，n，n+1并且对于i∈[1，n]都有{vi，vi+1}∈E，如果vi+1和vi相同，并且对于任意的i≠j∈[1，n]，有vi≠vj，则是一条长n的回路。如果图G没有回路，则G为树。
若 G （V， E ） 为无向图，则下面叙述等价：
（1） G 是树；
（2） G中任意两个节点由唯一的一条路径相连接；
（3） G 是连通的，但去除任意一条边后不再连通；
（4） G连通，且| E | = | V | -1；
（5） G中无回路且| E | = | V | -1；
（6） G中无回路，但是任增加一条边，则会出现回路。
若G （V， E ）是一个无向图，如果顶点集V可分割为两个互不相交的子集（A，B），并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集（i∈A，j∈B），则称图G为一个二分图。
因此对于Tanner图中回路的求解，实质上是二分图中的回路的求解问题。树是连通的没有任何回路的二分图，叶节点是度为1的节点，树中的内部节点是一个度最少是2的节点。
3 截断节点树原理
利用树求解Tanner图中的回路，其原理是这样的，比如对于校验矩阵H为：
H= 1 0 1 0 1 0 1 0
1 0 0 1 0 1 0 1
0 1 1 0 0 1 1 0
0 1 0 1 1 0 0 1
（1）选定一个码字节点或校验节点为根节点，比如校验节点C1 。
（2）从这个根节点C1出发，选取和其连接的节点并用边相连接，如上图为x1，x3，x5，x7 。 （3）再从这些节点出发，选取和它们连接的节点。
（4）如果节点不能再生长出新的节点或者在以前的树枝中出现过，则终止生长。我们统称之为端节点，并把不再生长的节点称为叶，而把前面树生长的过程中已经出现强行截断的节点为截断节点，也就是说端节点包括叶和截断节点。
（5）对于既不是叶也不是截断节点的节点，继续（3）。如果最终所有的端节点都是叶或截断节点，则停止生长。
把按上述方法得到的LDPC码的树称为码树。
我们把最先选择的节点称为根节点，从根节点长出的树枝的端点称为1级节点，也称为根节点的子节点，而1级节点也称为2级节点的父节点，依次类推，直到端节点，如果两个节点是由同一个节点所生成，那么我们称此节点为干节点，并且按照标号由小到大的顺序定义节点的级别。由级别高到低的顺序，选择节点，凡在树中出现至少两次的节点即为Tanner图中的一个回路，这时因为在上面的树生成的过程中，节点的第二次或更多次出现必然是截断节点，这样按照上述办法可以得到上例中的回路。
如果按节点级别排列这些环，并除去相同的环，那么就可以得到LDPC码Tanner图中的所有回路。由于上面的树图中，包含了所有的节点，称这样的图为连通图或单树，否则称为森林。
由上作树图方法可以看出公理或结论。
（1）除根节点外，一个节点有且只有一个父节点。
（2）叶是度数为1的节点，端节点全为叶而无截断节点的树没有回路。
（3）在树图中，除截断节点外，每个节点连接的边数即为节点的度。
（4）按上面方法，得到的一定是森林（多树），不一定是单树（即连通图）。
（5）对于多树的情况，如果在两个树上任意选择两个节点（不同类型）相连，对应于H中增加一个“1”，则森林的树目的个数少1，且没有任何新的回路增加。
这里，下面凡未特别提及，我们只讨论连通图的情况。
引理：由树图可恢复出Tanner图，从而可以得到校验矩阵H。
证明：根据上面作树图的方法知道，所有节点都将出现一次（除非它还是截断节点，意味着该节点在前面已经出现过），同时它也表示除了它的度和它的邻节点，如果按照Tanner图的方式，进行描述，将恢复出原来的图，并可以得到H。
定理1：回路中包含至少一个截断节点。
证明：截断端点的出现必然意味着节点的重复出现，又由于它们是树上的不同的分支，所以，那么必定有回路的出现。
定理2：对于连通图，树图中包含了Tanner图中的所有回路。
由引理很容易得到定理的结果，证明在此略去。
定理3：如果一个节点在树图中总共出现n次，那么此节点出现在Cn2个不同的回路中。
证明：n中选取2个，总共有Pn2种选法，由于回路没有方向，每个节点都将重复一次，显然不同回路的数目是Pn2/2=Cn2。
如果一个节点两次出现，且它们距最近的祖先节点分别为h1和h2，则存在一个长度为h=h1+h2的回路，并且这个祖先节点也处于这个回路中，由于h为偶数，h1、h2奇偶性相同。
由树图方法可以看出，每个回路中包含至少一个截断端点。因为截断端点的出现必然意味着节点的重复，又由于它们是树上的不同的分支，所以，那么必定有回路的出现。且如果一个节点在这样的树图中总共出现n次，那么此节点出现在Cn2个不同的回路中。
循着这样的原理，本论文通过Matlab仿真，实现求解LDPC码回路的算法如下图6。
仿真实现与结果：
对于校验矩阵为H=[1 0 1 0 1 0 1 0；1 0 0 1 0 1 0 1；0 1 1 0 0 1 1 0；0 1 0 1 1 0 0 1]，可以得到如下的树矩阵T，并采用matlab的元胞数组进行描述：
[1 1 0 0] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
[1 1 1 1] [1 3 1 1] [1 5 1 1] [1 7 1 1 1] [ ] [ ] [ ] [ ] [ ]
[2 1 1 1] [3 3 1 3 1 1][4 5 1 5 1 1 1] [3 7 1 7 1 1] [ ]
[ ] [ ] [ ] [ ]
[2 4 2 1 1][2 6 2 1 1][2 8 2 1 1] [3 2 3 3 1] [3 6 3 3 1] [3 7 3 3 1] [4 2 4 5 1] [4 4 4 5 1] [4 8 4 5 1]
[4 4 2 4 1 1 1] [3 6 2 6 1 1] [4 8 2 8 1 1 1] [4 2 3 2 1 1 1] [ ]
[ ] [ ] [ ] [ ]
其中树矩阵T中的元素Tij的前两个值Tij（1，2）描述当前节点，随后的两个值Tij（3，4）表明当前节点的父节点，父节点唯一，接续的值为1，1的个数表示此节点被截断次数，空矩阵表示无节点。由T可知，H的3行7列的（3，7）节点被截断1次，它存在于1个回路中，同理（4，2）节点被截断3次，存在于3个不同的回路中，依次类推。从而可以得到回路如下：
回路1：截断节点（3，7）—（1，7）—（1，1）—（1，3）—（3，3）；
回路2：截断节点（3，6）—（3，3）—（1，3）—（1，1）—（2，1）—（2，6）；
回路3：截断节点（3，7）—（3，3）—（1，3）—（1，1）—（1，7）；
回路4：截断节点（4，2）—（4，5）—（1，5）—（1，1）—（1，3）—（3，3）—（3，2）；回路5：截断节点（4，4）—（4，5）—（1，5）—（1，1）—（2，1）—（2，4）；
回路6：截断节点（4，8）—（4，5）—（1，5）—（1，1）—（2，1）—（2，8）；
回路7：截断节点（4，4）—（2，4）—（2，1）—（1，1）—（1，5）—（4，5）；
回路8：截断节点（3，6）—（2，6）—（2，1）—（1，1）—（1，3）—（3，3）；
回路9：截断节点（3，6）—（2，6）—（2，1）—（1，1）—（1，7）—（3，7）；
回路10：截断节点（4，8）—（2，8）—（2，1）—（1，1）—（1，5）—（4，5）；
回路11：截断节点（4，8）—（2，8）—（2，4）—（4，4）；
回路12：截断节点（4，2）—（3，2）—（3，3）—（1，3）—（1，1）—（1，5）—（4，5）；
回路13：截断节点（4，2）—（3，2）—（3，3）—（1，3）—（1，1）—（2，1）—（2，4）—（4，4）；
回路14：截断节点（4，2）—（3，2）—（3，3）—（1，3）—（1，1）—（2，1）—（2，8）—（4，8）。
通过对回路的重新排序容易找出重复出现的回路，排序规则如下：选择回路中节点（m，n），m+n值最小的为排序第一个节点，如果有多个节点m+n的值最小且相等，则选择m值小的优先，其次选择余下节点n值小的节点为排序第二个接点，然后按回路。由上面结果：回路1等价于回路3，回路2等价回路8，回路4等价回路10，回路5等价回路7，回路6等价回路9。由于截断的次序，它们的出现只是方向不同而已，重新排序后一样。也就是说其中的回路只有回路1（3）、2（8）、4（12）、5（7）、6（10）、9、11、13、14， 其回路的长度分别为4、6、6、6、6、6、4、8、8。但由于H的复杂性，需要注意的下面几点：
HE为结束标志矩阵，初始值为H，在生长的过程中，被找到的节点H中对应HE的节点置0。如果H为连通的，则为单个的截断树矩阵，HE元素全为零，即为结束标志。否则为多树，此时对每次不再生长后的HE，作为新的矩阵，按上面方法重求截断树矩阵，形成迭代运算，直到最终HE的元素全为0。
4 结束语
求解校验矩阵的回路是个复杂的过程，特别对于大型的H矩，而且对于回路缠绕情况下有待给出更明确的定义。本文利用Matlab的元胞数组，把Tanner转换为图论中的截断树，并且利用Matlab将截断树表示为元胞矩阵，以矩阵的形式表述树，从而给出了求解LDPC码Tanner图中的回路的算法，并通过计算机进行仿真。仿真结果对于分析回路和性能之间的关系奠定了基础。
参考文献
[1] R. G. Gallager， Low-Density Parity Check Codes， MIT Press， Cambridge， MA， 1963.
[2] D. J. C. Mackay， "Good Error-Correcting Codes Based on Very Sparse Matrices"， IEEE Trans. Inform. Theory， vol. 45， Mar. 1999.
作者简介：
张焕明（1970-），男，河南辉县人，研究生，讲师；主要研究方向和关注领域：通信与信息系统。
中国论文网(www.lunwen.net.cn)免费学术期刊论文发表,目录,论文查重入口,本科毕业论文怎么写,职称论文范文,论文摘要,论文文献资料,毕业论文格式,论文检测降重服务。
