围长为8的QC-LDPC码的显式构造及其在CRT方法中的应用

张国华，孙蓉，王新梅

（西安电子科技大学 综合业务网理论及关键技术国家重点实验室，陕西 西安 710071）

1 引言

具有较大围长的准循环低密度奇偶校验(QC-LDPC)码，由于具有线性时间可编码、需要的存储空间较小、译码性能优良等优点，目前得到人们越来越多的研究。借助于计算机搜索，人们提出了一些构造围长大于6的QC-LDPC码的准随机方法[1,2]。这些基于搜索的方法虽然比较灵活,但是由于没有解决码的存在性问题，因此不可避免地存在构造失败的可能性。相比而言，确定性方法可以直接给出校验矩阵的显式表达式，不存在构造失败的可能性，但是确定性方法的设计具有很大的挑战性，所以研究成果比较罕见。

(J,L) QC-LDPC码的校验矩阵是一个JL×的阵列，阵列中的每个元素都是一个PP×的循环置换矩阵（CPM）。到目前为止，构造围长大于6的QC-LDPC码的确定性方法只有几种。对于列重 J为 3的情形，Tanner[3]基于群结构提出了一类围长几乎全部达到最大值12的(3,5)QC-LDPC码（码长为5P,P为素数且P-1可被15整除）；B.Vasic[4]基于最早序列提出了一类girth-8 (3,L)QC-LDPC码;K.K.Liu[5]提出了一类girth-8 (3,L) QC-LDPC码；张国华[6]受贪婪搜索启发提出了一类girth-8 (3,L)QC-LDPC码。对于列重为4的情形，目前已知的确定性构造方法只有一种，即K.K.Liu提出的一类girth-8 (4,L) QC-LDPC码[7]。

本文提出了一种构造girth-8(4,L)QC-LDPC码的新的确定性方法。这种方法构造出的码允许码长在某个门限之上以L为步进连续取值；更引人注目的是，这种码的连续码长最小值不仅比文献[7]中码的连续码长最小值要小得多（仅为其3/4左右），而且几乎可以达到目前利用计算机大规模搜索得出的码长最小值。

本文组织如下：第2节描述了这种新码的构造方法，并证明了其围长特性；第3节比较了新构造方法和一些著名的搜索方法得到的码长最小值；第4节提出了这种新码的一种具体应用，即结合中国剩余定理(CRT)构造出一类围长至少为8并且码长非常灵活的合成QC-LDPC码；第5节是结束语。

2 构造方法

(4,L) QC-LDPC码的校验矩阵可以表示为

其中，I(x)表示一个受控于x的循环置换矩阵，具体定义与文献[1]完全相同；为了便于论述和证明，下文使用m表示x的第一个索引标记，使用i, j, k表示x的第二个索引标记。本文按照如下方式配置pm,j(0≤m≤3,0≤j≤L-1)：

令上述配置下得到的矩阵用HD表示。定义HD中第r, s, t行(0≤r, s, t≤3)循环置换矩阵所构成的矩阵为HD(r, s, t)。首先证明一些性质和引理。

性质1 p2,L-1＜3L2/4。

性质2 若j＞i,则p2,j＞p2,i+p1,j。

证明 对j采用数学归纳法。首先考察j=i+1的情形。根据式(2)和式(3)，p2,i+1＞p2,i+(i +1)=p2,i+p1,i+1。现在假设p2,j-1＞p2,i+p1,j-1,则根据式(2)和式(3)有p2,j＞p2,j-1+1＞p2,i+p1,j。

引理1 对于任意整数P≥3L2/4,HD(0,1,2)中无4-环；对于任意整数P≥3L2/4+L-1,HD中无4-环。

证明 根据式(2)～式(4)和性质2，引理1很显然成立。

引理2 对于任意整数P≥3L2/4，HD(0,1,2)的围长为8。

证明 根据引理1，只需证明不存在6-环和证明存在8-环。假设HD(0,1,2)中存在6-环。则该环可用式(5)描述，其中，0≤i, j, k＜L互异。

情形1)j＞k, k≠0：式(5)变成p2,j=p2,k-p1,i+p1,jmod P，这是不可能的，因为根据性质2，式(6)成立。

情形2)j＞k, k=0：式(5)变成p2,j+p1,i-p1,j=0mod P，这是不可能的，因为根据性质2，式(7)成立。

情形3)j＜k：式(5)变成p2,k=p2,j+p1,i-p1,jmod P，这是不可能的，因为根据式(3)，式(8)成立。

现在考虑8-环。根据式(2)，HD(0,1,2)中总是存在一个由式(9)描述的不依赖于P的8-环：

引理3 对于任意整数P≥3L2/4,HD(1,2,3)中无6-环。

证明 假设HD(1,2,3)中存在6-环。则该环可用式(10)描述，其中，0≤i, j, k＜L互异。

根据式(4)，式(10)变成(0-p1,i)+(p1,j-p2,j)+(p2,k-0)=0modP ，这意味着HD(0,1,2)中存在6-环。与引理1矛盾。

引理4 对于任意整数P≥3L2/4+L-1，HD(0,1,3)中无6-环。

证明 假设HD(0,1,3)中存在6-环。则该环可用等式(11)描述，其中，0≤i, j, k＜L互异。

根据式(4)，式(11)变成：

情形1)i＞k, k≠0：式(12)是不可能的，因为式(13)导致式(14)成立。

情形2)i＞k, k=0：式(12)变成p2,i+p1,i=p1,jmodP ，这是不可能的，因为根据性质1，式(15)成立。

情形3)i＜k, i≠0：式(12)变成p2,k=p2,i+p1,i-p1,jmod P，这是不可能的，因为根据式(3)，式(16)成立。

情形4)i＜k, i=0：等式(12)变成p2,k+p1,j=0modP，这是不可能的，因为式(17)成立。

引理5 对于任意整数P≥3L2/4+L-1,HD(0,2,3)中无6-环。

证明 假设HD(0,2,3)中存在6-环。则该环可用式(18)描述，其中，0≤i, j, k＜L互异。

根据式(4)，式(18)变成：

情形1)i＞j,j≠0：式(19)变成p2,i=p2,j-，p1,i+p1,kmod P，这是不可能的，因为根据式(3)，式(20)成立。

情形2)i＞j,j=0：式(19)变成p2,i+p1,i=p1,kmod P，这是不可能的，因为根据性质1，式(21)成立。

情形3)i＜j,i≠0：式(19)变成p2,j=p2,i+p1,i-p1,kmod P，这是不可能的，因为根据式(3)，式(22)成立。

情形(4)i＜j,i=0：式(19)变成0=p2,j+p1,kmod P，这是不可能的，因为根据性质1，式(23)成立。

根据引理1～引理5可以得到定理1。

定理1 对于任意整数P≥3L2/4+L-1,HD的围长均为8。

3 最小P值的比较

K.K.Liu最近提出了(4, L) QC-LDPC码的一种确定性构造方法，对于任意2PL≥，该方法构造出的LDPC码的围长均为8。根据定理1，构造的girth-8(4,L) QC-LDPC码的最小P值仅大约为K.K.Liu (4,L)QC-LDPC码的最小P值的3/4。这说明，构造的girth-8 (4,L) QC-LDPC码的码长具有更加广泛的取值范围。

构造的girth-8 (4,L)QC-LDPC码的最小P值甚至可以非常逼近基于计算机搜索的准随机方法所得到的最小P值。Fossorier[1]和Sullivan[2]采用基于计算机搜索的准随机方法，构造出了P值非常小的girth-8 (4,L) QC-LDPC码。对于L=4～13,Fossorier 给出了使得girth-8 (4,L) QC-LDPC码存在的最小P值。对于L=5～12,Sullivan给出了对应的搜索结果。图1表明，对于L=5～13本文新方法给出的最小P值与上述2种准随机方法给出的最小P值非常接近。

需要指出的是，虽然图1中的3种方法得到的最小P值非常接近，但是本文的方法是确定性的，不需要借助于任何计算机搜索过程。此外，该方法所对应的最小P值是P允许连续取值的最小值：只要P不小于该最小值，相应LDPC码的围长就为8。对于Fossorier和Sullivan方法得到的最小P值而言，当P大于该最小值时LDPC码的围长不能保证必然为8，除非利用他们的搜索算法再次搜索出满足girth-8条件的校验矩阵。

图1 3种方法得到的最小P值的比较

将HD的零空间对应的二元码记为D-QCLDPC码。下面首先分析D-QC-LDPC码的理论价值。文献[1]在III-B节中提出了一个相当难的问题（问题1）：如何给出使(J,L) QC-LDPC码围长至少为g的最小P值的解析结果？由定理1可知，只要P≥3L2/4+L-1就存在围长至少为8的(4, L)QC-LDPC码。显然，该结论对于条件g=8，J=4下问题1的解决具有重要的理论参考价值。

另一方面，通过仿真发现，与文献[1]搜索出的girth-8准随机QC-LDPC码相比，D-QC-LDPC码在译码性能上没有明显优势。但是，这并不说明D-QC-LDPC码就没有应用价值。相反，D-QC-LDPC码作为一个基本模块可以在其他的LDPC码构造方法（例如CRT构造法）中发挥至关重要的作用。

4 基于CRT构造围长至少为8的QC-LDPC码

最近，中国剩余定理（CRT, Chinese remainder theorem）被应用到QC-LDPC码的构造中[8,9]。利用CRT构造LDPC码的优势是，用若干个QC-LDPC短码作为分量码可以构造出QC-LDPC长码，并且QC-LDPC长码的围长不小于所有分量码的最大围长。将array码作为分量码，文献[8]利用CRT构造出了不含4环的QC-LDPC码，文献[9]利用CRT方法构造出了一类不含4环并且6环数量大大减少（但不能完全消除）的QC-LDPC码。由于array码的CPM尺寸为素数，因此这2种方法得到的QC-LDPC码的码长取值非常受限。本节将D-QC-LDPC码作为分量码，利用其CPM尺寸可以任意取值的优势，基于CRT方法构造出一类不仅完全消除4环和6环，而且码长非常灵活的QC-LDPC码。

4.1 构造方法

根据CRT原理，利用一个不含6环的QC-LDPC短码作为分量码，可以构造出一系列不含6环的QC-LDPC长码。D-QC-LDPC码的围长为8且CPM尺寸可以任意取值，因而非常合适作为CRT方法中的这种分量码。

设J∈{3,4}，L是满足L＞J的任意整数。令Pth(3,L)=3L2/4，Pth(4,L)=3L2/4+L-1。设P1≥Pth(J, L)。D-QC-LDPC码的校验矩阵H1是由P1×P1的CPM所组成的一个J×L阵列，其指数矩阵为。设P2是满足gcd(P1, P2)=1的整数（gcd表示最大公约数），H2是由P2×P2的CPM所组成的一个J×L阵列，其指数矩阵为E(H2)=()。令P=P1P2，定义指数矩阵E(H)=(pm,j)，其中，，A1和A2是满足gcd(A1, P1)=1、gcd(A2, P2)=1的2个任意正整数。根据CRT原理[9]，校验矩阵H是由P×P的CPM所组成的一个J×L阵列矩阵，其围长可以确保至少为8。

2方式下校验矩阵H的围长可能不同；即使围长相同，长度等于围长的短环数量也可能差别很大。下面提出一种选择指数矩阵E(H2)的启发式策略，以使校验矩阵H的围长尽可能大，并且短环数量尽可能小。

1)指数矩阵E(H)的首行首列元素初始化为0，即p0,j=0(0≤j≤L -1),pm,0=0(0≤m≤J -1)，其余元素初始化为∞。

2)按 照p1,1,…,pJ-1,1,p1,2,…,pJ-1,2,…,p1,L-1,…,pJ-1,L-1的顺序，依次确定。确定的策略是在0至P2-1中选择使当前H围长最大的元素。如果有多个元素同时满足该条件，可以随机或按照固定方式选择其中一个。这里采用固定方式，即选择最小元素。

4.2 例子与仿真

相对于高码率的LDPC码而言，构造性能优良的中低码率LDPC码通常会更困难。例如，W E.Ryan和S.Lin在系统总结目前LDPC码构造进展的最新专著《Channel Codes: Classical and Modern》[10]中所给出的绝大多数LDPC码举例均对应于高码率(大于0.75)，只有很少的几个例子对应于中低码率(0.5及其以下)。下面利用4.1节所述方法构造了2个设计码率为0.5的合成QC-LDPC码。为了对新合成码的性能作出客观评价，选择2种比较基准。第一种比较基准是1/2码率条件下的Shannon限(0.188dB)。第二种比较基准是文献[10]中设计码率为0.5且码长与新合成码最为接近的LDPC码。

例1 选择P1=29,P2=7,A1=19,A2=2。根据4.1节构造方法，得到了校验矩阵H的指数矩阵E(H)：

经验证，校验矩阵H的围长为10。校验矩阵H的CPM维数为(29×7)×(29×7)=203×203。对应的合成码码长为203×6=1218、码率为0.5016。在进行译码仿真时，和积译码算法的最大迭代次数设定为80。在BER=10-6时，译码性能距离Shannon限仅2.43dB(如图2所示)。文献[10]中Example 11.8利用基于RS码特殊子集的方法构造了一个码长为1488、码率为0.502的QC-LDPC码，在BER=10-6时该码的译码性能距离Shannon限为3.5dB。新合成码比Example 11.8码的性能改善了约1.07dB。

例2 选择P1=64,P2=7,A1=21,A2=2。根据4.1节所述构造方法，得到了校验矩阵H的指数矩阵E(H)：

经验证，校验矩阵H的围长为8。校验矩阵H的CPM维数为(64×7)×(64×7)=448×448。对应的合成码码长为448×8=3 584、设计码率为0.501 1。在进行译码仿真时，和积译码算法的最大迭代次数设定为80。在BER=10-6时，译码性能距离Shannon限仅2.15dB(如图2所示)。文献[10]中Example 11.12.基于素域中的加法群方法构造了一个码长为4 672、码率为0.501的(4,8)QC-LDPC码，在BER=10-6时该码的译码性能距离Shannon限为2.05dB。虽然新合成码比Example 11.12码的性能略差一些，但是前者码长要比后者码长短1 088bit。这说明新合成码的性能是非常优异的。

除了具有优异的译码性能，新合成码的一个突出优势在于码长取值的灵活性。对于例1和例2所述的基于RS码特殊子集的方法和基于素域中加法群的方法，其CPM尺寸与有限域的阶数(为素数或素数的幂)存在密切关联，因而CPM尺寸的选取不够灵活。而4.1节提出的新方法CPM尺寸为P=P1P2，其中P1为满足P1≥Pth(J, L)的任意整数，P2只要满足gcd(P1, P2)=1即可，所以CPM尺寸的取值非常灵活。此外，新合成码构造时不需要有限域知识背景，因此对于实际工程应用而言具有较大竞争力。

图2 D-QC-LDPC码作为分量码利用CRT得到的合成QC-LDPC码的性能曲线

5 结束语

本文提出了一种构造围长为8的(4,L)QCLDPC码的确定性方法。这类新码的最小P值与Fossorier和Sullivan利用准随机方法通过计算机大量搜索得到的最小P值非常接近。将新QC-LDPC码作为分量码，基于中国剩余定理构造出一类围长至少为8且码长取值非常灵活的合成QC-LDPC码。在1/2设计码率和中等码长条件下的仿真结果表明，这类新的合成QC-LDPC码在AWGN信道下具有优异的译码性能。显然，本文设计的矩阵DH也可以用来构造围长至少为8的多元QC-LDPC码，具体构造细节和译码性能仿真将是近期的研究内容之一。

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

[2] O’SULLIVAN M E. Algebraic construction of sparse matrices with large girth[J]. IEEE Trans on Information Theory, 2006, 52(2):718-727.

[3] KIM S, NO J S,CHUNG H, et al. On the girth of tanner (3,5)quasi-cyclic LDPC codes[J]. IEEE Trans on Information Theory, 2006,52(4):1739–1744.

[4] VASIC B, PEDAGANI K, IVKOVIC M. High-rate girth-eight low-density parity-check codes on rectangular integer lattices[J].IEEE Trans on Communications, 2004, 52(8):1248-1252.

[5] LIU K K, FEI Z S, KUANG J M. Novel algebraic constructions of nonbinary structured LDPC codes over finite fields[A]. Proc 68th IEEE VTC Fall[C]. Calgary, Alberta, Canada, 2008. 1-5.

[6] 张国华, 陈超, 杨洋等. Girth-8 (3,L)-规则QC-LDPC码的一种确定性构造方法[J]. 电子与信息学报, 2010,32(5): 1152-1156.ZHANG G H, CHEN C, YANG Y, et al. Girth-8 (3, L)-regular QC-LDPC codes based on novel deterministic design technique[J].Journal of Electronics & Information Technology, 2010, 32(5):1152-1156.

[7] LIU K K, FEI Z S, KUANG J M. Three algebraic methods for constructing nonbinary LDPC codes based on finite fields[A]. Proc 19th IEEE PIMRC[C]. Cannes, French Riviera, France, 2008.1-5.

[8] MYUNG S, YANG K. A combining method of quasi-cyclic LDPC codes by the Chinese remainder theorem[J]. IEEE Communication Letters, 2005, 9(9):823-825.

[9] LIU Y H, WANG X M, CHEN R W, et al. Generalized combining method for design of quasi-cyclic LDPC codes[J]. IEEE Communication Letters, 2008, 12(5):392-394.

[10] RYAN W E, LIN S. Channel Codes: Classical and Modern[M]. Cambridge University Press, 2009.