LDPC码译码算法及性能分析

现代电子技术ModernElectronicsTechnique2014年1月1日第37卷第1期Jan.2014Vol.37No.1

0引言信道编译码技术可以检测并且纠正信号在传输过程中引入的错误，能够保证数据进行可靠的传输[1]。LDPC码的校验矩阵具有稀疏的特性，因此存在高效的译码算法，其纠错能力非常强。1981年，Tanner提出了基于图模型描述码字的概念，将LDPC码的校验矩阵对应到Tanner图的双向二部图上。采用Tanner图构造的LDPC码，通过并行译码可大大降低译码复杂度。Mack⁃ay和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码校验LDPC码译码算法及性能分析李秀花1，2，高永安2，马雯2（1.杭州电子科技大学电子信息学院，浙江杭州310018；2.中国电子科技集团公司第五十研究所，上海200331）摘要：为了进一步降低低密度奇偶校验（LDPC）码译码算法的复杂度，基于经典置信传播（BP）译码算法，给出了对数域迭代后验概率对数似然比（APPLLR）算法。通过概率域的和积算法（SPA）和对数域的迭代APPLLR算法的性能仿真及分析可见，迭代APPLLR算法能以较小的性能损失换取复杂度的大幅降低。进一步选用迭代APPLLR算法，结合不同地形条件下的VHF频段信道模型，仿真了LDPC码编译码系统的性能。理论分析及仿真结果均表明，基于迭代APPLLR算法的LDPC码，实现简单，性能优异，具有良好的工程应用前景。关键词：LDPC码；迭代APPLLR；和积算法；VHF频段中图分类号：TN91⁃34文献标识码：A文章编号：1004⁃373X（2014）01⁃0001⁃04DecodingalgorithmandperformanceanalysisofLDPCcodesLIXiu⁃hua1，2，GAOYong⁃an2，MAWen2（1.SchoolofElectronicsInformation，HangzhouDianziUniversity，Hangzhou310018，China；2.No.50ResearchInstituteofChinaElectronicsTechnologyGroupCorporation，Shanghai200331，China）Abstract：Inordertofurtherreducethedecodingalgorithmcomplexityoflowdensityparitycheckcode（LDPC），aposteri⁃oriprobabilityloglikelihoodratio（APPLLR）algorithminthelogdomainisgiven，whichisbasedontheclassicalbeliefpropa⁃gation（BP）decodingalgorithm.Throughtheperformancesimulationandanalysisofsumproductalgorithm（SPA）intheproba⁃bilitydomainanditerativeAPPLLRalgorithminthelogdomain，itisshownthattheiterativeAPPLLRalgorithmcouldex⁃changealargereduceincomplexitywithlessperformanceloss.ByusingiterativeAPPLLRalgorithm，incombinationwithVHFbandchannelmodelindifferentterrainconditions，theperformanceofLDPCencodeanddecodesystemissimulated.Theo⁃reticalanalysisandsimulationresultsshowthattheLDPCcodebasedoniterativeAPPLLRalgorithmiseasytorealizeandhasexcellentperformanceandgoodprospectofengineeringapplication.Keywords：LDPCcode；iterativeAPPLLR；SPA；VHFband收稿日期：2013⁃09⁃16基金项目：国家国防科工局科研项目（B12020090）1

Copyright©博看网 www.bookan.com.cn. All Rights Reserved.现代电子技术2014年第37卷矩阵的一般步骤为：先生成一个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），再进行传递，这样就将大量乘法运算变为加法运算，大大简化了译码复杂度，利于硬件实现。下面重点介绍对数域迭代APPLLR译码算法。2.1迭代APPLLR译码算法的变量定义对于(N,K)LDPC码，定义变量U取值为0和1时的对数似然比（LLR）为：L()Udef=logP(U=0)P(U=1)（1）设发端发送的码字为u=[u1,u2,…,uN]，接收码字为y=[y1,y2,…,yN]，由此可以得出在迭代中传递的校验节点和信息节点的软信息为：λmn(un)def=log(qmn(0)qmn(1))（2）Λmn(un)def=log(rmn(0)rmn(1))（3）2.2迭代APPLLR译码算法迭代APPLLR译码算法的迭代过程如下：（1）初始化：设每个变量节点n的软信息为：L(un)=ln{P(un=0|yn)P(un=1|yn}（4）对于矩阵中H(m,n)=1，相应的变量节点的软信息初始化为信道输出的软信息，即λmn(un)=L(un)，Λmn(un)=0。（2）校验节点更新：根据每个变量节点n，向与该变量节点相连的所有校验节点传递更新的软信息，计算校验节点信息：Λmn()un=2tanh-1ìíîüýþ∏n′∈N()m\ntanhéëêùûúλmn′æèçöø÷un′2（5）（3）变量节点更新：根据每个校验节点m，向与该校验节点相连的所有变量节点传递更新的软信息：λmn(un)=L(un)+∑m′∈M(n)\mΛm′n(un)（6）对变量节点n进行判决时，变量节点软信息应为：λn(un)=L(un)+∑m∈M(n)Λmn(un)（7）（4）判决：当λn(un)0，则ûn=0，否则ûn=1，此时判决出的码为：û={û1,û2,…,ûN}。最后根据校验矩阵来判断所译出的码字是否正确。如果ûHT=0，那么译码正确，此时，停止迭代；否则继续迭代进行译码，直到迭代次数达到所设定的最大次数。如果此时仍未正确译码，则译码失败。由以上所述可见，在变量节点更新时只有加法运算，但是还可以再进一步降低算法的实现复杂度。采用迭代APPLLR算法，将LLRBP算法中的λn(un)代替λmn′()un′参与校验信息的迭代。即λn(un)不仅用于硬判决，还用于校验信息的更新。这样所传递的变量消息之间便引进了相关性，传递的变量消息就不再是外部消息，仅仅需要计算和存储一个变量消息的数值，可以大大地降低算法的复杂度。3LDPC码在高斯信道下不同译码算法的仿真结果和分析基于Matlab按照上述的编译码方法，在高斯信道下分别对LDPC码概率域的SPA和对数域的迭代APPLLR译码算法进行了误码性能仿真。然后由所得到的性能仿真图形进行分析比较。3.1概率域的SPA的仿真结果和分析高斯信道下，用BPSK调制，采用概率域的迭代译码算法，迭代次数为20，该程序的优点是译码效率高，其关键地方利用了LOG函数，提高了译码效率。相同码率均为12，码长分别为36，256，512，用概率域的迭2

Copyright©博看网 www.bookan.com.cn. All Rights Reserved.第1期李秀花，等：LDPC码译码算法及性能分析代译码算法时的编译码系统的误码率随信噪比变化的曲线如图2所示。图2SPA算法在不同码长下的性能由图2可见，译码前的误码率最高，采用概率域的迭代译码算法后，误码率大幅度降低，译码性能较好。码长为512的LDPC码纠错性能最好，码长为36的LDPC码纠错性能最差。由此可得：在相同码率下，随着码长的增加，LDPC码的纠错性能逐渐改善。3.2迭代APPLLR译码算法的仿真结果和分析高斯信道下，用BPSK调制，采用对数域的迭代译码算法，迭代次数为10，可以设置误码码字的最大数量来计算每个信噪比点，程序简明了，容易理解，而且译码效率非常高。相同码率为1/2，码长分别为36、256、512，用对数域的迭代APPLLR译码算法时的编译码系统的误码率随信噪比变化的曲线如图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）的时延及功率Group123时延/ns05601180相对功率/dB0-18.2-25.5表2城市（30~47.4MHz）的时延及功率Group1234时延/ns05109701430相对功率/dB0-5.2-9.2-12.13