一种改进的多元LDPC码译码算法

张福星，许生旺

(北京跟踪与通信技术研究所，北京 100094)



一种改进的多元LDPC码译码算法

张福星，许生旺

(北京跟踪与通信技术研究所，北京 100094)

在多元LDPC码的软判决译码算法中，迭代过程中没有使用判决结果和校验和中隐藏的一些信息，在判决结果中隐藏着稳定性信息，校验和中隐藏着变量节点的可靠度信息。从混合译码算法思路出发，借鉴硬判决译码算法中统计校验和的做法和联合迭代检测译码算法中的反馈调整思想，对FFT-BP译码算法进行了改进。改进算法利用迭代过程中的可靠性和稳定度信息，对由变量节点向校验节点传递的消息向量进行调整以使其提供更多正确信息。仿真结果表明，改进的译码算法在没有增加复杂度的前提下，提升了FFT-BP译码算法的性能，在不同参数设置下，性能改进在0.2 dB左右。

多元LDPC码；FFT-BP译码算法；算法改进

0 引言

Gallager在1963年提出了二元LDPC码概念[1]，Davey和MacKay于1998年引出了多元域上的LDPC码[2]。研究结果表明[3]，在突发噪声信道中，多元LDPC码可以获得更好的性能，当采用中短码长时，多元LDPC码的性能，特别是抗突发误码能力要明显优于二元LDPC码[4]。但是，多元LDPC码的译码复杂度随着多元域阶数的增大而急剧增长[5]，限制了其实际应用。多元LDPC码的推广应用需要寻求复杂度低的译码算法。

多元LDPC码译码算法主要可分为软判决译码算法和硬判决译码算法。软判决译码算法主要有BP、FFT-BP[6-7]和EMS[8]算法等，这些算法均是通过消息向量的迭代进行译码的，其普遍特点是复杂度高，但性能良好。硬判决译码算法由二元LDPC码的大数逻辑译码[9]和比特翻转译码[10]推广而来，这些算法译码复杂度低，但性能有损失。

1 混合译码

在软判决译码算法中，信道接收序列只被检测器用于一次性地提取软译码信息，如图1所示，其中X为发送序列，Y为接收序列，SISO为软输入软输出检测器，U为译码输出的结果。因为SISO检测器生成的概率或者似然比度量，能够包含接收序列中的绝大部分信息。在软译码判决算法中，只利用SISO检测器提取出的信息进行迭代译码。

图1 软判决译码信息提取

软判决译码算法忽略了两部分可利用的信息。一是信号的接收序列本身包含的信息，在检测器中并不能一次提取完毕；二是迭代过程中判决结果也包含着变量节点可靠性和稳定性信息，这一部分信息在迭代中并没有得到利用。

对接收序列只利用一次的问题，在文献[11]中，提出了一种新的对接收序列的处理模式，如图2所示。该处理模式源于硬判决算法，检测器基于最大似然准则对接收序列进行硬判决得到估计序列，不产生任何软信息。估计序列在多元LDPC码的硬译码器中经由码约束关系和消息传递原理得到纠错，同时根据大数逻辑规则产生可靠度向量。译码器将纠错完的序列和可靠度向量反馈给检测器，检测器利用获得的反馈信息对软接收序列进行修正。修正将受到噪声污染而偏离原始发送信号的接收信号逐渐移动到正确的发送星座点上。这种处理模式对接收序列的利用并不仅仅是单次的信息提取，而且是基于判决结果的反馈式的多次修正和信息提取。

图2 一种新的接收序列处理模式

这种新的处理模式将软判决译码算法中的迭代过程引入到硬判决译码算法中，并利用译码获得的信息对译码初始状态进行调整，是一种混合式的译码算法。

对于软判决译码过程中迭代出的结果包含信息未充分利用问题，也可以从混合译码的角度来进行思考。在硬判决译码算法中，如大数逻辑译码算法中，常常通过对判决结果的统计分析，来对码字的可能值进行判断和调整。可以将这种做法迁移到软判决译码算法中，将迭代后的判决结果用于微调译码向量，使迭代结果朝更有利的方向发展。

2 改进思路及算法

2.1 改进思路

将硬判决译码算法中的统计反馈调整思想应用到FFT-BP译码算法中，可以实现码算法性能上的提升。在联合迭代检测译码算法中[12]，2个最重要的译码策略是：

① 利用校验和信息，采用大数逻辑进行统计。大数逻辑是指在校验和提供的变量节点的外部信息中，对应符号出现的次数越多，该变量节点实际为该符号的可能性就越大；

② 利用变量节点的统计信息，对检测器接收端的信息序列进行调整。具体为使用统计获得的软信息，采用反馈的方式，对接收序列进行“去噪化”，使其慢慢移动到实际发送的星座点位置附近。

将这2个策略推广到FFT-BP译码算法中：

① 统计迭代译码的判决结果和其校验和，获得变量节点对应的稳定度信息和可靠度信息。在判决结果稳定的节点中既有保持正确的，也有保持错误的，此时需要利用可靠度信息来加以区分；

② 用获得的译码信息对迭代过程进行反馈调整。可以在保证稳定度和可靠度的前提下，对消息向量进行微调。调整可靠度高的变量节点的概率值，使其在下一次译码迭代时提供更多的正确信息。

在具体实现中，消息向量的调整幅度应与变量节点可靠度和稳定度有关。随着稳定度的逐渐增加，消息向量更确定的保持在正确或错误的状态。此时，引入可靠度对其正确性进行判断，可靠度高的节点，认为其已经稳定在正确的判决值下。

可靠度可采用非法校验值进行衡量[13]。若信道为加性高斯白噪声信道，编码码字为c=[c1c2…cN]，接收端接收信息y=c+n，n为加性噪声，则对y作如式(1)运算。

(1)

I=[(H·y)T(modq)·H](modq)= (φT·H)(modq)。

(2)

非法校验值为零的变量节点可靠程度较高，非法校验值不为零的变量节点可靠程度低。

(3)

在得到变量节点的稳定度和可靠度信息后，对可靠程度高和已稳定的变量节点，可将其视作为已成功译码的变量节点，并进行倾向性的调整。思路是将此变量节点译码结果对应位置的概率值调整为最大值。在改进的译码算法中，调整消息向量Qmn的方式如式(4)和式(5)进行调整的公式为：

Qmn=Qmn*μ，

(4)

(5)

2.2 改进后的译码算法

改进后的FFT-BP译码算法过程为：

(1)初始化

(6)

同时用式(1)计算发送序列每个位置的非法校验，用式(2)初始化非法校验值I。对H(m,n)≠0的位置，译码消息向量初始化为：

(7)

(8)

(9)

(4)判决码元符号

(10)

(5)更新可靠度信息

对当前迭代判决出的结果，用式(2)重新计算此时的非法校验值信息。

(6)更新稳定度信息

(7)更新消息向量

根据计算的非法校验值和统计的变量节点稳定度信息，对相应的消息向量进行调整。如果k(n)>c，且此位置的非法校验值为0，即I=0，则依式(4)和式(5)更新消息向量。μ可根据实际情况进行大小的调整。μ可取为较接近1的值以确保在迭代初期，译码正确与否并不明朗时，对消息向量的调整并不会引入额外的错误。

2.3 复杂度分析

若为q进制的多元LDPC码，校验矩阵大小为M×N，行重为dc，列重为dv，则单次迭代增加的计算量为：

乘法：2MN；

加法：2MN-M-N。

对消息向量进行更新的步骤的计算量与当前迭代中统计出的需要改进的节点数有关，其可能的最大计算量为：

乘法：Ndvq；

加法：Ndv。

改进后的译码算法在单次迭代中增加了计算可靠度和统计稳定度的计算量，可能增加的最大乘法计算量为2MN+Ndvq，最大加法计算量为2MN-N-M+Ndv。虽然单次迭代的计算量有些许线性增加，但随着对消息向量传递的调整改进，译码所需的迭代次数会下降。

3 仿真分析

对提出的改进算法进行仿真验证，所用的仿真码型为Mackay随机构造法构造的码长700的16元规则LDPC码，其行重为6，列重为3，码率为3/7。仿真使用的调制方式为16QAM，信道为AWGN信道，译码的最大迭代次数为20，仿真停止条件为错误100 bit，μ值为调整步长，c为稳定度参数。本文仿真了多种μ值和c值下的性能情况，并进行了综合的比较，仿真结果如图3所示。

图3 改进FFT-BP译码算法性能

从图中可以看出，不同参数下的改进译码算法与原始译码算法相比均有一定的性能提升，性能提升的幅度在0.1～0.2dB左右。

此外，仿真还统计了不同参数下译码算法的平均迭代次数，如表1所示。可以看出，不同参数下改进算法的平均迭代次数与原始译码算法相比，并没有显著变化，即在只增加了计算可靠度和统计稳定度的计算量的条件下，实现了性能的改进。

表1 不同参数下的译码平均迭代次数

4 结束语

从混合译码思路出发，讨论了将硬判决译码思想应用到FFT-BP译码算法中的问题。从大数逻辑译码算法中的统计调整思想出发，将其应用到FFT-BP译码算法中，对FFT-BP译码算法进行了改进。在统计的稳定度信息和计算的可靠度信息的基础上，迭代中改进的译码算法对变量节点的消息向量进行倾向性的调整，使消息向量能够提供更多的正确信息。仿真结果表明，改进的FFT-BP译码算法可以获得更好的性能。

[1] 刘 波,李旭东.LDPC码在深空探测中的应用[J].无线电工程,2009，39(10):13-15.

[2]DaveyD,MacKayD.Low-densityParityCheckCodesoverGF(q)[J].IEEECommunicationsLetters,1998,2(6):165-167.

[3]ChenJ,WangL,LiY.PerformanceComparisonbetweenNon-binaryLDPCCodesandReed-SolomonCodesoverNoiseBurstsChannels[C] ∥ProcICCCAS2005.HongKongIEEEPress，2005:1-4.

[4] 李 丹,白宝明,孙 蓉.多元LDPC码与二元LDPC码的性能比较[J].无线通信技术,2007,16(3)：1-6.

[5]WymeerschH,SteendamH,MoeneclaeyMA.ComputationalComplexityandQuantizationEffectsofDecodingAlgorithmsforNon-binaryLDPCCodes[C]∥IEEE.InternationalConferenceonSpeechandSignalProcessing.Montreal:IEEE,2004:669-672.

[6]SongH，CruzJR.Reduced-complexityDecodingofQ-aryLDPCCodesforMagneticRecording[J].IEEETransMagn,2003,39(3):1081-1087.

[7]BarnaultL,DeclercqD.FastDecodingAlgorithmforLDPCCodesOverGF(2q)[C]∥IEEE.ProceedingofIEEEITW2003.Paris:IEEE，2003:70-73.

[8]DeclercqD,FossorierM.DecodingAlgorithmsforNonBinaryLDPCCodesOverGF(q)[J].IEEETransactiononCommunication，2007,55(4):633-643.

[9]ZhaoD，MaX，ChenC,etal.AlowComplexityDecodingAlgorithmforMajority-logicDecodableNonbinaryLDPCCodes[J].IEEECommun.Lett,2010,14(11):1062-1064.

[10]卢建波.硬判决LDPC译码算法在卫星导航中的应用[J].无线电工程,2012,42(9):38-40.

[11]WangXP,BaiBM,MaX.ALow-complexityJointDetection-decodingAlgorithmforNonbinaryLDPC-codedModulationSystems[C]∥inProc.IEEEIntSympInformTheory,Jun,2010:794-798.

[12]ChenC,HuangQ,ChaoC,etal.TwoLow-complexityReliability-basedMessage-passingAlgorithmsforDecodingNon-binaryLDPCCodes[J].IEEETransactionsonCommunication,2009,57(12):3597-3606.

[13]吴晓丽,孟 涛,李 云,等.一种改进的多进制LDPC码的译码算法[J].空军工程大学学报：自然科学版,2010,11(4):73-77.

Modified FFT-BP Decoding Algorithm of Non-binary LDPC Codes

ZHANG Fu-xing,XU Sheng-wang

(Beijing Institute of Tracking and Telecommunications Technology,Beijing 100094,China)

Some information hidden in the decision results and sum of check equations is not used in soft-decision decoder for non-binary LDPC codes.However,stability and reliability information lies in the iteration results.In this paper,following the clue of hybrid decoding,the ideas in hard-decision decoding algorithm are used to modify the FFT-BP algorithm.In the new decoding algorithm,the stability and reliability information is used,and small adjustments are applied to the iteration results.Simulation results show that the modified FFT-BP algorithm can realize a performance improvement of about 0.2 dB.

non-binary LDPC code;FFT-BP decoding algorithm;modified algorithm

10.3969/j.issn.1003-3114.2016.06.14

张福星，许生旺.一种改进的多元LDPC码译码算法[J].无线电通信技术,2016,42(6):56-58,69.

2016-07-15

张福星(1992—)，男，硕士研究生，主要研究方向：信息与通信系统。许生旺(1963—)，男，研究员，主要研究方向：图像通信。

TN911.2

A

1003-3114(2016)06-56-3