杨卫国，于志军

(海军航空大学，烟台 264001)

0 引 言

低密度奇偶校验码(Low-Density Parity-Check，LDPC码)因其接近香农极限的译码性能，成为近年来信道编码研究的热点。LDPC码是Gallager博士在1962年提出的，但由于当时的条件所限，并没有引起人们足够的关注，在沉寂了几十年后，由Mackay和Neal证明了其在BP译码算法下，可以达到接近香农极限的性能，这之后，LDPC码爆发出了巨大的生命力[1-3]。以Gallager随机构造法和Mackay随机构造法为代表的随机构造法引领了LDPC码最初几年的发展，在Yu Kou和Shu Lin等人提出了利用有限域里的欧式几何和投影几何来构造LDPC码之后，循环和准循环LDPC码进入了人们的视线，这一类码字的校验矩阵具有循环或准循环特性，在编码过程中，编码器只需要使用简单的线性反馈移位寄存器来实现，大大降低了编译码复杂度，且有效缩减了需要的存储空间，是近几年来发展的重点。本文根据循环差集构造的检验矩阵自身的特点，采用快速编码的方法完成循环差集QC-LDPC码的构造，进一步降低了编码复杂度[4-8]。

1 循环差集的基本定义

1.1 循环差集的定义

定义一个循环差集由3个整数(v,k,λ)组成的整数对确定，记作D(v,k,λ)，表示以正整数v为模的k个互不同余的整数所组成的集，具体如(1)式所示

D=(a1,a2, …,ak)(modv)

(1)

如果对于d≠0(modv)，在D中恰好存在λ个有序对(ai,aj)能使等式(2)成立，

d=ai-aj(modv)

(2)

其中v称为循环差集的模，k称为循环差集的大小，3个参数之间满足k(k-1)=λ(v-1)的关系式。

当λ=1时，一个大小为k的循环差集的模v满足等式(3)，我们称这样的循环差集为完备循环差集。

v=k2-k+1

(3)

在完备循环差集的差集表中，非零元素只出现一次。例如一个大小为k=4，模v=13的完备循环差集{0,1,8,10}的差集表如表1所示。

表1 k=4，v=13完备循环差集差集表

表1中左侧表的第一行和第一列顺序排列k=4，v=13完备循环差集的元素，表中其余行的元素均由其上一行元素对应减去第一列的该行元素所得；对表1中左侧的表的有效部分取模13就可以得到右侧的差值表，表中除了0元素外，其余元素均不相同，且每个元素都只出现一次，且13满足等式v=k2-k+1，因此循环差集{0,1,8,10}是一个完备循环差集。又例如模v=21，大小为k=5的完备循环差集为{0,5,6,9,19}。

1.2 完备循环差集的构造

差集以0，0，1开头，序列中其他元素满足如下等式：

an=A·an-1+B·an-2+C·an-3

(4)

当A=B=C=1时，得到如下序列：

0，0，1，1，2，4，7，13，24，

44，81，149，274，504，927，…

对该序列取模q=3，并从0开始计数得：

表2 模13的完备循环差集

从表2中可以看出，对上述序列取模q=3后，若以“双0”为起始点，序列构成了一个周期为13的循环，而0的位置{0,1,8,10}刚好是模13的完备循环差集。完备循环差集序列的构造由三元数组(A,B,C)来确定，当取A=C=1,B=0时，对生成的序列取模q=2得：

表3 模7的完备循环差集

这样就构成了一个模为7的完备循环差集{0,1,5}，需要特别注意的是，循环差集的模和序列取模是不一样的(循环差集的模v=7，序列取模q=2)。

通过以上两个例子可以看出，当完备循环差集的模v不同时，用来生成循环差集的序列不同，对序列取模的模q也不相同，这里模q只可以是任意素数，通过改变(A,B,C)的值，我们总能找到可以生成模v=q2+q+1，大小k=q+1的完备循环差集的序列，具体不同模q所对应的(A,B,C)的生成规则如下：

(1)A,B∈[0,1,2,…,q-1]，C∈[1,2,…,q-1]且A和B不能同时为零，改变A,B,C的值，使到的序列的周期为v=q2+q+1，q=k-1是个素数；

(2)若存在任意一个正的整数z，满足式子z3=Az2+Bz+C(modq)，则此时的(A,B,C)所对应的序列不是我们需要的。

2 基于完备循环差集LDPC码的构造

使用和积译码算法时，校验矩阵中的环长对译码性能影响很大，一旦出现长度为4的环，将使码字的性能急剧恶化，而利用完备循环差集构造的LDPC码可以保证校验矩阵中不含有长度为4的短环，因此，在校验矩阵扩展后产生的新的校验矩阵中也不会含有4环[4-5]。具体的构造步骤如下：

(1)根据完备循环差集的大小k，模v以及三元数组(A,B,C)来生成一个完备循环差集；

(2)根据生成的完备循环差集得到相应的关联矢量，关联矢量可以通过对完备循环差集取模q=k-1得到，当模值为零则对应位取“1”，否则取“0”，关联矢量的长度为v，例如，表-3中的模7完备循环差集的关联矢量为[1 1 0 0 0 1 0];

(3)将关联矢量按照每次一位的位移量同方向循环移位v-1次，依次得到初始矩阵的2～v行，组合得到一个v×v的矩阵，例如首行为[1 1 0 0 0 1 0]，次行为[0 1 1 0 0 0 1]，依此类推；

(4)根据不同的权重和码率要求，将初始矩阵进行列分割得到校验矩阵的基矩阵；

(5)直接用步骤(4)生成的基矩阵作为校验矩阵或者扩展基矩阵，将基矩阵中的0元素和1元素分别替换为全零矩阵和循环移位矩阵，即得码字的校验矩阵。

这种编码方法虽然利用完备循环差集的特性，构造了不含四环的校验矩阵，但是在编码过程中仍然需要用到生成矩阵，对于码长较长的码字仍有大量的计算，没有能充分利用完备循环差集的特性。在生成关联矩阵的过程中不难发现，由于构造码字设定的完备循环差集均以“双0”开头，因此，产生的关联矢量的前两位永远是“1”，即[1 1 …]，以此生成的关联矩阵就必然具有双对角线的结构，继续前面的例子，以模7完备循环差集为例，关联矢量循环移位后的矩阵如下式所示：

(5)

式(5)中的矩阵H具有标准的双对角线结构，在快速编码算法中，通过将校验矩阵合理的进行排列，使得校验位的元素可以构成准双对校验结构，就可以在编码过程中不通过生成矩阵直接进行编码生成系统码。以此为依据，重新定义步骤(4)，在对初始矩阵进行列分割的过程中，特意保留双对角线上的1元素，即：

(4’)对初始矩阵进行列分割，对于第j列(j>1)，保留H(j-1,j),H(j,j)两元素，并将其余位置置0生成新的列，将新生成的列放置于基矩阵的第v+j列，第一列只保留第一行的元素。

步骤(5)不变。

继续上面的例子，初始矩阵H按照快速编码方法进行列分割后生成的基矩阵如式(6)所示。

⟹

(6)

生成矩阵Hb由于具有双对角线结构，在编码过程中可以采用快速编码方法，在不需要生成矩阵的情况下完成对信息的编码，相对于以往利用循环差集构造LDPC码的方法，具有更高的编译码速率。

在对基矩阵进行扩展时，最简单的方法就是将矩阵中的1元素和0元素分别替换为单位矩阵和全零矩阵，但这样生成的校验矩阵与基矩阵的环结构基本一致，并无太多改善，为了确保获得性能更加优良的码字，在扩展基矩阵的过程中，可以通过计算机搜索的方式确定循环移位矩阵的移位次数，减少校验矩阵中的6环，改善码性能。

3 仿真分析

按照前文所示的步骤，由于进行步骤(4’)时，除了第1列分割出一个“1”，其余v-1列分割出两个“1”，当k>3时，在不需要进行快速编码的情况下，可以根据码率继续对前v列进行列分割得到相应的校验矩阵。根据不同的素数可以构造不同的循环差集，继而可以构造不同码率的各种码长的LDPC码，表4列出了不同素数对应的不同码长的LDPC码。

表4 部分循环差集对应的LDPC码

根据香农信道编码定理的三个必要条件之一码长趋于无限长时码性能接近香农极限，且q较大时循环差集的构造比较复杂，因此本文只研究码长较短的情况。表-5列出了部分素数对应的完备循环差集，首先考虑快速编码算法，即码率均为1/2。

表5 部分素数对应的完备循环差集

根据表5所示，取z=0，对应不同的q可以得到不同码长的LDPC码，按照前文所述的步骤，根据完备循环差集生成的码，对编码输出采用BPSK调制，传输信道选用AWGN信道，译码算法采用和积译码算法，对不同码长的码性能仿真结果如图1所示。

图1 不同q值构造的LDPC码

从图1中可以看出，在信噪比较低时，较小的q值和较短码长的码字性能反而高于码长较长的码字，这是因为，在利用循环差集构造LDPC码时，行重就等于循环差集的大小k，由LDPC码校验矩阵的性质可知，变量节点的度越大，该变量节点从校验节点上获得的校验信息就越多，在译码时就可以迅速收敛到其真值，而校验节点的度数越大，在校验方程中引入的误差就越大，校验节点的度数就是常用的行重，因此，行重小的码在一定码长范围内有更优异的性 能，但当信噪比较大时，码长对码性能的影响更加明显。

图1显示的是直接采用循环差集构造的LDPC码的性能，当z≠0时，理论上可以通过改变z的值获得各种码长的码字，继续对各种循环差集构造的码字进行仿真，同样对编码输出采用BPSK调制，传输信道选用AWGN信道，译码算法采用和积译码算法。对上述不同q的取值，分别取z=5,z=10，仿真结果如图2～图5所示。

图2 q=5时循环差集LDPC码性能仿真

图3 q=7时循环差集LDPC码性能仿真

图4 q=11时循环差集LDPC码性能仿真

图5 q=17时循环差集LDPC码性能仿真

通过对图2～5的比较不难看出，当z≠0时，码长变长了，以不同q值构造的码性能均有了一定程度的提高，但各种码字性能提高的程度大相径庭，对于q=17的情况，根据上述分析性能仍然较差；q=11时，在低信噪比情况下码字性能几乎没有改善，只有信噪比较高时码字性能改善明显；q=5和q=7两种情况下码字性能改善最为明显。

当不采用快速编码算法，对q=5，q=7，q=11和q=17分别取码率为1/3，1/3，1/4，1/4进行仿真，仿真条件不变，仿真结果如图6所示。

图6 不同q值不同码率LDPC性能比较

从图6中可以看出，仍然是q=5和q=7时构造的码字具有最优的性能，q=11和q=17的码字性能几乎相同。由于对不同q值的仿真结果中码字长度均不一致，q=5和q=7时在码字长度较短的情况下仍然获得了比码字长度较长的码更优异的性能，因此，单独对q=5和q=7时构造的码字进行仿真。

图7 q=5和q=7时构造的码字性能比较

从图7中可以看出，当码率为1/2时，q=5和q=7构造的码长相近的码字性能几乎相同，而当码率为1/3时，q=7构造的码字性能更为优异，但无论q值的改变，本文方法构造的码字在1/2码率时拥有最佳的性能。

基于此，分别采用q=5和q=7构造的码字为基准码，码率为1/2，通过改变z的值使其与IEEE802.16e标准的码字性能进行比较，仿真结果如图8。

图8 完备循环差集构造的LDPC码与IEEE802.16e标准的码在长码时性能比较

图8中，q=5，z=28构造的码长为1736的码字，q=7，z=15构造的码长为1710的码字与IEEE802.16e标准中码长为1728的码字性能进行对比，通过观察不难发现，三种码的性能极为接近，在信噪比小于1.5时，q=5构造的码字与IEEE802.16e标准码性能几乎一致，但当信噪比增大时，完备循环差集q=7构造的LDPC码的性能更加优异。

4 结 语

本文基于完备循环差集构造了QC-LDPC码的校验矩阵，并根据构造特点对检验矩阵进行了列分割重排，使得校验矩阵具有了双对角线结构，在编码过程中可以采用快速编码算法，不必计算生成矩阵，进一步简化了编码过程，且由完备循环差集构造的校验矩阵中不含四环，保证了码性能，同时由于在校验矩阵的构造过程中只是对关联矢量的移位组合，因此大大节省了存储空间，此外，根据完备循环差集的生成方式，几乎可以覆盖所有码字长度，且可以通过改变z的值，对校验矩阵进行扩展，构造方式多样，码字性能优异。另外通过仿真分析发现，并不是所有的完备循环差集都适合构造LDPC码，特别是当差集大小较大，对应构造的校验矩阵的行重过大会严重影响码字性能，在本文选取的几种循环差集构造的LDPC码中，q=5和q=7时构造的码字无论是短码还是长码都有较优异的误码性能，低信噪比时q=5构造的码字性能占优，而高信噪比时q=7构造的码字性能占优[9-10]。

[1] GALLAGER R G.Low-density parity-check codes[J].Information Theory,IRE Transactions on,1962,8(1):21-28.

[2] MacKay D J C.Good error-correcting codes based on very sparse matrices[J].Information Theory,IEEE Transactions on,1999,45(2):399-431.

[3] 何善宝，赵春明，姜明.LDPC码的一种循环差集构造方法[J].通信学报，2004,25(11)：112-118.

[4] 靳蕃，陈志.组合编码原理及应用[M].上海科学技术出版社，1994.

[5] Fossorier M P C.Quasi-cyclic low-density parity-check codes from circulant permutation matrices[J].IEEE Transactions on Information Theory,2004,50(8):1788-1793.

[6] Tanner R M,Sridhara D,et al.LDPC block and convolutional codes Based on circulant matrices[J].IEEE Transactions on Information Theory,2004,50(12):2966-2984.

[7] Gallager R G.Low-Density Parity-Check Codes[D],Cambridge,M A:MIT Press,1963.

[8] MA Ke-xiang,ZHANG Peng.Low-Delay Loop Detection Algorithm for LDPC Codes[J].Journal of CAEIT,2015(4):341-343.

[9] Ivan B.Djordjevic.Quanturn LDPC Codes from Balanced Incomplete Block Designs[J].IEEE Commun.Letters,Vol.12,No.15,May 2008.

[10] Baraza J,Gracia J,Blanc S,et al.Enhancement of Fault Injection Techniques Based on the Modification of VHDL Codes[J].IEEE Trans.on Very Large Scale Integration Systems,2008,16(6):693-706.