低复杂度的LDPC并行分层译码算法研究

随着无线通信的快速发展，5G对传输速率和时延都提出了比较高的要求，而信道编码是实现这些要求的关键技术之一。低密度奇偶校验码（Low-Density-Parity-Check-Code，LDPC）是Gallager提出的一种线性分组码，目前被广泛应用于空间通信、光纤通信、数字广播和音频广播等领域。LDPC也被DVB-S2、CCSDS、IEEE 802.16e等标准所采纳。在2004年，LDPC码成功进入全球互联网接入（Wi-MAX）标准中，2008年，又被无线高保真（Wi-Fi）技术采用。5G的LDPC码是一种准循环的LDPC码（Quasi-Cyslic Low-Density-Parity-Check-Code，QC_LDPC），虽然LDPC码性能优异，但是译码算法复杂，因此降低其译码算法的复杂度一直是研究的重点。

常见的LDPC译码算法是置信度传播算法（Belief Propagation，BP），它是基于tanner图的传播算法。BP算法运用了tanh和tanh ^-1等函数，所以硬件复杂度较高，不利于工程实现。相关文献提出了一种高吞吐量分层解码架构，它对一层奇偶校验矩阵进行分块处理，其中每个块是一个循环权为K的Z×Z循环矩阵，当迭代次数为15次时，最大吞吐量为1.1 Gbit/s；相关文献提出了一种新的基于基图的5G LDPC码分层译码静态调度（BGSS），该方法根据BG矩阵的行权、列权和打孔非零元素个数确定各层的更新顺序，加快译码收敛速度，减少平均迭代次数；相关文献提出了一种基于精细-粗糙方法的多尺度循环移位网络，将循环移位尺度分解为精细部分和粗糙部分，所提出的MCSN结构在5G NR LDPC译码器中的面积节省高达56.75%。

本文提出的是一种改进的分层式译码结构，因为基矩阵的前4行不是严格正交，所以对前4层进行单独译码，后面的进行并行译码。在计算每一层的软信息时，就会更新此次迭代中的相关节点信息，用于下一层软信息的计算。该译码结构运用的是最小和译码算法（Min-Sum，MS），MS算法性能相比BP算法要差一点，但是复杂度更低，收敛速度更快，可降低所需的迭代次数。通过仿真可以发现该算法与传统的译码算法相比迭代次数减少4~5次，本文设计的译码算法结构在损失少量性能的情况下获得了较高的收敛速度以及较低的复杂度。

准循环LDPC码是结构化LDPC码的重要子集，它的奇偶校验矩阵由许多维度相等的方阵组成，每个方阵都是由大小相等的零矩阵、单位阵、单位阵的移位矩阵组成。如图1所示，H_b就是基矩阵，Z为提升因子，H即为扩展后的矩阵。在5G NR标准中，基矩阵分为BG1和BG2，BG1的大小为46×68，它适用于高码率、高吞吐、码长长的场景，BG2的大小为42×52，适用于低码率、低吞吐、码长短的场景。

5G NR的编码方案是基于H×v^T=0，一般先将H分为6个部分：，其中A是核心部分，对应待编码的信息比特；B是一个方阵且具有双对角结构，对应码率比较高的校验比特；O为全零矩阵；E是一个单位矩阵，对应于低码率的校验比特；C、D和E构成了单奇偶校验关系。将码字v分为2个部分v=[s，p₁，p₂]，s为信息比特，p₁和p₂为校验比特。编码过程大致如下：

然后运算矩阵再展开：

因为是模二运算，可以将式（2）化简：

根据式（3）可以求出p₁和p₂，然后得到码字v，即可完成编码。

LDPC的译码算法分为硬判决和软判决，硬判决运算简单且易于工程实现，但性能较差，所以只考虑软判决，这是一种基于后验概率信息的判决，经过反复迭代，使得LDPC的性能非常逼近香农限。常见的BP译码算法分为：对数域BP和概率域BP。而概率域运算含有大量的乘法运算，硬件实现时具有较高的计算复杂度、资源消耗大。在实际应用中，将概率信息用对数似然比表示，就得到了对数域上的BP算法，将大量复杂的乘法运算变为加法运算。

a）信道初始化：

b）校验节点发送给变量节点的信息：

根据式（5）的特点，引入了双曲正切函数：，可以利用这一性质对式（5）进一步化简：

c）变量节点传给校验节点的信息：

d）译码判决，经过迭代后变量节点的后验概率信息应变为：

当后验概率大于0时，将v_i判决为0，反之判决为1。

因为传统的BP译码算法复杂度太高，硬件实现难度太大，所以提出了一种结构简单，而且性能良好的分层结构。该结构基于改进的最小和译码算法，最小和算法是对校验节点传递给变量节点外信息的改进，将复杂的tanh函数和tanh⁻¹函数转化为基本的符号值计算和数值比较运算。分层结构将校验节点分成若干组，在每轮迭代中首先更新校验矩阵中的一组校验节点信息，然后更新与该组校验节点相连的变量节点信息，然后再更新下一组，直至最后一组。图2所示为该结构的Tanner图，在译码过程中，已经更新的变量节点信息能应用到本轮迭代后校验节点信息的更新过程中，这就使得迭代收敛速度加快了，很大程度上提高了译码吞吐率。它的译码器结构如图3所示，其中包括存储器、路由网络、移位网络、校验节点单元、控制器等。

在传统的对数域BP算法中，在信道初始化时，要想获得信道噪声功率σ²，须对其进行估计，但在最小和译码算法中，数值计算转变为变量节点概率绝对值的比较运算，而且信道参数是共同参数，所以在运算中可以省略，不会影响整个译码过程。在硬件实现时，就不需要设计信道参数估计模块，进一步简化了电路，提高了译码的时效性。所以可以将校验节点传给变量节点的信息改写为：

又因为：

然后，结合式（9），可化简得到：

根据tanh的函数可知其值是小于1的，所以相乘之后结果会变小，这里就使用最小值来代替连续相乘之后的结果，这样得到的最小值是肯定大于连乘之后的结果。最小和译码算法将LLR_BP算法的非线性乘法简化为了符号运算和最小值运算，带来了性能的损失，所以本文又引入了一个修正因子来补充损失的性能，而且复杂度大大降低了。

将Z个校验矩阵分为一层，BG1一共有46行，所以分为了46层。又因为基矩阵的前4行非零元素较多，每2行之间并非严格正交，如果并行译码会有一定的损失，但这种损失也是非常小的。所以提出了一种部分并行的结构：前4层单独解码，后面的再进行并行计算。其中l表示迭代次数，min₁和min₂分别表示上一次迭代中与校验节点相连的变量节点的最小值与次小值，mindex表示最小值的位置，index表示当前变量节点的序号，sign为符号函数。

通常把α叫做归一化因子，0≤α≤1。在实际应用中，α一般为取值0.6~0.9的一个常数，可以通过仿真找出最佳的归一化因子。虽然多了一次乘法运算，对计算复杂度影响不大，还可以很好地提升译码性能。

该译码算法以校验节点为单位，对校验节点分组，然后进行节点的更新，其算法流程如图4所示。

本次实验基于5G NR LDPC码进行仿真，对不同情况下的译码效果进行了仿真分析。首先对传统的不同译码算法结构进行仿真，码长K=3 960，码率r=1/3，基矩阵为BG1，扩展因子为60，调制方式为BPSK，在AWGN信道下传输，仿真平台为Matlab。使用Matlab产生一段二进制随机信源，整个过程基于一帧数据的模式。仿真流程如图5所示。

图6所示为加入本文提出的译码结构后的结果。从图6可以看出，在信噪比小于1.15 dB时，分层译码算法误码率都高于BP算法，但差距也很微弱，当信噪比大于1.15 dB时，分层译码性能要好于BP算法。

图7所示为各种算法的收敛性能。从图7可以看出，分层译码算法的收敛速度是最快的，其次是BP算法。当迭代次数在0~10次时，误码率下降较快，后面趋于平稳。该算法的收敛速度也很快，节省了多达5次的迭代，而且算法复杂度较低，工程上易于实现。

图8是在码长K=3 960，使用分层译码，调制方式为BPSK的情况下，不同码率以及迭代次数的误码率的仿真结果，从图8可以看出，码率越大误码率越高，迭代次数越多，译码效果越好，但在实际情况中，须选择合适的码率和迭代次数。

在分层译码结构中使用了归一化因子α，所以要找到最优的归一化因子，图9所示为不同归一化因子下的译码性能，该算法对归一化因子很敏感，在其他参数不变的情况下，改变了扩展因子和比特信噪比，可以看出在短码、中码、长码的情况下，最佳的归一化因子大致在0.6~0.8，但是在硬件实现时，二进制乘法可以转化为移位加法，综上，0.75可以被很容易地表示为二进制小数0.11，所以0.75为最佳的归一化因子。

该译码结构多次对N层进行迭代译码，相比于传统的译码算法，此结构算法复杂度低，且吞吐率也有一定的提升。该结构的译码吞吐率可表达为：

其中，M为基矩阵中行的长度，Z为扩展因子，Rate为编码码率，f_clk是时钟频率，N是译码结构的层数，I_iter为最大迭代次数。当时钟频率为800 MHz时，吞吐率大概为2.29 Gbit/s。可以看出该译码器具有良好的性能。综上，该译码结构在各种情况下都表现出不错的译码性能，算法复杂度低，且比较容易在硬件上实现。

衡量一个算法是否优良的重要指标是算法的复杂度，在码长K=3 960，码率为1/3的情况下，比较几种传统的译码算法和改进的分层译码算法的复杂度性能，令校验矩阵H的行数和列数分别为m和n，其中行重和列重为w_r和w_c，然后进行一次迭代后的复杂度如表1所示。

表1 不同译码算法复杂度

由表1可知，LLR_BP算法的加法次数虽然最少，但是它具有大量的乘法和除法，所以该算法的复杂度比较高，MS算法的复杂度是最低的，但是它的译码性能与其他算法相比是最差的，因此也不考虑，虽然分层译码比MS要多一步乘法运算，但相对于LLR_BP还是简单很多，综合考虑译码性能和译码复杂度，分层译码是最优选择。

本文提出了一种算法复杂度低且性能良好的分层译码结构，使用了改进的最小和译码算法，相对于传统的算法省去了大量的函数运算，并引入了归一化因子来改善性能，与BP算法相比，该算法获得了约0.1 dB的性能增益。考虑到基矩阵前4行之间并非完全正交，所以进行单独译码，具有更强的灵活性。此结构并行度高，具有较高的吞吐率，收敛速度快，减少了迭代次数。因此，本文提出的译码结构对无线通信中的5G NR具有重要意义，希望未来能在完整的通信系统上对此译码结构进行实现。

卢恒，硕士在读，主要研究方向为LDPC信道编码；

魏华，副研究员，博士，主要研究方向为通信专用集成电路与微电子系统、无线通信技术应用；

王国开，硕士在读，主要研究方向为无线通信技术与应用。