LDPC码SPA算法的迭代加速

李韦健

北京交通大学 北京 100044

引言

1962年，Gallager率先提出了低密度奇偶校验码的概念[1]，其通过校验矩阵的低密度特性尽可能降低了在与之相匹配的Tanner图中出现环路的可能，因此在码长较长的情况下其译码性能接近香农限，针对LDPC码，和积算法（sum-product algorithm，SPA）是目前比较常用的译码方式。

SPA译码算法作为最经典的译码方式，其基本的译码思路是在校验节点和变量节点之间不断进行信息交互来完成译码[2-3]，在不断迭代的过程中译码结果将符合所有校验方程而得到码字。

尽管SPA译码算法在译码性能方面极其优秀，但是同时也带来了极高的计算复杂度，为了优化此问题，研究者们提出了LLR SPA算法[4]，将概率域SPA译码算法传递的概率信息转换为对数似然比信息，从而由简单的加法运算取代原来复杂的乘法计算过程，在降低译码难度的同时译码时间也被大幅减少。

LLR SPA算法的主要优点是在复杂度比较低的同时又有较高的译码效率，但这种方式也导致了逻辑资源被大量占用。为了解决该问题，研究者们用一种近似的方式来简化计算过程，以损失少量计算精度的方式大大节省了逻辑资源，即Min-Sum（MS）算法[5]；以及通过增加一定的偏移量对损失的精度进行补偿的Offset Min-Sum（OMS）算法。

SPA通常采用泛洪调度算法，即在迭代过程中校验节点的更新和变量节点的更新是顺序进行的，校验节点的更新要在变量节点完成全部更新后进行，变量节点的更新也要在校验节点全部更新后进行[6]。当选择部分节点优先更新的调度算法时，可以有效加速迭代，提高收敛速度，黄捷等[7]采用动态调度的方式对信息进行有选择的更新以此来加快收敛，陈发堂等[8]依据残差值对振荡较大的变量节点处理有效加快了迭代速度。

以上对SPA的改进算法中，LLR SPA、MS、OMS均降低了计算复杂度，并不能加速译码收敛，调度的改进虽然能加速迭代，但计算复杂度和控制开销有较大增加。

受Gauss-Seidel法求解方程的启发，本文在泛洪SPA中引入新的节点更新规则，确保节点更新时均利用邻居节点的最新信息，减少了SPA的迭代次数，并改善其误码性能。需要指出，除了SPA，该算法还能直接应用上述各各种SPA的改进算法中，加速其译码收敛。

1 SPA简介

SPA算法的译码方式是基于Tanner图的，信道外信息输入之后顺着Tanner图的边在校验节点和变量节点之间持续交换，两种节点之间的信息轮流更新，两种节点信息分别完成一次更新表示一次迭代，在汇总完所有信息之后进行译码判决并输出译码结果。该过程中两种节点更新产生的信息作为信道外信息，而一开始得自信道的信息作为内信息。

为便于阐述SPA的流程，译码中用到的符号如表1所示。

表1 符号定义

SPA译码算法：

校验节点更新：

变量节点更新：

计算变量节点后验概率：

译码判决：

2 迭代加速

在求解方程组时，Jacobi迭代法的迭代形式为：

Gauss-Seidel迭代法的迭代形式为：

由于Gauss-Seidel迭代法利用了当前迭代的最新结果，即式（6）中的部分，因而加快了迭代的收敛速度。仔细观察可以发现SPA算法在校验节点以及变量节点更新部分的式（2）和式（3）同样可以利用这种方式进行改进，并且SPA译码算法中使用两种不同节点之间进行信息交互，这种改进将更有效。

加速算法：

如图1所示，变量节点收到信道初始信息之后进行信息的初始化，原始的信息更新步骤如下。

图1 Tanner图

将第n个变量节点第k次的传递的信息记为将第m个校验节点第k次传递的信息记为

根据高斯迭代方式提出加速算法，在每次迭代中，校验节点都能使用最新的迭代信息，则SPA中的变量节点信息更新过程变为：

3 仿真及分析

采用1/2码率的（2304，1152）LDPC码在AWGN信道下进行仿真，调制方式为BPSK，采用SPA译码，最大迭代次数为50。

图2所示为SPA和加速算法1、以及引入松弛因子的加速算法2的平均迭代次数比较。从图中可以看出，两种加速算法所需的平均迭代次数均明显好于SPA，且加速算法2较加速算法1有进一步加速性能。在信噪比超过1.6dB后，加速算法1所需迭代次数较SPA减少了43%，对加速算法2，这个减少量增加到56%。这意味着，采用加速算法后，只需不到SPA一半的迭代次数，便能达到同样的错误性能。

图2 （2304，1152）LDPC码在不同算法下的迭代次数比较

仿真显示三种算法误比特率相差不大，并且由于两种加速算法下译码收敛速度的提高，在平均迭代次数大幅减少的同时，其误比特率较SPA也有明显改善。

需要指出，由于两种加速算法仍旧使用泛洪调度，并未增加任何控制开销。计算复杂度和存储开销的增加更是微乎其微。

4 结束语

SPA每次迭代中，校验节点与变量节点交替更新。将Gauss-Seidel迭代思想引入SPA中，使得每次节点更新均采用邻居节点的最新信息。仿真结果表明，加速算法能够减少一半以上的迭代次数，且错误性能亦有改善，而译码复杂度几乎无任何增加。