【学术论文】基于迭代编码算法的混合构造算法

摘要：

为了确保第五代移动通信（5G）技术的可靠性、稳定性、高传输速率的优势，基于具有线性编码复杂度的迭代编码算法，提出了混合校验矩阵构造算法。该算法首先对传统迭代编码算法进行改进，使其适用于多元低密度奇偶校验（NB-LDPC）码；然后采用后向迭代法改变编码方案和校验矩阵构造方式使渐进边增长（PEG）算法具有下三角结构，并将其作为基矩阵；最后采用改进后具有下三角结构的QC-LDPC算法生成循环移位矩阵和有限域系数矩阵，同时消除短环影响，从中选取最优的校验矩阵。仿真结果表明，混合构造算法所构造的多元LDPC码不仅具有线性的编码和存储复杂度，且有较强的纠错能力。

❖

0 引言

随着移动互联网和物联网的不断发展，第五代移动通信(Fifth-Generation Mobile Communication Technology，5G)面临移动通信爆发式增长[1-2]。5G技术不仅需要大幅度提升频谱利用效率，而且需要具备支持海量设备连接的能力[3-6]。由于低密度奇偶校验(Low Density Parity Check，LDPC)码具有高可靠性、快速收敛性及较强抗突发错误能力[7-8]，可以提高系统有效性[9-10]，使得3GPP RAN1会议在2016年确定在5G移动通信中使用LDPC码作为移动带宽eMBB业务数据的长码块编码方案。

本文对2004年由王鹏提出的LDPC码迭代编码算法[11]进行改进，转变为适用于多元LDPC码的编码算法，称为多元迭代编码算法；2005年，Hu Xiaoyu提出了渐进边增长（Progressive Edge Growth，PEG）构造算法[12]，该算法译码性能好，但编码复杂度较高。本文针对PEG算法具有高编码复杂度这一缺点，提出改进的PEG算法，即irPEG算法；结构化构造算法，即QC-LDPC构造算法[13]，该算法复杂，译码性能差于随机构造算法，但复杂度大幅度下降，硬件实现性强。本文提出一种改进的QC-LDPC算法，使校验矩阵具有下三角结构，降低复杂度，加快收敛速度，构造出无短环的校验矩阵。然后，从编码复杂度和纠错性能两方面考虑，基于多元迭代编码算法，提出混合构造算法，即HC构造算法，将随机构造和结构化构造算法结合，irPEG算法构造基矩阵，改进的QC-LDPC算法生成循环移位矩阵和有限域系数矩阵，消除短环影响，设置校验矩阵个数，从中选取最优校验矩阵。该算法既具有随机构造的随机性，又保持结构化构造的低复杂度，降低结构化构造对误码性能带来的损失，是比较折中的算法。

1 多元迭代编码算法

在图1中对角线上的元素全部为GF(q)域上的非“0”元素，并且剩余的非“0”元素全部对应于对角线左边。若构造出的多元LDPC校验矩阵具有图1的结构，则在编码过程中可直接采用迭代编码算法编码。

其中，l∈[0，n-k-1]，hi，j表示校验矩阵H中第i行j列上的元素，且k=n-m。由式(1)知，多元迭代编码算法过程为利用校验矩阵H中各行约束关系，采用后项迭代算法，逐次计算每个校验位符号值。

对迭代编码算法改进，将二元迭代编码时采用的与(AND)和异或(XOR)运算，改进为GF(q)域上乘法和加法运算。同时多元迭代编码算法的运算过程中引入了GF(q)域上除法运算。对运算量简化，将对角线上元素设置为1，式(1)改为式(2)。

2 混合构造算法

2.1 irPEG构造算法

针对PEG算法具有较高编码复杂度的缺点，提出一种具有下三角结构非规则的PEG算法，即irPEG算法。该算法从编码方案、构造校验矩阵方面改进，以降低编码复杂度，提升纠错性能。具体步骤如下：

(1)确定基矩阵中各参数

行列数、变量节点度分布序列，并且初始化基矩阵的信息，包括与变量节点相互连接的校验节点的集合以及它的补集。

(2)构造基矩阵对角线右侧下三角部分

首先采用后项迭代算法从最后一列变量节点构造，根据变量节点度分布[14]向前连接校验节点。每列中第一个非“0”元素位置必须与对角线上校验节点连接，其余非“0”元素需添加在对角线左侧。寻找所有与该变量节点连接的校验节点集合，从中筛选度数最小的校验节点集合。若该集合含有多元素，则从中删除构成短环的校验节点，随机连接剩余某校验节点，若只有一个元素，则直接连接该校验节点。

(3)构造基矩阵的前n-m列

从第n-m个变量节点依次向前构造。根据初始化变量节点度分布序列选择度数最小的校验节点，保证每行行重相比于平均行重相差不大。删除构成短环的校验节点后，从剩余校验节点中随机连接。

由于构造出的矩阵具有下三角结构，构造时在满足式(4)度分布的基础上，将矩阵最后一列列重设置为1，校验部分对角线上元素均为1，下三角部分均为0元素。由此可见，可以利用式(2)直接采用后多元迭代编码算法进行编码。

2.2 混合构造算法

虽然irPEG算法结合多元迭代编码算法可大大降低编码复杂度，但更适用于中短码硬件实现，对于长码来说，硬件实现复杂度依然较高。此时牺牲多元LDPC码一定纠错性能，在改进的QC-LDPC算法的基础上使其具有下三角结构，同时采用irPEG算法构造基矩阵WJ×L，提高多元LDPC码随机性，降低结构化构造对纠错性能带来的损失。将改进的QC-LDPC构造算法与irPEG算法结合，称为混合构造算法，即HC构造算法。HC构造算法步骤如下：

(1)irPEG算法构造基矩阵WJ×L。

给定多元LDPC码度分布，根据irPEG算法构造出具有下三角结构二元基矩阵，大小为J×L。

(2)确定有限域元素系数矩阵GcJ×L，根据基矩阵非“0”元素位置，在(0，q-1)间随机选择gcj，l值。

(3)基矩阵WJ×L确定循环移位系数矩阵SJ×L。

将循环移位系数矩阵SJ×L对角线上系数设为0，随机选择移位系数sj，l，通过WJ×L结合避免长度为2i的充分必要条件，如式(5)所示，确定移位系数矩阵SJ×L中移位系数sj，l。

其中，0表示p×p维的零矩阵，P表示p×p维的单位阵，码长为n=p×L，码率为r=(1-J/L)。HC构造算法的流程图如图2所示。

3 编码复杂度分析

PEG算法、irPEG算法、HC算法的编码复杂度如表1所示。其中，w是生成矩阵的平均列重，n是码长，k是信息位长。

在存储复杂度方面，HC算法构造的LDPC码存储矩阵时存储一个p×p维目标方阵P、一个J×L维多元系数矩阵GcJ×L及一个J×L循环移位系数矩阵SJ×L。irPEG算法构造同样大小校验矩阵，存储一个p×J×p×L大小的校验矩阵。可见，HC算法与irPEG算法相比具有更简单的矩阵存储结构。

在编码复杂度方面，PEG算法采用高斯消去编码算法，irPEG算法和HC算法采用多元迭代编码算法。高斯消去编码复杂度包含预处理，运算复杂度为o(n3)，编码复杂度为o(n2)，整个编码过程需wn次乘法，(w-1)n次加法。多元迭代编码算法整个编码过程用到(w-1)(n-k)次加法，w(n-k)次乘法。

irPEG算法和HC算法能直接构造出下三角校验矩阵，避免了校验矩阵预处理的同时保证了校验矩阵的稀疏性。因此，w相对于n可以看成非常小的常数，实现多元LDPC码的线性复杂度编码，与传统的构造算法相比，大幅度地降低了编码的复杂度。

4 仿真结果及分析

仿真参数设置：度分布服从式(4)的多元LDPC码，矩阵通过PEG算法和irPEG算法生成，在十六进制1/2码率（Code1）和3/4码率（Code2）下进行仿真，Code1时，信息位长为512 bit；Code2时，信息位长为176 bit。译码采用Mixed Log-FFT-BP译码算法[15]，迭代次数25，BPSK调制，AWGN信道。

图3和图4分别为Code1和Code2时不同码率下的纠错性能。由图3和图4可知，irPEG算法与PEG算法误码率相比，性能相差不大，表明irPEG算法构造具有下三角结构的多元LDPC码在大幅度降低硬件实现复杂度的同时，具有较强的纠错能力。

对Code1和Code2译码时间进行测量，保持仿真环境一致性，如表2和表3所示。由表2可知，irPEG算法时间明显比PEG算法少，当误比特数较少时，时间节省量少于50%，随着误比特数增加，时间节省量稳定在50%，因此，irPEG算法耗费时间仅为PEG算法50%。Code2在信噪比为4 dB时的仿真测试结果如表3所示，同样表明译码所需时间减少一半。

参数设置如下：码率1/2、2/3、3/4、4/5、6/7，矩阵通过PEG和HC生成，十六进制(Code3)下仿真，1/2码率时，基矩阵16列，目标矩阵P为24×24单位阵；2/3码率时，基矩阵18列，P为16×16单位阵；3/4码率时，基矩阵16列，P为16×16单位阵；4/5码率时，基矩阵20列，P为12×12单位阵；6/7码率时，基矩阵14列，P为16×16单位阵，固定信息位长768 bit。图5为Code3情况时，PEG算法与HC算法在不同码率下的误比特率性能。

由图5可知，HC算法与PEG算法构造的多元LDPC码在低信噪比时没有明显差别；在高信噪比下HC算法性能略差于PEG算法构造的多元LDPC码，因此两种算法具有一致的编码增益。

5 结论

本文提出基于多元LDPC码迭代编码算法的混合校验矩阵构造算法，首先对迭代编码算法改进，使其适用于多元LDPC码；然后采用后项迭代法使PEG算法具有下三角结构，并将其作为混合构造算法基矩阵；最后采用改进后具有下三角的QC-LDPC码算法生成循环移位矩阵和有限域系数矩阵，设置校验矩阵的个数，从中选取最优的校验矩阵，该校验矩阵消除了短环影响，形成混合构造算法。仿真结果表明，本文提出的算法可以更好地适用于5G移动通信系统且满足译码算法的需求，对于高速通信设备来说是一种很好的候选校验矩阵构造算法。

参考文献

[1] TANG B，YANG S H.An LDPC approach for chunked network codes[J].IEEE-ACM Transactions on Networking，2018，26(1)：605-617.

[2] MENG J H，ZHAO D F，TIAN H，et al.Sum of the Magnitude for hard decision decoding algorithm based on loop update detection[J].Sensors，2018，18(1)：236.

[3] ZHANG C，HUANG Y H，SHEIKH F.Advanced baseband processing algorithm[J].Circuits, and Implementations for 5G Communication.IEEE Journal on Emerging and Selected Topics in Circuits and Systems，2017，7(4)：477-490.

[4] DJORDJEVIC I B.Multidimensional OAM-Based secure high-speed wireless communications[J].IEEE Access，2017，5(4)：16416-16428.

[5] MALANDRINO F，CHIASSERINI C F，KIRKPATRICK C.Cellular network traces towards 5G：using，analysis and generation[J].IEEE Transactions on Mobile Computing，2018，17(3)：529-542.

[6] SOTELO M，MARCO A，MAESTRE V，et al.Reasoning and knowledge acquisition framework for 5G network analytics[J].Sensors，2017，17(10)：2405.

[7] YU Y，CHEN W.Design of low complexity non-binary LDPC codes with an approximated performance-complexity tradeoff[J].IEEE Communications Letters，2012，16(4)：514-517.

[8] SONG L Y，HUANG Q，WANG Z L.Two enhanced reliability-based decoding algorithm for nonbinary LDPC codes[J].IEEE Transactions on Communications，2016，64(2)：479-489.

[9] ZHAO S C，MA X.Construction of high-performance array-based non-binary LDPC codes with moderate rates[J].IEEE Communications Letters，2016，20(1)：13-16.

[10] XIA T，WU H C.Blind identification of nonbianry LDPC codes using average LLR of syndrome a posteriori proba-bility[J].IEEE Communications Letters，2013，17(7)：1301-1304.

[11] 王鹏，王新梅.LDPC码的快速编码研究[J].西安电子科技大学学报，2004，6(31)：934-938.

[12] Hu Xiaoyu，EVANGELOS E，DIETER M A.Progressive edge growth tanner graphs[J].IEEE Transactions on Information Theory，2005，51(1)：995-1001.

[13] DRAGOI V，KALACHI H T.Cryptanalysis of a public key encryption scheme based on QC-LDPC and QC-MDPC codes[J].IEEE Transactions on Information Theory，2018，22(2)：264-267.

[14] TONG N N.Research of encode and decode algorithm optimization and application for non-binary LDPC codes[D].Harbi：Harbin Engineering University，2014.

[15] SONG H，CRUZ J R.Reduced-complexity decoding of Qary LDPC codes for magnetic recording[J].IEEE Transactions on Magnetics，2003，39(2)：1081-1087.

作者信息:

孟嘉慧，赵旦峰，张  良

(哈尔滨工程大学 信息与通信工程学院，黑龙江 哈尔滨150001)