基于BIBD的多进制准循环LDPC码构造

刘 冰，吴东伟，崔 洁，张用宇

(中国人民解放军91469部队，北京 100841)

0 引 言

多进制低密度奇偶校验码(low-density parity-check，LDPC)及其迭代译码算法(q-ary sum-product algorithm，QSPA)由Davey和Mackay于1998年首次提出[1]，相比于二进制LDPC码，其具有更好的差错性能优势，但这却是以更高的译码复杂度为代价换取来的，正是这种译码的高复杂度制约了多进制LDPC码构造的发展。基于FFT的QSPA译码算法(FFT-QSPA)的提出[2]有效解决了多进制LDPC码译码高复杂度的弊端，同时也促进了多进制LDPC码构造方法的研究。

多进制LDPC码的性能与校验矩阵H的结构密切相关。对于构造H方法，大体可以分为基于计算机搜寻的随机构造法[3]和基于代数和几何的结构化方法[4-7]两大类。构造多进制LDPC码的校验矩阵时，需要确定2个重要的参数，即非零值的位置和非零值的取值。只有当构造的校验矩阵中非零值的位置和取值都具有一定结构时，其矩阵才认为具有结构化的特性。一般而言，对二进制随机构造的LDPC长码比等长的结构化LDPC码性能更好，然而也正因为其校验矩阵的随机性，使得人们难以找到简单的编码方法；相反，结构化LDPC码在码的构造、编译码复杂度以及存储空间等方面较随机LDPC码有明显优势。而多进制LDPC码在短帧时具有接近Shannon限的能力，表现出了其在短码和中长码上所具有的优势，并且多进制LDPC码具有很好的纠错能力和较强的抗突发错误能力。因此，如同构造BCH码和RS码那样，寻找系统的、综合性能较好的多进制LDPC码的构造方法成为当前研究的热点。

准循环(qusic-cyclic，QC)作为一类非常重要的结构化LDPC码结构，其特殊的循环结构使得编码可以采用移位寄存器在线性时间内完成，译码可以采用计数器寻址，并且可以并行实现。Yu Kou[8]基于有限几何理论首次提出了一种代数的、系统的二进制LDPC码构造方法。L.Zeng[4-5]在二进制QC构造的基础上首次提出了基于有限几何和有限域的多进制准循环LDPC码的系统化构造方法。相比于RS码而言，其构造的码字在加性高斯白噪声(additive white Gaussian noise，AWGN)信道下可以取得很大的编码增益。上述方法都是准循环LDPC码的经典构造。组合设计是组合数学中的一个重要问题，其中一种特殊的组合设计被称为均衡不完全区组设计(balanced incomplete block design，BIBD)[9-10]。Bassem Ammar[9]将BIBD的一种特殊子类首次运用于二进制LDPC码的设计中，而目前尚无将BIBD法应用于构造多进制LDPC码的相关文献。

本文在BIBD构造和广义二维扩展的基础上提出三类基于BIBD的多进制QC LDPC码的构造方法，该方法可以取得girth至少为6的规则多进制QC-BIBD-LDPC码。由于基于BIBD构造多进制校验矩阵时，其所构造的伽罗华域值q是素数或是素数的幂，而采用低复杂度的FFT-QSPA译码时，只能对2的幂次域阶数构造的码字进行译码，因此在考虑到译码复杂度的前提下，采用BIBD构造多进制LDPC码时会涉及到2个不同的高阶域，需要进行适当的处理。

1 BIBD多进制准循环LDPC码

1.1 基本概念及构造方法

令GF(q)为具有q个元素的有限域。多进制规则LDPC码C由多进制稀疏校验矩阵H的零空间所定义，其具有以下结构化性质：

1)每行的重量为dc；

2)每列的重量为dv。无论是二进制还是多进制，LDPC码的构造都还需要增加一条性质；

3)任何2行(或2列)之间位置相同的非零值的个数不大于1。

这样构造出来的校验矩阵规则，由其零空间给出的码C称为(dv,dc)规则LDPC码。性质3称为RC约束，其保证了H的零空间给出的LDPC码C的Tanner图girth至少为6。如果H的行与(或)列具有不同的重量，那么H的零空间将给出一个非规则LDPC码。

令G={x(1),x(2),…,x(q)}是具有q个元素的Abelian群。G的一个BIBD是指G的n个dv子集，记为B1,B2,…,Bn，称为区组(Blocks)，它们满足如下条件：

1)每个元素恰好在n个区组中的dc个出现；

2)任一元素对恰好在n个区组中的λ个出现；

3)每个区组中元素的个数dv与X中的元素总数q相比非常小。

1)其行对应X的q个元素；

2)其列对应该设计的n个区组；

3)当且仅当第i个元素xi属于第j个区组Bj时，hij≠0且hij∈GF(q)，否则，hij=0。 这个矩阵被称为基于GF(q)域设计的关联矩阵H，H的列重和行重分别是dv和dc。

根据BIBD的第2个条件，H的2个行向量具有λ个公共的1分量。如果λ=1，H就满足了LDPC码所有定义的结构化性质，于是H的零空间给出了一个长度为n的(dv,dc)规则LDPC码，其Tanner图中没有长度为4的环，这是基于BIBD最直接构造LDPC码的方法。

1)在s个区组中的sdv个元素中，dc个元素属于q组中的一组；

2)s个区组中元素的差对称重复，且每一个出现λ次。通过将G中每个元素逐个加到每一个区组B1,B2,…,Bs上，可以得到一个具有参数M=kq，N=sq，dc，dv和λ的BIBD。

由于采用BIBD构造校验矩阵中的循环阵大小都是素数的幂pm，将BIBD构造的校验矩阵扩展到多进制上，可直接在GF(pm)域上进行，即在BIBD决定的位置上随机或有规律地填入GF(pm)域中的非零值。但这种方法构造出的多进制LDPC码只能采用QSPA算法或其衍生算法来译码，而不能采用低复杂度的FFT-QSPA译码算法，采用QSPA算法存在的缺陷是复杂度较高，不利于工程实现。应用FFT-QSPA的前提是域的阶数必须为2的幂次，因此，构造基于BIBD多进制LDPC码时需要综合考虑编译码复杂度等实际情况。此时会涉及到GF(pm)和GF(2l)两个域，多进制LDPC码校验矩阵非零值的位置由GF(pm)域上的BIBD设计决定，而非零值的取值由GF(2l)域决定。这2个域的具体关系如下：(2l-1)·(rt-1)

其中[·]表示向上取整。

令β是GF(2l)域的本原元。将BIBD区组的多进制位置向量定义为z(Bi)=(z0,z1,…,zpm-1)， 其向量取值对应的是GF(2l)域中的pm个元素，其中zi=βimod(2l-1)，i∈Bi，其他所有分量为0。Bi中的元素称为位置数，决定着校验矩阵中非零值的位置。因此，z(Bi)是GF(2l)域上的pm重向量，其重量为区组Bi中所包含元素的个数。

多进制位置向量z(Bi+1)定义为位置向量z(Bi)向右循环移一位，第1列至第pm-1列的元素右移后乘以β得到第2列至第pm列的元素，而最后1列元素右移后乘以βrt(2l-1)-(pm-1)后得到第1列元素。多进制位置向量z(Bi+j)定义为区组Bi中元素依次加非零值j∈GF(pm)后得到取值在GF(2l)域的多进制位置向量。这样，在GF(2l)域上可形成以Bi，Bi+1，…，Bi+pm-1的位置向量为行的多进制pm×pm大小的循环阵Q。所以，Q是根据区组Bi的广义二维pm重扩展：

(2)

根据上述基本概念和提出的规则，可以由基本区组Bi进行广义二维pm重扩展得到多进制准循环矩阵。由于多进制校验矩阵非零值的位置和数值的选取分别是建立在GF(pm)和GF(2l)两个不同域上，元素的位置由GF(pm)域来确定，而元素的数值在GF(2l)域内选取。因而构造出的二维pm重矩阵Q在GF(2l)域上一般具有域元素分布不均的特性。上述广义二维扩展方法充分考虑了编码和译码的复杂度，从工程的角度出发更有利于实际应用。

1.2 I类QC-BIBD-LDPC码

1)I-A类设计

令t是满足12t+1=pm的1个正整数，其中p是1个素数，m是1个正整数。假设GF(pm)域有1个本原元α满足α4t-1=αc，其中c是一个小于pm的正奇数。于是，对于具有kq=12t+1个元素的集合X，存在一个BIBD，它有N=t(12t+1)个区组，每个区组由dv=4个元素组成，每个元素恰好在dc=4t个区组中出现，每个元素对恰好在λ=1个区组中出现。用GF(pm)域的元素α-∞=0,α0=1,α,α2,…,α12t-1来表示集合X的12t+1=pm个元素。于是，X的BIBD可由下述t个基本区组完全确定：

Bi={0,α2i,α2i+4t,α2i+8t}。

(3)

其中0≤i

H=[Q0,Q1,…,Qt-1]。

(4)

由于λ=1，并且H具有广义循环形式，因此，H的零空间给出了一个长度为N=t(12t+1)的QC-BIBD-LDPC码，其girth至少为6。对于1≤v≤t，可以灵活地选择v个循环阵Q0，Q1，…，Qv-1来构造如下矩阵：

(5)

表1在素域GF(12t+1)中本原元α满足α4t-1=αc时参数的取值

Tab.1 A list parameters that the prime field CF(12t+1) has a primitive elementαsuch that the conditionα4t-1=αcholds

t12t+1(α，c)113(2，1)673(5，33)897(5，27)

2)I-B类设计

与I-A类设计相似，令t是满足20t+1=pm的1个正整数，其中p是1个素数。假设GF(pm)域有1个本原元α满足α4t+1=αc，其中c是1个小于pm的正奇数。X的BIBD由下述t个基本区组完全确定：

Bi={α2i,α2i+4t,α2i+8t,α2i+12t,α2i+16t}。

(6)

表2在素域GF(20t+1)中本原元α满足α4t+1=αc时参数的取值

Tab.2 A list of parameters that the prime field GF(20t+1)has a primitive elementαsuch that the conditionα4t+1=αcholds

t20t+1(α，c)241(6，3)361(2，23)12241(7，179)14281(3，173)21421(2，227)

1.3 Ⅱ类QC-BIBD-LDPC码

令t是满足4t+1=pm的1个正整数，即4t+1是1个素数的幂。令k=3，GF(pm)域中的每个元素重复3次，可得到具有kq=3(4t+1)个元素的集合X。 假设GF(pm)域有一个本原元α满足(αc+1)/(αc-1)=αd， 其中c和d是2个正奇数。于是，对于具有kq=3(4t+1)个元素的集合X， 存在1个BIBD，它的参数如下：M=3(4t+1)，N=3t(4t+1)，dv=4，dc=4t，λ=1。 于是，X的BIBD由下述基本区组完全确定：

其中0≤i

Ⅱ类BIBD设计的广义多进制循环矩阵H具有如下形式：

(8)

其中，

M=[M1,M2,…,Mt]，

(9)

C=[C1,C2,…,Ct]。

(10)

式中：Mi和Ci为(4t+1)×(4t+1)的广义循环矩阵；O为一个(4t+1)×t(4t+1)零矩阵；循环阵Mi和Ci分别是通过将GF(pm)域中的每个元素逐个加到第i个基本区组Bi中的前2个元素和后2个元素上而得到部分块的广义二维pm重扩展。Mi和Ci的行重和列重都为2。

表3 在素域GF(4t+1)中本原元α满足(αc+1)/(αc-1)=αd时参数的取值

对于2≤v≤t，可以分别删除矩阵M，C和O中的后t-v个循环阵，这样可以得到3个新的矩阵去替代原来的M，C和O，其形式如式(8)所示。H(2)的零空间给出的是II类多进制QC-BIBD-LDPC码，码长为N=v(4t+1)， 最小距离至少为5。表3给出了部分t， 4t+1，α和c的取值表，以使在素域GF(4t+1)中存在满足(αc+1)/(αc-1)=αd的本原元α。

1.4 Ⅲ类QC-BIBD-LDPC码

令t是满足4t+1=pm的1个正整数，其中p是1个素数。令k=5，GF(pm)域中的每个元素重复5次，可得到具有kq=5(4t+1)个元素的集合X。 假设GF(pm)域有一个本原元α满足(αc+1)/(αc-1)=αd， 其中c和d是2个正奇数。于是，对于具有kq=5(4t+1)个元素的集合X， 存在一个BIBD，它的参数如下：M=5(4t+1)，N=5t(4t+1)，dv=5，dc=5t，λ=1，X的BIBD由下述基本区组完全确定：

(11)

其中，0≤i

Ⅲ类BIBD设计的广义多进制循环矩阵H具有如下形式：

其中M和C如式(9)和式(10)所示，D=[D1,D2,…,Dt]， 具有与M和C相同的形式。循环阵Mi，Ci，Di分别是通过将GF(pm)中的每个元素逐个加到第i个基本区组Bi中的前2个元素、接着的中间2个元素、最后1个元素0上而得到部分块的广义二维pm重扩展。通过删除后t-v个循环阵得到H(3)，其零空间给出的是Ⅲ类多进制QC-BIBD-LDPC码，码长为N=5v(4t+1)，最小距离至少为6。

2 仿真结果及性能分析

本节给出上述由BIBD构造出的多进制QC-BIBD-LDPC码采用FFT-QSPA译码时的性能，并与相同比特长度的RS码进行比较。所有仿真中的信号均采用BPSK调制，且在双边功率谱密度为N0/2的AWGN信道中传输。译码采用FFT-QSPA算法且最大迭代次数设置为50。

图1 采用FFT-QSPA译码的128-ary (146,74) QC- BIBD-LDPC码和采用BM算法GF(28)域上的 (128,64) RS码的误码和收敛性能Fig.1 Error performances and rate of decoding convergence of the 128-ary(146,74)QC-BIBD-LDPC code decoded with the FFT-QSPA and the(128,64)RS code over GF(28) decoded with the BM algorithm

对于Ⅱ类多进制QC-BIBD-LDPC码，取t=9，v=9，rt=13，可设计出1个111×999的多进制校验矩阵H(2)， 其列重和行重分别是4和8。H(2)的零空间给出1个码率为0.8919的4-ary (999,891) QC-BIBD-LDPC码。为了与其他方法构造的多进制和二进制LDPC码比较，给出了同比特长度的4-ary (999,888) Mackay LDPC码、二进制(1998,1776) Mackay LDPC码以及GF(28)域上(250,222)RS码的误码和迭代性能比较。可以看出,相比于二进制LDPC码来说构造出的多进制LDPC码在误码和迭代性能上所具有的优势。对于不同构造方法相同参数的多进制LDPC码，采用FFT-QSPA译码复杂度是相同的(复杂度为O(qlog2q))，且低于QSPA译码算法(复杂度为O(q2))，高于二进制信度传播(belief propagation，BP)译码算法(复杂度为O(1))。对于Ⅲ类多进制QC-BIBD-LDPC码，取t=3，v=2，rt=1， 可设计出码率为0.5的16-ary (130,65) QC-BIBD-LDPC码。这类LDPC码的FFT-QSPA和RS码BM算法的误码性能和迭代性能如图3所示，可以得出与Ⅰ类和Ⅱ类多进制BIBD-LDPC码相似的结论。

图2 4-ary (999,891) QC-BIBD-LDPC码、4-ary (999,888) Mackay LDPC码和GF(28)域上的 (250,222)缩短RS码的误码和迭代性能比较Fig.2 Error performances and average numbers of iterations for the 4-ary(999,891)QC-BIBD-LDPC code,4-ary(999,888) Mackay LDPC code and the(250,222)shortened RS code over GF(28)

图3 采用FFT-QSPA译码的16-ary (130,65) QC- BIBD-LDPC码和采用BM算法GF(27)域上的 (74,38)缩短RS码的误码和迭代性能Fig.3 Error performances and average numbers of iterations of the 16-ary(130,65)QC-BIBD-LDPC code,decoded with the FFT-QSPA and the(74,38)shortened RS code over GF (27)decoded with the BM algorithm

3 结 语

在应对突发噪声和混合类型噪声上，多进制码比二进制码更为有效。对于随机噪声以及突发噪声和干扰同时存在的通信系统或数据存储系统来说，多进制LDPC码是一种现代高效纠错码。本文提出的基于BIBD的多进制LDPC码的构造方法，首先在素域GF(pm)上构造出基本区组，然后对这些区组在GF(2l)域进行广义二维pm重扩展得到相应的多进制校验矩阵。在提出规则的框架下构造出的多进制LDPC码具有广义QC特性，编码和译码复杂度低，其Tanner图没有长度为4的环路，采用低复杂度FFT-QSPA译码时具有很好的性能。仿真结果表明，构造出的多进制QC-BIBD-LDPC码具有快速收敛的特性，在性能上相比于同比特长度的RS来说具有明显的编码增益。所以，在通信和存储应用领域本文提出的多进制LDPC码具有替代RS码的潜能。

[1] DAVEY M C,MACKAY D J C.Low-density parity check codes over GF(q)[J].IEEE Communications Letters,1998,2(6):165-167.

[2] BARNAULT L,DECLERCQ D.Fast decoding algorithm for LDPC over GF(2q)[C]//IEEE Information Theory Workshop.Paris,France:IEEE,2003:70-73.

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

[4] DIAO Q,ZHOU W,LIN S,et al.A transform approach for constructing quasi-cyclic Euclidean geometry LDPC codes[C]//2012 Information Theory and Applications Workshop.San Diego,USA:IEEE,2012:204-211.

[5] ZENG L,LAN L,TAI Y Y,et al.Constructions of non-binary quasi-cyclic LDPC codes:A finite field approach[J].IEEE Transactions on Communications,2008,56(4):545-554.

[6] HUANG Q,DIAO Q,LIN S,et al.Cyclic and quasi-cyclic LDPC codes on constrained parity-check matrices and their trapping sets[J].IEEE Transactions on Information Theory,2012,58(5):2648-2671.

[7]CHEN C,BAI B,WANG X.Construction of nonbinary quasi-cyclic LDPC cycle codes based on singer perfect difference set[J].IEEE Communications Letters,2010,14(2):181-183.

[8] KOU Y,LIN S,FOSORIER M P C.Low-density parity-check codes based on finite geometries:A rediscovery and new results[J].IEEE Transactions on Information Theory,2001,47(7):2711-2736.

[9] AMMAR B,HONARY B,KOU Y,et al.Construction of low-density parity-check codes based on balanced incomplete block designs[J].IEEE Transactions on Information Theory,2004,50(6):1257-1269.

[10] LAN L,TAI Y Y,LIN S,et al.New constructions of quasi-cyclic LDPC codes based on special classes of BIBD′s for the AWGN and binary erasure channels[J].IEEE Transactions on Communications,2008,56(1):39-48.