基于PEG算法的LDPC码构造及改进

1、基于PEG算法的LDPC码构造及改进桂林电子科技大学硕士研究生纠错码理论课程学生： 王广耀 学号： 1502201054专业： 信息与通信工程题目： 基于PEG算法的LDPC码构造教师： 王俊义职称： 教授时间：2015.11.17基于PEG算法的LDPC码构造及改进摘要：渐进边增长(PEG)算法构造的低密度奇偶校验码(LDPC)在保证局部围长最大时仍有较多数目的短环。针对该问题，提出一 种新的准循环LDPC码构造方法。该方法在PEG算法中采用环多项式(PC)标记，利用PC-PEG方法构造的矩阵作为基矩阵，并对 其进行准循环扩展，以消除基矩阵中的短环。实验结果表明，该方法构造的LDPC码可大幅

2、减少短环的数目。同时由于引入了准 循环结构，能降低编码复杂度。为了兼顾LDPC码较高的纠错性能和较简单的硬件实现，提出了一种基于PEG算法的准循环LDPC码校验矩阵的构造方法，该方法首先利用PEG算法构造基矩阵，然后利用提出的移位参数公式来构造循环移位矩阵，再用循环移位矩阵和全零矩阵对基矩阵进行优化扩展，形成的校验矩阵最短环长至少为8环。该方法具有与PEG算法非常接近的纠错性能，尤其是当信噪比高于1.2 dB时要优于PEG直接构造法，而硬件实现比PEG算法简单，且参数选择灵活方便。关键词：低密度奇偶校验码；渐进边增长算法；准循环结构；短环；循环置换矩阵；基矩阵1、概述PEG (progress

3、 edge growth)算法是当前公认的对中、短码长LDPC码构造非常有效的算法之一，它采取逐边添加的力一式构造码的Tanner图，在满足给定度分布的条件下能使Tanner图中短环数量尽可能少，使码的圈长尽可能大。但由于其采用随机构造的做法，使该类码的H矩阵缺乏结构性，编码复杂度高，尤其是对长码而言，其构造及编码实现的运算量更是剧增。基于PEG算法的QC-LDPC码是首先以PEG算法构造，一个维数较小的一致校验矩阵，称为基矩阵，再将基矩阵中的“基矩阵维数由编码后的码长n和循环置换矩阵的维数P及码率决定。文献fl给出了一种基于PEG算“1”元素和0元素分别替换为px p维的循环置换矩阵(或单位

4、矩阵的循环移位)和全零矩阵。法的QC-LDPC码构造力一法，但在扩展的过程中只消除了部分6环，没有将圈长扩大。文献fl给出了另一种扩展PEG算法构造的基矩阵的力一法，但由于PEG算法的非结构化，这种算法只是扩大了基矩阵中的一部分环的长度，不能确定是否扩大了圈长。本文提出的基于PEG算法的 QC-LDPC码构造力一法成功扩大了圈长，同时扩大了部分其他长度的环。算法中用到了PEG算法，环搜索算法，单位矩阵的循环移位值的选择算法，并通过仿真验证了改进力一法的有效性。胡晓宇等人提出了PEG算法，MacKay认为PEG码是目前最佳的Gallager码(码长在500以上)。我们可以用图例和算法流程来解释这

5、种构造力一法。PEG算法不仅可以构造规则码，而且可以构造非规则码，算法和上面基本类似，只要把变量节点按度数升序排列即可。PEG算法可以获得尽量大的局部最小圈长。本文的环搜索算法采用的是迪科斯彻算法(Dijkstra)的思想，该算法是由荷兰计算机科学家艾兹格·迪科斯彻(Edsger Wybe Dijkstra) 1959年发明的。算法解决的是有向图中最短路径问。通过该算法可以找到所有长度为L的环长。但是上述算法的计算量很高，与校验矩阵的列数成线性关系，计算过程中的存储量要求也很高。由式(1)准循环矩阵中环的形成条件知，当回路中的各顶点的移位值当且仅当满足式(1)的等式时矩阵中形成长度为

6、Zt的环·其中，Sak/3k为H矩阵中回路的第k个顶点所在的循环子矩阵的移位值。如果选择适当的一组循环移位值，使其不满足上面的等式，就能消除长度为Zt的环。由等式的性质，我们知道当等式中只有一个变量时才能根据等式关系求出它的确切值。在本算法中也是将首先确定上面等式(1)中的2 t-1个值，然后根据式(1)求出不能选择的循环移位值。由QC-LDPC的校验矩阵的环结构可以看出，如果依次确定各列中循环子矩阵的移位值，并且只考虑当前列与其前的所有列形成的环，那么通过去除满足等式(1)的循环移位值，可得到可选的循环移位值的集合，此集合任一个移位值都能消除该列与其前的所有列形成的环。算法的具体步

7、骤如下:1.如果循环矩阵的维数是L，基矩阵中每个块元素可选的移位值的集合是(1, 2, 3.L-1)o2.矩阵中第一列的循环子矩阵的移位值从他们的移位值集合中随机产生。3.从矩阵的第二列开始，每一列的第一个循环子矩阵的移位值在1到L-1中随机产生， 然后产生的记录循环的矩阵中搜索它与前面的列是否形成环，如果形成环，就根据上面的等式计算出此列的其他循环子矩阵不应该选择的移位值，并从他的可选的移位值集合中去除这一元素。4.在循环子矩阵可选的移位值集合中随机选择移位值。5.逐列进行步骤3中的操作，确定矩阵中所有块元素的移位值。利用上述算法，若一个块元素被包含在小于L-1个环中，必然会消除矩阵中包含这

8、一块元素的所有长度为2t的环;若大于L一1也有很大可能消除所有长度为2t的环。构造基于PEG算法的准循环低密度奇倡检验码的步骤如下: 1.根据要生成的准循环低密度奇倡奇倡校验码的码长，码率，校验矩阵的行重，列重的要求确定基矩阵的码长、码率、行重、列重，以及循环置换矩阵的维数L; 2.利用PEG算法生成一个基矩阵; 3.利用环搜索程序找到矩阵中的短环; 4.利用搜索到的记录环的矩阵统计出经过每一列的环的数量，按照环数的降序对矩阵的列重新排序; 5.搜索新生成的校验矩阵中的短环; 6.应用移位值选择程序确定块元素的移位值; 7.将列的顺序重排恢复成原矩阵; 8.根据不同的移位值选择循环置换矩阵进行

9、扩展，对于基矩阵中的零元素用L维的全零力一阵扩展。利用上述算法可以使生成的准循环低密度奇倡校验码的圈长增加2，使矩阵中的短环减少。此算法的缺点是计算量较大，适用于在基矩阵较小，需要消除的环长也较小的情况。本论文中利用此力一法构造了列重为3,圈长为8,码率为0.5，码长分别为504,1008以及码率为0.33，码长为816的准循环低密度奇倡校验码。2、PEG构造法 PEG算法是一种逐边增加的算法，每增加一条边时按照树形图展开'展开终止的条件为当前校验节点集合的补集不为空集，再展开一步，校验节点集合的补集为空集则终止，或者展开到校验节点数不再随展开而增加时停止。这样虽然可以保证每增加一条边

10、可以使局部围长最大，但是该构造方法短环数较多，较多的短环数将严重影响译码性能，为此，本文引入一种PC标记法以减少短环的数目。 图1是以变量节点K为根节点展开的树形图，节点的环多项式计算方法如下：(1) 初始化根节点的多项式值为1,图中PC(K) = 1; (2)子节点的多项式PC值等于父节点乘以尤，如果1个子节点有2个或者更多的父节点，则该节点的多项式PC值计算如下：首先把所有父节点的PC值相加；然后把得到的值乘以X，即为该子节点的C值，例如：7有 2个父节点，则7的值为2x3。同一个校验节点可能在展开的树形图中多次出现，则校验节点c7的多项式PC值可以描述如下：PC(Cj) = wxx2kx

11、 + w2x2(t+1)-1 + ，A= 1,2，其中，wvc241表示添加叫条:的环；w2x2(t+1H表示添 加w2条2(k +1)的环。如果校验节点Cp在树形图中没有出现，则Cp的多项式PC值为0，选择Cp建立边将不会导致任何环长小于2(/ + 2)的环，I为树形图展开的最大层数。 PCPEG构造法采用比较各校验节点的多项式PC值进行新增边的选择：比较校验节点的环多项式的最小幂次，然后从各校验节点的最小幂次集合中选择其中的最大值，这样可以保证该校验节所形成的最短环最大。如果这样的校验节点不唯一，进一步比较系数值，选择系数值最小的可以保证该短环的数目最小。在实际构造中，可以给x赋 一个值(

12、令x = 0.1)，将多项式简化为一个代数值，从而将比较环多项式的幂次和系数值简化为比较环多项式的值，将两步简化为一步比较。简化后PCPEG构造法的复杂度没有明显增加，其性能也不会发生恶化。采用PCPEG构造法构造一个码长为n包含个校验式的LDPC码，具体步骤如下所示:对于每一个变量节点= 1,2，(1) 为变量节点K添加第一条边时，选择度数最小的校验节点连接，添加其他边时转步骤 (2)变量节点和校验节点PC值初始化。1) 变量节点值初始化2)校验节点PC值初始化，PC(Ck) = 0(3)以G为顶点按树形图展开，并逐层更新变量节点和校验节点的PC值。(4)若校验节点Cj由变量节点V;展开得到

13、，校验节点的PC值更新如下：PC(CJ) = PC(CJ) + xPC(Vi)(5)若变量节点&由校验节点展开得到，变量节点 1的C值更新如下：PC(Vq) = PC(Vq) + xPC(Cp)(4)选择PC值最小的校验节点作为新增连接边，即Cj = arg min(PC(C)。其中，Vc为可选校验节点的集合。(5) 返回步骤(2)完成变量节点其他边的建立。2.1 PEG算法的原理PEG (Progressive Edgerowth)算法9是一种能有效构造具有较大环长LDPC码校验矩阵的算法，被Mackay称为是目前所知道的最好的LDPC码的构造方法，尤其对构造短长度的LDPC码，如5

14、00,1 000,2 000等是十分有效的。 PEG算法是在Tanner图上某一个节点(比如变量节点)出发，不断添加节点的边，给每个节点添加边时，保证在该节点处的环长最大，从而使最终构造的Tanner图的短环数量尽可能少而码的Girth尽可能大。尽管PEG算法每次添加新边时能保证环长度最大，但不能对Tanner图中的环结构进行全局优化，所以采用PEG算法构造的LDPC码，其Tanner图中的环结构复杂，特别是在长码长时由于环交织的问题，存在大量公共节点，会在一定程度上降低迭代译码算法性能，因此PEG算法一般适用于短码的构造。2.2 LDPC码校验矩阵的构造方法 PEG算法在短码时表现出优异的性

15、能，准循环LDPC码具有实现方便的特点，但准循LDPC码在构造检验矩阵时要先构造出基矩阵。本文将两者相结合来构造基于PEG算法的准循环校验矩阵，即先用PEG算法构造出短码的校验矩阵基矩阵A，然后用循环置换矩阵I Phi)和全0”方阵对其扩展而得到准循环LDPC码校验矩阵H，这样不但弥补了PEG算法在长码构造时的缺陷，还可用简单的线性移位寄存器对LDPC码进行编码，减少了校验矩阵的存储空间，从而便于硬件实现。具体的构造步骤如下: (1)确定需要设计的准循环LDPC码校验矩阵H的行数mb(也即准循环LDPC码的校验位长度)、列数nb(也即准循环LDPC码的码长)、节点度分布等参数。 (2)应用PE

16、G算法构造满足度分布要求的基矩阵A，其维数为mXn，搜索并记录最短的环及其中顶点的位置。 (3)对基矩阵A的优化扩展。先根据基矩阵A中元素1”的位置，按式(6)计算循环移位次数的值;再找出基矩阵A中各短环顶点元素“1”的的值后判断是否满足式(5)，如果不满足则对其中的值进行修正，直到满足为止;最后对基矩阵A中的元素“1”用维数为bxb的对单位方阵右循环，(修正值)次后的循环置换矩阵代替。 (4)重复步骤(3)，直到环记录中所有环的“1 "元素被替换。 (5)对基矩阵A中不属于短环的“ 1”元素用维数为bxb的循环置换矩阵代替。(6)对基矩阵A中的元素0o用维数为bxb的全“0”方阵代

17、替。 这样就构造出了维数为mb x nb，码率为R= (nb-mb) /nb=l-m/n=l-dv/dc,的准循环LDPC校验矩阵H。可见，这种方法对LDPC码参数的设置比较灵活，通过改变n值、m值或b值，可以构造出不同的准循环LDPC码校验矩阵H;通过对P，的优化设计，来保证所设计的准循环LDPC码校验矩阵H中不含6环，即最短的环为8环。3、基于PCPEG算法的准循环扩展假设扩展后的校验矩阵具有如下形式：其中，1表示单位矩阵循环移位Rhj次后得到的循环置换矩阵，-/在/-为置换矩阵的维数。/(-I) 表示pxp维的全零矩阵，/(0)为单位矩阵。定理若矩阵的树形图中包含一个长为2/的环，当 且

18、仅当好矩阵中包含一个长为2?的闭合回路，且有：其中，&为h矩阵中回路的第&个顶点所在块元素的移位值。构造开矩阵时，若能保证任意长为2的闭合路径均不满足定理中的条件，则构造出的LDPC码的围长最大为2。因此，在对基矩阵进行准循环扩展时，适当选择各个循环移位矩阵的移位值可以进一步消除基矩 阵中的短环。通过上面的分析，可以得到构造丑矩阵的准循环扩展算法步骤如下:(1)通过PCPEG算法设计出满足度分布要求的基矩阵，搜索并保存环的路径。以基矩阵中的环为单位逐步完成对T元素的替换，即在所记录的环中取出长度最短的环，将环中“1”元素逐个用循环置换矩阵替换，设定各循环置换矩阵的移位值，使其不

19、满足定理1的约束条件。(3)重复步骤(2)，直到环记录中所有环的“1”元素均被替换。1基矩阵中不属于任何环的“1”元素用随机移位次数的循环置换矩阵替换，“0”元素用全零矩阵替换。2搜索矩阵对应树形图的围长，检测长度为围长的环包含的变量节点数是否满足设计要求，若不满足，则回到步骤(1)重新构造，若满足，则输出丑矩阵。 4、迭代编码算法若LDPC码的校验矩阵具有如图1所示的下三角结构,在图中对角线的位置上为全 1!,而其余的 1!均在对角线的左边,则可以直接采用迭代编码算法进行编码.设码字向量为xFn ,将其分为2个部分,即信息位向量sF n-m 和校验位向量pFm ,亦即x(

20、s,p)Fn-m。则该码的编码过程可具体描述为 图1 具有下三角结构的LDPC码的校验矩阵1) 直接将信息比特的值赋给信息位向量s; 2)采用后项迭代的方式确定所有校验位的值,即对所有的l0,n-k-1,从小到大依次计算下式 式中:hi,j表示第i行,第j列上的元素.实际上,该编码过程就是在从上到下依次利用校验矩阵各行的约束关系.对于每一个校验约束关系,其中涉及的变量除了对角线上的 1!所对应的校验位外,其余的变量要么是信息位,要么就是前面已经求出的校验位,也就是说,该校验关系中只有一个未知变量,因此可以很容易求出校验位的值.当校验矩阵的平均行重相对于码长可以看做很小的常数时,该编码

21、方法就具有线性的复杂度;同时该编码算法不需要对校验矩阵进行预处理。5、改进度的PEG构造算法基于高斯消去的编码算法和基于近似下三角结构的有效编码算法适用于一般的校验矩阵,但在编码的过程中需要对校验矩阵进行一定的预处理,两种算法都包括对矩阵的求逆,求逆的过程不仅计算量大,硬件难以实现,同时还要求矩阵满秩,在实际应用中,很多情况下并不能满足上述条件.因此,直接构造性能优异的、具有下三角结构的校验矩阵且可采用迭代编码算法的LDPC码具有重要的实践意义.针对此,文中提出了一种直接构造具有下三角结 构的非规则LDPC 码的方法-改进的PEG算法。PEG构造方法是迄今为止构造性能优异的构造中短码长LDPC

22、码的有效方法.该算法在已有Tanner图上添加边来构造最终的Tanner图,每次添加时都尽可能减少对已有Tanner图的影响,及尽可能使LDPC码的围长较大.它不但适用于规则LDPC码的构造,同样也适用于非规则LDPC码的构造.本文提出的构造算法基本与PEG的算法流程相同.主要的改进有如下几点: 1)在添加比特节点时,即添加H矩阵的每列时,顺序是沿着列号由大到小的顺序依次进行. 2)在添加图1所示的下三角部分的比特节点时,每个比特节点的第1校验位必须添加在对角线 的位置上,其余的校验位添加在对角线的下方,即添加H矩阵中具有下三角结构的那些列时,每列的第1个 “1”在对角线的位置上,其

23、余的 “1”在对角线的下方。 3)为了尽量满足给定的度分布,同时为了使构造的LDPC码的围长尽量大,在构造非下三角部分的节点时,按照节点度数递减的次序依次添加剩余的比特节点,即H矩阵的每列。6、编码复杂度分析基于高斯消去的编码算法复杂度计算包含2个部分:一是将校验矩阵高斯消去成下三角矩阵的结构即对校验矩阵进行预处理,运算复杂度为o(n3 ),其中n为码长.二是编码复杂度为o(n2 ),这是因为该编码算法的编码复杂度取决于生成矩阵的稀疏性,设生成矩阵的平均列重为w,则整个编码过程中大约需要wn次与运算,(w-1)n次异或运算.尽管LDPC码的校验矩阵是非常稀疏的,但它的生成矩阵却并不稀

24、疏,通常w与n的比值是一个不可忽略的常数,这使得其编码复杂度往往与其码长的平方呈正比. 而迭代编码算法的编码复杂度完全取决于LDPC码的校验矩阵的稀疏性,设校验矩阵的平均列重为w,则整个编码约需要w(n-k)次与运算,(w-1)(n-k)次异或运算,其中n为码长,k为信息为长,当w相对于n可以看作很小的常数时,该编码算法就具有线性的复杂度.本文提出的改进的PEG算法能够直接构造出具有下三角结构的校验矩阵,不仅避免了对校验矩阵的预处理,同时保证了矩阵的稀疏性,因此平均列重w相对于码长n就可以看作一个很小的常数,即可实现LDPC码的线性复杂度编码. 由上述分析可知,虽然改进的PEG构造算法在性能上

25、并不能超越PEG构造算法,但其最大的优势在于其编码复杂度低,更易于实现。7、仿真结果及分析图2所示的是在MSK调制,误码率在r=1/2和r=2/3情况下的性能仿真曲线.其中LDPC码的信息位长均为1024,译码采用BP译码算法,为了 给硬件实现提供参考,最大译码迭代次数取为25,信道为高斯白噪声信道.PEG构造算法采用基于高斯消去的编码算法,而改进的PEG构造算法采用迭代编码算法.其中1/2误码率的LDPC码的变量节点度分布服从(x)=0.30013x+0.28395x2 +0.41592x7 ;2/3误码率的LDPC码变量节点度分布服从(x)=0.25105x+0.30938x2 +0.00

26、104x3 +0.43853x9 .从图中可以看出,采用改进PEG构造方法与直接应用PEG构造方法构造出的LDPC码的误码率曲线基本重合,即这2个LDPC码的纠错性能非常接近,从而表明改进的PEG算法构造的具有下三角结构的LDPC码可以具有较强的纠错能力. 图2 改进的PEG构造方法构造的LDPC码的性能本节对基于PEG算法循环置换矩阵扩展的QC-LDPC码进行了仿真，并与MacKay随机码，PEG随机码，PEG单纯扩展的QC-LDPC码进行了比较分析。在仿真结果中，本文构造的基于PEG算法循环置换矩阵扩展的QC-LDPC码表示为PEG-E-LDPC，原论文中构造的QC-LDPC码表示为PEG

27、-OE-LDPC Mackay随机码表示为Mackay-LDPC PEG算法直接构造的LDPC码表示为PEG-LDPC纯扩展生成的QC-LDPC码表示为EG-PE-LDPC oE61No(dB)图IAWGN信道下PEG-E-LDPC(504,252)的误码性能。基于高斯消去的LDPC码编码算法复杂度较高,在中短码长时不易实现.对此,T.J.Richardson等提出了一种基于近似下三角矩阵的有效编码算法(也叫贪婪算法).该算法虽然可以实现在线性时间内编码,但其应用条件受一定的限制,成为实用化过程中的一个阻碍.因此,近年来出现了一种低编码复杂度Quasi Cyclic LDPC码的编码算法.QC

28、码编码可以用简单的移位寄 存器实现,其生成矩阵具有循环或准循环的特性,因此可以实现线性复杂度编码.QC码虽然有简单的编码结构,但是其码长和码率的参数选择不够灵活,导致该算法构造出的码字不具有兼容性,实用性较差.随后王鹏等在提出了迭代编码算法，该编码算法不仅具有线性编码复杂度,且不会改变矩阵的稀疏性,同时克服了码长和码率的参数选择不够灵活的缺陷.在本文中,将进一步对迭代编码算法进行研究,并针对该编码算法提出一种具有下三角结构的非规则LDPC码校验矩阵的构造方法-改进的PEG构造算法。低密度奇偶校验(Low Density Parity Check, LDPC)码以其低复杂度的迭代译码算法和可逼近

29、信道容量限的纠错性 能而得到众多学者的关注。目前性能优良的LDPC码大都通过随机构造方法构造，但是这种码编码复杂度高，不利于硬件实现文献4提出的渐进边增长(Progressive Edge Growth, PEG)算法是一种随机构造算法，其参数构造方便灵活，并且在每次添加一条边时使局部围长都保持最大，但是PEG算法以及后来人们在其基础上修改的其他算法都只 考虑了围长，忽视了短环的数目，如果短环的数目偏多， 即使围长较大，也将严重影响译码性能。文献7提出了基PEG算法的准循环码(Quasi-cycle Low Density Parity Check, QCLDPC)构造方法，具有与随机码相近的性能，同 时由于引入准循环结构减少了存储空间，降低了编译码复杂度。但该方法没有进一步研究准循环码的环结构，进而减少码中短环的数量。本文在