人们对通信系统的要求是永无止境的，例如希望通信系统更廉价、更快速、更可靠、不但需要传输话音，还需要传输数据图像等，这些迫使许多研究者寻找取得接近或最终达到香农限的可靠通信的方式。文献[1]提出低密度奇偶校验(low density parity check,LDPC)码，近十几年来，它在纠错编码领域得到了极大的发展，已经成为了Turbo码的有力竞争者。LDPC码是最有希望在广泛的信道范围下接近香农极限的误差纠正技术^[2]。

根据LDPC码校验矩阵的构造方式的不同，编码的构造方法主要分为随机构造和结构化构造两类。随机构造的方法虽然纠错性能优秀，但是由于校验矩阵的随机性无法实现简单编码，编码复杂度高、硬件成本昂贵且不易于实现^{[3, 4]}。结构型码由于其校验矩阵的准循环特性使其备受青睐，具有代表性的结构型码主要是文献[5, 6]提出的一系列基于有限几何和基于有限域的LDPC码的构造方法。由于LDPC码不允许存在短环，否则将使得译码器不能快速收敛甚至不能收敛，因此构造大围长的LDPC码成为编码学的研究热点^[7]。文献[8]提出了一类QC-LDPC码存在2k环的充要条件，码字性能非常优秀，但缺点是循环置换矩阵的维数P值下界不能简单连续取值。文献[9]提出当列重为5、6及不小于7的3种情况时，依次利用完全确定的方式构造围长为8的QC-LDPC码。文献[10]基于环约束方程并利用贪婪算法获得大围长的OCS-LDPC码，需要通过计算机搜索获得。文献[11]的确定码和文献[12]的QF-LDPC码都是定式构造围长为8的码字，但是由于列重为3的单一选择以及码率受限，导致实际应用有很大的局限性。

本文利用卢卡斯数列(Lucas sequence)的性质提出了一种行重为k，列重为j(j≥3)的规则的卢卡斯QC-LDPC(L-QC-LDPC)码构造方法。这种方法构造出来的QC-LDPC码可以有效地避免短环，且L-QC-LDPC的围长至少为8；特别地，该方法构造码的码型都具有一定的结构特征、计算复杂度低、易于硬件实现且p值的下界允许连续取值。

QC-LDPC码的校验矩阵是由分组矩阵构成的，而每个分组的矩阵又是由满秩的循环置换矩阵和全0的方阵组合而成。校验矩阵H的列重和行重分别用j和k表示，QC-LDPC码的校验矩阵为：

对应的指数矩阵为：

式中，2≤j≤k≤p；I₀是p×p维的单位矩阵；I_n是置换矩阵，通过I₀右移n位得到；指数矩阵中的y(s,i)(0≤s<j，0≤i<k)表示该循环置换矩阵的移位值。

校验矩阵含有的环可以用对应的指数矩阵中的元素表示，QC-LDPC码中长度为2k的环可以表示为y(s₀,i₀),y(s₀,i₁),y(s₁,i₁),…,y(s_k-1,i_k-1),y(s_k-1,i₀),y(s₀,i₀)。文献[8]给出了校验矩阵中存在长度为2k的环的充要条件满足式(3)，其中，i_t≠i_t+1,s_t≠s_t+1。构造LDPC码的首要条件就是避免四环，即y(s₀,i₀)-y(s₁,i₀)+y(s₁,i₁)-y(s₀,i₁)≠0 mod p。因此若要使得设计的QC-LDPC码避免存在长度为2k的环，就必须通过一定规则的设计使得下式不成立：

定义1 对于一个整数数列l(n)，n为正整数。如果l(n)=l(n-1)+l(n-2)，n≥3且l(1)=2，l(2)=1，满足以上初始条件和递推关系的数列称为卢卡斯数列，它的每一项称为卢卡斯数。

典型卢卡斯数列表示如下：2,1,3,4,7,11,18,39,57,96，…。

定理1 对于一个卢卡斯数列，若n>m且n，m，k∈Z+，则有l(n+k)-l(n)>l(m+k)-l(m)^[13]。

本文基于卢卡斯数列中元素的性质特征构造出一个列重和行重分别为j和k、围长至少为8的规则QC-LDPC码。

首先构造一个指数矩阵为：

式中，W的维数为j×k，j≥3，k>j。指数矩阵W的第一行为全0，第二行为集合{l(n)}中的前k个元素：l(0),l(1),…,l(k-1)；从集合{l(n)}中的第j+1个元素开始到第j+k个元素作为指数矩阵的第三行：l(j+1),l(j+2),…,l(j+k)；…；最后一行的元素为：l((j-2)(j+1)),l((j-2)(j+1)+1),…,l((j-2)(j+1)+k-1)，即指数矩阵中任意元素y(s,i)( 0≤s<j,0≤i<k)，当s=0时，y(s,i)=0；当s≠0时，y(s,i)=l((s-1)(j+1)+i)。然后对指数矩阵W进行填充，W中对应的元素用p×p的单位矩阵及其相应的循环移位矩阵替换，其中p>l((j-2)(j+1)+k-1)；0元素用p×p的单位矩阵I₀替换，I_y(s,i)用相应的单位矩阵右循环移位y(s,i)位得到的矩阵I(l((s-1)(j+1)+i))进行替换，最终构成校验矩阵H。

定理2 只要满足p>l((j-2)(j+1)+k-1)，基于卢卡斯数列构造的QC-LDPC码的校验矩阵H对应的Tanner图的围长至少为8。

证明：为了证明H对应的Tanner图中的环长为8，要依次证明Tanner图中没有四环和六环。

对于四环，由式(3)可知要避免四环即y(s₀,i₀)-y(s₁,i₀)+y(s₁,i₁)-y(s₀,i₁) ≠0 mod p。为了不失去一般性，假设i₀<i₁,s₀<s₁，则有：

y(s₀,i₁)-y(s₀,i₀)=l((s₀-1)(j+1)+i₁) -
l((s₀-1)(j+1)+i₀)
y(s₁,i₁)-y(s₁,i₀)=l((s₁-1)(j+1)+i₁)-
l((s₁-1)(j+1)+i₀)

由定理1可得：

y(s₁,i₁)-y(s₁,i₀)>y(s₀,i₁)-y(s₀,i₀),
0<y(s₁,i₁)-y(s₁,i₀)+y(s₀,i₀)-y(s₀,i₁)<p

因此所构造的校验矩阵已经有效地避免了四环的存在。

对于六环，Tanner图中存在六环的可能性有6种形式，如图 1所示。

图1

图1 6种六环的存在形式

图 1所示6种六环的存在形式，根据结构形式可将其分为两类：前4种具有相同的结构形式为一类，后两种具有相同的结构形式为另一类。每一类中的任意形式可以在已知其中一种的情况下，通过特定的方式得到其他形式。所以，为了证明H矩阵中不存在六环，只需分别证明这两种结构任意一种形式是不存在的，理论分析及证明如下：

1) 第一大类

图 1中的形式1的六环不存在性证明分为两种情况。

① 当六环的所在位置的第一行就是校验矩阵的第一行，即s₀=0，令t_i=s_i-1,1≤i<j，由式(3)和式(4)可得：

y(s₀,i₀)-y(s₀,i₁)+y(s₁,i₁)-
y(s₁,i₂)+y(s₂,i₂)-y(s₂,i₀)=
0-0+l(t₁(j+1)+i₁)-l(t₁(j+1)+i₂)+
l(t₂(j+1)+i₂)-l(t₂(j+1)+i₀)=
l(t₁(j+1)+i₁)-l(t₁(j+1)+i₂)+
l(t₂(j+1)+i₂)-l(t₂(j+1)+i₀)

由图 1中的第一种形式令i₀=i₂-m,i₁=i₂-n且m>n，原式可以简化为：

由定理1可得：l(t₂(j+1)+i₂)-l(t₂(j+1)+i₂-m)>l(t₁× (j+1)+i₂)-l(t₁(j+1)+i₂-n)。

所以，0<(5)<l(t₂(j+1)+i₂)<p，即原式≠0 mod p。

② 当s₀≠0时，有：

y(s₀,i₀)-y(s₀,i₁)+y(s₁,i₁)-
y(s₁,i₂)+y(s₂,i₂)-y(s₂,i₀) >
y(s₀,i₀)-y(s₀,i₁)+y(s₁,i₁)-
y(s₁,i₂)+y(s₁,i₂)-y(s₁,i₀) =
y(s₀,i₀)-y(s₀,i₁)+y(s₁,i₁)-
y(s₁,i₀)>0
y(s₀,i₀)-y(s₀,i₁)+y(s₁,i₁)-
y(s₁,i₂)+y(s₂,i₂)-y(s₂,i₀) <
y(s₂,i₀)-y(s₀,i₁)+y(s₁,i₁)-
y(s₁,i₂)+y(s₂,i₂)-y(s₂,i₀) =
y(s₁,i₁)-y(s₀,i₁)+y(s₂,i₂)-
y(s₁,i₂)<y(s₁,i₂)+y(s₂,i₂)-
y(s₁,i₂)=y(s₂,i₂)<p

所以利用夹逼准则可知，原式≠0 mod p。

2) 第二大类

图 1中的形式5的六环不存在性证明也分为两种情况。

① 六环的所在位置的第一行就是校验矩阵的第一行，即s₀=0，令t_i=s_i-1,1≤i<j，由式(3)和式(4)可得：

y(s₀,i₀)-y(s₀,i₁)+y(s₂,i₁)-
y(s₂,i₂)+y(s₁,i₂)-y(s₁,i₀)=
0-0+l(t₂(j+1)+i₁)-l(t₂(j+1)+i₂)+
l(t₁(j+1)+i₂)-l(t₁(j+1)+i₀)=
l(t₂(j+1)+i₁)-l(t₂(j+1)+i₂)+
l(t₁(j+1)+i₂)-l(t₁(j+1)+i₀)

由图中的第五种形式令i₀=i₂-m，i₁=i₂-n且m>n，原式可以简化为：

由定理1可得：

l(t₁(j+1)+i₂)-l(t₁(j+1)+i₂-m)<
l(t₂(j+1)+i₂)-l(t₂(j+1)+i₂-n)

所以，0>(6)>-l(t₂(j+1)+i₂)，即原式≠0 mod p。

② 当s₀≠0时，有：

y(s₀,i₀)-y(s₀,i₁)+y(s₂,i₁)-
y(s₂,i₂)+y(s₁,i₂)-y(s₁,i₀)<
y(s₁,i₀)-y(s₁,i₁)+y(s₂,i₁)-
y(s₂,i₂)+y(s₁,i₂)-y(s₁,i₀)=
y(s₁,i₂)-y(s₁,i₁)+y(s₂,i₁)-y(s₂,i₂)<0
y(s₀,i₀)-y(s₀,i₁)+y(s₂,i₁)-
y(s₂,i₂)+y(s₁,i₂)-y(s₁,i₀)>
y(s₀,i₀)-y(s₀,i₁)+y(s₂,i₁)-
y(s₂,i₂)+y(s₀,i₂)-y(s₀,i₀)=
y(s₀,i₂)-y(s₀,i₁)+y(s₂,i₁)-
y(s₂,i₂)>y(s₂,i₁)-y(s₂,i₂)>
-y(s₂,i₂)>-p

所以，利用夹逼准则可知，原式≠0 mod p。

综上所述，图 1中的6种六环形式是不存在的。因此当p>l((j-2)(j+1)+k-1)时，构造的L-QC-LDPC码的校验矩阵对应的Tanner图中没有四六环，定理2得证。

通常情况下，QC-LDPC码为了存储其校验矩阵，需要存储指数矩阵中的每一个元素值，即使是仅仅存储每一个元素值，也需要一定的存储空间，对于编码器来说，节省存储空间就是降低实际应用中的成本。而对于卢卡斯数列，仅需存储0、l(1)和l(2)的3个元素，其他元素的值可由简单的加法和乘法运算得到，这样很大程度上节省了系统所需要的存储空间。

本文在仿真中采用BPSK调制，传输信道选用AWGN信道，采用BP译码算法。首先基于卢卡斯数列所构造的L-QC-LDPC码指数矩阵如式(4)所示；然后确定所构造的LDPC码的列重和行重的参数j和k，构造一个j×k的指数矩阵；例如j=3，k=6，对应的指数矩阵W可以表示为W(3,6)。将k维的全0向量作为指数矩阵的第一行，前k个卢卡斯数作为指数矩阵的第二行，第四个到第k+3个数作为指数矩阵的第三行，即得到指数矩阵：

通过指数矩阵确定参数p，上述指数矩阵p的取值范围为p>47，为构造码长1302的QC-LDPC码，令p=217，指数矩阵中的0元素扩展为217×217的单位矩阵I₀，其他元素扩展为相应的单位矩阵的右循环移位。图 2给出了所构造的码字在BP译码中不同迭代次数下的误码性能，由图 2可见，在BER为10^-5时，迭代次数为10、20、30、40和50时所需的SNR分别为：3.81、3.60、3.48、3.45和3.43dB，距香农限分别为：3.623、3.413、3.293、3.263和3.243dB。在SNR=4.0dB的情况下，所对应的BER分别约为：3.277×10^-6、7.424×10^-7、3.84×10^-7、3.064×10^-7和2.569×10^-7。通过以上分析可以得出，随着迭代次数的增加，纠错性能越来越好，但NCG提高幅度却越来越小。迭代过程其实是节点信息更新的一个过程，变量节点译码器将附加的信息传送给校验节点译码器，然后校验节点译码器将更新的信息传送给变量节点译码器，如此迭代，最终完成整个译码过程。但是当每个译码器信息更新到一定量后，每次迭代后再转化的信息很少，对结果影响不大，甚至有可能没有需要再转化的信息。通过仿真分析可以看出，译码迭代30次与50次时与香农限仅仅相差0.05dB左右，非常接近，而译码迭代50次时时间复杂度和运算量都较高。因此，需要在复杂度和纠错性能之间找到一个折衷点，所以选择迭代30次。

图2

图2 不同迭代次数的误码性能图

为充分说明(1302，651)L-QC-LDPC码的纠错性能，在相同条件下不同码字仿真结果如图 3所示。由图 3可知，在误码率为10^-6时，在相同的码长、1/2码率的条件下，所构造的L-QC-LDPC码与其他算法构造的码相比，均有不同程度的性能提升，如表 1所示。从表中可以看出，L-QC-LDPC码与文献[10]的OCS-LDPC码相比，可获得约2dB的净编码增益，与文献[11]的确定性码及文献[12]的QF-LDPC码相比，分别有约0.8dB和0.1dB净编码增益的改善。在相近码长、相同行列重和码率的情况下，所提出的码字与文献[7]中基于有限域的循环子集的QC- LDPC码相比，提高了约0.5dB的净编码增益的改善。同时可以从表中看出，本文提出的码最接近香农限。

图3

图3 不同码字的性能对比图

表1

表1 不同对比算法所构造的码与香农限的距离及和L-QC-LDPC码相比获得的净编码增益

表1 不同对比算法所构造的码与香农限的距离及和L-QC-LDPC码相比获得的净编码增益 码型 距香农限距离 /dB 净编码增益 /dB L-QC-LDPC码 3.613 / OCS-LDPC码 5.613 2 D-LDPC码 4.463 0.8 QC-LDPC码 4.113 0.5 QF-LDPC码 3.713 0.1

本文提出一种基于卢卡斯数列构造围长至少为8的规则L-QC-LDPC码的确定性方法。当p>l((j-2)(j+1)+k-1)时，这类码字可以有效地避免四六环。仿真结果表明，在同等条件下，L-QC-LDPC码的性能明显优于OCS-LDPC码和确定性码，略优于QF-LDPC码。与OCS-LDPC码相比，其构造简单，不需要借助计算机搜索或者计算，虽然确定性码和QF-LDPC码都是定式构造—给定校验矩阵的显式表达式，但是它们的列重受限。除此之外，对于编码器而言，基于卢卡斯数列的码字只需要存储3个元素：0、l(1)和l(2)，其他元素的值可以通过简单的加法和乘法运算得到，可以有效地节约系统所需要的存储空间，进而降低硬件实现成本和复杂度。