一种基于最小和译码框架的动态偏移补偿方法

摘要

本发明公开了一种基于最小和译码框架的动态偏移补偿方法，以tanner图上迭代运行的置信传播(BP)作为LDPC的译码方法；LDPC为低密度奇偶校验码；以m表示Tanner图中校验节点的索引，以n表示变量节点；在校验节点阶段，基于SPA(和积译码算法)的译码通过下式来计算和更新第i次循环时的外部信息该基于最小和译码框架的动态偏移补偿方法对信息阈值的鲁棒性更好，从而更有利于硬件实现。

权利要求

1.一种基于最小和译码框架的动态偏移补偿方法，其特征在于，以tanner图上迭代运行的置信传播(BP)作为LDPC的译码方法；LDPC为低密度奇偶校验码；

以m表示Tanner图中校验节点的索引，以n表示变量节点；

在校验节点阶段，基于SPA和积译码算法的译码通过下式来计算和更新第i次循环时的外部信息

其中， 且β0表示动态偏移值，有sgn(*)为符号函数，max(*)为取最大值函数，min(*)为取最小值函数，|*|为取绝对值函数；

Lj为 为第i‑1次迭代时变量节点j上更新的并将传递到校验节点m上的信息；

Lmin是指所有Lj的绝对值中的最小值；

式中， 表示除变量节点n之外的 的子集， 表示与校验节点m相链接的变量节点集合。

2.根据权利要求1所述的基于最小和译码框架的动态偏移补偿方法，其特征在于，β0的计算通过查表法或基于分段线性函数逼近法来实现。

3.根据权利要求1或2所述的基于最小和译码框架的动态偏移补偿方法，其特征在于，变量节点n的信道可靠性由输入值的初始化：假设变量节点n的信道可靠性由输入值以log‑likelihood rations(LLR)的形式初始化，并标记为 代表LDPC码的长度，即{0...N‑1}代表LDPC码的所有变量节点集合。

说明书

一种基于最小和译码框架的动态偏移补偿方法

技术领域

[0001] 本发明涉及一种基于最小和译码框架的动态偏移补偿方法。

背景技术

[0002] 众所周知，tanner图上迭代运行的置信传播(Belief Propagation，BP)是低密度奇偶校验(LowDensity ParityCheck，LDPC)码最突出的译码方法。对于每次迭代，BP译码主
要包括两个阶段的更新，校验节点阶段和变量节点阶段。著名的和积算法被认为是性能最
好的BP译码算法，即校验节点更新阶段的乘积计算和变量节点更新阶段的求和运算，但由
于和积算法在校验节点更新阶段的高计算复杂度问题其在硬件上很难实现。

[0003] 在校验节点更新阶段，不同的算法会显著影响译码性能。对数域和积算法(log‑SPA)与和积算法的译码性能等价，复杂度更低。然而，由于存在数值饱和问题，对数和积算
法对信息阈值及其精度都有严重的敏感性。因此，对数域和积算法的硬件实现仍然是很困
难的。最小和算法(Min Sum Algorithm，MSA)采用最小值运算来估计校验节点更新阶段所
需计算的信息，这是一种简化的方法，大大降低了译码的复杂度。然而，由于在校验节点更
新阶段对所需计算信息的过高估计，MSA的这种近似会明显地降低误码率(BER)译码性能。
随后，有文献提出了偏移最小和算法(Offset MSA，OMSA)和归一化最小和(Normalized 
MSA,NMSA)，以提高MSA的误码性能。这两种算法分别引入一个恒定偏移量和一个比例因子
来补偿对MSA中校验节点输出信息的过高估计。之后，一些OMSA和NMSA的改进版本也被提
出，例如自适应OMSA和自适应NMSA，以进一步提高比特误码率(Bit Error Rate,BER)性能。
这些方法本质上是在MSA框架下构造出来的，并且偏移量和归一化因子等参数是基于密度
演化(Density Evolution,DE)等方法的大量模拟结果。因此，尽管它们具有硬件友好性，但
是对于不同的LDPC码都需要寻找其最优的参数才能保证最优性能。另外，这些传统的MSA类
算法的BER性能都是是以大量的迭代次数为前提获得验证的，并没有充分考虑收敛速度的
增益。

[0004] 近年来，校验节点中采取不同算法对LDPC译码收敛速度的影响引起了众多研究者的关注。有文献引入了机器学习来优化偏移量或归一化因子，并且它们的值会随着迭代而
变化。尽管其改善了BER性能和收敛速度增益，但是该方法的主要问题是参数众多，从而导
致了应用方面的局限性。

[0005] 因此，有必要设计一种基于最小和译码框架的动态偏移补偿方法。

发明内容

[0006] 本发明所要解决的技术问题是提供一种基于最小和译码框架的动态偏移补偿方法，该基于最小和译码框架的动态偏移补偿方法易于实施，且对信息阈值的鲁棒性更好，从
而更有利于硬件实现。

[0007] 发明的技术解决方案如下：

[0008] 一种基于最小和译码框架的动态偏移补偿方法，以tanner图上迭代运行的置信传播(BP)作为LDPC的译码方法；LDPC为低密度奇偶校验码；

[0009] 以m表示Tanner图中校验节点的索引，以n表示变量节点；

[0010] 在校验节点阶段，基于SPA(和积译码算法)的译码通过下式来计算和更新第i次循环时的

[0011] 外部信息

[0012]

[0013] 具体说明：“Lj为 为第i‑1次迭代时变量节点j上更新的并将传递到校验节点m上的信息；”等号前上标括号中的i表示第i次循环的意思，意思是第i次循环的外部信
息。j是变量节点的索引的意思。

[0014] 公式也可以采用这个表达方式：

[0015] 其中， 且β0表示动态偏移值，有

[0016] sgn(*)为符号函数，max(*)为取最大值函数，min(*)为取最小值函数，|*|为取绝对值函数；；

[0017] Lj为 为第i‑1次迭代时变量节点j上更新的并将传递到校验节点m上的信息；Lmin是指所有Lj的绝对值中的最小值；

[0018] 式中， 表示除变量节点n之外的 的子集， 表示与校验节点m相链接的变量节点集合。

[0019] β0的计算通过查表法或基于分段线性函数逼近法来实现。

[0020] 变量节点n的信道可靠性由输入值的初始化：

[0021] 假设变量节点n的信道可靠性由输入值以log‑likelihood rations(LLR)的形式初始化，并标记为 指的是来自信道的变量节点n的LLR初始值， 这个公式表示在
计算从校验节点m传播给变量节点n的外部信息时是由与校验节点m连接的所有除节点n外
的所有变量节点的信息来决定。

[0022] 有益效果：

[0023] 本发明基于LDPC码的置信传播(BP)译码，对其校验节点的更新过程展开研究，利用双曲正切函数的等价变换，提出了一种基于最小和译码框架的动态偏移补偿方法。仿真
结果表明，与传统纠错性能最好但硬件实现效果不佳的对数域和积算法(log Sum Product 
Algorithm,log‑SPA)相比，本发明所提出的算法在误码率和收敛速度方面的性能损失几乎
可以忽略不计。更重要的是，相对于log‑SPA算法，该方法对信息阈值的鲁棒性更好，从而更
有利于硬件实现。

[0024] 本发明提出了一种新的名为动态偏移最小和(Dynamic OMSA,DOMSA)的MSA扩展算法，它通过引入接近最优的动态偏移校正因子来补偿MSA中校验节点端的输出。根据实验结
果，DOMSA算法在BER性能以及收敛速度上，近乎达到了SPA算法的性能极限。最重要的是，与
log‑SPA不同，DOMSA对信息大小及其精度的阈值不敏感，这更符合实际硬件实现需求。

附图说明

[0025] 图1为(64800,32400)DVB‑S2LDPC码的误码率性能比较示意图；

[0026] 图2为(64800,32400)DVB‑S2 LDPC码的误码率性能比较的收敛性能对比示意图。

具体实施方式

[0027] 以下将结合附图和具体实施例对本发明做进一步详细说明：

[0028] 实施例1：

[0029] 符号说明：

[0030] 本发明将使用以下符号。

[0031] n，j，nk：Tanner图中变量节点的索引

[0032] m:Tanner图中校验节点的索引

[0033] 第i次迭代时校验节点m上更新的并将传递到变量节点n上的外部信息

[0034] 第ith迭代时变量节点j上更新的并将传递到校验节点m上的信息

[0035] 与校验节点m相链接的变量节点集合

[0036] 除变量节点n之外的 的子集

[0037] M(n)：与变量节点n相链接的校验节点集合

[0038] card(·):一个集合的元素数量

[0039] 校验节点m的行重,亦写成

[0040] 与校验节点m相链接的变量节点向量。

[0041] 基于SPA的BP译码研究

[0042] 在LDPC码中，其奇偶校验矩阵的行和列与Tanner图中校验节点和变量节点有关。如果变量节点n受到了校验节点m的校验约束，那么在Tanner图上，变量节点n与校验节点m
会有一条相连的边。基于BP算法的LDPC译码器采用了一种迭代的两阶段消息传递方案，包
括校验节点阶段和变量节点阶段的更新。在两个阶段的更新过程中，消息沿着tanner图中
校验节点和变量节点之间的连线边缘进行迭代传递。

[0043] 假设变量节点n的信道可靠性由输入值以log‑likelihood rations(LLR)的形式初始化，并标记为 n∈{0...N‑1}，N代表LDPC码的长度，即{0...N‑1}代表LDPC码的所有
变量节点集合； 表示LDPC BP译码时需要使用到的变量节点的初始值，它会被用在下文公
式(2)和(1)、(4)、(6)中，如公式(2)中i＝1时的变量节点更新时，这时的 同样公
式(1)、(4)、(6)中计算i＝1时的外部信息时需要用到 在校验节点阶段，基于SPA
的译码通过式(1)来计算和更新外部信息

[0044]

[0045] 这一步骤组合了所有在上一次迭代过程中，变量节点所更新的输入LLR信息

[0046] 在变量节点端，校验节点计算过的信息 将继续被传递到变量节点，然后通过(2)的求和运算来更新变量节点的信息 在(3)中， 表示在变量节点n中更新并在下
一次迭代时被传递到校验节点m的LLR信息。

[0047]

[0048]

[0049] 这样的两阶段过程会一直迭代重复，直到更新的变量值趋于收敛。

[0050] SPA的扩展算法

[0051] SPA是一个应用于LDPC码的最优BP算法。但是由于在校验节点阶段的高计算复杂度，它很难在硬件设备中实现。现有几种主要的SPA扩展算法，他们与SPA的步骤相同，但校
验节点阶段中公式(1)的计算有所不同。

[0052] (1)Log‑SPA

[0053] Log‑SPA作用于对数域，其中SPA所需的乘法运算被诸如(4)之类的加法运算代替。

[0054]

[0055] 其中sign(x)表示x的符号，公式φ(x)可以表示为：

[0056]

[0057] φ(x)是一个递减函数，且φ(x)>0，它决定了 的幅值。Log‑SPA等效于SPA算法，但复杂度较低。然而，由于用有限精度计算时，(5)中双曲正切函数的数值饱和问题，
log‑SPA对信息大小及其精度的阈值具有严重的敏感性。

[0058] (2)最小和算法(MSA)

[0059] 由于公式(4)中双曲正切函数的性质， 的幅值被最小输入信息 所决定，并可以近似为：

[0060]

[0061] 公式(6)便是MSA，它极大地降低了译码的计算复杂度。但是，这种近似可能会大大降低LDPC译码的BER性能。

[0062] 显然，比起公式(4)，(6)中的MSA高估了 的大小。为了消除这样的误差，人们引入了偏移因子β和归一化因子α，分别得到了OMSA和NMSA算法。

[0063] 与MSA相比，OMSA和NMSA在增加少量复杂度的情况下提高了误码率性能。然而，这些因素与LDPC码的许多参数有关，并且通常需要通过对特定码型的广泛仿真来优化。

[0064] 本发明提出的动态偏移最小和算法

[0065] A.提出的算法

[0066] 本发明的主要思想是优化校验节点上如公式(1)所示的外部信息的更新过程。

[0067] 为了简化表示，本发明将(1)中的 表示为Lj。根据双曲正切函数的性质，有：

[0068]

[0069] 以及

[0070]

[0071] 将(9)和(10)代入公式(1)中，本发明可以得到如下表达式，

[0072]

[0073] 公式中，i与j的物理含义不一样。等号前上标括号中的i表示第i次循环的意思，意思是第i次循环的外部信息。j是变量节点的索引的意思。

[0074] 接着，本发明基于多项式乘法准则，并利用指数函数在指数部分小于0时取值逐渐趋于0的特性，将公式(11)进一步的扩展。通过这种方式，公式(11)化简并取主要影响部分
为

[0075]

[0076] 其中， 且

[0077]

[0078] β0是一个动态偏移值，用于补偿基于MSA算法时对于校验节点外部信息的过高估计。这个动态偏移值是在线计算的，并根据输入信息的变化基于公式(13)进行近似计算。公
式(12)和(13)是本发明提出来的DOMSA中最重要的贡献。Algorithm 1总结了所提出的
DOMSA中校验节点更新方法。为了简化Algorithm1的表示，本发明将向量
表示为从第k个变量节点输入给校验节点m的信息，即
且 同理，Algorithm1的输出向量
对应公式(12)，即

[0079] B.数学分析

[0080] 在公式(12)中，对于硬件实现来说最大的计算量在β0中，β0基于公式(13)来计算。观察公式(13)，对数函数的括号内部是一些指数函数的和。显然，有

[0081] Lmin‑|Lj|≤0，andβ0＞0   (14)

[0082] 因此，根据指数函数的性质，本发明知道与(5)中的log‑SPA不同，这些指数函数的实现可以在查找表中得到很好的量化，也可以用分段线性函数逼近。

[0083] 对于公式(13)中的对数函数，它是一个缓慢而逐渐上升的函数。并且满足以下关系：

[0084]

[0085] 例如当 有β0≤ln(19)＝2.94。因此，对数函数也可以用查表法实现，或者基于分段线性函数逼近法来实现。

[0086] 仿真结果

[0087] 为了展现出本发明所提出的DOMSA的应用潜力，研究了第二代卫星数字视频广播标准(DVB‑S2)中，码字长度64800，1/2码率LDPC码的误码率和收敛性能。采用AWGN信道和
BPSK调制方式。此外，本发明将蒙特卡罗实验次数设置为10000。

[0088] 图1展示了当最大迭代次数设置为50和30时，所提出的DOMSA和其他译码算法(SPA、OMSA[6]、ANMSA[7])之间BER性能的比较。对于迭代次数为50的DVB‑S2 LDPC码，本发
‑6 ‑5
明的DOMSA在10 的误码率下比OMSA的性能好0.15dB，在小于10 的特定误码率下比ANMSA
的性能至少提升0.1dB。此外，当最大迭代次数为30次时，DOMSA的译码性能更为突出。此外，
可以观察到，虽然ANMSA在高噪声区域比OMSA有更好的性能，但是它表现出严重的错误平层
问题，而本发明所提出的DOMSA并不存在这个问题。

[0089] 图2探讨了在4种Eb/No情况下，OMSA、SPA和DOMSA在迭代次数增加时的收敛性能。结果表明，在每种Eb/No情况下，DOMSA的收敛速度都比OMSA快，且与SPA的收敛速度几乎相
同。此外，与DOMSA相比，OMSA在低信噪比(SNR)下的收敛速度要慢得多，例如Eb/No＝1dB。即
使在高信噪比(Eb/No＝2dB)下，它仍然低于SPA和DOMSA。

[0090] 表1总结了当译码的最大迭代次数设置为50时，SPA、OMSA和DOMSA平均迭代次数。该表再次证明了本发明提出的DOMSA算法在收敛速度上与SPA算法基本相同，且明显快于其
他两种算法。

[0091]

[0092] 表1译码平均循环次数对比(最大循环次数设置为50)

[0093] 总结

[0094] 本发明通过对最小和算法引入一种近似最优的动态偏移补偿方法，提出了一种新的基于BP的LDPC译码算法。从误码率、收敛速度和对信息门限的敏感性三个方面分析了传
统LDPC译码算法的缺陷。同时，基于双曲正切函数的等价变换和多项式乘法准则的应用，推
导了SPA算法在校验节点更新过程的等价表示，并从硬件实现复杂度的角度给出了其近似
表示。结果表明，与传统的MSA译码方案相比，本发明提出的DOMSA译码方案具有更高的误码
率性能和更快的收敛速度，且与SPA和log‑SPA译码的性能基本相同。与log‑SPA不同的是，
根据本发明的数学分析，DOMSA对信息阈值的鲁棒性更好，从而更有利于硬件实现。