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]，h_i，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算法构造基矩阵W_J×L，提高多元LDPC码随机性，降低结构化构造对纠错性能带来的损失。将改进的QC-LDPC构造算法与irPEG算法结合，称为混合构造算法，即HC构造算法。HC构造算法步骤如下：

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

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

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

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

    将循环移位系数矩阵S_J×L对角线上系数设为0，随机选择移位系数s_j，l，通过W_J×L结合避免长度为2ⁱ的充分必要条件，如式(5)所示，确定移位系数矩阵S_J×L中移位系数s_j，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循环移位系数矩阵S_J×L。irPEG算法构造同样大小校验矩阵，存储一个p×J×p×L大小的校验矩阵。可见，HC算法与irPEG算法相比具有更简单的矩阵存储结构。

    在编码复杂度方面，PEG算法采用高斯消去编码算法，irPEG算法和HC算法采用多元迭代编码算法。高斯消去编码复杂度包含预处理，运算复杂度为o(n³)，编码复杂度为o(n²)，整个编码过程需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)