多元LDPC码的构造与译码研究综述

赵勇 夏融 丁彦

摘 要：随着通信技术的不断进步，LDPC码以其优越的纠错性能和高效译码算法成为信道编码中关键技术之一，被广泛应用于多种通信标准中。其中，多元LDPC码在高阶调制下以及突发错误信道中表现更好，尤其是短到中等码长条件下性能提升明显，但也存在不足。为了更好协调频带利用率与误码率之间关系，降低译码复杂度，文章对多元LDPC码的构造与译码方面展开论述，主要阐述了其发展历程和研究现状，探讨了目前存在的问题以及改进方向。

关键词：信道编码，LDPC码，多元LDPC码，构造，译码

0   引言

科技的进步对当前通信系统提出了更高要求。一直以来，信道编码作为数字通信系统中保证信息可靠传输的关键技术之一而备受人们关注，其中低密度奇偶校验LDPC码是一种常用的线性分组码，最早由Gallager在1962年其博士论文中提出，证明具有可以十分接近香农极限的纠错性能，但受当时硬件计算能力的限制，直到1995年，LDPC码才重新引起了学术界和工业界的广泛关注。

LDPC码的特点是其校验矩阵具有稀疏性，矩阵中含有大比例的零元素，结构相对简单，主要采用软判决译码算法，通过在变量节点和校验节点之间反复传递外信息实现信息收敛，从而正确译码。LDPC码已成为DVB-S2、WiFi等应用场景中常用的编码方式，对比3G和4G移动通信标准中使用的Turbo码来说，中短码长下LDPC码具有较好的瀑布曲线性能以及更灵活丰富的码长和码率。2016年，成功作为5G移动通信技术标准中数据业务信道的编码方案。除了目前已经广泛使用的二元LDPC码，多元LDPC码的优势明显，但也存在着阻碍其发展的难点和挑战，其多元特点增加了校验矩阵构造的难度，提高了编译码复杂度。本文首先介绍多元LDPC码的基本概念，阐述LDPC码的优缺点以及实际应用场景，针对多元LDPC码的构造和译码方面研究展开论述，讨论目前常见的构造和译码方式并分析其优势和不足，最后进行总结。

1 多元LDPC码的基本概念

设GF（q）是包含q个元素的伽罗华域，其中q由素数的幂得到。定义在有限域GF（q）上的校验矩阵H=[hi，j]0≤i≤m，0≤j≤N构成了一个q元的规则LDPC码，该码具有以下结构性质：      （1）固定的列重和行重;（2）每两行（或两列）对应位置都不存在相同非零值。如果行重列重不唯一，则称该码字为非规则LDPC码。

二元LDPC码的校验矩阵由“0”和“1”组成，而多元LDPC码的校验矩阵则是由有限域中域元素组成，例如在伽罗华域GF（23）下，域元素包括{α﹣∞=0，α0，α1，…，α6}，其中α表示该域下的本原元，用α的多次幂可以表示所有域元素。多元LDPC码的表示方法主要有两种，校验矩阵和Tanner图。其校验矩阵中的非零元素在Tanner图中表示为连接边上的标签值。定义在GF（23）的多元LDPC码的Hq见公式（1）：

对应的Tanner图见图1：

为了降低运算量和硬件存储空间，在构造LDPC码时采用准循环结构，称为准循环低密度奇偶校验码（QC-LDPC），其校验矩阵由多个循环移位子矩阵构成，仅通过循环移位子矩阵简单地移位操作便可完成构造，结构化的校验矩阵在保证性能的同时，大大降低了运算量和存储空间，方便编码，也加快了译码收敛速度。

2   多元LDPC码的优缺点及应用场景

LDPC码在码长趋于无穷时，性能可以逼近香农极限，但在实际应用中多使用中短码长进行传输。由于接收端必须接收完整的码块后才能进行译码，因此当码长较长时延更大，不利于在时延要求高的场景下使用，因此提升中短码长性能是十分重要的。此外，随着码率增大，编码序列中包含有用信息位数增大，校验位数减少，纠错能力下降。

多元LDPC码定义在有限域上，利用域元素直接编译码，具有一定性能增益，其优点如下：（1）纠错性能优异，由于多元LDPC码用一个多元字符代替多个二元比特，可以掩盖中小环的存在，在译码过程中可以减少重复迭代的可能，提高纠错性能;（2）抗突发错误能力强，对于同时发生随机和突发错误的通信和数据存储信道，多元LDPC码可以将二元比特的突发错误合并成少量的多元符号错误，具有很强的抗突发错误的能力;（3）传输速率范围大，它可以使用于高阶调制通信中，提供更高的数据传输速率和更大的频谱效率。

基于上述优势，多元LDPC码值得学术界更多的关注，但研究多元LDPC码也要考虑几个方面的难点：（1）构造难度大。其校验矩阵具有多元特点意味着构造时需要考虑合适的有限域和本原元，基矩陣的度分布以及非零元素的选择等因素，构造时可以借鉴许多二元LDPC构造方法;（2）译码复杂度高。多元LDPC码的译码算法中译码复杂度很高，目前也一直致力于寻找纠错能力强，译码过程简单的译码算法;（3）性能分析困难。运用密度演进算法等分析工具进行性能分析时复杂度更高。

由于不同应用场景下信道条件不同，对LDPC码的要求也不同。对于移动通信信道来说，随着用户数量的增加，要求具有更高传输速率以及更大信道容量。而对于卫星信道来说，其传输带宽较窄，需要较高的频带利用率以及更好的抗干扰能力。高阶调制技术的使用可以提高频带利用率，目前主要的高阶调制技术有正交幅度调制技术QAM和相移键控PSK调制技术等。更高阶数的调制技术可以带来频带利用率的提升，但弊端是使得译码门限提高，即达到相同的误码率时需要更高的信噪比。由于多元LDPC码直接对符号进行编译码，适合与高阶调制技术结合。多元LDPC码可用一个符号代表多个比特，可以克服突发错误，带来了性能提升。基于上述优势，多元LDPC码值得学术界更多的关注，但研究多元LDPC码也存在构造、译码以及性能分析等方面的难点，优化多元LDPC码的码字结构、降低译码复杂度以及分析码字性能具有一定实际意义。

3   多元LDPC码的构造与译码研究

20世纪60年代左右，Gallager在提出二元LDPC码的同时开始利用有限域构造多元LDPC码，但只是从思想上提出多元码。直到1998年，Mackay和Davey成功证明了基于有限域随机构造出来的LDPC码性能优于二元LDPC码，在高斯白噪声（AWGN）信道和二元擦除信道（BEC）上都具有良好的迭代译码性能。

事实上，多元LDPC码的构造方法可以分为两类，即随机化构造方法和结构化构造方法。PEG算法是一种常用的随机构造法之一，已知度分布下可逐步建立起校验节点和变量节点之间的连接，用于建立较大环长的多元LDPC码的Tanner图。近似环外消息度（ACE）算法也是著名的基于计算机的随机构造算法之一，它在考虑环的基础上，增加了重叠环对译码的影响，以此来提高译码迭代时外信息的流通性。上述随机构造法需要进行大量的计算机搜索运算，构造的码字毫无规律，虽然随机构造的LDPC码具有良好的性能，但编码复杂度很高。

利用代数理论、有限几何知识以及矩阵运算理论为主的结构化构造法可用于构造一类校验矩阵具有规律结构的多元LDPC码。通过利用特殊结构的集合，例如完美差分集、素数集和好码等可以构造一类具有规律性结构的LDPC码，有效地改善了瀑布区性能，带来一定的性能提升。构造多元LDPC码时可以结合“好”码带来结构上的优化，包括广义RS码（GRS）和非规则重复累加码（IRA）等。通过结合其他码字特性，优化多元LDPC码的校验矩阵，使其可以高效编码，易于硬件实现，进一步提升编码器吞吐量。有限几何知识是构造LDPC码的重要方式之一，最早，利用点和线之间关系可以得到最小距离和陷阱集较优的码字结构，具有非常低的错误平层。矩阵运算理论中掩模技术使用较多，掩模技术主要通過将已知结构的校验矩阵与某一掩模矩阵相乘，改变原有矩阵结构，在降低短环数目的同时使其度分布更好，稀疏性更强。

此外，衡量码字优劣的指标很多，包括环分布、最小距离、陷阱集等，上述几种结构化构造方法也从这些衡量指标出发。其中对于环的存在，特别是短环，易带来变量节点之间的相关性，使得外信息仅传递几次就回到自身节点，不利于准确译码，如PEG算法专注于设计环长较大的码字。最小距离则反映了编码后码字在受到噪声干扰时变为相邻码字的难易程度，最小距离越大则受噪声影响越小，也越容易译码，也是影响译码门限和性能曲线瀑布区的关键因素之一。由于多元LDPC码定义在有限域上，其校验矩阵由域内元素组成，因此从优化系数集的角度，可实现对环等衡量指标的优化。

除了构造方面对于提升LDPC码性能带来好处外，复杂度较低的译码算法也十分重要，不仅可以降低对硬件的要求，也可扩大编码应用场景。对于多元LDPC码来说，译码复杂度较高，是限制它在现实应用场景的范围的主要原因之一，因此降低其译码复杂度是很有意义的。降低计算量和复杂度的主要解决途径包括简化每次迭代时有限域上的加法运算和乘法运算复杂度，保证纠错性能的前提下，尽可能降低迭代次数等。

目前，复杂度较高的多元和积译码算法（QSPA）依旧是目前性能最优的译码算法，但不适用于实际，随后又产生了基于傅里叶变换的FFT-QPSA，进一步基于对数域提出了Log-FFT-QSPA，避免了实数乘法运算。虽然上述各种算法在一定程度上降低了译码复杂度，但是依旧不利于实际应用。因此采用消息截短和排序方法来进一步降低复杂性和内存需求，同样其复杂度主要集中在校验节点的更新处理上。2007年，扩展最小和（EMS）算法出现了，是一种通过牺牲性能降低复杂度的算法，也是目前应用最广泛的多元译码算法之一。EMS算法将输入节点更新的外信息减少，但是输出并存储的值仍不变，这无形中增大了对存储器的要求，因此为节省内存，文献[1]提出与对两类节点都进行了截短处理，用补偿因子解决因截短外信息引起的性能下降问题，结果表明在每次译码迭代中显著降低了复杂度，将译码器的外信息截短到有限的数值，可以减少对内存的需求，是一种较好的硬件实现方案，但是对截掉的部分采用相同值替代可能会带来一些误差。

总的来说，EMS算法复杂度比QSPA低，但有较大的性能损失，为缩小两者之间的性能差距，在校验节点更新中采用改进的检泡算法，包括动态EMS算法、基于动态检泡的EMS算法和联合解调EMS算法，性能上有所提升。文献[2]提出了一种基于组合优化的简化最小和算法，利用校验节点处理的近似方法实现复杂性和性能之间的权衡。文献[3]在MSA中利用可靠性估计提高误码性能，相比位翻转算法（BF）具有更大的优势，主要应用于实时译码和纠错场景下的性能提升，具有更高的安全性。文献[4]则通过大量仿真分析了EMS算法中码率、迭代次数、排序个数以及修正因子对译码性能带来的影响，归纳总结其中的译码规律。

除上述算法外，一种用于多元码译码的低复杂度准优化迭代算法被提出，即Min-Max算法，将EMS算法中的加法运算简化为最大值运算，降低了译码复杂度。随后，提出了一种自适应Min-Max算法，在原有算法基础上，利用校验和中非零元素存在的比例作为自适应调节变量节点长度的依据，进而降低复杂度。同样，在原有Min-Max算法基础上提出改进措施，在译码过程中主要传递可靠度较高的校验节点信息以提高纠错效率。由于多元码字可由二元比特表示，直接对比特进行译码可以简化译码难度，故提出一种基于扩展矩阵的Min-Max算法，将多元的节点扩展为二元节点进行运算处理，它不仅降低了高斯消元法的计算复杂度，而且提高了误差性能，但是运算时间会增加。

综上所述，对于多元LDPC码的构造问题，核心目标是对衡量码字结构的指标进行优化，从而快速准确地构造一个结构良好的校验矩阵，有利于接收端准确译码。而对于多元LDPC码的译码问题，需要分析两类节点译码规律，在尽可能不降低纠错性能的同时，降低两类节点更新过程中的运算量。

4 结语

本文针对信道编码中常用的线性分组码—LDPC码进行讨论，多元LDPC码在中短码长下具有更好的性能增益而引起人们的注意，但也存在一些问题有待解决。先介绍了多元LDPC码的基本概念，其次探讨了其优缺点以及应用场景，最后从构造和译码两个方面对目前多元LDPC码的研究现状进行论述，从优化校验矩阵结构以及降低译码复杂度这两个优化方向上对相关研究进行综述，对优化多元LDPC码具有一定的指导意义。

[参考文献]

[1]VOICILA A，DECLERCQ D，VERDIER F，et al.Low-complexity decoding for non-binary LDPC codes in high order fields[J].IEEE Transactions on Communications，2010（5）：1365-1375.

[2]Wang C L，Chen X，Li Z，et al.A simplified min-sum decoding algorithm for non-binary LDPC codes[J].IEEE Transactions on Communications，2013（1）：24-32.

[3]Babu J C，Reddy C C，Prasad M N G.Generation and decoding of non-Binary LDPC codes using MSA decoding algorithm[C].Singapore：Micro-Electronics Springer，2018.

[4]蔡蓉燕.非二元低密度奇偶校验码LDPC译码性能研究[D].成都：西南交通大学，2016.

（编辑 王永超）