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

《基于PEG算法的LDPC码构造及改进》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、其进行准循环扩展，以消除基矩阵中的短环。实验结果表明，该方法构造的LDPC码可大幅减少短环的数目。同时由于引入了准循环结构，能降低编码复杂度。为了兼顾LDPC码较高的纠错性能和较简单的硬件实现，提出了一种基于PEG算法的准循环LDPC码校验矩阵的构造方法，该方法首先利用PEG算法构造基矩阵，然后利用提出的移位参数公式来构造循环移位矩阵，再用循环移位矩阵和全零矩阵对基矩阵进行优化扩展，形成的校验矩阵最短环长至少为8环。该方法具有与PEG算法非常接近的纠错性能，尤其是当信噪比高于1.2dB时要优于PEG直接构造法，而硬件实现比PEG算法简单，

3、且参数选择灵活方便。关键词：低密度奇偶校验码；渐进边增长算法；准循环结构；短环；循环置换矩阵；基矩阵1、概述PEG(progressedgegrowth)算法是当前公认的对中、短码长LDPC码构造非常有效的算法之一，它采取逐边添加的力一式构造码的Tanner图，在满足给定度分布的条件下能使Tanner图中短环数量尽可能少，使码的圈长尽可能大。但由于其采用随机构造的做法，使该类码的H矩阵缺乏结构性，编码复杂度高，尤其是对长码而言，其构造及编码实现的运算量更是剧增。基于PEG算法的QC-LDPC码是首先以PEG算法构造，一个维数较小的一致校验

4、矩阵，称为基矩阵，再将基矩阵中的“基矩阵维数由编码后的码长n和循环置换矩阵的维数P及码率决定。文献f}l给出了一种基于PEG算“1”元素和‘0’元素分别替换为pxp维的循环置换矩阵(或单位矩阵的循环移位)和全零矩阵。法的QC-LDPC码构造力一法，但在扩展的过程中只消除了部分6环，没有将圈长扩大。文献f}l给出了另一种扩展PEG算法构造的基矩阵的力一法，但由于PEG算法的非结构化，这种算法只是扩大了基矩阵中的一部分环的长度，不能确定是否扩大了圈长。本文提出的基于PEG算法的QC-LDPC码构造力一法成功扩大了圈长，同时扩大了部分其他长度的

5、环。算法中用到了PEG算法，环搜索算法，单位矩阵的循环移位值的选择算法，并通过仿真验证了改进力一法的有效性。胡晓宇等人提出了PEG算法，MacKay认为PEG码是目前最佳的Gallager码(码长在500以上)。我们可以用图例和算法流程来解释这种构造力一法。PEG算法不仅可以构造规则码，而且可以构造非规则码，算法和上面基本类似，只要把变量节点按度数升序排列即可。PEG算法可以获得尽量大的局部最小圈长。本文的环搜索算法采用的是迪科斯彻算法(Dijkstra)的思想，该算法是由荷兰计算机科学家艾兹格·迪科斯彻(EdsgerWybeDijkst

6、ra)1959年发明的。算法解决的是有向图中最短路径问。通过该算法可以找到所有长度为L的环长。但是上述算法的计算量很高，与校验矩阵的列数成线性关系，计算过程中的存储量要求也很高。由式(1)准循环矩阵中环的形成条件知，当回路中的各顶点的移位值当且仅当满足式(1)的等式时矩阵中形成长度为Zt的环·10基于PEG算法的LDPC码构造及改进其中，Sak/3k为H矩阵中回路的第k个顶点所在的循环子矩阵的移位值。如果选择适当的一组循环移位值，使其不满足上面的等式，就能消除长度为Zt的环。由等式的性质，我们知道当等式中只有一个变量时才能根据等式关系求出

7、它的确切值。在本算法中也是将首先确定上面等式(1)中的2t-1个值，然后根据式(1)求出不能选择的循环移位值。由QC-LDPC的校验矩阵的环结构可以看出，如果依次确定各列中循环子矩阵的移位值，并且只考虑当前列与其前的所有列形成的环，那么通过去除满足等式((1)的循环移位值，可得到可选的循环移位值的集合，此集合任一个移位值都能消除该列与其前的所有列形成的环。算法的具体步骤如下:1.如果循环矩阵的维数是L，基矩阵中每个块元素可选的移位值的集合是(1,2,3...L-1)o2.矩阵中第一列的循环子矩阵的移位值从他们的移位值集合中随机产生。3.从

8、矩阵的第二列开始，每一列的第一个循环子矩阵的移位值在1到L-1中随机产生，然后产生的记录循环的矩阵中搜索它与前面的列是否形成环，如果形成环，就根据上面的等式计算出此列的其他循环子矩阵不应该选择