基于Matlab平台的LDPC码快速仿真研究

基于Matlab平台的LDPC码快速仿真研究刘英，张志亮(四川大学锦城学院，四川成都611731)摘要：对提高基于Matlab平台的低密度奇偶校验码的仿真速度进行了研究，为加快仿真速度，编解码核心过程用符合mexFunction格式的C语言编写。并针对快速编码算法及迭代译码算法进行了优化，然后编译成动态链接库文件在M语言中调用。仿真结果表明，优化后的仿真速度相比优化前获得大幅提高，平均提升了57倍。关键词：低密度奇偶校验码；Matlab；快速仿真；快速编码算法中图分类号：TN91li22文献标识码：A文章编号：1004373X(20lO)090121一02FastLDPCCodecSimulationBasedonMatlabPlatformLIUYing，ZHANGZhiliang(JinehengCollege，$ichuanUniversityChengdu611731China)Abstract：AcceleratingLDPCeodecsimulationonMatlabplatformisstudiedInordertOmakethesimulationrunfaster，thecoreprocessofcodinganddecodingusesClanguagethatconformtOmexFunctionformat，bothfastcodingalgorithmanditerativedecodingalgorithmareoptimized，thencompilesintoadynamic-linklibraryfileinMlanguageThesimulationresultprovesthatthesimulationspeedruns57timesfasterthantheonewithoutoptimizationKeywords：LDPC；Matlab；faStsimulation；fastcodecalgorithmLDPC码是一类可以用非常稀疏的校验矩阵H或二分图来描述的线性分组纠错码L1，在基于置信传播的迭代译码条件下具有逼近Shannon极限的性能z】。LDPC码因优异的性能成为近年信道编码研究的热点，众多学者提出了各自的构造法用于构造各有特色的LDPC码4。在研究LDPC码的过程中，需要对构建的LDPC码进行仿真，获知其在不同信道下的性能。实用的LDPC码往往具有较大规模的校验矩阵，并且对应的生成矩阵不再是稀疏矩阵，按分组码的矩阵相乘方式进行编码运算量较大。在迭代译码过程中，因需要计算二分图上众多节点之间的信息传递，以及进行迭代结束判决，需要进行大量的循环及运算。Matlab平台是进行通信算法仿真的一个良好平台，但LDPC码的编解码涉及到大量的循环及运算，直接用Matlab的M语言实现仿真速度较慢，如何在Matlab平台上实现快速的LDPC码编解码算法，进行快速的LDPC码仿真，具有比较重要的应用意义。1快速编码算法Richardson和Urbanke给出了IDPC快速编码的方法引，对于图1所示的近似下三角形式校验矩阵，相应的码字向量X分成三部分，工=sP。Pz；s为原输入的信息向量；p，P2为校验向量。令西=一ErlB+收稿日期：2009。1221D，设可逆，则pT=一矿1(一lirlA+c)，。可单独计算出G，=矿1(一JiT_1A+C)，G，即为Pt的生成矩阵，然后根据p一G，可求得校验向量P-。再对所有的i1，优一g，从小到大依次利用迭代方程Pz(i)=，rg卜1h&+h；舯。p，(f)+hi,j+，附。p。(i)求j暑1J毒1j；1得P2。图1近似下三角形式校验矩阵实际使用的LDPC码校验矩阵不一定都是直接支持快速编码的近似下三角形式，这可以通过联合可逆行变换算法变换得到j。在实际编码中，先根据校验矩阵计算出G，。，然后利用Matlab的矩阵运算，根据pTG，s可求得校验向量P。Matlab适于作矩阵运算，但因其属于解释性语言，处理循环迭代速度较慢。为提高速度，P。的迭代求解使用C语言进行编写。为使C语言编写的函数可以在Matlab的M语言中调用，C函数需要按照Matlab要求的mexFunction格式进行编写，再在Matlab中使用mex命令，将其编译成动态链接库dll文件供M语12】万方数据言中调用7。因为迭代求解Pz时需要依次使用到H矩阵从第1行开始的，zg行，而H矩阵本身为稀疏矩阵，里面为1的元素很少，为进一步提高速度，减少算法查找非零元素的时间，先将H矩阵的前mg行按行顺序将行中元素1的列位置查找出来，构成一维矩阵序列V，并将其作为参数传递给迭代求解函数。迭代时每求解一个p。校验位，依次取出V序列里的元素，得到对应行中元素1的列位置，然后将该位置的s信息向量位或p，校验向量位进行GF(2)上的模2累加(可用异或实现)，直到取出的列位置到达当前计算的Pz校验位列位置为止，此时的模2累加值即为当前计算的Pz校验位的值，然后开始下一个p。校验位的计算。使用此算法，迭代时无需在整行中查找l的列位置，而直接从y序列中获得对应行中的1的列位置，因而可以减少循环查找次数，提高速度。2基于置信传播的迭代译码算法LDPC码使用基于置信传播的迭代译码算法，这是其性能优异的原因之一8。迭代译码算法过程如图2所示：首先，根据信道接收值y计算每个码元变量的后验概率信息，即厶寻LLR(xjlYj)；在之后的每一轮迭代中，每个校验节点i计算出相应的对数似然信息R。(z)并传递给相邻的变量节点歹；每个变量节点歹也计算出相应的信息Q。(z)并传递给相邻的校验节点i，其中1为迭代次数凹。丑：，Ito(m图2迭代译码算法示意图相应的迭代公式可表示为：rfJ，Z=0Q0(1)一厶+R旬(z一1)，zo(1、IflMO)tanh(Rd(z)2)一Utanh(Q疆(z)2)(2)tJ,kEN(f)每次迭代过后，进行码比特判决，得到x7，若日TX70或者迭代次数到达最大迭代次数则结束，否则再次进行迭代。迭代译码涉及到大量的循环，因此该过程同样用C语言进行编写。在迭代过程当中，需要122查找每个信息节点所连接的校验节点及每个校验节点连接的信息节点，如果每次都根据H矩阵的一行或一列来进行搜索，将会耗费大量的查找时间，所以设计了如下优化的数据结构及实现方法，便于快速查找相连的节点：(1)为便于查找每个信息节点所连接的校验节点，先统计日矩阵每列1的总个数，构成1咒的一维矩阵序列C，然后对整个日矩阵按列顺序将列中元素1的行位置查找出来，构成一维矩阵序列J，其元素个数等于H矩阵中1的总个数，亦即二分图中边的总数。(2)为便于查找每个校验节点所连接的信息节点，先统计H矩阵每行1的总个数，构成1m的一维矩阵序列R，然后对整个H矩阵按行顺序将行中元素1在J的位置查找出来，构成一维矩阵序列K。(3)因为六及Rd(z)，Q口(Z)都只在边上传递，因此只需要根据每条边来计算，而边的总数等于H矩阵里1的总数。为便于计算，j及R“(z)，Q“(Z)都按J中的边顺序排列存储，此时，查找J即可得到信息节点所在的列位置。计算R。(z)的传递时，根据R可知与某校验该节点相连的信息节点的个数，从而在K中取出对应的信息节点在J中的排列位置；计算Q。(z)的传递时，根据C可知与某信息节点相连的校验节点的个数，从而在J中直接取出对应的校验节点。使用这种方法不用每次迭代都去查找H矩阵中的非0元素，提高了运算速度。3仿真上述的优化只是针对数据结构及有效查找节点的优化，并没有改变迭代译码算法本身，在相同输入情况下，优化算法和原始算法两者的译码过程一致。为了验证上述优化算法的速度提升，在AWGN信道上作LDPC编码BPSK调制的仿真，LDPC码使用HuXiao-Yu的PEG方法构造的PEGReg5041008正则码10，译码最大迭代次数设定为50。表1给出了不同信噪比下仿真l000次编译码的平均每次编码译码时间。可见，采用本文的优化数据结构及实现方法，仿真速度平均提高了57倍。裹1不同信嗓比下平均每次编码译码时间(下转第128页)万方数据图8系统程序流程图石油仪器，2002，16(1)36-38E83DALLAS公司DSl8820数据手册M美国；DALLAS公4结语司，200193胡汉才单片机原理及系统设计M北京：清华大学出版利用AT89C51单片机和DSl8820数字温度传感社，2002器可以实现多点温度的检测与控制。系统具有信号数10忠梅单片机的C语言应用程序设计M北京：北京航空字化、硬件简单化和抗干扰能力强等特点，如果与相应航天大学出版社，1997作者简介：王红玲女，1962年出生，河南许昌人，副教授。主要从事电力电子方面的教学与研究工作。(上接第122页)4结语Matlab是一个常用的通信仿真平台，本文对在Matlab平台上实现快速的LDPC码编解码算法，进行快速的LDPC码仿真进行了研究。利用符合Matlab要求的mexFunction格式的C语言改写编解码算法，并优化其中的数据结构及实现方法，大幅提升了仿真速度，减小了仿真所用的时间，对进一步研究不同LDPC码的性能或寻找更好的LDPC码具有较重要的意义。参考文献口GALLAGERGLow-densityparity-checkcodesJIRETransonInformationTheory，1962：21282MACKAYDJC，NEALRMNearShannonlimitper-formanceoflOWdensityparitycheckcodesJElectronicsLetters，1997，33：457-4583MACKAYDJCGooderror-correctingcodesbasedonverysparsematricesJIEEETransonInformationThe-ory，1999，45：3994314翁芸，颜珂斐，郭引川，等LDPC码的改进及其应用的研究J现代电子技术，2005，28(1)：4951，575RICHARDSONTJ，URBANKERI。Efficientencodingoflow-densityparity-checkcodesJIEEETranson，InformationTheory，2001，47：6386566王萼芳高等代数教程(上)M北京：清华大学出版社，19977MathWorksIncMatlabR13onlinehelpMs1：MathWorksInc。20028HUXiao-Yu，ELEFTHERIOUEARNOLDDM，eta1Efficientimplementationsofthesum-productalgorithmfordecodingLDPCcodesCGlobalTelecommunicationsConferenceS-1：IEEE，20019程敏LDPC码的译码算法的研究D南京：南京邮电学院，200310HUXiao-Yu，ELEFTHERIOUE，ARNOLDDMProgressiveedge-growthTannergraphsCProcofIEEEGlobalTelecomConfS1：IEEE，2001作者简介：刘英女，1983年出生，山西省忻州人，硕士研究生，助教。主要研究方向为测试计量技术及仪器。128万方数据基于Matlab平台的LDPC码快速仿真研究作者：刘英，张志亮，LIUYing，ZHANGZhi-liang作者单位：四川大学,锦城学院,四川,成都,611731刊名：现代电子技术英文刊名：MODERNELECTRONICSTECHNIQUE年，卷(期)：2010,33(9)被引用次数：1次参考文献(10条)1.GALLAGERGLow-densityparity-checkcodes19622.MACKAYDJC;NEALRMNearShannonlimitperformanceoflowdensityparitycheckcodes外文期刊1997(6)3.MACKAYDJCGooderror-correctingcodesbasedonverysparsematrices外文期刊1999(2)4.翁芸;颜珂斐;郭引川LDPC码的改进及其应用的研究期刊论文-现代电子技术2005(01)5.RICHARDSONTJ;URBANKERLEfficientencodingoflow-densityparity-checkcodes外文期刊20016.王萼芳高等代数教程(上)19977.MathWorksIncMatlabR13onlinehelp20028.HUXiao-Yu;ELEFTHERIOUE;ARNOLDDMEfficientimplementationsofthesum-productalgorithmfordecodingLDPCcodes外文会议20019.程敏LDPC码的译码算法的研究学位论文200310.HUXiao-Yu;ELEFTHERIOUE;ARNOLDDMProgressiveedge-growthTann