一种类Raptor多速率QC-LDPC码的代数构造方法

李华安，白宝明，徐恒舟，陈 超

(1.西安电子科技大学 综合业务网理论及关键技术国家重点实验室，陕西 西安 710071；2.周口师范学院 网络工程学院，河南 周口 466001)

低密度校验(Low-Density Parity-Check，LDPC)码是一类具有可逼近香农容量限的信道编码，由稀疏矩阵的零空间定义。低密度校验码最早由GALLAGER[1]于20世纪60年代在其博士论文中提出，在此后的近35年里，几乎被编码界忽略。在此期间，关于低密度校验码的研究甚少。值得一提的是TANNER[2]的工作，他推广了低密度校验码，并为其引入了图表示方法，即现在广被使用的Tanner图。直到上世纪90年代中期，多位编码学者发现具有稀疏(低密度)校验矩阵的线性分组码在迭代译码算法下具有逼近信道容量限的性能[3]，而且这类码还具有线性编译码复杂度，因此低密度校验码又重新引起大家的研究兴趣。虽然低密度校验码的早期研究不够成熟，错过了3G和4G标准，但因为其出色的性能和较低的译码复杂度，被重新发现后迅速被广泛且深入地研究。起初低密度校验码的校验矩阵很少具有结构特性，即原始低密度校验码是随机的。而若一个码没有结构特性，则编译码过程将比较复杂，因此人们提出了结构化低密度校验码。最为典型的结构化低密度校验码是准循环低密度校验(Quasi-Cyclic LDPC，QC-LDPC)码[4]。这类码编译码复杂度低，且在中短码长下，设计良好的QC-LDPC码译码错误平层低，性能优于随机低密度校验码，因此被广泛研究，包括设计与构造[5-8]、译码算法[9-11]以及应用[12-15]，并且这类码已被多个重要国际标准采纳，如WiMAX[12]、CCSDS[13]、WiFi[14]以及5G[15]等。

在实际的移动通信系统中，无线信道的时变特性以及多径衰落影响了信号传输，一些不可预测的干扰也会导致信号传输失败。除了采用纠错码，还会采用自动重传请求和自适应编码调制等方法进行差错控制，以确保服务质量，而可支持多种码率的变码率低密度校验(Variable-Rate LDPC，VR-LDPC)码可以满足这一要求。目前最为常见的VR-LDPC码主要有两种：具有固定信息位长度的速率兼容低密度校验(Rate-Compatible LDPC，RC-LDPC)码[15-17]和具有固定码长的多速率低密度校验(Multi-Rate LDPC，MR-LDPC)码。其中，打孔、缩短以及扩展是构造RC-LDPC码的常见方法，最为典型的是标准5G LDPC码[15]。由于MR-LDPC码的码长固定，非常适用于一些特殊的应用场景，包括多级编码调制系统和卫星通信，因此也被广泛研究。如在文献[18]中，作者基于删除的方法分别构造了多元MR-LDPC码，仿真结果显示所构造的码在不同码率下均具有较好的译码性能。

5G通信是通信基础研究与科技创新的结晶，也代表着信道编码技术在移动通信领域的突破与变革。3GPP关于5G信道编码的标准化基本完成，相关结论也已写入NR的R15规范[15]。R15阶段属于基础功能阶段，完成了增强移动宽带场景下信道编码研究与标准化工作，而后续阶段主要任务之一是增强超高可靠性的低时延通信等。我国科技部于2018年11月拟将“与5G/6G融合的卫星通信技术研究与原理验证”课题列入国家重点研发计划“宽带通信和新型网络”重点专项中。这说明了探索地面网络与其他通信系统融合方案的必要性与重要性，也是我国实现无线通信技术与星地融合从跟跑、并跑到领跑的重大需求。5G NR R15标准化的低密度校验码是一类具有类Raptor(Raptor-like)结构的RC-QC-LDPC码[17]。因此，笔者主要研究具有Raptor-like结构的MR-QC-LDPC码的构造方法，探索未来地面网络与其他对MR-LDPC码有需求的通信系统的编码融合方法。

结合代数和叠加构造方法，通过渐进改变移位尺寸，笔者构造了一类码长固定、具有Raptor-like结构的MR-QC-LDPC码。所构造的码具有易于硬件可实现的编译码器，而且可基于校验矩阵直接编码。此外，因为结合了代数方法，所构造的码的循环移位矩阵具有明显的代数结构，矩阵存储复杂度极低，即在已知基矩阵条件下，根据两个值就可得到MR-QC-LDPC码不同码率的循环移位矩阵。这种方法适用于构造具有类Raptor结构的MR-QC-LDPC码，在多种速率下具有较好的整体性能。

1 Raptor-like低密度校验码与准循环低密度校验码

1.1 Raptor-like LDPC码

二元低密度校验码是一类特殊的线性分组码，由稀疏矩阵H(矩阵中包含多数个“0”和相对少量的“1”)的零空间定义，这里矩阵H被称为低密度校验码的校验矩阵。而Raptor-like LDPC码的校验矩阵具有如下形式：

其中，HHR为高码率的校验矩阵，HIR是在高码率矩阵的基础上扩展得到的矩阵，I为单位阵。可以看出，Raptor-like LDPC码可以看成是高码率校验矩阵码为外码、扩展校验矩阵码为内码的串行级联码，非常适用于设计RC-LDPC码。因为扩展部分引入了很多重量为1的列，这些列一般会恶化码的译码错误平层性能，但由于此处低码率扩展部分[HIRI]只是作为内码，并不会引起明显的错误平层问题。

Raptor-like LDPC码可否基于校验矩阵直接编码与HHR的结构有关。当考虑系统Raptor-like LDPC码时，可以将其校验矩阵分为5个部分，如图1左边所示。此时，校验矩阵是否支持可直接编码与矩阵D的结构有关。而当D设计为下三角、单对角或者双对角矩阵以及三者的混合结构时，即可根据校验矩阵直接编码。笔者只关注D为双对角或者“单对角+双对角”的混合形式，而图1中的D即为双对角矩阵。

图1 一种可直接编码的Raptor-like LDPC码校验矩阵结构

1.2 准循环低密度校验码的叠加构造

考虑正整数Z和整数集合SZ={0，1，…，Z-1}。对于集合中的任意元素p∈SZ，可以用Z×Z大小的二元循环置换矩阵(Circulant Permutation Matrix，CPM)表示。为简单起见，将该循环置换矩阵表示为Q(p)。Q(p)具有如下特点(注：行和列标注方式均为0，1，…，Z-1)：

(1) 首行惟一非零元素“1”所在位置为p；

(2) 每一行由上一行循环右移一位得到；

(3) 最后一行循环右移一位得到首行。

不难看出，p∈SZ和Q(p)具有一一对应关系。方便起见，引入Q(-1)表示Z×Z大小的全零矩阵。称上述过程为Z阶矩阵散列(Z-fold Matrix Dispersion)，参数Z被称为移位尺寸。

二元(N，K)QC-LDPC码的校验矩阵H通常可以表示为阵列H=[Hi，j]0≤i

上述过程统称为叠加构造过程。这个过程依次设计基矩阵B和循环移位矩阵P，将P中的移位值散列为循环矩阵或大小相同的全零矩阵，从而得到QC-LDPC码的校验矩阵H。因此，叠加构造主要涉及3个矩阵和一个过程，即基矩阵、循环移位矩阵、循环矩阵和矩阵散列。

相关研究表明，影响QC-LDPC码迭代译码性能的主要因素有码字分布、环分布、围长和陷阱集等结构，而环分布均与其他结构有着直接或间接的联系。研究中还发现，QC-LDPC码Tanner图中的环由循环移位矩阵P以及移位尺寸Z决定，具体如下面引理所述。

引理1(Fossorier公式[4])设QC-LDPC码的循环移位矩阵P=[pi，j]0≤i

(1)

其中，0≤iZ

引理1指出了长度为2d∈[g，2g-2]的环的个数的一种计算方法，即只需搜索矩阵P中满足式(1)的非负移位值组数即可。在下文中，“d-环”表示长度为d的环，Nj(P，Z)表示对于移位尺寸为Z、围长为g的循环移位矩阵P，考虑长度为(2j+2)∈[g，2g-2]的环时满足式(1)的非负移位值组数。

1.3 一类代数构造方法及其有关结论

有很多代数方法可以用来构造不存在长度为4的环的循环移位矩阵。一种典型且非常灵活的方法是基于非二元素有限域的两个任意集合来设计。设S1={i0，i1，…，imb-1}(mb

P=[pk，t]0≤k

(2)

下面的引理给出了基于式(2)所示代数方法构造的循环移位矩阵的围长特性。

引理2基于素域GF(q)任意两个集合构造的具有如式(2)形式的循环移位矩阵P，其q阶矩阵散列定义的QC-LDPC码的Tanner图不存在4-环，围长至少为6[19]。

因此，当待设计的循环移位矩阵的移位尺寸为素数时，可以基于式(2)方法构造循环移位矩阵P，此时由P散列得到的阵列H不存在4-环。此外，还可以通过对P或H进行掩模处理以进一步改善QC-LDPC码的环分布。

2 Raptor-like MR-QC-LDPC码的代数构造

在QC-LDPC码的叠加构造中，要求基矩阵B已知。一般要求B具有较好的迭代译码门限，设计方法主要有计算机辅助的EXIT图搜索算法(如P-EXIT[20])和代数方法[19]。好的迭代译码门限可以提供较好的瀑布区性能，但不能保证所设计的码有较低的译码错误平层。而影响错误平层的主要因素有距离分布、环分布、围长以及陷阱集等。为获得较低的错误平层性能，在构造QC-LDPC码的循环移位矩阵P时应综合考虑这些因素的影响。在笔者提出的构造方法中，主要考虑环分布以及围长。

笔者提出的Raptor-like MR-QC-LDPC (RL-MR-QC-LDPC) 码代数构造方法需要已知具有类Raptor结构的基矩阵，而设计这类基矩阵的常见方法有基于P-EXIT的扩展方法。为提高性能，在设计基矩阵时可以基于打孔打掉某些信息比特，即假设前np列为内置打孔列。这些列的重量一般较高，与这些列对应的信息位不会被送入信道中传输，接收端译码时将这些信息位按照打孔比特处理。由于基矩阵是基于扩展方法设计的，高码率部分的基矩阵嵌套在低码率部分的基矩阵中，而低码率的基矩阵由高码率的基矩阵扩展而得，基矩阵的大小会随着码率的减小而增大。因此，构造这类码的难点在于：在保证码长固定不变的条件下，如何构造RL-MR-QC-LDPC码不同码率的循环移位矩阵，即随着码率变小(此时对应的基矩阵/循环移位矩阵的大小变大)，如何同时增加校验位和减少信息位。针对该难点，笔者结合代数方法和叠加构造，通过渐进改变移位尺寸来设计RL-MR-QC-LDPC码。

已知基矩阵B的信息位列数为kb，内置信息位打孔列数为np。为简单起见，将np固定为2。假设要构造的RL-MR-QC-LDPC码的码长为N，码率集合R={R1，R2，…，RT}(对于1≤i

(3)

(1) 计算参数：确定基矩阵B=[bi，j]0≤i

(2) 构造系数矩阵：构造mb×nb大小的系数矩阵C=[ci，j]mb×nb，其中

(4)

因此，待确定的值为{c0，kb，cr2nd，kb，cmdual-1，kb}。为了保证校验矩阵可直接编码，要求c0，kb=cmdual-1，kb，最终只有{c0，kb，cr2nd，kb}两个值需要确定。进一步，基于基矩阵B对C的前kb列进行掩模处理，得到Cmask=[c′i，j]0≤i

(5)

(3) 循环移位矩阵：码率Rt的循环移位矩阵为Pt=[pi，j]mt×nt，对于0≤i

(6)

因为所有循环移位矩阵均基于Cmask获得，而Cmask基于式(2)的代数方法构造，因此要求Zt∈SP，其中，SP表示由所有素数构成的集合。

(7)

其中，gt表示Pt的围长。选取{c0，kb，cr2nd，kb}，同时使M1和M2尽可能小，即只考虑围长g以及长度为g+2的环的影响。可以看出，准则M1和M2摒除了移位尺寸大小的影响，从而实现对可支持不同移位尺寸的循环移位矩阵的构造。

例如，大小为7×10、支持3种码率的RL-MR-QC-LDPC码的基矩阵以及系数矩阵如图2所示，其中mdual=4，r2nd=2。如图2所示，为了编码简单，双对角部分除了第1列，其余非负移位值均固定为0。根据Fossorier公式，即使C的多数值具有式(2)的形式，但因为双对角部分0的存在，也可能存在4-环，因此需要优化选取{c0，kb，cr2nd，kb}，改善最终循环移位矩阵的环分布，以获得较好的性能。

图2 一个RL-MR-QC-LDPC码的基矩阵与系数矩阵

图3 Raptor-like MR-QC-LDPC码的打孔与缩短示意图

笔者所构造的低密度校验码在不同码率下校验矩阵均具有类Raptor结构，这类码的快速编码参见文献[20]。

综上，笔者提出的设计与构造方法融合了多种技术，包括扩展、打孔和缩短处理，以及代数与叠加构造方法。所构造的RL-MR-QC-LDPC码的码率越低，基矩阵/循环移位矩阵越大，移位尺寸越小。因为Cmask具有明显的代数结构，在已知基矩阵B前提下，只需已知{c0，kb，cr2nd，kb}即可获得所提出的RL-MR-QC-LDPC码所有码率的循环移位矩阵，因此存储复杂度极低。

基矩阵B的非零元用于指示循环移位矩阵中非负移位值的位置，而置换非打孔信息列并不影响B的迭代译码门限。因此，还可以通过置换基矩阵B的非打孔信息列得到新的基矩阵和系数矩阵Cmask，并同时优化选取{c0，kb，cr2nd，kb}，保证最终的循环移位矩阵整体具有较好的环分布，进一步提高性能。

3 数值结果

根据上一节介绍的方法构造了RL-MR-QC-LDPC码，并通过仿真验证所设计的码的性能。在所有仿真中，考虑二进制输入加性高斯白噪声(Binary Input Additive White Gaussian Noise，BI-AWGN)信道，译码算法采用最大迭代次数为50的和积算法(Sum-Product Algorithm，SPA)[20]。

笔者所构造的RL-MR-QC-LDPC码的码长为960 bit，可支持的码率集合R={1/2，2/3，5/6}，基矩阵B的散点图如图4(a)所示，因此mb=18，nb=34，np=2，kb=16，r2nd=2。选取Wc=(10 000，1 000，100，1)，根据上一节介绍的代数方法，选取{c0，16，c2，16}={31，35}。基于上一节方法可获得不同码率的循环移位矩阵Pt(1≤t≤3)，将Pt(1≤t≤3)进行Zt阶矩阵散列，最终得到码率Rt(1≤t≤3)的编译码校验矩阵Ht(1≤t≤3)。3种码率的相关编码参数如表1所示，包括基矩阵大小、移位尺寸、信息位缩短位数和校验位打孔位数。对于3组码率，信息位打孔位数均为2Zt(1≤t≤3)。

表1 构造码长为960 bit的RL-MR-QC-LDPC码的编码参数

图4(b)展示了所构造的RL-MR-QC-LDPC码的误块率(BLock Error Rate，BLER)性能，以及WiMAX标准中具有相同参数的低密度校验码的误块率性能。从图中可以看出，笔者所构造的码整体性能优于标准WiMAX LDPC码[12]。需要说明的是，不同参数下标准WiMAX LDPC码对应不同的循环移位矩阵，而笔者构造的RL-MR-QC-LDPC码的矩阵存储复杂度极低，即只需要知道基矩阵和数值对{c0，16，c2，16}，就可以得到不同码率的循环移位矩阵。

(a) 基矩阵

(b) BLER性能

4 结束语

结合代数和叠加构造方法，通过渐进改变移位尺寸，笔者提出并构造了具有固定码长的类Raptor多速率准循环低密度校验码。基于该方法，随着码率减小，对应的基矩阵/循环移位矩阵增大，移位尺寸变小。为了获得固定码长和匹配不同信息位长度，还引入了信息位缩短和校验位打孔操作。笔者所构造的码兼具准循环和类Raptor结构，因此具有易于硬件可实现的编译码器，其编码也可直接基于校验矩阵实现。此外，因为引入了代数方法，所构造的码具有极低的矩阵存储复杂度，即只需知道基矩阵以及两个数，就可得到不同码率的循环移位矩阵。数值仿真表明，所构造的码的整体性能优于相同参数下的标准WiMAX LDPC码。NR R15规范的标准5G LDPC码是具有类Raptor结构的速率兼容低密度校验码，因此笔者提出的方法可为未来地面网络与其他对MR-LDPC码有需求的通信系统的编码融合提供一种可行方案。