黄 柔,黎 勇,2
(1.重庆邮电大学 通信与信息工程学院,重庆 400065;
2.重庆大学 计算机学院,重庆 400044)
低密度奇偶校验(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码的译码复杂度。
与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是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
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码码长; 由文献[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码校验矩阵均按照本节方法求得。 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; 选择(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) (20) SCN分量码采用(7,4)QR码,它的校验矩阵HQR为 (21) (22) D-GLDPC码的校验矩阵可以通过基矩阵Ha进行行列扩展得到。 行扩展:对于Ha的每一行,每个元素“1”随机用HQR的列向量替换(每一个列向量只能用一次),每个元素“0”用相同长度的全零列向量替换,得到的矩阵记为H′,表示为 (23) H= (24) 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) 本文采用QR码和SPC码,分别作为SCN、SVN的分量码,来研究D-GLDPC码与LDPC码在不同码长和不同码率条件下的性能; 以(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 本文基于QR码构造了QR-QC-LDPC码,将其作为全局码,QR码作为SCN分量码,SPC码作为SVN分量码,构造了D-GLDPC码。对SCN分量码采用APP译码算法,以此简化了D-GLDPC码的译码。2种不同码长不同码率的D-GLDPC码,与参数相同的LDPC码进行仿真对比,结果显示D-GLDPC码在错误比特率和译码收敛速度上均有明显的性能提升。
k=(n+1)/2是QR码的信息位长;
d是QR码的最小汉明距离。2.1 QR-QC-LDPC码的构造
Csl为有限域GF(2)上模n的代表元为sl的分圆陪集。2.2 D-GLDPC码的构造
2.3 D-GLDPC码的译码
仿真平台为Visual Studio 2015,通过编码程序对随机产生的数据信息进行编码;
调制方式采用BPSK,模拟信道环境采用AWGN信道;
编程语言采用C/C++;
D-GLDPC码的校验矩阵与同码率的LDPC码的校验矩阵相同,译码过程中的最大迭代次数设定为50次。
扩展阅读文章
推荐阅读文章
老骥秘书网 https://www.round-online.com
Copyright © 2002-2018 . 老骥秘书网 版权所有