非规则LDPC码的局部消环

1、非规那么LDPC码的局部消环论文导读：再保证整个LDPC码的环最大化。个图的围长定义为。该度分布下变量节点的度数为2、3和9。为了讨论方便将上述方法称之为局部消环。围长，非规那么LDPC码的局部消环。关键词：LDPC码，围长，度分布，局部消环1 引言1962年，Gallager在他的博士论文【1】中提出了低密度奇偶校验码其中H正好为该LDPC码对应的校验矩阵。考虑A的平方： 的元素可由如下公式计算： 该式子正好是节点和之间长度为2的路径的个数。因为当时，那么有两条边连接,和。定理1：中(i,j)项的值等于节点到节点长度为n的路径个数。定理2：在一个给定的围长为n的图中，节点和位于某个n环上正好

2、相对的位置3环的消去及局部消环如果某一LDPC码对应的Tanner图需要消去的环被检测到，接下来要做的就是从该图中消去此环。通过交换节点之间的边可以消去检测到的环，但同时必须保证没有新的同等长度或更小长度的环产生。通过交换节点之间的边消去环的另一个好处是并没有改变图中节点的度分布。首先，需要一条在环上的边。定理2中检测环的方法给出了环中相对的两个节点vi和vj。免费论文，围长。免费论文，围长。如果节点vk为环上与vj相邻的节点，那么其与vi的距离必为n/2-1。免费论文，围长。免费论文，围长。因此，有如下式子可以得到vk： 这样就得到环上的一条边e=vjvk。免费论文，围长。接下来需要寻找图中

3、的一条边与该边交换，交换后破坏了此环的同时，没有生成同等长度的和更小长度的环。定义Ce为所有与边e长度大于等于n-1长的节点的集合。那么该集合包含的节点是满足式子的节点的集合。随机取一条两个节点都在Ce中的图中的一条边e。如果不存在这样的边，那么边e不能通过交换节点之间的边从该环中去除而不产生新的长度相等或更小的环，那么需要选择环中另外一条边。假设e的两个端点为vl和vm。图2表示删掉边e和e，生成边。 图2 节点vj,vk,vl和vm之间边的交换 定理 3：用边e2和e2取代边e和e将消去边e和e所在的n环，并且同时没有生成新的小于n或等于n的新环。(定理1、2和3在文献【6】中有详细证明过

4、程)以上为如何通过交换节点之间的边来消去检测到的需要消去的环。接下来要解决的问题就是如何通过该方法首先保证度数低的节点之间的环的长度最大化，再保证整个LDPC码的环的最大化。我们可以通过如下两个方案完成局部消环。方案一：令H=,其中Hh由校验矩阵H中度数高的节点组成。Hl由校验矩阵H中度数高的节点组成。 因为最正确度分布中校验节点的度数根本不变，所以这里指的度数上下只针对于变量节点。首先根据(7)式寻找一条边e，然后按(8)式寻找集合Ce，在Ce中随机选取一条边，再按图1所示交换这两条边所在节点之间的边，使Hl局部中短环尽量的消去。然后消去H中的短环，在这个过程中通过(10)式选取的环上的一条

5、边和Ce中节点的选择都限制在Hh中，这样我们就没有改变Hl中的边，从而使H中的短环消去的同时保证Hl没有改变。免费论文，围长。方案二：如方案一，同样先尽可能大的消去Hl中的短环。假设经过消环后，Hl中的最小环长为m。从四环开始，根据(10)式选取环上的一条边e。接下来选取Ce，将(11)式修改为，在Ce中随机取一条边e。然后按图2交换e和e节点之间的边。由定理3可知交换后不会产生小于或等于m的环。通过这个步骤就消去了4环，同时没有产生小于或等于m的环。重复上述步骤，消去6、8,直到m-2环。方案一和方案二都可以完成局部消环。实际运行中，方案一的可行性远远高于方案二，效果也比方案二好。4 仿真结

6、果及讨论为了验证局部消环相比于只简单的整体消环方法的更优性能，本文给出了局部消环和整体消环在相同码长、AWGN信道条件下，用BP算法迭代译码的误码率、误帧率仿真结果图。图3 分别通过局部消环和整体消环构造的码长为1000、码率1/2的LDPC码性能比拟图3中的码码率都为1/2，码长为1000。LR-part和LR-whole的度分布为文献【3】中给出的最大变量节点为9时的最正确度分布。该度分布下变量节点的度数为2、3和9。我们将2和3看成低度数，9看成高度数。LR-part码为方案一局部消环后的码，其中度2和3之间的最小环长为12，整体环长为6。LR-whole为只整体消环的码，其中整体环长为

7、8。图3的码最大迭代次数都为80。仿真结果说明，我们通过局部消环的矩阵由于优先保证了度数小的节点之间环的最大化，而比直接整体消环所构造出的LDPC码译码性能要高。5 结论直接构造出不包含短环的LDPC码是困难的。本文讨论了一种首先随机生成一给定度分布下的LDPC码，然后通过交换节点之间的边的方法，先最大可能地消去度数低的节点之间的短环，然后在保证度数低的节点之间最小环不变的情况下最大可能地消去整个LDPC码中短环的方案。由于该方法在消去LDPC码短环的同时并没有改变该LDPC码对应的Tanner图中节点的度分布，从而得到一个不包含短环而度分布确定的LDPC码。该方法尽最大可能降低了环对降低LD

8、PC码译码性能的影响。仿真结果说明，该方法相比于只简单的从整体上消去短环构造的LDPC码更好地改善了LDPC码的性能。算法1： 校验矩阵H的局部消环。1 B=H中度数低的节点构成的局部2 C=H中度数高的节点构成的局部3 B1=对B消环4 H1=5 A=6 n=47 由(7)选取一条边e，并且该边在H1中度数高的节点之间8 由(8)式选取集合Ce9 Ee=所有Ce中节点组成的H1的边，并且这些边的变量节点属于度数高的局部10 如果Ee不空，交换e和e，更新H1和A11 n=n+212 重复7-11，直到没有可以交换的边参考文献：【1】R. G. Gallager, Low-Density Pa

9、rity-Check Codes. Cambridge, MA:MIT Press, 1963.【2】D. J. C. MacKay and R. M. Neal, Near-Shannon-limitperformance of low density parity check codes ; Electron. Lett., vol. 32,Aug. 1996: 1645-1646.【4】赵岭,张晓林,朱曼洁,一种用于规那么QC-LDPC码的高效译码方法2007 33(09):64-65【5】J. Pearl, ProbabilisticReasoning in Intelligent Systems: Networks of Plausible Inference. San Francisco, CA: Morgan