非规则LDPC码译码改进算法及其DSP实现

为了降低非规则低密度奇偶校验(low-densityparity-check,LDPC)码译码算法的复杂度，提出一种适合数字信号处理嚣(digital signal processor，DSP)实现的低运算复杂度、低误码平台译码的改进算法。

该算法校验节点的运算采用修正最小和算法，外信息的更新采用串行方式，既保持了串行和积算法在有限迭代次数下译码门限低的优点，又降低了节点运算复杂度和误码平台。用定点DSP芯片实现的非规则LDPC码译码器的实测结果表明，该算法能以较低的实现复杂度获得低的误码平台和译码门限。

低密度奇偶校验(low-density paruty-check，LDPC)码是一种非常有效的信道编码方案，已经成为新一代数字卫星广播(DVB-S2)等标准的信道编码方案，具有重要的应用价值。

LDPC码译码器设计的实现成为近年来研究的热点。LDPC码译码器的实现方法主要有2种：一种是基于超大规模集成电路(VLSI)的设计;另外一种是基于数字信号处理器(digital signalprocessor，DSP)等指令串行执行系统的实现。

LDPC码译码多采用和积(sum-product，SP)译码算法，影响其复杂度的因素有迭代次数和每次迭代的运算复杂度。由于DSP芯片指令串行执行的特点，要实现较高速率的LDPC码译码器，必须同时减少迭代译码次数和每次迭代的运算量。文提出一种逐个校验节点串行更新的迭代译码算法(S-SP)，并说明在二进制对称信道(BSC)下可以有效降低迭代译码的次数;为降低每次迭代的运算复杂度，校验节点的运算存在一些简化的译码算法，如修正最小和算法(modified mim-sum，MMS)等，但这些算法的译码门限有一定的损失。

本文研究非规则LDPC码的S-SP算法在加性高斯白噪声(AWGN)信道下的性能，说明该算法虽能降低迭代次数，但是存在误码平台较高的问题。考虑到简化的译码算法(例如MMS算法)有复杂度和误码平台低的特点，本文综合这2类算法的特点，提出了串行MMS(S-MMS)算法，该算法在有限迭代次数下具有低的误码平台和较低的译码门限，实现了复杂度和性能的较好折衷，适合于用DSP实现。

1 LDPC码简介和迭代译码算法

1.1 LDPC码简介

LDPC码是一种分组码。其校验矩阵为超稀疏随机矩阵，设为H。对于任何一个合法的码字v，都有校验方程。由该方程可知，校验矩阵中每行的非零元素，将所对应的LDPC码元映射成一个相当于校验码的约束，定义这种约束关系为一个校验节点。校验矩阵中每列的非零元素对应LDPC码的同一个码元，形成了一个相当于重复码的约束，定义这种约束关系为一个变量节点，而矩阵中的非零元素，既参与了变量节点的重复码的约束关系，又参与了校验节点的校验码的约束关系;因此定义矩阵中非零元素所对应的关系为连结这2种节点的“连结线”。因此，LDPC码的结构也可以用图1的因子图表示。

LDPC码的编码，先利用校验矩阵得到对应的生成矩阵，然后直接用信息序列和生成矩阵相乘即可得到编码码字，而LDPC码的译码则利用校验节点和变量节点的约束关系，在2类节点间通过“连结线”进行外信息的传递，从而实现迭代译码。

1.2 LDPC码迭代译码算法

定义为变量节点n的先验信息，即对数似然比;表示第k次迭代中，从校验节点m到变量节点n的外信息;表示第k次迭代中，从变量节点n到校验节点m的外信息;为第k次迭代后变量节点n的后验信息;M(n)表示和变量节点n相连的校验节点的集合;N(m)表示和校验节点m相连的变量节点的集合。

标准的和积(SP)译码算法如下。

步骤l 初始化。

其中：xn为发送比特;yn为接收符号。采用二进制相移键控(BPSK)调制，信道为AWGN信道。

步骤2迭代译码。

迭代译码包括2个步骤，变量节点的计算和校验节点的计算。本文中设定固定的迭代次数K，然后判决输出。

1)变量节点的运算(对所有的变量节点n)。

2)校验节点的运算(对所有的校验节点m)。

其中k≥1.

步骤3后验信息计算和判决输出。

串行和积译码算法(S-SP)，在计算校验节点m时，需要将上面和积(SP)算法中的步骤2变量节点的运算修改为

其k≥1，假设校验节点的计算从1开始，也即m依次取1，2，3，…，M，这里M为校验节点的个数，如图1所示。

S-SP算法和SP算法的不同点在于：在SP算法中，所有与校验节点m相邻的变量节点更新时所使用的校验节点外信息都来自上一次的迭代输出，然后进行校验节点m的运算。而在S-SP算法中，计算校验节点m时，和其相连变量节点的更新可以使用本次迭代中已经更新过的外信息。从上面的分析也可看出，S-SP算法的复杂度和SP算法相同，另外，可通过合理设计，使得该算法需要的存储资源可降低为原来的1/2。

2 改进的迭代译码算法和优化设计

文指出，在BSC信道下，S-SP算法可以有效降低迭代译码次数。本文研究了该算法在AWGN信道下的特点，发现该算法虽可以降低迭代译码次数，但是存在误码平台较高的缺点。后面将利用仿真结果说明这一特点。

本文将S-SP算法与修正最小和算法(MMS)结合，提出了改进算法，将外信息的更新采用串行更新策略，校验节点的计算采用修正最小和算法，称为串行修正最小和算法(S-MMS)。该算法解决了S-SP算法的误码平台较高的问题，译码门限和标准的SP算法相比，性能损失很小。

提出的串行修正最小和算法(S-MMS)，其迭代译码步骤2修改如下。

设定固定的迭代次数K，对校验节点m，依次取1，2，3，…，M，进行下面的2个步骤。

1)变量节点的运算(只计算和校验节点m相连的变量节点)。

其中：r=│N(m)│表示集合N(m)中的元素个数，即非规则码的校验节点m的阶数;βr为非规则码不同阶校验节点的偏移因子;sgn()为符号函数。

最优的偏移因子βr值，可以采用密度演化或者计算机仿真的方法得到。

本算法变量节点的运算只包括求和运算，校验节点只包括最大、最小和减法操作，与SP算法的校验节点运算的非线性函数ln(tanh())相比，量化噪声对其影响小。本文针对定点DSP芯片特点，信道观测值和迭代译码中的外信息，都采用16 b的量化精度，有利于优化指令并行度，并可以降低存储器读取、存储延时。[!--empirenews.page--]

3 算法性能仿真测试

为验证本文算法的有效性，结合非规则LDPC码对算法的性能进行了计算机仿真，并利用TI公司的定点DSP对其性能进行了测试。

仿真采用的非规则LDPC码的码长为4.096kb，码率为1/2，变量节点和校验节点的度分布分别为λ(x)=0.27x+0.25x2+0.01x3+0.47x9和ρ(x)=0.47_x6+0.53x7。

据ρ(x)可知，非规则LDPC码校验节点的阶数为7和8，通过计算机仿真得到的最优偏移因子分别为β7=0.45，β8=O.60。

图2给出了不同迭代次数下S-SP译码算法和SP算法的性能比较。可以看出，在AWGN信道下，S-SP算法仍可以有效地降低迭代译码次数，或者说在相同的有限迭代译码次数下，尤其是迭代次数为10次和20次时，性能有明显改善;但是，S-SP算法的缺点是有较高的误码平台。

图3给出了不同迭代次数下，S-MMS算法和SP算法的性能比较。可以看出，S-MMS算法误码平台降低，译码门限略高于SP算法，在迭代次数较小时，性能仍有明显改善。当迭代次数为20，Eb/No较小时，S-MMS算法与SP算法相比性能略有恶化，但Eb/No较大时，性能有明显改善，且误码平台降低，例如误比特率Pe为10-5时，信噪比改善约0.1 dB。在误码率10-6时，信噪比改善约0.25 dB。当迭代次数为50，Eb/No较小时，译码门限恶化约0.15 dB，Eb/No较大时，性能仍有所改善，误码平台降低。

综合比较图2和图3，S-MMS算法和S-SP算法相比，Eb/No较小时，译码门限恶化约为0.1～0.2 dB，Eb/No较大时，例如在误比特率Pe为10-6时，性能仍有所改善。考虑到一般通信系统要求译码后的误码率低于10-5，S-MMS算法在Eb/No较小时的性能恶化对其应用影响不大，适合实际应用。

图4给出了不同迭代次数下，利用TI公司的DSP芯片TMS320C6416T实现的采用量化SMMS算法的译码器的仿真测试性能和未量化S-MMS算法的比较。可以看出，定点DSP芯片上实现的S-MMS算法和未量化的算法性能几乎完全一致，进一步说明了本算法利用DSP芯片实现的有效性。DSP芯片实现的译码器的具体性能见表1。