学文网The Simulation of the Improvement of the IPEG Algorithm
Lv Xiao
（Shannxi Railway Vocational & Technical Institude，Weinan 714000，China）
摘要： 本文在对改进的IPEG算法分析的基础上，给出了这种算法的一种仿真实现。该算法的优点是增加了信息节点的连通性，从而减少了小停止集。仿真结果表明，与用IPEG算法相比较，利用此种方法构造的LDPC码具有更低的错误平层。
Abstract: The modification on the improved progressive-edge-growth(IPEG) algorithm is introduced in this paper, and the simulation of this algorithm is given based on the analysis of the algorithm. The advancements of the algorithm is increasing the connectivity of variable nodes using extrinsic message degree of variable nodes, which results in reducing the small stopping sets. Through computer simulation, the result shows that the codes constructed by the proposed algorithm have lower error floor than those constructed by the original IPEG algorithm
关键词： PEG算法 停止集 EMD
Key words: Progressive-edge-growth（PEG）algorithm；stopping set；extrinsic message degree（EMD）
中***分类号：TP39 文献标识码：A文章编号：1006-4311（2011）14-0189-02
1绪论
低密度检验码（Low-Density Parity-Check Codes，简称LDPC）由于其接近信道容量的性能（在无限块长和无环的情况下）和低复杂度的迭代译码受到了广泛的关注[1][2]。然而，在实际应用中，在有限块长的情况下我们无法避免环的存在。置信传播（Belief Propagation，BP）算法在无环的情况下可以达到最优的解码[3]。如果在有环的情况下，消息传播的***性就会受到影响。因此，使环尽可能的大进而减小消息之间的依赖性是很合理的。在这种观点下，渐进加边（Progressive-Edge-Growth，简称PEG）算法的提出相对于随机构码来说，改进了LDPC码的性能，渐进加边算法主要的思想就是在构造LDPC码的时候使每个信息节点的环长都达到最大[4]。
LDPC码的在二进制删除信道下的性能取决与信息节点之间的连通性，而连通性又与停止集相关，停止集可导致迭代译码失败。连通性可以由外信息度（Extrinsic Message Degree，简称EMD）或者近似外信息度（Approximate Cycle EMD，简称ACE）[6]表示。在改进渐进加边（Improved Progressive-Edge-Growth，简称IPEG）算法中[7]，介绍了ACE的概念，并且还介绍了IPEG算法在高信噪比的情况下可以改进LDPC码的性能。
本文对改进的IPEG算法进行了仿真。改进的IPEG算法使用信息节点的外信息度增加了信息节点之间的连通性，并且减少了小的停止集。
2信息节点的连通性
奇偶校验矩阵和二部***有一对一的对应关系，例如***1：
校验矩阵中的一列（或行）与二部***中的信息节点一一对应。hij表示校验矩阵中第i行和第j列交叉点上的元素，当且仅当hij=1时表示在第i个信息节点和第j个校验节点之间有一条边的存在。
定义1：（停止集[5]）信息节点的一个子集S，如果S所有的邻接校验节点都连接到S至少两次，S就被称为停止集。
例如，如***1所示，信息节点的子集A=v■，v■，v■形成了一个停止集，而子集B=v■，v■，v■则不是一个停止集，因为B的两个邻接校验节点c3和c4连接到B只有一次。在校验矩阵中，停止集还可以根据S对应的列的和（不是模2和）来判定，如果列的和中没有出现1，则S是停止集。A对应的列的和为[0 2 2 2]T，没有出现1。
防止小的停止集的出现就可以预防小的最小距离[6]，这是已经被证明的。为了避免小的停止集的出现，我们必须使信息节点的子集具有更多的外连边。外连校验节点的数量定义如下。
定义2：（EMD[6]）一个信息节点集的外连校验节点就是单独连接到这个信息节点集的校验节点。一个信息节点集的EMD值就是这个信息节点集的外连校验节点数。
我们可以看到，一个停止集的EMD值是0，并且信息节点集所对应的列的和中的1的数量就等于这个集合的EMD。在上面的例子中，B所对应的列的和为[2 2 1 1]T，所以的EMD值为2。
定义3：（ACE[6]）一个长度为2d的环的ACE值为∑■d■-2，d■为环中第i个信息节点的度数。
当信息节点和它们的邻接校验节点组成一个单独的环的时候，信息节点的EMD值等于它们的ACE值，但是，如果组成的是多重环，则ACE值就变成了它们AMD值的上限。在***1中，信息节点v■，v■，v■和它们的邻接校验节点组成了一个6环，它们的ACE值为1，然而，因为这个6环中包含了一个4环，这些信息节点的EMD值就是0。
3对IPEG算法的改进
有n个信息节点和m个校验节点的标准PEG算法如下所示[4]：
在上面的算法中，dj是信息节点sj的度数。E■■代表连到sj的第k条边，E■表示连上sj的所有的边的集合。N■■表示从sj展开l层所连接到的所有校验节点的集合，N■■是N■■的补集。我们用Ω■■表示将要连接到sj的第k条边的所有校验节点的集合。当Ω■■中的候选节点多于一个的时候，PEG算法就随机的选取一个。然而，IPEG算法引入了ACE的概念，并且提出了一种选择的标准。IPEG算法从Ω■■中选取使新形成的环的ACE值最大的那个节点。如果有多个候选节点都使新环有相同的ACE值，IPEG也是随机的选择一个。我们提出的改进就在这里，当多个候选节点都使新环有相同的ACE值时，我们选择那个可以增加信息节点连通性的那个节点。
Φ■■表示用IPEG算法中的标准所筛选出来的校验节点的子集。显然，Φ■■是Ω■■的一个子集。当Φ■■中的有多个元素的时候，我们可以从已展开的PEG***里面提取出一个子***，每一个子***都由Φ■■中的一个元素到根结点sj的一个回溯组成，因此，我们知道在每一个组途中都包含了哪些信息节点，我们能很容易的计算出哪个子***有更高的EMD值。最后，我们就从Φ■■里选一个有最大EMD值的校验节点。
***2中所示的就是一个从两个有相同ACE值，但EMD值不同的校验节点中选择一个检验节点。而这两个校验节点按照IPEG算法中的标准被认为是没有差别的。然而，我们使用改进IPEG算法就可以做到更好的选择。在***2中，左边的那个候选节点的EMD值比右边的那个大，所以被选中。也有可能在Φ■■中有多个候选节点具有相同的EMD值。在这种情况下，我们就选择对应子***包含信息节点最多的那个校验节点。如果这样还不能选出哪个校验节点最合适，也就是说我们按照所有的标准（环长，ACE，EMD，包含最多信息节点），我们就随机的选择。
4仿真结果
我们分别用IPEG算法和改进IPEG算法构造不规则LDPC码，块长是2000。信息节点度分布则采用[2]中的数据。λ■（x）是的度分布。我们用高斯信道下的最大迭代200次的BP算法。
λ■（x）=0.21991x+0.23328x2+0.02058x3+0.08543x5+0.06540x6+
0.04767x7+0.01912x8+0.08064x18+0.22798x19
***3显示的是在块长为2000的条件下的误帧率（frame error rate，FER）和位误码率（bit error rate，BER）。我们看到，在块长为2000时，IPEG构造的码在FER为10-5的时候出现了错误平层，但是用改进的IPEG算法构造的码在相同区域内并没有出现错误平层。
5结论
在本文中，我们讨论了信息节点的连通性，并其为选在检验节点提出了更详细的条件，从而防止小停止集的出现。仿真结果表明，与用IPEG算法相比较，利用改进的IPEG算法构造的LDPC码具有更低的错误平层。
参考文献：
[1]R.G.Gallager，“Low-density parity-check codes，”IRE Trans.Inf. Theory,vol.IT-B，pp.21-28，Jan.1962.
[2]T.Richardson，M.Shokrollahi，and R.Urbanke，“Design of capacity approaching irregular low-density parity check codes，”IEEE Trans. Inf.Theory, vol.47，pp.619-637，Feb.2001.
[3]R.M.Tanner，“A recursive approach to low complexity codes，”IEEE Trans.Inf.Theory，vol.27，pp.533-547，Sept.1981.
[4]X.Y.Hu，E.Eleftheriou，and D.M.Arnold，“Progressive edge-growth Tanner graphs，”in Proc.IEEE GLOBECOM’01，vol.2，pp.995-1001，Nov.2001.
[5]C.Di，D.Proietti，I.E.Telater，T.J.Richardon，and R.L.Urbanke，“Finite-length analysis of low-density parity check codes on the binary erasure channel，”Proc.IEEE Tran.Inf.Theory，vol.48，no.6，pp.1570-1579，June 2002.
[6]T.Tian，C.R.Jones，J.D.Villasenor，and R.D.Wesel，“Construction of irregular LDPC codes with low error floors，”in Proc.IEEE m.，vol. 5，pp.3125-3129，May 2003.
[7]H.Xiao and A.H.Banihashemi“Improved progressive-edge-growth（PEG） construction of irregular LDPC codes，”IEEE Commun.Lett.，vol.8，pp.715-717，Dec.2004.
转载请注明出处学文网 » 改进的IPEG算法仿真实现