基于扩展PEG算法的低密度校验码构造方法

基于扩展PEG算法的低密度校验码构造方法2008年第10期中图分类号:TM911.22文献标识码:A文章编号:10092552(20o8)10一OOO403基于扩展PEG算法的低密度校验码构造方法倪俊枫,甘小莺,张海滨,徐友云(上海交通大学电子工程系,上海2ay240)摘要:提出了一种带扩展的PEG算法进行LDPC码的构造.相对于经典的PEG算法而言,该算法在构造的时候考虑的H矩阵行重的分布,另外构造的H矩阵具有准循环移位的特性,易于硬件实现.因此,该算法有着非常高的实用价值.关键词:PEG;H矩阵;环;循环移位扩展Construction0fLDPCcodebasedonexpansionPEGalgorithmNIJunfeng,GANXiao-ying,ZHANGHai.bin,XUYou.yun(DepartmentofEleOronicEngineering,ShanghaiJiaotongUniversity,Shanghai2OO24O,Cllina)Abstract:ThepaperproposedExpansionPEGAlgorithmtoconstructtheHmatrixofLDPCcode.ComparedtothenormalPEG蛔,expansionPEGalgorithmconsiderstherOWweightdistributionoftheHmatrix.Moreever,theHmatrixconstructedbyexpansionPEGalgorithmisaQcmatrix,whichiseasytoimplementinhardwareandhasveryhighvalueofpracticalusage.Keywords:PEG;Hmatrix;girth;expansionPEG低密度校验码(LDPC码)是由Gallager提出的信道编码,由于它的性能接近香农极限,以及具备简单的编译码算法,因此LDPC码是现在信道编译码中的重点研究领域.LDPC迭代译码算法是在无环假设下获得的,但是由于在LDPC码中环是无法避免的,导致LDPC码在迭代的时候比特节点和校验节点之间传递的信息产生相关性,因此使用迭代译码无法达到最优的译码结果.另外,目前通过密度演化的方法,可以获得最优度分布对,使用最优度分布对可以构造出近似香农极限的LDPC码.文献4构造了距离香农限0.0045dB的LDPC码.但是密度演化所获得的度分布中,许多度非常大,这导致在构造的时候会产生很多的短环,如果构造的时候不对环长进行控制的话,构造的LDPC码无法获得良好的译码性能.构造具备大环长的LDPC码的方法很多,其中比较流行的有有限几何的方法以及代数的方法,但是这些方法无法构造特定的度分布对的LDPC码.另外通过边增长的方法(PEG算法)可以构造具备特定的度分布对,同时具有较大环长的LDPC码,但是这种方法只能用来构造随机码,而使用随机码无法-?-4?-?进行快速译码,因此这种构造方法的应用范围受到了局限.文中提出了一种基于PEG算法的矩阵构造方法(扩展PEG算法),该方法由PEG算法衍生,一样可以构造出非常大环长的LDPC码,同时构造的矩阵具有准循环的特性,从而保证了使用这种方式构造的校验矩阵具有可并行译码的特性.1经典PEG算法PEG算法是一种贪婪算法.如图1所示,在构造初始阶段,Tanner图只有校验节点,该算法将往Tanner图中添加特点度数的比特节点,直到添加的比特节点的数目达到要求的个数.其中比特节点的度数可以通过密度演化获得.在添加比特节点的时候,每往Tanner图中添加一条边,添加的边所产生的环的环长是目前可以获得的最大环长.PEG算法的具体实现方法如下所示:(1)往Tanner图中添加第m个比特节点.收稿日期:2OO71018基金项目:国家自然科学基金重点资助项目(60332030)作者简介:倪俊枫(1982一),男,硕士研究生,从事信道编译码方向的研究.鄙比特节点校验节点O乜.图1PEG算法构造不意图(2)添加第m个比特节点的第一条边,由于在添加第一条边的时候不会带来环,因此只需要寻找在当前度最小的校验节点与之相连.(3)依次添加第m个比特节点的其余边,重复如下的步骤,直到该节点的边添完.从第m个变量节点出发,寻找它的N(k)子集,其中k满足(k+1)=,而N(k).N(k)定义为从变量节点出发,经过k条边,能够达到的校验节点的集合.(k)是N(k)的补集.在(后)中寻找度最小的校验节点与之相连.(4)m=m+1,如果m大于比特节点的总个数则退出,否则回到步骤1.2扩展PEG算法从经典的PEG算法的实现的角度来看,有如下的不足:首先,在PEG构造的时候,并没有考虑到校验节点的度的约束,这样构造出来的矩阵即使能够满足比特节点的度分布要求,仍然不能满足校验节点的度分布的约束.其次,使用经典的PEG算法构造出来的矩阵是随机的,这样构造出来的矩阵有理论研究价值,但是应用价值不高.本文提出的扩展PEG算法,可以弥补上述的两个不足.扩展PEG算法的基本思想是使用两次构造的方法,第一次构造的时候使用加入校验节点约束的PEG算法,构造出一个基矩阵如图2(a)所示,然后在的基础上使用带环长检测的循环移位扩展的方法将中的非零元素进行扩展,如图2(b)所示,构造出最终的日矩阵.2.1带校验节点度约束的PEG算法带校验节点度约束的PEG和经典的PEG算法的区别就在于比特节点会从合法的校验节点的集合中对校验节点进行选取,每增加一条边都需要检111llIIIJ1iI.Jl1ll11Jill,w11l11jIllll1_lIlT1r1l_fiiIriJII1J_l_1厂.寸:1f【l(a)HB矩阵示意(b)HB矩阵中某非零元素扩展示意图2两次构造方法不意图查增加边的校验节点是否达到了预设值D一,如果达到了,则这个校验节点将会从中去除.具体的计算步骤如下:(1)假设密度演化的结果中有n种比特节点的度D,根据比特节点的度分布以及矩阵的列数确定每一种比特节点度所占的比特节点的个数,计为(i=1n).同样假设有m种校验节点的度DD(按照递减顺序排列),根据校验节点的度分布以及矩阵的行数确定每一种校验节点度所占的校验节点的个数.计为(=1m)(2)初始化,D设置为D当前具有D一大小度的校验节点个数计为count.Ca中包含所有的校验节点.(3)往Tanner图中添加第/IZ个比特节点.(4)添加第m个比特节点的第一条边.在中选择当前度最小的校验节点与之相连.检查选择的校验节点的度是否等于D一,如果等于,将该校验节点从中去除,同时count加1.假设当前一等于如果count的大小等于的话,count清零,D一等于D.(5)依次添加第m个比特节点的其余边,重复如下的步骤,直到该节点的边添完.从第m个变量节点出发,寻找它的N(k)子集,其中k满足N(k+1)ncA=,而N(k)nCA.在N(k)n寻找度最小的校验节点与之相连.重复步骤(4)中的部分.(6)m=m+1,如果m大于比特节点的总个数则退出,否则回到步骤(1).2.2循环移位扩展在做完了带校验节点度约束的PEG构造之后,得到矩阵,由于第一次构造的矩阵的大小很小,因此包含了很多的短环,因此需要在循环移位扩展的时候对短环进行检测,同时通过设置合理的循环移位因子消除这些短环.通过移位,因此消除短环的原理如下.图3是PEG算法构造的H矩阵中的一个环4扩展出来的,虽然在H矩阵中这是一个环,但是在<图3(a)中,这个环被消除了.但是在图3(b)中仍然存在环.在图3(b)中,假设非零元素i的循环移位因子为,在图中,假设往右和往下的方向是正方向,往左和往上的方向是负方向,另外定义=sign(一P),在正方向的时候,sign=1,负方向的时候sign=一l.所以图中有:=o,而在图3(口)中,这个情况不存在,即o将这个结论推广,任意长度的环,只要经过满足:Pl0条件的扩展,这个环将不存在.?-_-_-_节点1P1=3节点2P2=4节点lPl=3节点2P2=4骨_lL1IlIlI!节点3P3=b厂T厂rr_十时lll;.E(a)不产生环的循环移位扩展(b)产生环的循环移位扩展图3PEG算法构造的H矩阵中环的扩展(1)将日矩阵的列反序排列得到日,也就是说,将矩阵的第i列和第n列交换,n为矩阵的总列数.得到的矩阵计为日,.(2)从日矩阵的第k列开始,对每个非零元素进行循环扩展.如果是第一个元素,则使用随机的循环移位因子进行扩展,并将该元素加入已扩展元素集合.如果不是第一个元素,则:搜索该元素在已扩展元素集合中参与的环.60.10O11E一3蚕1E-41E.51E-61E.7使用上文介绍的消环方法选择合适的循环移位因子对环进行消除.将该元素加入已扩展元素的集合.(3)k=k+1,如果k大于矩阵的列数则构造结束,否则返回步骤2继续进行扩展.说明:在步骤1中对日矩阵进行反序排列是因为在第一次构造时,后添加的列容易产生环,因此在循环移位扩展构造的时候需要对后添加的列先进行循环移位扩展,以消除前一次构造所带来的环.3仿真结果分别使用了带扩展的PEG算法和经典的PEG算法对112和3/4码率的LDPC码进行构造,构造的码长为3720.两种码率的LDPC码日矩阵的列重分布如表12所示.表11/2码率H矩阵列重分布列重列重分布2367200.硼O.3024O.02930.1299O.O517表23/4码率H矩阵列重分布列重列重分布0.41090.34O5O.lO.O676O.1209在AWGN信道下仿真的性能的比较如图4所示,使用算法为BP算法,迭代次数100次.051.01.52.02.530354.0Eb/NO(dB)图4AWGN信道下经典PEG算法和带扩展的PEG算法BER性能比较(下转第58页)圈一能量消耗为5n焦耳.要评估使用同中心簇的计划的CCIP协议的性能,进行一个实验关于现有的PEGASIS协议和有6个级别的CCIP协议.所以,每个级别有24个节点.根据上文提到的公式,计算传感器节点从第一循环到第1500个循环的总的剩余能量.利用这个结果,可以很容易比较现有的PEGASIS协议和高级PEGASIS协议的总的剩余能量.图5显示了传感器网络每个循环的总的剩余能量的仿真结果.从图6中可以看到使用同中心簇的机制的高级PEGASIS协议的性能比现有的PEGASIS要好.日面图5每次循环后所有节点的剩余总能量图6显示了高级PEGASIS协议比上现有的PEGASIS议的能量效率.它代表了高级PEGASIS协议和现有PEGASIS协议相比的总剩余能量率.如果当循环接近1500,高级PEGASIS协议能量效率会高出35%或更多.3结束语检查了现有PEGASIS协议下的冗余数据流.在WSN中,节省能量是最重要的事情.所以,本文提出使用同中心簇的机制的PEGASIS协议来延长网络的生命周期.高级PEGASIS协议使用同中心簇的机制,数据总是向基站流动.因此,它避免了不必要的数据传送,在性能评估方面,与现有PEGASIS相比,节省了大约35%的能量.未来研究的重点是使用不同参数的性能评估研究级别的分配和头节点的选择来最大化网络的生存时间.图6每次循环中CCLP协议与PEGASIS协议相比的能量效率百分比参考文献:1张海波,陈涤,李骐,等.无线传感器网络的最低能量保护分簇算法J.计算机工程与应用,2O06(35).2熊焰,吕天行,苗付发,等.无线传感器网络中一种能量有效的簇头选举算法J.计算机工程,2OO6,32(24).【3jWendiRabinexHeinzelmnAnanthaOumdrakasan,HariBdaktisbuan,.Ersy-EfficientCentnunicatienPeodforWtrdessMicaosmsorNet-wokEC.SystemSciences,2OOO.1:h-oceedmgsofthe33rdAnnualHa.waiiInternationalConference,Jan.2OOO.4OssarnaYonnis,ScaFahmy.HEED:AHybrid,EnergyEfficient,DistributedClusteringApproachforAdHoe11801NetworksJ.IEEETransactionsOnMobileComputing,Oct.2OO4,3(4):366379.责任编辑:肖滨(上接第6页)4结束语带扩展的PEG算法可以获得和经典PEG算法相当的环长.另外,通过性能仿真可以发现,带扩展的PEG算法和经典PEG算法的性能相当.但是带扩展的PEG算法可以获得具有循环移位特性的H矩阵,非常适合硬件的实现,这个相对于经典的PEG算法来说有着非常大的优势.因此,带扩展的PEG算法有着非常大的应用价值.参考文献:1HuXY,EleftherionE,ArnoldDM.ProgressiveedgegrowthTanner一58一graphsJ/Proc.IEEEGlobecom2001,SanAntonio,TX,Nov,2001:9951001.2HuxY,EleftherionE,ArnoldDM.Rellarandie丑rprogressiveedgegrowthtannergraphsJ.IEEETransactionInformationTheory,2OO5,