基于广义等差数列的大围长QC-LDPC码构造
时间：2023-02-26 15:45:07 来源：千叶帆 本文已影响人
赵 辉，余孟洁，安 静，邝凯达，吕典楷
(1.重庆邮电大学 通信与信息工程学院，重庆 400065；
2.重庆邮电大学 信号与信息处理重庆市重点实验室，重庆 400065)
准循环低密度奇偶校验(quasi-cyclic low-density parity-check，QC-LDPC)码由于具有接近香农极限、易于实现等优异性能，逐渐发展为当前编码领域的研究热点之一[1]。因为类似于置信传播(belief propagation，BP)[2]的QC-LDPC码译码算法是基于Tanner图中变量节点和校验节点间的符号可靠性信息迭代更新的决策过程[3]，短环的存在会严重影响译码性能。因此，构造大围长QC-LDPC码对于提高码字的编译码性能具有重要意义。
目前，QC-LDPC码的构造方法大致分为随机构造和结构化构造两类[4]。由于当码长较短时基于随机方法构造的QC-LDPC码容易出现较高的错误平层且复杂度较高，考虑到工程实现的可能性，人们对结构化构造方法进行了大量的研究。彭海英等在文献[5]中提出了一种基于中国剩余定理(Chinese remainder theorem，CRT)的QC-LDPC码组合设计方法，设计出的码字中不存在6环，但该方法在扩展因子的取值上存在一定局限性，且只能用于构造列重为3的QC-LDPC码。袁建国等提出了一种基于斐波那契-卢卡斯序列的Type-II QC-LDPC码构造方法，该方法虽然避免了4环的存在，但需要额外的打孔技术来减少6环的数量。文献[7]中张轶等提出了一种利用等差数列构造围长为8的QC-LDPC码的方法，但该方法只能用于构造列权重为3的QC-LDPC码，在灵活性上具有一定的局限性。
针对上述分析，本文提出一种基于广义等差数列(generalized arithmetic sequence，GAS)的QC-LDPC码构造方法。利用GAS中元素的差值不等性构造QC-LDPC码的循环移位系数矩阵(cyclic shift coefficient matrix，CSCM)，并给出移位系数值(shift coefficient value，SCV)的解析表达式。然后提出一种局部优化算法对存在第二类6环结构的码字进行围长优化，构造的QC-LDPC码围长至少为8。
QC-LDPC码是由CSCM和扩展因子P确定的一种高度结构化的LDPC码。考虑一个 (n,k) QC-LDPC码，码字的CSCM为[8]
(1)
式中：每一个pj,l(1≤j≤J， 1≤l≤L) 都是一个SCV,取值范围为 {-1,0,1,2,…,P-1},J=(n-k)/P，L=n/P分别为CSCM的行数和列数。将式(1)中J×L个SCV用与其相对应的J×L个大小为P×P的循环置换矩阵(cyclic permutation matrix，CPM)代替，可得QC-LDPC码的奇偶校验矩阵H[9]
(2)
式中：I(pj,l) 是将大小为P×P的单位矩阵IP×P向左循环移位pj,l个单位得到的CPM。当pj,l=0时，I(pj,l) 代表P×P单位矩阵；
当pj,l=-1时，I(pj,l) 代表P×P零矩阵[10]。若式(1)中所有的pj,l均不等于-1，则由E确定的QC-LDPC码为规则LDPC码，否则为不规则LDPC码[11]。
当用Tanner图对QC-LDPC码进行表示时，Tanner图中的变量节点和校验节点依次交替连接的边所形成的闭合路径称为QC-LDPC码的环。环所包含的边的数目称为环的长度，长度为4和6的环被称为短环。假设QC-LDPC码的CSCM中有k个SCV{p1,p2,…,pk}， 其中k为大于2的整偶数。若 {p1,p2,…,pk} 满足pi和pi+1在同一列或同一行，pi和pi+2不在同一列和同一行，则 {p1,p2,…,pk} 形成长度为k的环的充要条件为[12]
(3)
若一个QC-LDPC码的CSCM中有S个长度为k的环，那么当CSCM根据扩展因子P的大小扩展为QC-LDPC码时，校验矩阵H中将会出现至多S×P个长度相同的环[13]。由此可以看出，若能保证CSCM中不存在短环结构，则对应的校验矩阵H也不会受到相应短环结构对码字译码性能的影响。因此，本文将CSCM作为构造大围长QC-LDPC码的目标矩阵，先构造不存在短环结构的CSCM，再根据扩展因子对CSCM进行扩展得到无短环结构的QC-LDPC码。
广义等差数列是由等差数列衍生而来的一种常见的整数数列，其定义为：对于一组整数数列，若数列中所有偶数位上的值与其前一位奇数位上的值之差满足等差数列的定义，则称其为广义等差数列。广义等差数列中奇偶位上的差值满足的等差数列的公差称为广义等差数列的广义差值，记为dj。由于广义等差数列中所有元素之间的差值满足等差数列的定义，因此广义等差数列中的元素具有差值不等的性质。例如数列 {1,2,4,7,11} 和数列 {0,4,12,24,40} 都是广义等差数列，数列中各元素的差值分别为 {1,2,3,4} 和 {4,8,12,16}， 广义差值分别为dj=1和dj=4。
由于本文将CSCM作为构造大围长QC-LDPC码的目标矩阵，因此基于GAS的QC-LDPC码构造实质上是基于GAS构造QC-LDPC码的CSCM。为了保证所构造的CSCM中不存在短环结构，下面分别对CSCM中不存在环长为4和环长6的短环结构的条件进行分析。
图1 4环结构分布
图2 QC-LDPC码中6种可能的6环结构
图3 6环结构分布
根据上述分析构造CSCM，使其每一行的元素均构成一个GAS，且广义公差满足dj+1>dj， 则CSCM满足无4环和第一类6环结构的条件，即f2-f1≢f3-f4，f1-f2+f3-f4+f5-f6≢0。
例如，考虑一个大小为3×6的CSCM
(4)
可见，E0的每一行都是一个GAS，广义公差分别为1,3和5。由于E0满足无4环和第一类6环结构的条件f2-f1≢f3-f4和f1-f2+f3-f4+f5-f6≢0， 则由E0扩展得到的QC-LDPC码中不存在4环和第一类6环结构。
为使全文叙述更加清晰，对相关的参数作如下规定：在基于GAS构造的CSCM中，第j行中每前后两个数的差值组成的等差数列记为uj，uj的公差即为广义差值dj；
第j行的第一个值记为初值aj；
第j行与第一行的初值之差记为梯度值bj。
表1给出了式(4)所示矩阵E0中上述参数的取值情况。
表1 矩阵E0的相关参数取值
可见，基于GAS构造的CSCM中梯度值bj和广义差值dj满足关系
(5)
则CSCM中的元素满足
(6)
由式(6)可知
(7)
将式(5)代入式(7)，则得SCV的解析表达式
(8)
该方法可以通过改变CSCM的行数J、列数L，初始值a1和初始坐标 (j,l) 来实现码率和码长的灵活性选择。例如，令J=3,L=6,a1=3， (j,l)=(2,2)， 将j={1,2,3}，l={1,2,…,5,6} 代入式(8)，可得码率约为0.5的QC-LDPC码的CSCM
(9)
同理，令J=3,L=10,a1=2， (j,l)=(1,2)， 将j={1,2,3}，l={1,2,…,9,10} 代入式(8)，可得码率约为0.7的QC-LDPC码的CSCM
(10)
3.1 4环分析
由式(3)可知，当移位系数值pj0,l0，pj0,l1，pj1,l1，pj1,l0满足
pj0,l0-pj0,l1+pj1,l1-pj1,l0≡0(modP)
(11)
时，4环存在。令pj0,l0-pj0,l1+pj1,l1-pj1,l0=Qfour， 1≤j0≤j1≤J， 1≤l0≤l1≤L， 将式(8)代入Qfour有
(12)
Qfour=pj0,l0-pj0,l1+pj1,l1-pj1,l0>0
(13)
另一方面，用pj1,l0替换pj0,l0， 有
Qfour=pj0,l0-pj0,l1+pj1,l1-pj1,l0 (14) 根据式(13)，式(14)和夹逼定理可得 0 (15) 由此可知，本文构造的QC-LDPC码不满足式(12)，即基于GAS构造的QC-LDPC码中不存在4环结构。 对于第一类6环结构，以图2中的结构(a)为例，当且仅当移位系数值pj0,l0，pj0,l1，pj1,l1，pj1,l2，pj2,l2，pj2,l0满足 pj0,l0-pj0,l1+pj1,l1-pj1,l2+pj2,l2-pj2,l0≡0(modP) (16) 时，6环存在。令pj0,l0-pj0,l1+pj1,l1-pj1,l2+pj2,l2-pj2,l0=Qsix， 其中1≤j0≤j1≤j2≤J， 1≤l0≤l1≤l2≤L。 将式(8)代入Qsix可得 (17) 用j1代替j2代入式(17)可得 (18) 同理，用pj2,l0替换pj0,l0代入式(17)可得 Qsix=pj2,l0-pj0,l1+pj1,l1-pj1,l2+pj2,l2-pj2,l0=-pj0,l1+pj1,l1-pj1,l2+pj2,l2 (19) 因为pj1,l1-pj0,l1 Qsix (20) 同理，根据式(18)、式(20)和夹逼定理可知 0 (21) 因此，式(16)不成立，即构造的QC-LDPC码中不存在第一类6环结构(a)(图2)。同理可以证明第一类6环结构中的其余3种结构也不存在，即基于GAS构造的QC-LDPC码中不存在第一类6环结构。 下面分析第二类6环结构。以第二类6环结构中的结构(e)(图2)为例，将第二类6环结构(e)(图2)与第一类6环结构中的结构(a)(图2)进行比较，比较分析结果如图4所示。 图4 第二类6环和第一类6环的结构比较分析 由图4中的子图(b)和式(3)可知，6环结构(e)(图2)不存在的充要条件是 pj2,l2-pj2,l3+pj4,l3-pj4,l4+pj3,l4-pj3,l2≢0(modP) (22) 令pj2,l2-pj2,l3+pj4,l3-pj4,l4+pj3,l4-pj3,l2=Qleft， 引入pj3,l3对Qleft进行变换可得 Qleft=-(pj2,l3-pj2,l2)-(pj4,l4-pj4,l3)+(pj3,l4-pj3,l3)+(pj3,l3-pj3,l2) (23) 将上式中4组SCV用对应的差值d1，d2，d3，d4表示可得 Qleft=-d1-d4+d3+d2 (24) 因为d2-d1>0，d3-d4<0， 所以当d2-d1=d3-d4时，有 Qleft=(d2-d1)+(d3-d4)=0 (25) 即式(22)不能被保证，第二类6环结构(e)(图2)在d2-d1=d3-d4时存在，同理对于图2中第二类6环结构(f)(图2)也存在同样的问题。然而，对于第一类6环结构(a)(图2)，由于d3-d1>0，d4-d2>0， 因此式(22)总是成立的，即第一类6环结构总是不存在的，这与第一类6环结构部分的证明结果是一致的。 为消除基于GAS构造的CSCM在满足d2-d1=d3-d4时存在的第二类6环结构，这里提出一种局部优化算法对CSCM的围长进行优化，该算法的流程如下。 步骤1 获取输入矩阵E0， 设置控制因子σ=1， 初始化权值矩阵B为与E0大小相同的零矩阵。 步骤2 判断矩阵E0中是否存在三列值可以组成新的矩阵M， 若存在，执行步骤3； 步骤3 若M中存在一组SCV满足式(3)，则在权值矩阵B中记录成环路径，即令矩阵B中对应位置上的值+1，然后执行步骤2； 步骤4 若矩阵B为非零矩阵，选取矩阵B中元素值最大的坐标 (j,l) 作为需要被更新的坐标，执行步骤5； 步骤5 根据步骤4中得到的坐标 (j,l) 更新矩阵E0对应坐标上的SCV，E0j,l=pj,l+σ。 步骤6 判断新的E0中是否存在第二类6环结构，若不存在，算法结束，输出矩阵E=E0； 以式(4)所示的E0为例，将E0代入上述提出的局部优化算法，得到矩阵B中元素值最大的坐标为 (j,l)=(3,3)， 因此E03,3=p3，3+σ， 通过上述局部优化算法处理以后得到矩阵 (26) 且由E构造的QC-LDCP码中不存在6环结构，围长为8。可见，当d2-d1=d3-d4时，在基于GAS构造的QC-LDPC码不存在4环结构和第一类6环结构的基础上，该局部优化算法可以保证构造的QC-LDPC码中不存在第二类6环结构，即构造的QC-LDPC码的围长至少为8。 为了验证本文所提构造方法的性能，本节对提出的基于GAS构造的QC-LDPC码与文献[4]、文献[7]和文献[12]中提出的QC-LDPC码进行Monte Carlo仿真比较。基于MATLAB的仿真环境设置如下：信道为加性高斯白噪声(additive white Gaussian noise，AWGN)信道，调制方式为二进制相移键控(binary phase shift keying，BPSK)调制，译码算法为Log-似然比(LLR)-BP译码算法，每个信噪比下的错误码组数不小于100组，设置最大迭代次数为50。 将参数J=3，L=6，a1=1， (j,l)=(1,3) 代入式(8)所示的SCV解析表达式，得到基于GAS构造的大小为3×6的QC-LDPC码的CSCM为 (27) 取扩展因子P=256对式(27)所示的CSCM进行扩展，得到码率R约为0.5，码长为1536的QC-LDPC码。为了保证比较的有效性，根据文献[4]、文献[7]和文献[12]中提出的方法构造码长相同的QC-LDPC码与本文提出的基于GAS构造的QC-LDPC码进行比较，仿真结果如图5所示。从图5可以看出，与文献[12]和文献[7]中提出的QC-LDPC码相比，本文基于GAS方法构造的QC-LDPC码在误码率(bit error rate，BER)为10-5时分别实现了大约0.1 dB和0.2 dB的信噪比增益。同时可以看出，与文献[4]中提出的码字相比，本文构造的QC-LDPC码在BER=10-4时实现大约0.5 dB的信噪比增益。 图5 本文构造的(1536,765)QC-LDPC码与对比文献的码字BER性能对比 同理，将参数J=3，L=10，a1=0， (j,l)=(1,1) 代入式(8)所示的SCV解析表达式，得到基于GAS构造的大小为3×10的QC-LDPC码的CSCM为 (28) 设置扩展因子P=256对式(28)中的CSCME2进行扩展，得到的QC-LDPC码码长为2560，码率约为0.7。同理，为了保证比较的有效性，根据文献[4]、文献[7]和文献[12]中提出的方法构造码长同为2560的QC-LDPC码进行仿真比较，仿真比较结果如图6所示。由仿真结果可知，与文献[4]、文献[7]和文献[12]中提出的码字相比，本文构造的码字在BER为10-5时分别实现了约0.1 dB、0.2 dB和0.4 dB的BER性能提升。此外，从图中可以看出，本文提出的QC-LDPC码在BER接近10-7的时候，“瀑布区”仍然具有很大的斜率，且没有出现错误平层。 图6 本文构造的(2560,765)QC-LDPC码与对比文献的码字BER性能对比 为了进一步说明上述进行仿真的4种QC-LDPC码之间误码率性能差异的原因，本文利用环搜索算法分别对上述4种码字的短环数量进行了仿真比较，分别给出了各码字在扩展因子P=256时的短环数和8环数，如表2所示。从表中可以看出，在相同的码长和码率下，本文提出的基于GAS构造的QC-LDPC码具有更大的围长，或者在具有相同围长的情况下拥有更少的短环数。由于QC-LDPC码的围长越大，短环数越少，码字的最小汉明距离(MHD)下界就越大，BP类迭代译码算法的性能下降就越少，因此本文提出的基于GAS构造的QC-LDPC码具有更佳的BER性能。 表2 本文提出的QC-LDPC码和参考码字的环数比较 本文提出了一种基于GAS和局部优化算法的大围长QC-LDPC码构造方法。首先，利用GAS中各元素之间的差值不等性构造QC-LDPC码的CSCM，根据扩展因子对构造的CSCM进行扩展，得到的QC-LDPC码中一定不存在4环和第一类6环结构，且当CSCM中的元素不满足d2-d1=d3-d4时第二类6环结构也不存在。然后提出一种局部优化算法对存在第二类6环结构的CSCM进行围长优化，消除CSCM的第二类6环结构，确保基于CSCM扩展得到的QC-LDPC码中不存在短环结构影响码字的译码性能，围长至少为8。仿真结果表明，与现有的一些构造方法相比，根据本文提出的基于GAS构造方法构造的QC-LDPC码在AWGN信道上表现出更好的误码率性能。3.2 6环分析
3.3 局部优化算法
若不存在，即所有可能的组合已经全部搜索完毕，执行步骤4。
若不存在一组SCV满足式(3)，则直接执行步骤2。
若矩阵B为零矩阵，算法结束，输出矩阵E=E0。
否则执行步骤2。
