具有较大围长的正则LDPC码构造方法介绍

1962年Gallager提出低密度校验(Low DensityParity Check，LDPC)码，后来Tanner对它进行了很有价值的补充，直到1995年又被Mackey重新提出。如果采用和积迭代译码算法，LDPC码具有非常接近香农限的性能。如果在LDPC码的Tanner图中存在环，在迭代译码的过程中错误信息将会膨胀，对于LDPC的译码性能相当有害，尤其是较短环的存在，所产生的危害尤为严重。所以，在构造LDPC的过程当中，要尽量避免短环的出现。为了尽量减小Tanner图中环的存在对相应LDPC码在和积译码算法下所得性能的影响，一些研究学者基于代数方法和启发式搜索方法，提出了一些具有较大围长的LDPC码构造方法。研究表明，通过增大LDPC码的围长，在一定程度上可以改善码的纠错性能。本文构造了正则LDPC码，在构造过程中讨论了设计围长的参数选举，使得满足一定的条件就可以避免校验矩阵的小围长出现，使得所构造的矩阵具有较大围长。

1．LDPC码的构造理论

考虑长为16的(2，4)正则LDPC码对应的Tanner，如图1所示。


从图1中很显然可以看出，该Tanner中环的最小长度为8，因此对应LDPC码的围长也为8。

按图1将其中的变量结点和校验结点依次编号，可以得到对应LDPC码的校验矩阵，如图2所示。


图2矩阵很有规律，可以看作是由两个行重为2、维数为8×8的循环方阵拼接而成。因此可以猜想，采用某些有规律的矩阵合并成校验矩阵，这样生成的LDPC码很可能会具有较大的围长。或者说，将LDPC码的校验矩阵分裂为若干个子矩阵，然后每个子矩阵再按照某种规律构造，就有可能避免小环的出现。

这里采用矩阵分裂的思想。设要构造一个长为72(n=ρUU∈N)的(λ，ρ)正则LDPC码，将该码的校验矩阵分裂为(λ，ρ)个U×U的子矩阵。



式中：每个子矩阵Hi,j=I(ai,j)(0≤i<λ，0≤j<ρ)均为一个单位阵或者单位阵的循环移位ai,j表示该单位阵的各行循环右移的位数。显然，这样构造的校验矩阵也不可能为满秩，至多为λρ-λ-1。
为便于描述，用A=(ai,j)表示由各个子方阵的循环移位参数组成的矩阵，用(I，J，i，j)表示校验矩阵中的元素，其中(I，J)为该元素所属的子矩阵的坐标，(i，j)为该元素在它所属的子矩阵中的坐标。称Tanner图中每个变量结点参与的所有环的最小长度为该变量结点的环长，则显然相应LDPC码的围长就等于各个变量结点环长的最小值。将n个变量结点分为P组，每一组变量结点对应一列子矩阵，则考虑到各个子矩阵的循环特性，有如下定理成立。

定理1  属于同组的变量结点具有相同的环长。

证明：设任意两个同组的变量结点x和y，分别对应一列子矩阵的第x列和第y列，且y-x=dmodU，其环长分别为C(x)和C(y)，并设变量结点x的最小环路径如图3所示。



根据各个子矩阵的循环特性，可以找到另一个环的路径如图4所示。



显然该环路长度为C(x)且经过变量节点y，故有：

C(x)≥C(y)    (2)
同理可得：
C(x)≤C(y)    (3)

综合上面两式，有C(x)=C(y)即对任意两个同组的变量节点，它们的环长均相等，证毕。

由定理1可知，按照上述方法构造的校验矩阵所对应的LDPC码，所有变量节点的环长至多有ρ种情况，因此对这样构造的矩阵只需要分别从各组中抽取一个变量节点，然后只对这ρ个变量节点进行检测，即可确定整个码的围长。

2校验矩阵中循环移位参数的选取

下面讨论4环的情况。如果一个LDPC码含有4环，则它所对应的校验矩阵中必然有4个“1”处于某个矩形的四个顶点，该环路路径可表示为：


定理2  按照式(1)所示矩阵分裂方法构造的矩阵所对应的LDPC码不含长为4的环的充要条件有式(6)成立：


该定理的正确性从前面的描述中即可得知，这里不再赘述。

由定理2很容易得到下面推论：

推论1：按照式(1)所示矩阵分裂构造方法构造的矩阵所对应的LDPC码不含长为2l的环的充要条件为：


在编码设计时，可以首先确定所构造LDPC码设计围长，然后根据上面的定理和推论列出相应的不等约束，进而寻找满足这些不等约束的参数即可。

在进行参数选择时，可以根据上面分析和设计的围长列出各参数所对应满足的约束方程，然后寻找满足这些约束方程的参数取值。然而，由于这些约束方程均为不等约束，因而无法采用一般的方程组求解法；如果采用穷举的方法去遍历各个参数的所有可能组合，继而从中找出满足约束的一组，搜索的范围将有己U(λ-1)(ρ-1)，这样即使U的取值范围很小(如102)，总的搜索范围也将很大，因而无法实现。

为了实现参数的快速选取可以采用下述逐参试探算法：   

(1)令ai,0=0(i=0，1，…，λ-1)及a0,j=0(j=1，2，…，ρ-1)；

(2)随机在{0，1，…，U-1)中选取a1,1取值，然后判断a1,1是否满足给定的不等约束，若满足则确定取值，否则重新执行(2)

(3)按照(2)的方法一次确定剩余子矩阵的循环移位参数。

按照上面算法，每个参数至多需要U次试探，这样总共的试探次数至多为(λ-1)(ρ-1)U，远远小于整个搜索空间U(λ-1)(ρ-1)。

由于该算法采用逐个确定参数的方法，显然最后确定的参数受到的约束是最多的，定义N(l)为考虑消除Tanner图中长度为2l的环时最后一个参数受到的约束方程个数，则有：



由于各个约束方程均为不等约束，每个约束只能限制参数不能取某个特定的值，因此所有不等约束限制参数所不能取的值的个数至多为约束方程数目的两倍。考虑到所要构造的LDPC码的码长，U的取值一般在100左右，因此消除六环一般都可行。

3仿真及性能分析

取U=168，按照上面的方法构造长度为1 008的(3，6)正则LDPC码，通过计算机搜索检测发现，得到子方阵的循环参数为：

检测发现LDPC码的围长为10，为了保证所构造码的码率严格等于0.5，可以从生成的检验矩阵中删去2个“1”。该码在AWGN信道下的纠错性能如图5所示，图中的另外两条曲线分别为相同长度、随即构造、不消除4环的(3，6)正则LDPC码的性能曲线。其中，girth表示围长；ave表示所有变量节点的平均环长。

文献[8，9]采用PEG算法所构造的长度为1 008的(3，6)正则LDPC码的围长为8，平均环长为9.66，稍劣于上面构造的LDPC码，因此该方法用于正则LDPC码的构造时要优于其他的构造方法。

通过分析发现，采用该方法构造的正则LDPC码与文献[10]所述方法一样，其围长存在一个上限，下面进行详细介绍。考虑一个维素为2U×3U的矩阵，将其分裂成6个维素为U×U的子方阵，每个方阵均为单位阵或单位阵的行循环移位，则可以得到一个行重为3、列重为2的矩阵。不失一般性，令第一行子方阵均为单位阵，其余两个方阵的行右循环移位参数分别为a1,1和a1,2，则不论a1,1和a1,3如何取值，该矩阵始终存在如图6所示的12环。


将图6环上各个的非零元素依次编号，并令编号为1的元素坐标为(0，0，x，x)，则环上各节点的坐标如图7所示。



因此，若采用上面的方法构造(λ，ρ)正则LDPC码，只要λ≥2，ρ≥2且λ+ρ≥5，相应的校验矩阵中也就必然包含图所示的字矩阵或其转置矩阵，于是得到的LDPC码的围长也就必然不可能超过12。

4结  语

给出了一种高围长的正则LDPC码的构造方法，具体分析了去环方法和循环移位参数的选取。用这种方法构造的LDPC码的H矩阵具有很好的结构。仿真表明，用该方法构造的码在AWGN信道下性能要优于随机构造的码。