基于PC－PEG算法构造的QC－LDPC码性能研究

杨 张，袁梅冷，雷海军

(1.深圳职业技术学院，广东 深圳 518055;2.深圳大学计算机与软件学院广东省普及型高性能计算机重点实验室，广东 深圳 518060)

责任编辑:时 雯

1 LDPC简述

LDPC(Low Density Parity Check)码即为低密度奇偶校验码，它是 Gallager［1－2］在1963 年提出的具有稀疏校验矩阵的线性分组码，Turbo码的迭代译码思想在LDPC码中的应用使其对较长的LDPC码在BPSK调制性能中接近AWGN信道下的Shannon限。LDPC码的优良性能已被公认为将代替Turbo码应用在分布式视频编码(DVC)及下一代通信技术等领域。

目前，对于性能优良的LDPC码均采用随机构造方法，这种码具有两个缺点:码字无规则，需要较大的存储空间;随机构造方法在参数控制方面不是很灵活，必须在构造出校验矩阵后才可根据校验矩阵计算码长、码率［3］。文献［4］中PEG算法虽然可以使参数构造方便灵活，并且可以在每次添加一条边时使局部圈长都保持最大，但是PEG算法以及后来人们在其基础上修改的其他算法都只考虑了圈长，忽视了小环的数目，如果小环的数目偏多，即使圈长较大，也将严重影响译码性能。文献［5］为了实现LDPC部分并行译码的特点，以PEG算法为基础引入了QC特性［6－7］，该方法构造的LDPC码可以保证局部圈长最大，并且准循环特性可以减小存储空间，同时可以实现工程上的部分并行译码性能，但是该方法在保证局部圈长最大情况下仍然没有使小环数目最小。本文充分分析了构造LDPC码的校验矩阵，得知各种算法存在的优缺点，对文献［6］使用的PEG算法采用PC标记法修改，使PEG算法同时满足局部圈长最大、小环数目最小，然后引入QC特性，在保证译码性能相当的前提下实现工程上的部分并行译码。

2 PC(Polynomial of Cycle)标记法原理

PEG算法是一种逐边增加的算法，每增加一条边时按照 Tanner图展开［8－9］，展开终止的条件为当前校验节点的集合的补集不为空集，再展开一步则校验节点集合的补集为空集则终止，或者展开到校验节点数目不再随展开而增加时停止，这样虽然可以保证每增加一条边局部圈长最大，但是该构造方法小环数目较多，较多的小环数目将严重影响译码性能，因此本文将引入一种PC标记法减少小环的数目。

图1是以变量节点Vi为根节点展开的树形图，具体PC标记法描述如下。

图1 树形Tanner展开

定义一，初始化根节点Vi的PC值为1，若C2和C3是从Vi展开得到，Vi是父节点，C2和C3是子节点，在下一次展开式子节点必须排除父节点。

定义二，子节点的PC值等于父节点乘以x，所以C2和C3的PC值为x，如果一个子节点有两个或者更多的父节点，则PC值计算如下:首先把所有父节点的PC值相加;然后把得到的值再乘以x，即为该子节点的PC值，例如C7有两个父节点，则C7的值为2x3。

PC的表达式wxk中，w和k代表2个重要信息，k代表当前展开节点的环长，w代表当前展开节点的小环数目。若C5，C1和C4为集合中待选校验节点，则此时可以根据计算得到的PC值选择C5，从而保证小环的数目最小，因为C5有2个小环，C1有3个小环，C4有3个小环。

同一个校验节点可能在展开的树形图中多次出现，则校验节点Cj的PC多项式值可以表示为

式中:w1x2k－1表示添加w1条2k的环;w2x2(k+1)－1表示添加w2条2(k+1)的环。如果校验节点Cp在树形图中没有出现，则Cp的环多项式为0，选择Cp建立边，那么将不会出现环长比2(l+1)短的环，l为树形图展开的最大层数。

最优节点选择方法:比较校验节点的环多项式，选择幂次最小的校验节点，然后从幂次最小校验节点集合中选择幂次最大的，这样可以保证该校验节所形成的最小环最大，如果幂次最大的校验节点不唯一，进一步比较系数值，选择系数值最小的可以保证该小环的数目最小。这里不直接在校验节点环多项式中选择幂次最大的理由在于:最大的幂次虽然保证了有较大的环，但是不能保证最小环的大小。

3 基于PC－PEG的QC－LDPC码的构造算法

PC－PEG算法是在PEG算法上基础上改进的，也是一种逐渐增加边的算法，以变量节点按树形图展开，由于是要选择最优的校验节点，所以按上述方法分别计算所有校验节点的PC值wxk，k代表当前展开的节点的环长，w代表当前展开节点的小环数目，所以需要选择k最大、w最小的校验节点。由于LDPC译码算法本质上是一种并行译码，可以通过构造具有QC特性的LDPC码使其实现工程上的部分并行译码，且可以节省存储空间。

综上所述，采用PC－PEG算法构造具有准循环特性的QC－LDPC码，并对并行译码性能进行分析。要构造QC－LDPC码首先要确定参数:矩阵大小、循环移位矩阵、度分布。分析本文提出的PC－PEG算法并对QC－LDPC码进行构成，具体过程如下:

1)构造矩阵H，大小为m×n，循环移位矩阵Q，大小为L×L，确定基矩阵的大小c=m/L，t=n/L。

2)采用PC－PEG算法构造基矩阵Hb，可以保证较大圈长的同时具有较少的小环数目。

对于每一个变量节点Vi(i=1，…，n)，有:

(1)为变量节点Vi添加第一条边时，选择度最小的校验节点连接，其他边时转(2);

(2)变量节点和校验节点PC值初始化;

①变量节点PC值初始化，即

②校验节点PC值初始化，即

(3)按第1节的方法树形展开，并逐层更新变量节点和校验节点的PC值;

①若校验节点Cj由变量节点Vi展开得到，校验节点Cj的PC值更新为

②若变量节点Vq由校验节点Cp展开得到，变量节点Vq的PC值更新为

(4)根据第1节介绍的最优节点选择方法寻找最优校验节点Ci建立边，即

(5)返回(2)完成变量节点Vi其他边的建立。

3)根据步骤2)构造的基矩阵Hb采用式(7)计算得到循环移位参数矩阵P，即

式中，aij是已知的，z是一个从0开始的记号，它表示在基矩阵Hb中每一行1的相对位置，例如z=0每一行首先出现1的位置，z=1表示每一行其次出现1的位置。

4)根据步骤3)计算得到的循环移位参数矩阵P和循环移位矩阵Q，得到最终的校验矩阵H。

4 实验性能测试

4.1 实验小环数目统计

实验采用Mackay构造算法、PEG构造算法、基于PC的PEG算法(PC－PEG)。PEG算法构造的QC－LDPC码(PEG QC－LDPC)、改进 PEG算法构造的 QC－LDPC码(PC－PEG QC－LDPC)的校验矩阵为256 ×512，变量节点的度为3，校验节点的度为6(少数校验节点的度为5或者7)，环的个数统计如表1所示。可以看出采用PC－PEG算法构造的校验矩阵中8环的数目为407，PEG算法构造的校验矩阵中8环个数为897，8环数目减少了54.6%。在引入QC特性后PEG QC－LDPC算法增加了6环数目(192个)，8环数目(1 304个)，虽然引入了QC特性有利于并行译码和存储，但小环的加入必将影响其性能，所以必须减少小环的数目，本文采用的PC－PEG QC－LDPC算法比PEG QC－LDPC算法减少了6环数目103个(53.6%)，减少了8环数目711个(54.5%)，即使它与PEG算法相比还是有一定的小环，但它具有QC特性。

表1 变量节点环个数统计

4.2 并行译码性能分析

在并行译码方面，结合LDPC译码特点:信息在变量节点和校验节点之间根据Tanner图上的边连接来回传递，可知LDPC在理论上是一种并行算法，但在工程运用中很难实现。若有多个CNU(Check Node Update)，VNU(Variable Node Update)计算节点，当CNU更新时需要用到变量节点信息(Qij)，且当需要的所有Qij都准备好时才可以进行运算，同理当VNU进行更新时需要校验节点信息(Rij)，且当所有校验节点信息准备好时才可以进行计算，对于全部并行实现来说可以将每一个Qij和Rij都用一个寄存器来存储，此时再对VNU或者CNU进行运算时可以读取所有数据，实现完全并行译码，但这种方法会耗费大量的存储空间，在实际应用中对于码长较长的情况则不能实现。面对以上问题可以通过时分复用有限存储空间，实现部分并行译码，但对于不规则的LDPC码，在进行VNU或者CNU计算时，可能读取的Qij或Rij不在同一列或同一行上，从而导致大量节点运算处于等待状态，并行译码效率也很低。当引入QC特性后根据校验矩阵分块结构的特点，Qij和Rij的信息可以根据分块矩阵的结构分别存储在L×(n/L)个存储空间上，每个时钟可以读取L×(n/L)个数据，从而也保证了读取的数据刚好在L行或者m/L列上，使变量节点或者校验节点的更新无须一直处于等待所需数据，再通过复用计算单元实现部分并行译码。

4.3 译码性能分析

本节实验采用PEG算法、PEG QC－LDPC算法、PCPEG QC－LDPC算法构造的校验矩阵分别为(256，512)和(512，1 024)，循环移位矩阵大小为8×8和16×16，变量节点的度为3，校验节点的度大多为6，只有少数分布为5和7。仿真条件采用BPSK调制、AWGN信道，采用对数域和积译码算法，最大迭代次数为50，每次测试至少收集到200个错误比特时停止仿真，分别计算在各个信噪比下的BER，如图2～3所示。

图2 (256，512)L=8在不同信噪比下的误码率

图3 (512，1 024)L=16在不同信噪比下的误码率

从表1统计的小环数目可知PC－PEG QC－LDPC和PEG QC－LDPC相对于PEG算法都有小环(6环)，分别为89个和192个，从而导致在相同信噪比下其误码率要高于PEG算法(见图2、图3)，但是其QC特性可使它在并行译码、存储空间上发挥很大作用。PC－PEG QC－LDPC算法误码率要低于PEG QC－LDPC算法，因为其减少了6环数目103个(53.6%)，8环数目减少了711个(54.5%)。从图3可知，当码长增加时PEG算法误码率要明显低于PEG QC算法，但在高信噪比下PC－PEG QC算法的误码率接近PEG算法。

5 结论

本文提出的PC－PEG算法在保证Girth最大的条件下减少了小环的数目，实验测得PC－PEG相比PEG算法在8环数目中减少了490个(54.6%)，并且引入了QC特性，虽然引入了QC特性增加了小环的数目，但是它使得LDPC部分并行译码得以实现，解决了工程上并行实现的问题，并且节省了很多的存储空间，对于较长的LDPC码可在工程中实现。由实验可知，PC－PEG QC－LDPC比PEG QC－LDPC的译码性能好，当码长增加时，在高信噪比下，与PEG算法性能相当。

［1］LI Z W，CHEN L，ZENG L Q，et al.Efficient encoding of quasi cyclic lowdensity parity－check codes［J］.IEEE Trans.Comm.，2006，54(1):7l－81.

［2］CHUNG S，FORNEY G D，RICHARDSON T J.On the design of lowdensity parity－check codes with in 0.0045 dB of the shannon limit［J］.IEEE Communications Letters，2001，5(2):58－60.

［3］LEI J，WANG J H.Quasi－cyclic extension based on PEG algorithm for construction of LDPC codes［J］.Journal on Communications，2008，29(9):103－110.

［4］杨翔，王琳，黎勇.基于PEG算法的多进制PCGC码［J］.重庆邮电大学学报:自然科学版，2008，20(2)，139－142.

［5］VUKOBRATOVIC D，SENK V.Generalized ACE constrained progressive edge－growth LDPC code design［J］.IEEE Communication Letters，2008，12(1):32－34.

［6］刘星成，程浩辉.基于PEG算法的准循环LDPC码构造方法研究［J］.电路与系统学报，2009，14(4):115－119.

［7］LIU X C，CHENG H H.Study on the construction method of Quasi－Cyclic LDPC codes based on progressive edge－growth algorithm［J］.Journal of Circuits and Systems，2009，14(4):115－119.

［8］林炳，姜明，赵春明.基于二维优化的QC－LDPC码构造方法［J］.东南大学学报:自然科学版，2010，40(1):6－10.

［9］熊磊，姚冬萍，陈霞.基于环多项式的渐进边增长构造算法［J］.北京交通大学学报，2010，34(2):20－23.