2码出特

LDPC码译码算法及性能分析

李秀花;高永安;马雯

【摘要】Inordertofurtherreducethedecodingalgorithmcomplexityof

lowdensityparitycheckcode(LDPC),aposteri-oriprobabilityloglikelihood

ratio(APPLLR)algorithminthelogdomainisgiven,whichisbadonthe

classicalbeliefpropa-gation(BP)hthe

performancesimulationandanalysisofsumproductalgorithm(SPA)inthe

proba-bilitydomainanditerativeAPPLLRalgorithminthelogdomain,itis

shownthattheiterativeAPPLLRalgorithmcouldex-changealargereduce

giterativeAPPLLR

algorithm,incombinationwithVHFbandchannelmodelindifferentterrain

conditions,theperformanceofLDPCencodeanddecodesystemis

-reticalanalysisandsimulationresultsshowthattheLDPC

codebadoniterativeAPPLLRalgorithmiasytorealizeandhas

excellentperformanceandgoodprospectofengineeringapplication.%为

了进一步降低低密度奇偶校验（LDPC）码译码算法的复杂度，基于经典置信传播

（BP）译码算法，给出了对数域迭代后验概率对数似然比（APPLLR）算法。通

过概率域的和积算法（SPA）和对数域的迭代APPLLR算法的性能仿真及分析可

见，迭代APPLLR算法能以较小的性能损失换取复杂度的大幅降低。进一步选用

迭代APPLLR算法，结合不同地形条件下的VHF频段信道模型，仿真了LDPC码

编译码系统的性能。理论分析及仿真结果均表明，基于迭代APPLLR算法的

LDPC码，实现简单，性能优异，具有良好的工程应用前景。

【期刊名称】《现代电子技术》

【年(卷),期】2014(000)001

【总页数】4页(P1-4)

【关键词】LDPC码;迭代APPLLR;和积算法;VHF频段

【作者】李秀花;高永安;马雯

【作者单位】杭州电子科技大学电子信息学院，浙江杭州310018;中国电子科技

集团公司第五十研究所，上海200331;中国电子科技集团公司第五十研究所，上

海200331;中国电子科技集团公司第五十研究所，上海200331

【正文语种】中文

【中图分类】TN91-34

0引言

信道编译码技术可以检测并且纠正信号在传输过程中引入的错误，能够保证数据进

行可靠的传输[1]。LDPC码的校验矩阵具有稀疏的特性，因此存在高效的译码算

法，其纠错能力非常强。1981年，Tanner提出了基于图模型描述码字的概念，

将LDPC码的校验矩阵对应到Tanner图的双向二部图上。采用Tanner图构造的

LDPC码，通过并行译码可大大降低译码复杂度。Mackay和Neal利用随机构造

的Tanner图研究了LDPC码的性能，发现采用和积算法（SPA）的LDPC码具有

优异的译码性能，在长码时甚至超过了Turbo码[2]。本文采用Mackay基于二分

图提出的改进方案构造LDPC码的校验矩阵。基于置信传播（BP）算法，给出了

一种简化的BP算法——对数域迭代APPLLR算法，复杂度大大降低。目前，

LDPC码是最有希望在广泛的信道范围取得香农容量的误差纠正技术[3]，在保证

LDPC码纠错性能的前提下，降低编译码器实现的复杂度是研究的重点，引发了信

道编码界的研究热潮。

1LDPC码编码

LDPC码是一种性能非常接近香农极限的“好”码，它是惟一用校验矩阵来表示的

线性分组码。LDPC码的编码主要分两步进行，首先构造奇偶校验矩阵，然后是基

于奇偶校验矩阵的编码算法。

1.1校验矩阵的构造

根据式子n*j=m*k可知，规则的LDPC码(n,j,k)，当参数n,j,k确定后，可以得到

校验方程的数目m，则校验矩阵H的大小就可以定为m×n。构造LDPC码校验

矩阵的一般步骤为：先生成一个m行n列的全0矩阵，然后随机地将每列中的j

个0换成1，每行中的k个0换成1。但在随机置l的过程中，必须避免出现长度

为4的环[4]。如果最小环长为4，在迭代中非常容易造成错误信息的扩散传播，

从而导致译码性能的下降[5]。

Mackay为了消除校验矩阵中长度为4的环，基于Tanner图提出了改进的构造方

案。采取的准则是：在构造时必须保证任意两列间的交叠重量不超过1。本文采用

的是Mackay的1A构造方法，按照此方法构造的一个LDPC码（3，6）码如图

1所示。

图1Mackay的1A构造方法

Mackay的1A构造方法是最基本的一种构造方法，它要求保证固定列重为γ，而

行重尽可能均匀的保持为ρ。利用Mackay构造方法得到的LDPC码距离特性很

好，且没有短环。

1.2基于奇偶校验矩阵的编码算法

LDPC码的直接编码方法就是利用高斯消去法，产生一个下三角矩阵，然后进一步

初等变换得到右边单位阵形式H=[P|I]，由G=[I|P]得到生成矩阵，再利用信息码

元向量u和生成矩阵G相乘可得到完整码字C，即C=M*G直接编码[5]。

2LDPC码译码[4，6-7]

BP算法是在Gallager提出的概率译码算法基础上发展而来的。BP算法每次迭代

包括2步：变量节点的处理和校验节点的处理。概率域就是在节点间传递的是概

率信息，采用很多乘法运算，运算量大；而对数域的和积算法实现是将概率值通过

对数似然比变化为软信息值（LLR），再进行传递，这样就将大量乘法运算变为加

法运算，大大简化了译码复杂度，利于硬件实现。下面重点介绍对数域迭代APP

LLR译码算法。

2.1迭代APPLLR译码算法的变量定义

对于(N,K)LDPC码，定义变量U取值为0和1时的对数似然比（LLR）为：

设发端发送的码字为u=[u1,u2,…,uN]，接收码字为y=[y1,y2,…,yN]，由此可以得

出在迭代中传递的校验节点和信息节点的软信息为：

2.2迭代APPLLR译码算法

迭代APPLLR译码算法的迭代过程如下：

（1）初始化：设每个变量节点n的软信息为：

对于矩阵中H(m,n)=1，相应的变量节点的软信息初始化为信道输出的软信息，即

λmn(un)=L(un)，Λmn(un)=0。

（2）校验节点更新：根据每个变量节点n，向与该变量节点相连的所有校验节点

传递更新的软信息，计算校验节点信息：

（3）变量节点更新：根据每个校验节点m，向与该校验节点相连的所有变量节点

传递更新的软信息：

对变量节点n进行判决时，变量节点软信息应为：

（4）判决：当λn(un)≥0，则n=0，否则n=1，此时判决出的码为：={1,2,…,N}。

最后根据校验矩阵来判断所译出的码字是否正确。如果HT=0，那么译码正确，此

时，停止迭代；否则继续迭代进行译码，直到迭代次数达到所设定的最大次数。如

果此时仍未正确译码，则译码失败。

由以上所述可见，在变量节点更新时只有加法运算，但是还可以再进一步降低算法

的实现复杂度。采用迭代APPLLR算法，将LLRBP算法中的λn(un)代替λmn′(u

n′)参与校验信息的迭代。即λn(un)不仅用于硬判决，还用于校验信息的更新。这

样所传递的变量消息之间便引进了相关性，传递的变量消息就不再是外部消息，仅

仅需要计算和存储一个变量消息的数值，可以大大地降低算法的复杂度。

3LDPC码在高斯信道下不同译码算法的仿真结果和分析

基于Matlab按照上述的编译码方法，在高斯信道下分别对LDPC码概率域的

SPA和对数域的迭代APPLLR译码算法进行了误码性能仿真。然后由所得到的性

能仿真图形进行分析比较。

3.1概率域的SPA的仿真结果和分析

高斯信道下，用BPSK调制，采用概率域的迭代译码算法，迭代次数为20，该程

序的优点是译码效率高，其关键地方利用了LOG函数，提高了译码效率。相同码

率均为，码长分别为36，256，512，用概率域的迭代译码算法时的编译码系统的

误码率随信噪比变化的曲线如图2所示。

图2SPA算法在不同码长下的性能

由图2可见，译码前的误码率最高，采用概率域的迭代译码算法后，误码率大幅

度降低，译码性能较好。码长为512的LDPC码纠错性能最好，码长为36的

LDPC码纠错性能最差。由此可得：在相同码率下，随着码长的增加，LDPC码的

纠错性能逐渐改善。

3.2迭代APPLLR译码算法的仿真结果和分析

高斯信道下，用BPSK调制，采用对数域的迭代译码算法，迭代次数为10，可以

设置误码码字的最大数量来计算每个信噪比点，程序简明了，容易理解，而且译码

效率非常高。相同码率为1/2，码长分别为36、256、512，用对数域的迭代APP

LLR译码算法时的编译码系统的误码率随信噪比变化的曲线如图3所示。

图3迭代APPLLR算法在不同码长时的性能仿真

由图3可见，码长为512的LDPC码纠错性能最好，码长为36的LDPC码纠错

性能最差。即在相同码率下，随着码长的增加，LDPC码的纠错性能逐渐改善。

3.3概率域的SPA和对数域的迭代APPLLR译码算法的误码性能比较及分析

高斯信道下，用BPSK调制，分别对码率为1/2，码长为256的LDPC码概率域

的SPA和对数域的迭代APPLLR译码算法的性能比较，如图4所示。

图4LDPC码概率域与对数域译码算法性能仿真

由图4可见，概率域的SPA算法复杂，需耗费较多的硬件资源和时间，仿真性能

略好；对数域的迭代APPLLR算法将大量乘法运算变为加法运算，大大简化了译

码复杂度，算法收敛所需的迭代次数减少一半，译码器的延时也比较小，更利于硬

件实现。对数域译码算法运算量的下降是以牺牲一部分的性能为代价的，在复杂度

降低的同时，抗干扰能力也在下降，但性能的恶化并不大。

4LDPC码在VHF频段信道下的仿真结果和分析[8-10]

VHF频段小尺度模型信道的仿真场景为乡村、城市、沿海、郊区。所仿真的信道

基本上是相关的，即是平稳衰落过程。其中相关时间是由时延相关时间（单位：

ns）和移动速度来计算。一般情况下，将VHF频段划分为三个子频段：高频段

（67.3～108MHz）、中频段（47.4～67.3MHz）、低频段（30～47.4MHz）。

本文只对低频段信道进行仿真，为了针对更恶劣的情况，在瑞利多径衰落信道下进

行仿真，在四种不同的场景下的时延及功率如表1～表4所示。

表1乡村（30～47.4MHz）的时延及功率Group相对功率/dB0-18.2-25.512

3时延/ns05601180

表2城市（30～47.4MHz）的时延及功率Group1234时延/ns

***********相对功率/dB0-5.2-9.2-12.1

表3沿海（30～47.4MHz）的时延及功率Group123时延/ns09101480相对

功率/dB0-15.0-18.9

表4郊区（30～47.4MHz）的时延及功率Group123时延/ns010702260相

对功率/dB0-16.9-21.0

LDPC码在瑞利多径衰落信道（低频）下，用BPSK调制，采用对数域的迭代APP

LLR译码算法进行性能仿真，码率为1/2，码长为256的LDPC码的编译码系统

分别在乡村、城市、沿海和郊区四种不同场景的误码率随信噪比变化的曲线，如图

5所示。

图5VHF频段信道下四种场景的性能仿真

由图5可见，LDPC码在比高斯信道更加恶劣的瑞利信道下，其误码率随信噪比变

化的曲线呈下降的趋势。LDPC码在信道条件相对较好的乡村场景下的误码性能最

好，在信道条件最恶劣的城市场景下的误码性能最差。由此可以得到，其误码性能

与时延、功率及四种场景的环境、地形等因素有着密切的关系。时延越小，功率越

小，地形越平坦开阔，障碍物越少，LDPC码的纠错性能越好。即LDPC码随着信

道条件恶劣程度的增加，其译码性能也在逐渐降低。

5结语

信道编译码技术已成为现代通信系统不可缺少的关键技术。基于图模型的LDPC

码使人们以较低的复杂度实现了可靠通信，对LDPC码的研究不仅具有重要的学

术价值和理论指导意义，更具有强烈的应用背景及十分显著的经济效益。LDPC码

是近年来信道编码领域一个里程碑式的进展，优异的纠错性能和自然并行的译码算

法使得它在多个国际性通信标准中得到应用。通过对高斯信道和VHF频段信道模

型的误码性能仿真可见，基于迭代APPLLR算法的LDPC码，复杂度大大降低，

利于硬件实现，纠错性能优异，具有良好的工程应用前景。

参考文献

[1]魏瑞刚，陈晖，邱金蕙.高速数据传输中的LDPC码译码算法研究[J].无线电工程，

2011（3）：20-22.

[2]王琳，徐位凯.高效信道编译码技术及应用[M].北京：人民邮电出版社，2007.

[3]MACKAYDJC，annonlimitperformanceoflow

densityparitycheckcodes[J].ElectronicLetters，1996，33（6）：457-458.

[4]袁东风，张海刚.LDPC码理论与应用[M].北京：人民邮电出版社，2008.

[5]张仲明.高速数传中LDPC码关键技术研究[D].北京：国防科学技术研究生院，

2009.

[6]贺鹤云.LDPC码基础与应用[M].北京：人民邮电出版社，2009.

[7]范建晓.高效的LDPC译码算法[D].北京：北京邮电大学，2010.

[8]BROWNES，CHANDLERSAG，ementoftimedelay

spreadinSierraLeone[C]//Proceedingsof19917thConerenceonAntennas

，USA：ICAP，1991：961-964.

[9]VIGNERONPJ，ationmodelsformobileterrestrial

VHFcommunications[C]//Proceedingsof2008IEEEMilitary

go，CA：IEEE，2008：1-7.

[10]XIAOCS，ZHENGYR，ticalsimulationmodelsfor

RayleighandRicianfading[C]//Proceedingsof2003IEEEInternational

age，Alaska：IEEE，2003：3524-

3529.

[11]袁瑞佳.LDPC码的高效编译码实现技术研究[D].西安：西安电子科技大学，

2012.