基于QR码和SPC码的双广义LDPC码构造及性能研究

黄 柔，黎 勇,2

(1.重庆邮电大学 通信与信息工程学院，重庆 400065；2.重庆大学 计算机学院，重庆 400044)

0 引 言

低密度奇偶校验(low-density parity check, LDPC)码最初由Gallager[1]提出，在被MacKay和Neal重新发现后受到了广泛的关注[2]。LDPC码是一类具有稀疏校验矩阵的线性分组码，具有接近香农极限的译码性能。然而，研究发现，LDPC码在迭代译码过程中容易出现错误平层问题。为了获得更低的错误平层，广义LDPC(generalized LDPC, GLDPC)码和双广义LDPC(doubly-generalized LDPC, D-GLDPC)码相继被提出。用具有一定纠错能力的分量码替换LDPC码的单奇偶校验(single parity check, SPC)节点得到GLDPC码[3]。在GLDPC码的基础上，将LDPC码的变量节点也用分量码替换得到D-GLDPC码，相应的变量节点和校验节点分别称为超变量节点(super variable node, SVN)和超校验节点(super check node, SCN)。Yige Wang等人于2006年提出了D-GLDPC码，构造了分别以汉明码和SPC码作为分量码的D-GLDPC码，其性能明显优于同码率的LDPC码和GLDPC码[4]。

D-GLDPC码的Tanner图可以通过将LDPC码的Tanner图中的原始变量节点和校验节点分别替换为SVN分量码和SCN分量码而得到。SVN分量码和SCN分量码的码长分别等于对应变量节点和校验节点的度数。相比GLDPC码，D-GLDPC码在分量码的选择上更加灵活，克服了短码长的LDPC码的性能不佳和GLDPC码的码率损失问题，但同时也增加了译码复杂度[5]。目前，常见的构造D-GLDPC码的方法，选取的是译码相对容易的线性分组码，如SPC码[6-7]、汉明码、BCH等，但这些码的性能不太好，若要选取性能较好但译码复杂的线性分组码，就要控制该线性分组码的比例。鉴于此，本文首先基于平方剩余(quadratic residue, QR)码构造了QR-QC-LDPC码，其校验矩阵具有准循环特性，不需要占用大量的存储空间，且编译码复杂度较低。然后，将QR-QC-LDPC码作为全局码，选取纠错性能优异的QR码作为SCN分量码，选取SPC码作为SVN分量码来构造D-GLDPC码。此外，根据分量码的特点选取合适的译码算法来降低D-GLDPC码的译码复杂度。

1 D-GLDPC码和QR码介绍

1.1 D-GLDPC码的定义

与LDPC码相似，D-GLDPC码也可以表示成(n,k)的形式，即码长为n，信息位数目为k。D-GLDPC码校验矩阵的行数和列数分别等于超校验节点的个数M和超变量节点的个数N，校验矩阵中坐标为(i,j)的元素若为“1”则表示第i个超校验节点与第j个超变量节点相连，即二者之间有消息传递，反之，若元素为“0”则表示二者之间没有消息传递。同LDPC码，D-GLDPC码校验矩阵每一行中元素“1”的个数为该行行重，即所有超变量节点与第i个超校验节点相连的边数dci；每一列中元素“1”的个数为该列列重，即所有超校验节点与第j个超变量节点相连的边数dvj。D-GLDPC码的码长为

(1)

由于M个SCN的校验方程之间可能存在冗余，D-GLDPC码的校验比特为

(2)

由(1)—(2)式可得D-GLDPC码的码率满足

(3)

1.2 D-GLDPC码的Tanner图表示

图1是D-GLDPC码的二分图。图1中，黑色圆圈表示通过信道传输的超变量节点的信息位，每个超变量节点的信息位都是D-GLDPC码的一部分；白色圆圈表示超变量节点，超变量节点的个数为N，度分别为dv1、dv2、…、dvN，相应的子码为(dv1,kv1)、(dv2,kv2)、…、(dvN,kvN)；白色方框表示超校验节点，超校验节点的个数为M，度分别为dc1、dc2、…、dcM，相应的子码为(dc1,kc1)、(dc2,kc2)、…、(dcM,kcM)。从图1可以看到，第j个超变量节点(dvj,kvj)的一部分连接通过信道传输的kvj条边即kvj个信息比特，另一部分则连接来自超校验节点的dvj条边；第i个超校验节点(dci,kci)连接来自超变量节点的dci条边。

图1 D-GLDPC码的二分图Fig.1 Bipartite graphs of D-GLDPC codes

1.3 QR码介绍

QR码是一种严谨且优美的代数码[8]，作为BCH循环码的一个重要子类，它不仅具有丰富的代数结构，还拥有大于或等于二分之一的码率。在同等或相近码长下，QR码比传统的BCH码、RM码有更大的最小汉明距离，因而纠错性能更优。

定义在伽罗华域GF(2m)上的(n,k,d)QR码的生成多项式形式为

(4)

(4)式中：β是有限域GF(2m)上的n次单位原根；Qn是小于n的正整数j取平方后得到的模n的平方剩余集，即

Qn={i|i≡j2modn},1≤j

(5)

(4)式的展开形式为

g(x)=g0+g1x+…+gn-kxn-k

(6)

(6)式中：n是QR码码长；k=(n+1)/2是QR码的信息位长；d是QR码的最小汉明距离。

由文献[9]可知，QR码的生成多项式g(x)和校验多项式h(x)满足

g(x)·h(x)=xn+1

(7)

因此，QR码的校验多项式h(x)可表示为

h(x)=h0+h1x+…+hkxk

(8)

根据多项式的展开规则可以由(8)式得到(n-k)个方程，即

(9)

(9)式中，vn-i-j表示QR码中的一位。由此，不难得出h(x)的反向多项式为

xkh(x-1)≜hk+hk-1x+…+h0xk

(10)

h(x)的反向多项式xkh(x-1)也是xn+1的一个因式，它可以生成一个(n,n-k)循环码，该循环码的校验矩阵为

(11)

由(9)式可知，QR码码字集合中的每一个码字v与H中的每一行都有v·HT=0，故H是QR码的校验矩阵。后文构造QR-QC-LDPC码和D-GLDPC码所用到的QR码校验矩阵均按照本节方法求得。

2 D-GLDPC码的构造及译码

2.1 QR-QC-LDPC码的构造

QC-LDPC码是一类结构化的LDPC码，其校验矩阵具有准循环的特点，这使得其编译码复杂度比较低。因此，本文选择QR-QC-LDPC码作为构造D-GLDPC码的全局码。

(n,k,d)QR码的生成多项式的根{βi|i∈K}为该QR码作为循环码的零点集，K为零点集中的指数集，根据(4)式可知指数集K等于平方剩余集Qn。故QR码在伽罗华域GF(2m)上的校验矩阵Hqr,full为[10]

(12)

(12)式中：jl∈Csl,1≤l≤k；Csl为有限域GF(2)上模n的代表元为sl的分圆陪集。

选择(17,9,5)QR码构造QR-QC-LDPC码。由QR码的定义可知，(17,9,5)QR码定义在有限域GF(28)上，β是有限域GF(28)上的17次单位原根。计算得该QR码的平方剩余集为

Q17={1,2,4,8,9,13,15,16}

(13)

QR码的平方剩余集Qn也是该QR码作为循环码的零点集中元素的指数集，由文献[10]可知，QR码的指数集Qn是该QR码在有限域中的一些分圆陪集的并集。故(17,9,5)QR码在有限域GF(2)上模17的分圆陪集为

(14)

从(14)式可以看出，该QR码零点集中元素的指数集为分圆陪集C1，故(17,9,5)QR码在有限域中的校验矩阵为

(15)

需要注意的是，(15)式中所有β的指数都进行了模17运算。

本小节基于(17,9,5)QR码构造了两个不同的QR-QC-LDPC码。(17,9,5)QR码的平方剩余集、在有限域GF(2)上模17的分圆陪集，以及在有限域中的校验矩阵形式均与(15)式相同。但是，两个QR-QC-LDPC码均选择(15)式的不同子矩阵作为各自的基矩阵，具体构造方式如下。

选择(17,9,5)QR码平方剩余集中的(1,9,13)三个元素，并选择其校验矩阵的前7列构造行数为3列数为7的基矩阵B，基矩阵形式为

(16)

对基矩阵B进行扩展，可以得到参数为(119,68)的规则QR-QC-LDPC码，其行重为7，列重为3，码率约为0.571，校验矩阵形式为

(17)

选择(17,9,5)QR码平方剩余集中的(1,2,4,8,9)5个元素，并选择其校验矩阵的前7列构造行数为5、列数为7的基矩阵B，基矩阵形式为

(18)

对基矩阵B进行扩展，可以得到参数为(119,34)的规则QR-QC-LDPC码，其行重为7，列重为5，码率约为0.286，校验矩阵形式为

(19)

2.2 D-GLDPC码的构造

(20)

SCN分量码采用(7,4)QR码，它的校验矩阵HQR为

(21)

(22)

D-GLDPC码的校验矩阵可以通过基矩阵Ha进行行列扩展得到。

行扩展：对于Ha的每一行，每个元素“1”随机用HQR的列向量替换(每一个列向量只能用一次)，每个元素“0”用相同长度的全零列向量替换，得到的矩阵记为H′，表示为

(23)

H=

(24)

2.3 D-GLDPC码的译码

D-GLDPC码也可以采用置信传播(belief propagation, BP)译码算法进行迭代译码。令D-GLDPC码的码字为b=(b1,b2,…,bN)，bj=(bj,1,bj,2,…,bj,kvj),j=1,2,…N，采用BPSK调制，得到的传输序列为：c=(c1,c2,…,cN)，cj=(cj,1,cj,2,…,cj,kvj)，cj,i=1-2bj,i，i=1,2,…kvj。令y=(y1,y2,…,yN)为接收到的序列，则y=c+g，g服从均值为0、方差为N0/2的高斯分布。

第n个超变量节点和第m个超校验节点的消息传递如图2—图3所示。

图2 第n个超变量节点的消息传递Fig.2 Message passing of the n-th super variable node

图3 第m个超校验节点的消息传递Fig.3 Message passing of the m-th super check node

D-GLDPC码的BP译码算法具体步骤如下。

步骤1初始化。设置初始迭代次数i=1，最大迭代次数为IMax，对于每一个超变量节点n(1≤n≤N)有

(25)

步骤2水平方向n=nm,q，对每一个超校验节点m(1≤m≤M)有

(26)

步骤3垂直方向m=mn,p，对每一个超变量节点n(1≤n≤N)有

(27)

(28)

步骤4硬判决。判决公式为

(29)

由于水平方向的计算复杂度较高，因此本文对超校验节点分量码采用适于线性分组码的后验概率(a posteriori probability, APP)译码算法[11]。具体译码算法步骤如下。

输入：P(r1|v1),P(r2|v2),…,P(rN|vN)

2)对于n=1,…，N更新

μ(s,n)=μ(s,n-1)P(rn|vn=0)+

μ(s+hn,n-1)P(rn|vn=1)

(30)

3)如果P(rn|vn=0)≠P(rn|vn=1)，n=1,…,N则

P(vn=0|r,v∈V)=

(31)

输出：P(v1=0|r,v∈V),…,P(vN=0|r,v∈V)

3 仿真结果

本文采用QR码和SPC码，分别作为SCN、SVN的分量码，来研究D-GLDPC码与LDPC码在不同码长和不同码率条件下的性能；仿真平台为Visual Studio 2015，通过编码程序对随机产生的数据信息进行编码；调制方式采用BPSK，模拟信道环境采用AWGN信道；编程语言采用C/C++；D-GLDPC码的校验矩阵与同码率的LDPC码的校验矩阵相同，译码过程中的最大迭代次数设定为50次。

以(17)式构造的(119,68)QR-QC-LDPC码的校验矩阵作为母矩阵。使用分量码(7,4)QR码对其作行替换，分量码(3,2)SPC码对其作列替换，得到(238,85)D-GLDPC码，码率为0.357。仿真结果如图4所示。由图4可知，和同等码率下的LDPC码相比，D-GLDPC码的性能明显更优。即使将最大迭代次数设定为5，D-GLDPC码的性能依然优于同码长、同码率LDPC码。当最大迭代次数设定为20、30或50时，D-GLDPC码的性能几乎没有提升，但相比LDPC码提升效果显著。也就是说，D-GLDPC码经过20次译码迭代便可快速收敛。这也表明，D-GLDPC码的平均译码迭代次数低于LDPC码。

图4 (238,85)D-GLDPC码与(238,85)LDPC码比较Fig.4 Comparison between (238,85) D-GLDPC code and (238,85) LDPC code

以(19)式构造的(119,34)QR-QC-LDPC码的校验矩阵作为母矩阵，使用分量码(7,4)QR码对其作行替换，分量码(5,4)SPC码对其作列替换，得到(476,221)D-GLDPC1码，码率为0.464。此外，利用PEG算法构造行重为7，列重为5的(119,34)LDPC码，对其采用相同分量码作行列替换得到同码长同码率的D-GLDPC2码。仿真结果如图5所示。由图5可知，与相同码长、码率下的LDPC码相比，D-GLDPC1码的性能明显更优，在BER为3×10-5时，D-GLDPC1码有接近1.4dB的性能增益。与相同码长、码率下的D-GLDPC2码相比，在BER为8×10-6时，D-GLDPC1码有超过0.1dB的性能增益。

图5 (476,221)D-GLDPC1码与(476,221)LDPC、(476,221)D-GLDPC2码比较Fig.5 Comparison of (476,221) D-GLDPC1 code with (476,221) LDPC code and (476,221) D-GLDPC2 code

使用CPU为intel(R) Core(TM) i7-7700K 4.2GHz的台式电脑，在32GB内存、64位操作系统的运行环境下，对比D-GLDPC码和同等码率LDPC码的单个码字的平均译码时间，(238,85)D-GLDPC码、(476,221)D-GLDPC码与同码率LDPC码的平均译码时间对比如图6—图7所示。由图6—图7可知，D-GLDPC码比同码率LDPC码的平均译码时间更短，这主要是因为D-GLDPC码的超校验节点分量码采用的APP译码减少了计算量，从而缩短了译码时间。

图6 (238,85)D-GLDPC码与(238,85)LDPC码的平均译码时间Fig.6 Average decoding time of (238,85) D-GLDPC code and (238,85) LDPC code

图7 (476,221)D-GLDPC码与(476,221)LDPC码的平均译码时间Fig.7 Average decoding time of (476,221) D-GLDPC code and (476,221) LDPC code

4 结 论

本文基于QR码构造了QR-QC-LDPC码，将其作为全局码，QR码作为SCN分量码，SPC码作为SVN分量码，构造了D-GLDPC码。对SCN分量码采用APP译码算法，以此简化了D-GLDPC码的译码。2种不同码长不同码率的D-GLDPC码，与参数相同的LDPC码进行仿真对比，结果显示D-GLDPC码在错误比特率和译码收敛速度上均有明显的性能提升。