码率自由且低误码平台QC－LDPC码的设计

易 丹

（武汉交通职业学院，湖北 武汉 430065）

0 引言

低密度奇偶校验（LDPC）码最先被Gallager发明，由于当时计算机条件的限制，没有引起人们的关注。后来在上个世纪九十年代初被MacKey等重新发现，他们通过系统仿真发现LDPC码的性能超过以前发现的各种编码，比Turbo码更接近香农限，因此引起了通信研究者的极大关注，现在已经成为编码领域一项热门的研究方向。Thmos J．Richardson等提出了采用密度进化算法优化非规则LDPC的度分布对［1］，HuXiaoYu等提出了采用PEG算法增大校验矩阵的围长［2］，Tao Tian等提出了采用ACE算法增大校验矩阵中环之间的连通性［3］，虽然这些算法可以提高非规则LDPC的性能，降低它的误码平台，但是由它们设计出来的非规则LDPC不易硬件实现。随后，2005年，Seho Myung等提出了一种易于硬件实现的高性能的QC－LDPC，使得LDPC的硬件应用成为可能［4］，现在这种结构化QC－LDPC已经被IEEE802．16e和IEEE802．11n推荐采用。但是，Seho Myung等没有提出任意码率QC－LDPC的设计方法。本文提出了一种任意码率QCLDPC的设计方法，编码复杂度和IEEE802．16e相同，但是误码平台更低。

1 易于硬件实现的QC－LDPC码的结构

Seho Myung，Kyeongcheol提出了一种结构化的QC－LDPC码［5］，这种LDPC码编码复杂度和编码码长呈线性关系，并且在译码过程中可以并行执行并节省存储空间，所以非常适合于硬件实现。另外，仿真结果显示这种LDPC码的性能优良。它的校验矩阵H的结构如下式（1）所示。

校验矩阵包含两部分：结构自由的H1和结构相对固定的HP。假设H有M行N列，QC－LDPC码的码率R＝M／N，则要求HP有M行和M列，其中度为2的列数为M－1，度为3的列数为1。HP所占的列数决定了QC－LDPC码得码率大小，这种结构化的设计可以使这种QC－LDPC码的编码复杂度和编码长度呈线性关系。HP中的I表示一个大小为［L，L］的单位矩阵；0表示大小为［L，L］的零矩阵；Px表示一个单位置换序列，这个序列是通过将I循环右移x次得到。

2 码率自由且低误码平台的QC－LDPC码的设计

设计结构化QC－LDPC码的一般步骤是：首先通过密度进化算法得到一个好的度分布对，然后根据这个度分布对搜索到围长尽量大的校验母矩阵，最后使用大小为［L，L］的单位矩阵、0矩阵或者Px填充校验母矩阵。在这个过程中H的度分布由码率的大小决定，同时，度分布对的好坏，校验矩阵的最小围长（girth）以及环之间的连通性决定最后得到的QC－LDPC码的性能。所以本文通过优化度分布对、最小围长以及环之间的连通性来得到码率自由且低误码平台的QC－LDPC码。

2．1 改进的密度进化算法

原始的密度进化算法复杂度非常高，并且只给出了非规则LDPC的度分布对的求法［6］。但是我们需要高效率的优化结构化QC－LDPC的度分布对，所以我们需要改进原有的密度进化算法，使得它的计算复杂度降低，并且更重要的是能够优化结构化QC－LDPC的度分布对。首先，我们采用高斯近似（Gaussian Approximation）来求给定度分布对的门限值。高斯近似是文献［1］提出的门限值求法的一种近似，可以大大的节省计算时间，但是精度的损失却很小。然后使用差分进化（Differential Evolution）完成全局搜索，得到门限值最大的那个度分布对［7］。这里我们需要改进差分进化的全局约束条件，使优化的度分布对满足结构化QC－LDPC校验矩阵的要求。Seho Myung，Kyeongcheol等提出的全局约束条件［8］仅包含下面的式（2）－（4）。

dv（dc）表示变量（校验）节点的最大的度。λi（ρj）代表从变量（校验）节点i（j）发出的边占Tanner图中所有的边的比例。除此了上面三个约束条件外，本文通过分析HP的结构，还提出了其它的两条约束条件，如下面的式（5）、（6）所示。

Pv2表示度为2的变量节点在所有变量节点中所占的比例，Pv3表示度为3的变量节点在所有变量节点中所占的比例。添加这两个全局搜索的约束条件后，可以使优化后的度分布对满足H的要求。在第四部分的仿真结果中，我们列出了改进的密度进化算法得到的四组不同码率的度分布对。

2．2 改进后的PEG算法

在校验母矩阵设计过程中，要求母矩阵包含的短环尽量少，最小围长尽量大，这样可以使最后的校验矩阵的围长较大［9］。Hu XiaoYu提出了一种应用于非规则LDPC码的PEG算法，这个算法主要的思想是按照度分布对，通过依次在校验节点和变量节点之间添加边连接，每次新边的位置要求使Tanner图的围长达到最大［10］，最后得到大围长的校验矩阵。我们可以使用PEG算法简单快速的得到校验母矩阵，但是PEG算法不能直接应用于结构化QC－LDPC，这里需要将PEG算法做出改进。由于校验矩阵中只有HP部分的结构固定，所以改进后的PEG算法首先按照度分布对要求生成HP，然后使用原来的PEG算法生成H1即可。改进后的PEG算法如下所示。

改进后的PEG算法：

2．3 实施增大围长和ACE约束

TaoTian等学者发现，LDPC码的性能不仅受环长的影响，而且也受到环之间的连通性的影响［11］。有可能一个LDPC码的Tanner图中包含比较多的短环，但是这些短环之间的连通性良好，从而导致这个LDPC码的纠错性能没有预期的那么差。环之间的连通性使用ACE值来表示，一个长为2l的环的ACE值为，其中di表示此环中第i个变量节点的度。度为d的单个变量节点的ACE值为d－2，单个校验节点的ACE值为0。当使用置换序列填充校验母矩阵时，我们在使校验矩阵的围长尽量大的同时，也要使环之间的ACE尽量大，特别是那些度为2和3组成的环。所以在置换序列填充校验母矩阵的时候，不仅要考虑使用文献［4］中的方法尽量增大H的围长，并且也要使用文献［3］的方法消除那些ACE值非常小的关键环。我们使用图1和2来说明这些关键环在H中的分布。两图取自H的一个片段，包含部分的H1和全部的Hp。图1中使用实线勾画出了两个环，环长分别为8和4，它们是由度为2、3的变量节点形成的环，ACE值都为2。图2也使用实线勾画出两个环，环长分别为10和6。它们是由度为2、3的变量节点形成的环，ACE值也为2。

图1 环长为8和4的关键环

图2 长为10和6的关键环

由于这些环的ACE值特别小，只有2，所以它们与其它环的连通性很差，在译码过程中这些环容易产生错误不可纠的情况，所以我们在随机产生Px填充校验母矩阵时应该消除这些关键环。根据文献［2］，如果图1和2中长为的环被置换序列填充后形成的链条，当10modL时则可以消除这些关键环。

3 仿真结果

3．1 好的度分布对

表1 四种不同码率的好的度分布对

表1是通过改进后的密度进化算法，搜索到1／2、2／3、3／4、5／6四种不同码率的好的度分布对，并计算它们对应的门限值。从下表我们可以看到这些门限值非常接近香农限。在搜索过程中，我们设定［M，N］分别为［12，24］、［8，24］、［6，24］和［4，24］。

3．2 性能对比

为了比较使用本文方法设计的QC－LDPC码和IEEE802，16e中QC－LDPC码的性能，我们分别设计码率为1／2、2／3、3／4、5／6，码长为2304的四种QC－LDPC码。仿真的信道为二进制输入加性高斯白噪声（Binary－InputAdditiveWhite－GaussianNoise，BIAWGN）信道，译码方法为BP译码算法，迭代次数为50次，曲线上的每个点的仿真帧数为30000帧。从图3我们可以看到，采用本文提出的方法设计的QC－LDPC码的误码平台更低，并且当码率越小时，这种优势越明显。

图3 提出的QC－LDPC码与IEEE802．16e中的QC－LDPC码的性能对比

4 结束语

本文改进了密度进化算法和PEG算法，使它们能够应用于结构化QC－LDPC中，可以生成高性能、码率自由的可硬件实现LDPC码。并且在填充校验母矩阵过程中实施增大围长和ACE的约束，使得QC－LDPC码的误码平台降低，性能优于IEEE802．16e中的QC－LDPC码。本文提出的设计方法可以应用在无线通信系统中，提高通信系统的抗干扰性。

［1］［6］Thmos J．Richardson，M．Amin Shokrollahi，Rüdiger L．Urbanke．Density of Capacity－Appro aching Irregular Low－Density Parity－Check Co des［J］．IEEE Transaction on Information Theory，2001，（2）：619－637．

［2］［10］Hu XiaoYu，E．ELEFTHERIOU，D．－M．Arn old．Irregular Progressive Edge－Growth（PEG）Tanner Graphs［C］／／Proceeding of ISIT．Lausanne，Switzerland：IEEE，2002：480－480．

［3］［11］Tao Tian，Christopher R．Jones，John D．Vill asenor，et al．Selective Avoidance of Cycles in Irregu lar LDPC Code Construction［J］．IEEE Transaction on Communication，2004，（8）：1242－1247．

［4］［5］［9］Seho Myung，Kyeongcheol Yang．Quasi－Cyclic LDPC Codes for Fast Encoding［J］．IEEE Transaction on Information Theory，2005，（8）：2894－2901．

［7］Vitaliy Feoktistov，Stefan Janaqi．Generalization of the Strategies in Differential Evolution［C］／／Proceeding of the 18th Internation Parallel and Distributed Processing Symposium．France：IEEE，2004：153－156．

［8］贾向东，海阳，欧阳玉花．基于差分进化的非规则LDPC码分布对优化［J］．无线电工程，2009，（3）：24－25．