LDPc编码的研究与硬件实现(硕士论文)

gongkunjxl

贡献于2014-03-29

字数:0 关键词: 嵌入式开发

北京邮电大学 硕士学位论文 LDPC编码的研究与硬件实现 姓名:唐启荣 申请学位级别:硕士 专业:信号与信息处理 指导教师:吴文礼 20070307 北京邮电大学硕士论文摘要LDPc编码的研究与硬件实现摘要1948年Sh砌on提出并证明了著名的有扰信道编码定理,在Sh锄on信道编码定理指导下,越来越多的逼近Sh锄on理论极限的编码方法被提出并得到广泛应用。从早期的分组码、代数码、RS码、卷积码,直到今天的Turbo码和低密度奇偶校验码(10wdells时p耐哆checkcodes,简称LDPC码),系统性能与ShanIlon极限的差距越来越小。作为一种新的编码技术低密度校验(LDPC)码是一种基于图和迭代译码的信道编码方案,性能非常接近ShaIlnon极限且实现复杂度低,具有很强的纠错抗干扰能力。本文对LDPC码进行了系统研究。首先介绍了LDPC码的定义,然后介绍LDPC码的结构及其编码思想,给出了LDPC码的一些原始构造方法,并根据LDPC码的特点及目前LDPC码编码时存在的缺点,介绍一种实用性更强的u)PC改进编码方法。介绍编码以后,本文对译码方法作了简要介绍,重点介绍BP译码办法以及对BP译码算法做简化以后实用的译码办法。最后,本文重点介绍如何用FPGA硬件实现LDPC编码。主要工作和创新点如下:1、概括了信息论、信道编码领域的基本原理和信道编码从理论到实践的发展。包括Sh籼on信道编码定理,概述了具有接近Sh锄on极限的信道编码、特别是LDPC码的历史发展和现状。2、研究了LDPC码的码结构,在介绍LDPC码的校验矩阵表示、Ta彻e:图表示、度数分布的基础上,给出了规则码和非规则码的参数定义。3、从LDPC码编码角度研究了低密度校验矩阵的构造,包括规则码矩阵和非规则码矩阵,研究了Gallager构造法、BIBD组合构造法和Macl【av构造法。基于非规则码的准循环码构造方法。结合实际应用,介绍了实用的改进构造方法,包括近似下三角编码方法,万旋转编码方法和单位阵编码方法。4、研究了LDPC码的译码。在研究了硬判决译码,概率域BP算法和LLR域BP算法的基础上,重点研究了LDPC码改进的译码算 北京邮电大学硕L论文摘要法,包括迭代APP算法、U】ⅥPBP.Based算法、APP.Based算法等。5、结合实际工作,介绍LDPC编码的FPGA实现方法和LLR估计算法的FPGA实现方法。介绍了实际应用中编码的码矩阵特点,并提出针对性的实现方法,并用FPGA实现并作出modelsim仿真。关键词:LDPC码,Tallller图,稀疏矩阵构造,置信传播算法,FPGA 北京邮电大学硕士论文摘要RESEARCHoFLDPCCoDINGANDDEVELoPMENToNHARDWAREABSTRACTShaIulonde’rel叩edf.锄ousinterruptedchallIlelcodingtheoD,inl948.UnderSh锄ontheory,moreandmorcchannelcodingmethodwhichareclosetoSh籼on1iIllitedarcdevelopedandusednow.Fro】moldmethodsuchasBCHcoding,Algebmcode,RScodeandconv01utionalcodingt0Tu曲codingandLDPC(10wdensityparitycheckcodes)coding,thec印abilityisgetclosetosh锄onlimited.LoⅥr-D即sityParity-Check(LDPC)Codesareacl嬲sofch籼elcodesbasedongrapllsanditemtivedecodingwhosepeffb皿anceisVeryclosetotheShaIlnon1inlitwithlowcomplex时aIldhavestrongerrorcon仃olstren昏h.Inthisdissertation,t11ethcory’designandapplicationofLDPCcodcsarestudied,whichinvolveSblockcodesprinciples,codestmctIlre,decoding,constmctionofsparsep撕ty.checkmatrix,densi够evolutionand印plicationsofLDPCcodes.111isanicleprovidcmethodstodevcl叩itbasedonFPGA.111eminworkSandi衄oVatioIlsare勰f01lows:1.The如nd锄entalsOfinfomationtlleory'channelcodingandthedevelopmentf.romtheo可t0practiceofch锄elcodingarcgcnerated.AndtheintroductionofShannonchannelcodingtheoIyandchannelcodingmemodsclosedtoSha肌onlimited,especiallymedeVelopofLDPCcoding.2.ThestructurcofLDPCcodesisstudied.Basedonttlematrixrepresentation,T撇er'degreedistributionofLDPCcodes,meparametersofi玎egular觚dregularcodcsaredeflned.3.Researchtheconstmctionoflowdesitypatitymat血f.romLDPCcodes,includingi仃egularalldrcgularcodes.Thisarticlein仃oduceGallager,BIBDandMackaymethodsandalsoirregularmethod.AccordiI培topanice,italsointroducesscveralpmcticalmethods,suchas 北京邮电大学硕}论文摘要sub.trianglemethod,rotational石methoda11dunitmatrixmethod.4.ThedecodingofLDPCcodesisstudied.Harddesitiondecodingisstudied.Basedontheprobabili哆domainandtheloglikelihoodratiodomainofBPdecodingofLDPCcodes,themodifiedBPdecodingalgorjthmsarepaidmoreattentionto,includingtheAPP:UMPBP-Based,APP.Basedal窟orithms.5.Accordingtopmcticalwo咄thedevelopofLDPCcodingandLLRevaluationindecodingusingFPGAareintroduccd.Tllestmctureofpmcticalmatrixa11dhowtomakeittoFPGAchipareshownandModelsimsirnulation.KeywOrds:Low-Dens时Pari妒CheckCodes,Tanncr鲫h,sparSeparity-checkmatrix,BeliefPropagation,FieldprDgramma【blegatesamy 独创性(或创新性)声明本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除了文中特别加以标注和致谢中所罗列的内容以外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得北京邮电大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。申请学位论文与资料若有不实之处,本人承担一切相关责任。本人签名:唐宙&日期:兰竺隍塑塑关于论文使用授权的说明学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定,即:研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许学位论文被查阅和借阅;学校可以公布学位论文的全部或部分内容,可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。(保密的学位论文在解密后遵守此规定)保密论文注释:本学位论文属于保密在一年解密后适用本授权书。非保密论文注释:本学位论文不属于保密范围,本人签名:麈笸整导师签名:—誓秦弓扩,jL叭/戎l\】,tot’适用本授权书。日期:竺]生塑整望日期:垫监兰墨整旦 北京邮电大学硕士论文第~章绪论第一章绪论1.1Shannon信道编码定理假设一个通信系统,信源序列【,=(U,u:,..⋯,以),各个分量是统计独立同分布的随机变量,取自有9个符号的集合。设)(-(五,五,...,以)是相应的信道输入,Y气E,E,..⋯,E)是信道的输出,而【,=(Ul,u2,..⋯,【,。)是接收者根据Y对U的估计。对此系统传输质量的要求是对所有的i,有P(U,≠U,)<占,£是某个很小的数值【I】。根据有关定理‘上一,(【,;u)≥∑,(【,;u,)(1.1),(【,;u)=Ⅳ(U)一日(UIuj)≥Ⅳ(u,)一日2(F)(1.2)J∥;功≤J(x;y)可知主≤£以H((,』)一日2(占)(1.3)(1.4)如果是二进制等概信源,信源的平均信息量村@)tl,上式变为鲁≤南ms,开1一皿(占)、’比率k/n是系统的速率,表示每次利用信道所传输的比特数,表示系统的有效性。当信源一定时,上式是错误概率‘的上升函数,要降低误码率就应该降低传输速率。如果设计一个速率R=Ii}/疗>c系统,则最终错误概率占≥巧‘(1一云)>o(1.6)即当速率高于信道容量时不能实现可靠通信。而在速率R小于信道容量c时,Sh锄on指出,可以通过编码来实现任意可靠(占是任意小的数)的通信,称为信道编码定理【I】.描述如下:每个信道具有确定的信道容量c。对于任意占>O和R11.k,码率,>1一竺。构造一个维数为m×n的矩阵H,通过高斯消元法将其变成如下形式.E,=【‘月一言‘月一I)尸’‘;‘H‘】(2.2)如果H是满秩的,变换后不存在全O的行。由以上变换可以得到系统形式的生成矩阵G=【只加圳,。。】,信息序列“=【“。,“:⋯,‰】通过c=IlG映射为码字c。虽然H是稀疏的,但是矩阵P通常不是稀疏的,编码过程中需要存储P的元素,存储6 北京邮电大学硕士论文第二章LDPc码的结构量较大。同时,编码的运算量是码长的二次方的形式,在码长较大时。需要采取措施降低复杂度。2.1.2Ta肌er图表示除了用校验矩阵表示LDPC以外,还可以用双向的图模型表示u)Pc码Ⅲl。T姐n盯图”4是一种双向图,可以用G={ⅣE))表示,其中v是节点的集合,矿=%U以是维数为m×n的校验矩阵,%=(61,62,⋯.也)称为变量节点(或位节点、左节点),对应校验矩阵的列,同时对应码字中的位;屹=(cl,c2,..⋯r.)是校验节点(cl雠knode,函数节点、右节点),对应校验矩阵的行,也就是校验方程。E是节点之间相连的边的集合E£%×屹,同类节点之间没有边相连,只有在两类节点之间有边存在。如果校验矩阵的第i行第j列元素为是非零的,则.‰n盯图的第j个位节点与第i个校验节点有一条边相连。即当^。=1时,节点q与6,之间有一条边相连,边(c。,6,)∈E.与节点的相连的边数目称为节点的度(deF∞),从某个节点出发又回到此节点为一循环(cyclc),所经过的边的个数称为循环长度,其中最短循环的长度称为图G的Giml。校验矩阵的行重和列重与节点的度一致,亿ncr图与校验矩阵一一对应。上节中的校验矩阵对应的Ta曲er图如图2.1所示,具有10个变量节点和5个校验节点,每个变量节点都有2条边,每个校验节点都有4条边。c1c2c3c4c5blb2b3b4b5b6b7b8b9b10图2.1校验矩阵的Tann目图表示2.13度的表示点变量节点U)PC码的校验矩阵和Ta皿er图是等价的,对应的是一个LDPC码C,而一个LDPC码的集合可以用度数分布或码生成函数表示。设最大变量节点的度为7 北京邮电大学硕L论文第二章LDPc码的结构d,,最大校验节点度数为d。;丑(n)表示与度数为i≥2的变量(校验)节点相连的边数在总的边数中所占的比例,由此构造多项式正A(工)=∑丑工“三2(2.3)p(J)=∑岛工“1,一2其中A(1)=p(1)=1。五(J),户(石)称为度数分布或码生成函数。设总边数目为E,度数为i的变量(校验)节点占总变量(校验)节点的比例为口,(6『)。如变量节点数为n,校验节点数为m,则有五,=!:!!:!‘E岛:翟兰(2.4)岛。——j—U.唧由于∑q=l,∑6f=1拈嘉2嘉2高2高但.5)铲筹:≠生(26)q2参2商‘2。6’¨参2嚣伍7)同时可知码率为,:l一竺:1一二I!!:!兰(2.8)以jA(J)出一因此,码长n,度数分布旯(J),p(工)决定了码率和校验方程的个数,对应的是一个码的集合,记为c“(A,p)。满足度数分布五(J),p(x)的校验矩阵有很多个,不同的构造方式得到的校验矩阵的性能是不同的,有关矩阵构造问题在第三章中讨 北京邮电大学硕上论文第二章LDPc码的结构2.2规则LDPC码和非规则LDPC码如果校验矩阵的各行中非零元素的个数是相同的,各列中非零元素的个数也是相同的,此时LDPC码为规则码。此时,伽ner图中所有变量节点具有相同的度d,,所有校验节点具有相同的度t。此时,其度数分布为纵曲爿?-I㈤从而=≯一1、’总边数E=耐,=耐。(2.10)码率为,:尘竺:l一竺:1一拿(2.11)万一4。与规则码对照,如果校验矩阵的各行中非零元素的个数是不相同的,各列非零元素的个数也是不相同的,此时LDPC码为非规则码.非规则码的结构由其数分布决定,式(2.12)是度数分布为A(工)=O.4工+O.6工2,以功=O.缸2+O.4,的非规则码的校验矩阵,下图2.2是其T趾n盯图。日=blb2b3b4b5b6b7b8b9b10b11b12图2.2一种非规则码的Ta衄日图9节点变量节点(2.12)1OOOOOO1lOOOO1lO1O1l1O0O0OOO1OO1OlOOOOOO1OlOl1OOlOOOO1O1OOOOOOlOO1OOOlOOOOOlOOO1OOOOOOOllOOOOlOlOOOOOlOOlOOO 北京邮电大学硕士论文第二章LDPc码的结构2.3规则码和非规则码的性能比较通过仔细选择码的度数分布,非规则码的性能比规则码的有较大的提高,采用优化度数分布的非规则u)Pc码的性能已经超过了1.I】rbo码。非规则码的性能优于规则码,可以从LDPC码的译码过程解释p4。U)PC码的译码是一种Ta∞盯图上的置信传播算法,有关比特为O或l的置信消息在节点上处理后沿着校验节点和变量节点之间的边传递。初始时,变量节点接收信道传送的初始消息,每一个校验节点收集与其相邻的变量节点的外部消息,处理后传向与其相邻的变量节点:然后进行变量消息的处理,每一个变量节点收集所有的消息后进行判决,如不能正确译码且没有达到最大迭代次数,则将外部消息再传回与其相邻的校验节点继续迭代。下图是规则码的译码过程示意图。如第一次迭代的校验消息处理时,校验节点cl传向变量节点b1的消息是来自与cl相邻的变量节点b2'b3,b4,不包括b1传向c1的消息。然后进行变量消息的处理,如变量节点b1收集初始消息及从校验节点c1.c2传来的消息,处理后进行判决。所有的变量节点判决后,如译码错误,则变量节点继续将外部消息传递给与其相邻的校验节点。如bl传给cl的消息来自初始消息和c2,不包括上次cl传给bl的消息。这个消息传递过程一直进行,直到正确译码或达到最大迭代次数。因此,译码时,从变量节点的观点来看,与之相连的校验节点越多越好,变量节点的度数越大,它就能从更多的相邻校验节点处得到更多的置信信息,可以更加准确的判断出它的正确值:但从校验节点的观点看,恰恰相反,与校验节点相邻的变量节初始消息点越少越好,校验节点的度数越小,它能给相邻的变量节10 北京邮电大学硕士论文第二章LDPc码的结构变量消处理初识消息b10图2.3规则码的译码过程示意图点提供的消息置信度越高。由于变量节点和校验节点具有相同的总的边数,故对于这两种矛盾的要求,非规则码可以更灵活地实现折衷。在非规则码的译码过程中,度数高的变量节点接收到的置信消息多,迅速实现正确译码,它们可以给相邻的校验节点传送更加有效的信息,而这些校验节点又可以给与它们相邻的度数更小的变量节点更多的信息,从而产生波浪效应。度数高的变量节点首先正确译码,接着是度数稍低的变量节点,然后是度数更低的,如此继续下去,直到译出所有的变量节点。2.4本章小结LDPC码的校验矩阵是一种稀疏矩阵,即矩阵中非O元素的个数远远小于O元素的个数,或者矩阵的行重和列重与码长相比是很小的数。LDPC码由其校验 北京邮电丈学硕士论文第二章LDPC码的结构矩阵决定。校验矩阵确定后,变换后得到生成矩阵,从而实现了u)Pc码的编码。除了校验矩阵表示LDPC码外,可以用一种称为Tanncr图的双向图来表示LDPc码。T觚ner图与校验矩阵一一对应,只有校验节点和变量节点。与节点相连的边与矩阵中的非零元素的位置一致。从Ta加cr图上可以定义节点的度、循环。根据阿m盯图上节点的度,定义u)Pc码的度数分布。度数分布指的是与节点相连的边在总边中所占的比例。由度数分布、码长,可以决定码率、校验位个数以及度不同的节点的分布。如果校验矩阵的各行中非零元素的个数是相同的,各列中非零元素的个数也是相同的,此时U)PC码为规则码。与规则码对照,如果校验矩阵的各行中非零元素的个数是不相同的,各列中非零元素的个数也是不相同的,此时LDPc码为非规则码。通过仔细选择码的度数分布,非规则码的性能比规则码的有所提高。12 北京邮电大学硕上论文第三章LDPC码校验矩阵的构造第三章LDPc码校验矩阵的构造一种编码方法的好坏完全由它的校验矩阵来确定,也就是说校验矩阵的结构对于码的性能有着决定性作用。LDPc码是用一个稀疏校验矩阵来定义的,所谓的稀疏校验矩阵,就是指校验矩阵中每行、每列包含的。1”的个数相对于码长来说都是很小的数。我们根据校验矩阵中每行的行重和每列的列重是否相同,把LDPC码分为规则LDPc码和非规则LDPC码。在文献p川中指出:非正则码在译码性能上要优于正则码的性能,但是正则码由于其结构规则所以更适合于vLSI的实现。从第二章LDPc码的定义我们可以看出,要设计一个LDPc码,最直接最有效的方法就是按照指定标准构造一个低密度奇偶校验矩阵H。随着LDPc码越来越多地得到人们的重视,其构造方法也层出不穷。当然,构造方法的不断推出,是为了实现以下几个目的:优化码结构:增大二分图中的周期:减少编码复杂度。下面我们从规则码和非规则码两个方面来分别介绍一下LDPc码的结构。3.1规则LDPC码规则u)PC码是LDPC码中最简单的形式,早在1962年,Gallag盯就提出了其构造方法,但是限于当时的条件和人们认识的水平,这种码一直未受到人们的认可。多年以后,当LDPC码再次走进人们的视眼的时候,这种码的构造方法开始层出不穷,下面我们将着重介绍几种构造方法。3.1.1Gauager的构造方法1962年,Gallag盯在文献【3a中提出了一种构造(n,j,k)规则LDPc码的方法,我们把这种方法构造出来的u)PC码称为Gallag盯码。该方法的具体思想是:首先构造一个每列只有一个“1“,每行有k个“1”的子矩阵H。,然后对H。进行(j—1)次随机的列置换,分别得到(j·1)个子矩阵,利用这j个子矩阵得到校验矩阵H,这样得到的校验矩阵码长为n,行重为k,列重为j,其结构如下所示:日=日。刀2(乩)万』(风)(3.1)其中I矩阵日。的列置换。下面我们给出一个(20,3,4)u)Pc码的矩阵形式,如图所示,从矩阵的结构我们可以更清楚地理解Gallager的构造方法。 北京邮电大学硕t论文第三章LDPc码校验矩阵的构造110O0OO01O0OO0O0OOO0O0OO0O11l1O0OO0OOOO0OOOOOO011llOOOOO0O0O00OOO0OO1l11OOOOOOOOOOOOO0OOOOO1OOO1OOO1OOO1OOO1OO0lOO0lOOO000O10OO10OOO0OO10OO1OO0OOOlOOO0O11l1OOOOOOl000OO10OlOOlOOOOO00O1OOO1O1OO0OOllOOOO1OOO0010OOOO1OOO1OO0OlO0O1OOOOlO0OOO0lOO0O1OO0O1O0O00100OOl0O0OlO0OO1O0lO00O0O0lOOO0l00OOlOOO0l图3.1码长为20,列重为3,行重为4的正则码的校验矩阵对上述U)PC码,给定校验矩阵后,如果校验矩阵的行是线性无关的,那么编码的码率为l一姜,相反,若校验矩阵的行是线性相关的,那么编码的码率要大于l一车,也就是说,任何一个gallagcr码的码率都不会小于l一手。疗石3.1.2广义LDPC码的构造方法广义LDPC码(简称为GLD码)最早是由I肋仃nai叮p”和Bou仃ospl单独提出来的,作为Gallag盯提出来的u)Pc码的推广形式,广义LDPc码是利用线性分组码的校验矩阵来取代LDPc码中每一个奇偶校验等式而形成的,其构造思想与Gallag盯码的构造思想大致相同。广义LDPc码可以运用基于构造码所用的软输入软输出译码思想的迭代译码方法进行译码,这种方法将在第四章进行阐述。此外,广义LDPc码的译码器结构规则,而且可以并行实现,这一点对于实际中电路的实现是非常有益的。众所周知,LDPc码是通过一个稀疏校验矩阵来定义的,校验矩阵中的每一行是一个纠正单个错误的校验等式,由于广义LDPC码是LDPC码的通用型,所以该码也可以由一个稀疏校验矩阵H来定义,而且这个矩阵可以通过用一个码c0(,l,七)的校验矩阵H。替换LDPc码的每一行来形成。对于长度为N、行重为k、14 北京邮电大学硕士论文第三章LDPC码校验矩阵的构造列重为j的广义u)Pc码来说,我们可以通过.j个列重为“l”、行重为“k”的构造矩阵H。构成。首先,我们选择一个合适的校验矩阵H。作为基矩阵。该矩阵具有如下特点:(1)该矩阵对应的码长为n,且要求N/n为一个整数;(2)该矩阵对应的列重为“1”、行重为‘‘k”:(3)为了使所生成的GLD码对应的校验矩阵中没有任何两个子码有多余一列的非零元素是重叠的,我们要求N/n≥n。有了构造矩阵H。以后,我们把H。作为子矩阵的块对角矩阵来形成第一个子矩阵Ⅳ1,该矩阵的行重和列重与矩阵风的相同;接着对Ⅳ1,进行a.1)次列置换得到(j.1)个子矩阵Ⅳ1,日2,..⋯.,日,,最后把这j个子矩阵从上到下依次排列得出矩阵H,下图为广义LDPc码校验矩阵的结构图,其中石。(《2茎fs,))代表一个随机的列置换(即对H,进行随机列置换)。Ⅳ1=风0⋯00O风⋯OOOO⋯风OOO⋯O风日1日2=石2(日1)H3=乃(H1)H7=石J(日1)图3.2广义LDPC码校验矩阵的结构图3.1.3Mackay的构造方法Mackay在构造校验矩阵时,引入了一些重量为2的列来降低整个校验矩阵的重量,以减少Ta加盯图中循环的数量,由此减少译码算法受到圈的影响,但是引入重量为2的列会导致低重量码字的出现,需要采取措施减少其出现的概率。为此,Mackay给出了如下的构造方法“”.构造法lA:对于M×N的矩阵,我们可以随机地构造,使其列重为j(如j=3).。行重尽可能相同,且任意两列重叠的1的个数不大于l。图3.3给出了码率为l/2,列重j=3的构造。 北京邮电大学硕士论文第三章LDPc码校验矩阵的构造M④oN图3.3码率为三,列重j=3的构造‘\\,/,—、\、\\弋j图3.4构造法2A严生的矩阵构造法2A:利用该构造方法构造的校验矩阵,前些列列重为2,且这些列由两个Z等×等的单位矩阵构成。如图2.4所示,任何一列中都没有重叠的“1”。剩余的(Ⅳ一警)列是随机构造的,其列重为3,每行l的个数尽可能一致,且整个矩阵中任意两列重叠的1的个数不大于1。图2.4为码率为1/3的码的构造结构。构造法1B和2B:分别从利用构造法lA和2A构造出来的矩阵中删除一小部分列,使得对应新矩阵的二分图中没有小于某个长度1(如1《)的圈,这两种方法我们分别称之为1B和2B。3.1.4组合学构造法组合学构造法是一种基于组合数学中BIBD理论的构造方法,该方法构造出来的LDPC码为规则LDPC码,且没有长度为4的循环p1。BIBD是BalaJlced111咖pletcBlockDesi印的缩写,即均衡不完全的区组设计p1,下面我们给出该设计的定义。设x=“,而,¨.,‘)为试验对象集合,v为试验对象的数目。所谓均衡不完全的区组,指的是由X中的子集构成区组的集合。B为区组的数目,即设为6 北京邮电大学硕士论文第三章LDPC码枝验矩阵的构造慨,口:,...,见)。每组有x的k个元素,并满足以下的条件:(1)x中的每一个元素在b组中正好出现r次(2)任意一对属于X的元素在b组中正好同时出现五次(3)kc—z产~,,,d,,(4.1)式中,b.为第i次迭代的门限值,d,和d。分别为变量节点和校验节点的次数,其中,z,=l一2ng(_y,,,,)=【半】‘【三≠r。适当地选择b.,可使p,+。最小,若b,为使(4.2)不等式成立的最小整数,p。将取得最小值。业4燃r小1㈤)‰一【l一(1—2pj)小1j”一’如果算法应用于次数分布对为(五,p)的非规则码,则有结果肌-一纠,鼽1卜A“川-训氖7b钔^川(4.3)式中,d,为变量节点的最大次数,6J.J为随节点和迭代次数变化而变化的门限值。使p,+-最小化的岛.J是满足如下(4.4)式的最小的正整数。塑4掣r√”(4.4)poll—p(1—2pj)J、’ 北京邮电大学硕士论文第四章LDPC码的译码4.2BP译码算法建立在Ta衄盯图上的LDPC码,其BP译码的每次迭代包括两步:校验节点的处理和变量节点的处理,可参照图2.3。在每次迭代中,所有校验节点从其相邻的变量节点处接收消息,处理后,再传回到相邻的变量节点然后所有的变量节点进行同样的过程。最后变量节点收集所有可以利用的消息进行判决。在LDPc码的译码过程中,每一个校验(或变量)节点可以看作是一个处理器,所有校验(或变量)节点的处理可以同时进行,因此利用并行结构可以构造高速LDPc码的译码器。但是,并行处理硬件电路面积大。相反,1.urbo码的译码是串行的,对硬件电路要求低,而译码延时长。根据消息的表示形式,BP译码可以分为概率BP算法和LLRBP算法。概率BP算法的消息是用概率形式表示,是BP算法的通用形式,可以适用与非二进制的L【)Pc码的译码。而对二进制u)Pc码,消息可以表示为对数似然比形式,相应的译码算法称为LLRBP译码。4.2.1概率BP算法调制后每一个码字萨(c。,c2,...c。)映射为传输序列x:(x。,x2⋯_.x.)然后通过信道,接收到的序列为y=(y。,y:,..⋯.,y.).根据y译码得到译码序列为c.首先介绍所用到的有关符号的含义,r。(b)(b=O,1)表示校验节点j传给变量节点i的外部概率信息,即在给定信息位及其它信息位具有独立概率分布条件下,校验方程j满足的概率;q。(b)表示变量节点i传给校验节点j的外部概率信息,即在得到所有校验节点和信道的外部信息后,判断变量节点c,=b的概率;c(i)表示与变量节点i相连的校验节点的集合c。=a:h。=1);R0)表示与校验节点j相连的变量节点的集合,R,={j:h。=1);C(i)\j表示除j外与变量节点i相连的校验节点的集合;R(j)\i表示除i外与校验节点j相连的变量节点的集合;c。:包含c;的第j个校验方程中的第k个比特;y々:对应于。目的接收值;P.(1)=P“c。=lIy,):接收到y。后判断发送比特(或变量节点)为c。=l的后验概率。P目=Pr(oH=lIy目):接收到y目后判断包含c,的第j个校验方程中的第k个比特为c。=1的后验概率; 北京邮电大学硕:上论文第四章LDPC码的译码s,:c中的比特满足包含c,的d。个校验方程。引理1:二进制序列a_(a。,⋯,a.),其中p(a^=1)=Pt,则a中包含偶数个1的概率是寺+寺兀(1—2仇),a中包含奇数个1的概率是寺一寺兀(1—2p。)·‘扣l厶二t-lGallager定理:尸(c,=OIy,S)P(q=1Iy,墨)肛q\,’ec』V/由引理1,可知白(o)=丢+昙兀(1—2#.』)'。(1):昙+寻兀(1—2只,,)在比特概率·-,E^、f-‘jE月.UPF相互独立时,Gallager定理给出了后验概率”P的计算方法。根据引理1Gallager定理可改写为:P(c,=O『y,置)P(q=lly,墨):半熙@。,2—F丽竹‘0’的(o)=(1一只)兀“o)。⋯.一7码.::|(4.7)∥(1)=暑兀州1)、’因此,BP译码步骤总结如下(为表示方便,消息符号中的上标表示迭代次数):·初始化计算信道传递给变量节点的初始概率P。(1),P.(0)=l-P。(1)i=1,2,...,n。然后对每一个变量节点i和与其相邻的校验节点j∈c(i),设定变量节点传向校验节点的初始消息黧卜:?(4.8)g∥(1)=只(1)、7·迭代处理st印1校验节点消息处理对所有的校验节点j和与其相邻的变量节点i∈R(j),第1次迭代时,计算第j个校验节点传向第i个变量节点的消息矧 北京邮电大学硕士论文第四章LDPc码的译码巧o(o)=寺+寺兀(1—29铲(1))‘‘q。"1l㈣'●、7杈1)=1一o(o)=寺一寺兀(1—29矿(1))‘‘reR,Ⅵst印2变量节点消息处理对所有的变量节点i和与其相邻的校验节点j∈C(i),计算第i个变量节点传向第j个校验节点的消息衫’(o)=岛只(o)兀嘴(o)。⋯⋯⋯=”。⋯(4.10)∥(1)=xⅣ弓(1)兀坍(1)⋯⋯’其中KF是校正因子,使g∥(o)+g≯(1)=1。st印3译码判决对所有变量节点计算硬判决消息。。g∥(o)=K,只(o)兀∥’(o)∥(1)咆刖)亓粕)@。1D其中K.是校正因子,使得g∥(o)+g?’(1)=1。若gj。(1)>叮jo(o)贝0c·=1,否则c,=o·停止^r若日c=O或者达到最大迭代次数,则结束运算,否则从st印l继续迭代。如果矩阵H中不包括循环,则迭代次数趋于无穷时,Q,(0)和Q,(1)收敛于c.的后验概率:对于好的LDPc码,算法可以检测不正确的码字。4.2.2LLRBP算法如果概率消息用似然比表示,则得到LLRBP算法,大量的乘法运算可以变为加法从而减少运算时间。为此需要定义对数似然比(Lut)消息如下:信道勰消觚驴109器-log鬻搿校验节点传向变量节点的消觚俨109器变量节点传向校验节点的消觚¨-l。g嚣 北京邮电大学硕士论文第四章LDPC码的译码变量节点收集到的所有消息工(吼)-l。g豢等(4.9)重写为l一2白(1)=l+兀(1—2%(1))利用恒等式伽【111工=事{;,伽【lIl哇l。烈风/A))=岛一A=l一2p。,(风+A=1)及对数似然比的定义,式(4.12)可化为锄(三撕,]=.飘鼬c圭‰埘而式(4.101可化为(4.12)(4.13)工(幻)=工(只)+兀三(¨(4.14)J、qV因此,LUtBP算法总结如下:·初始化计算信道传递给变量节点的初始概率似然比消息UP.),1=l,2,,..,n。然后对每一个变量节点1和与其相邻的校验节点j∈c(i),设定变量节点传向校验节点的初始消息00’(吼)=£(曰)·迭代处理stcpl校验节点消息处理:对所有的校验节点j和与其相邻的变量节点i∈R(j),第1次迭代时,计算第j个校验节点传向第i个变量节点的消息鼬(抄c白,)=。飘蛐c圭‰瑚,、(4.15)∥乜瑚时‘L现劬c知伪JsteD2变量节点消息处理对所有的变量节点i和与其相邻的校验节点jEc(i),第1次迭代时,计算第i个变量节点传向第j个校验节点的消息心o(%)=三(曰)+兀00(o..)(4.16)st印3译码判决对所有变量节点计算硬判决消息 北京邮电大学硕士论文第阴章LDPC码的译码00(吼)=£(曰)+兀of)(o)jEc。(4.17)若0‘’(g,)>O,则cf_0,否则cJ-1‘停止.r若日c=O或者达到最大迭代次数,则结束运算,否则从stcp1继续迭代。4.2.3AwGN信道下的初始消息下面推导常用的AWGN信道下、BPSK调制的LDPC码译码的消息初始化.在通信系统中,采用二进制数字调制,码字c.,映射为符号x,,x。气-1)“,i-l,2,...’Il。AwGN信道模型,接收符号y,=x。+n,,各个n。为统计独立同分布的高斯随机变量,双边功率谱密度为n。/2,可知y.是均值为1、方差为艿2的高斯变量。在信源等概分布时,P(x。斟l产P“x。一1)=妄,此时概率BP译码的初始消息为叮舯廿晌。1∽)廿电一1∽)2鬲嘉(4.18)g≯(0)=Pr(cf20l乃)=P“‘2+1l乃)2方‘4_9)证明:M一∽=等产=丛铲:旦Q!兰三型!丛墨三型p(yI而=1)P“而=1)+p(,I‘=一1)P“而=一1)(4.20)南= 北京邮电大学硕士论文第四章LDPc码的译码得证。由此,LLRBP译码的初始消息为∥_劬卜以彤。101忑高礼g[一_109(exp学))=等4.3降低复杂度的BP算法(4.21)BP算法以其优越的性能和较低的复杂度得到了广泛的应用。为了得到一定条件下的译码性能与复杂度的合理折衷,MarcPC.Fossorie和Jin曲uCheIl等提出了几种简化的LLRBP算法,仅通过加法运算来完成LDPC码的译码,大大降低了译码的实现复杂度。下面分别介绍。4.3.1迭代APP算法在变量节点的处理中,只有加法运算,但是可以进一步降低算法的实现复杂度。如果用LLRBP算法中的£(吼)代替£(吼)参与校验消息的迭代,也就是£(吼)不仅用于硬判决,而且用于求解校验消息,此时BP算法简化为迭代的APP(apost耐谢probabi】ity)算法。这样计算,传递的变量消息之间引进了相关性,传递的变量消息就不再是外部信息,但是此时仅仅需要计算和存储一个变量消息的数值,可以大大降低算法的复杂度。4.3.2UMPBP.Based算法(最小和或最大积)tallllx,taIlll。(x)是奇函数,具有以下性质:tanh(工)=sgn(工)·tallll(IxJ)ta]【】11。1(力=s印(工)·tanh‘1(1工I)由此LLRBP算法中校验节点的处理可表示为(4.22) 北京邮电大学硕士论文第眄章u)Pc码的译码三(,』f)=2taIlh。1(兀tallll(寺工(钆”)rE正U·=2taIllll(兀s印(三(g¨”·兀tallll(寺I£(gq)I))fe^un一、j-=2(兀s烈£(g吖))-tallll。1(兀taIltl(寺I三(g吖)聊(4.23)』o—V』。■u-由于taIll【x1)在。到1之间取值,而且是x的单调递增函数,故,飘蛐(三似训∞z砾鼬(三愀们加5tanh(言删马(I£(g一)1)(4·24)工(。)-,飘8鲥地伪黑(№,)|(4.25)如果用上式作为LLRBP算法中的校验节点消息的处理,则称为最小和(Mins啪)算法或最大积(MaxProduct)算法。与LLRBP算法相比,此时校验节点的迭代只有比较运算与加法运算,大大降低运算量。对AwGN信道,初始LLR消息中的因子丢对迭代过程没有影响,可以忽略,因此BP.B船ed算法不需要信道的估计,所以也称为UMP(UnifomlyMostPaw砷11)BP.B够ed算法。4.3.3APP.Bas酣算法如果在校验消息和变量消息的计算过程中,都进行简化,将BP.B∞ed算法与迭代APP算法结合在一起,得到APP.Based算法。总结如下:·初始化计算信道传递给变量节点的初始概率似然比消息【胛。),i.1,2,¨⋯.,n。然后对每一个变量节点i,设定变量节点传向校验节点的初始消息0∞(g,)=三(鼻)=y·迭代处理step1校验节点消息处理:对所有的校验节点和与其相邻的变量节点i∈R0),第1次迭代时,计算第j个校验节点传向第i个变量节点的消息 北京邮电大学硕士论文第四章LDPc码的译码职o)=玎s印(一(桫凹(P(枷k月,⋯Ystep2变量节点消息处理对所有的变量节点i,第1次迭代时,计算第i个变量节点传向第j个校验节点的消息o,】(吼)=工(暑)+兀一o(o),eCstep3译码判决若07’(吼)>O,则c』=O,否则cj=l·停止若日c=O或者达到最大迭代次数,则结束运算,否则从st印1继续迭代。同样APP.B嬲cd算法不需要信道的估计,所以也称为uMP(unifonlllyMostPowermll算法。4.4本章小结Gallager首次提出的概率软判决迭代译码,可以看作是伽ner图上的置信传播(BP)算法,也称为和乘积算法或消息传递算法。从因子图角度,可以构建广义的和乘积算法,很多算法都可以看作是因子图上的和乘积算法。建立在Ta仰er图上的LDPc码,其BP译码的每次迭代包括两步:校验节点的处理和变量节点的处理。所有校验节点从其相邻的变量节点处接收外部消息,处理后,再传回到相邻的变量节点;然后所有的变量节点进行同样的过程。最后变量节点收集所有可以利用的消息进行判决。根据传递的消息的不同,BP译码有概率BP译码和LLRBP译码.LLRBP译码传递的是对数似然比消息,适用于二进制码。验证译码算法常用的通信系统环境是AWGN信道下采用BPsK调制,根据信道噪声的概率分布和接收符号,可以推导出u)Pc译码所需要的初始消息。通过修改LDPC译码的校验消息处理和变量消息处理可以获得降低复杂度的译码算法。变量节点接收所有的校验消息来进行迭代,简化为APP算法,降低存储量:变量消息传递给校验节点时,用变量消息的最小值代替总的乘积运算,简化校验消息处理过程,得到BP.B鹤ed算法,降低计算量,损失一点性能;APP算法的变量消息处理与BP.B勰cd算法的校验消息处理结合,得到APP—Based算法。 北京邮电大学硕士论文第五章u)PC编码的硬件实现第五章LDPc编码的硬件实现U)PC编码是一种接近仙农极限的信道编码,他在数字电视标准DvB.S2、DVB.TH、802.11n、802.16中得到广泛运用。我有幸参与了一个DVB-TH标准下的信道编码的FPGA实现。下文对我所负责的Lut估计模块和LDPc译码模块的硬件设计做简要介绍。5.1BPSK调制下的LLR计算的实现5.1.1理论分析由上文4.1.3司知,软信思的计算方法如F:根据信遭观测值y-,(1≤f≤_Ⅳ)估计噪声方差(万2),并且计算厶豫(y。)=等,将输入的观测值以16352个数为一组压入FIFo,在压入的同时将数据取绝对值送入累加器与平方累加器处理16340个数作为样本估算出方差,其余数不处理,留下时间算出争·具体算法是:a.求出E(Iy,I)和E(y。2)。b.Z芦E(y.z)/E2(1y。I),c.B一34.0516Z2+65.9548Z.23.6184,d.吉剐南参考资料【4j求出系数砉,再与F球。读出的该组16352个数分别相乘得出等。5.1.2LLR模块的设计。输入数据Yi,按照长度N分组,其中N是2的n次幂,n是自然。这一组数据 北京邮电大学硕£论文第五章LDPC编码的硬件实现算出一个系数,再分别与Yi相乘,依次输出。设计框图如下:图5.1u且估计设计框图1.控制信号产生模块:根据上电复位复位和一个桢同步信号,由计数器产生以下各个模块的控制信号always@(posedgedk)elses诅rt<=s锄;be百nif【!syIlc_.他g&&sync)cntt。=l;if【rst)elseit【cn卢=16351)cnt<=O;begilld∞锄t(-伽什l-bl;c咪‘司:m|aN矗finish《=o;i坟c11卢1635lIIcrlt<'16338)avai<=l;clear.,=1;elseavai<=0;f乱ch.(=O:////右nishavaj<=O;i坟cIl户16350)finiSh<=1;sync.—reg<=O;clse觚sh=16342)deaPo=1;elseelseclear<=O:38 北京邮电大学硕士论文第五章LDPc编码的硬件实现be百nsyncreg<=sync;if【syIlc)s切疗<_l;end北g∞t1;||黾‰研rc[7:O】fif0-put;always@(poscdgedk)b啦i郇t)beginrden<;O;wr朗<_O;仿真波形图:m|{妊tecLif(c11卢16340)舰ch<一1;clsef乩d1<=O:elsebegillif(start&&∞卢=16351)be百nwren<=l;衄del辩begin绛£即(黾吁倒endif【、vr∞&&cⅡ睁=16350)rden<=l;el∞rden<可dcn;end由上到下,各信号为:cll(:系统工作始终,与输入数据同步;fst:复位信号,在上电时复位了,正常工作rs仁0;sync:桢头信号,每桢有16352个输入值,在每桢的开头与第一个数同时出现 北京邮电大学硕上论文第五章LDPc编码的硬件实现的高电平,表示一桢的开始。syllcreg:将syIlc信号延时一拍。目的是在第二桢来的时候让计数器在桢头信号时为O;cnt:计数器,啦!6351循环;右msh:在每桢最后一拍的完成指示信号。作用是存储运算出来的系数;做ch:在累加器和平方累加器算完16340次累加和平方累加之后将结果缓存的指示信号;clear:在触ch信号存下结果后将累加器和平方累加器清零,准备下一次计算;avai:在每桢前16340拍让累加器和平方累加器工作的使能信号;start:当复位后出现第一个桢头信号时置一;啊髓:FIF0写使能。star}l以后,第二个桢头信号来时,∞t也已经和sync对齐了,FIFO开始存入数据,wT曲=1并且一直保持;rd舅:FIFO读使能。在写入数据一桢以后,将数据读出,岫l-l并且一直保持;2.FIFO模块:储存N个数据,N=2“。一共使用16352个数,所以通过控制FIFO读写使能控制第一组有效数据存满以后开始读数据,然后不停的读写,将上一组数据读出来,实现缓存的功能。din:系统输入的数据啊;fi旬out:矗fo缓存一桢的数据后。输出的上一桢的yi;clk:fifo时钟,就是系统时钟;rst:fifo复位信号,就是系统的复位信号:忻蛆:写使能,由使能产生模块生成rd皿:读使能,由使能产生模块产生3.取绝对值模块,Input; 北京邮电丈学硕士论文第五章u)Pc编码的硬件实现din【7:o】:输入的yidin—abs:输入是正数,daca0叶=datain;负数时,输入数据采用符号位+绝对值形式的话,直接符号位取反,补码时dafa01】仁loooooooo.dataill。硼si印din-abs=(dill【7】)?{l,bO,din【6:O】):din∥如果补码则是9.blo0000000—din4.平方累加器。需要平方累加器的使能信号。用顶层模块计数器产生。使用ipcore,乘法累加器实现。这种方法存在的问题是:数据是连续的,本组数据输入完成以后,紧接着后面的数据就要进来,没有空余时间清理本组数据,所以16352个数据,取前16340个参加参数的计算,由使能信号控制。din_sel:输入的每桢前16340个IyJI。当avai=l,输入diLabs,否则输入0;鹊si印d嗵舅l=avai?dillJbs:8fboooooOoo;I酗40ma.—data:∑y?,防止上溢出,共32bit。高4bit是o,中间20b“整数位,低l8bit小数位。C1】c:工作时钟,就是系统时钟clear:平方累加器的清0信号,由使能产生模块产生;5.累加模块以平方累加模块方法类似,也是采用以上办法din.Sel:与平方累加模块相同。共8bil,bit7符号位,bit6~4整数位,bit3~o41 北京邮电大学硕He文第五章u)Pc编码的硬件实现小数位。Si印+absl甜404-data:∑Iy,J,防止上溢出,共32bit·高11bit是o,中间17bit整数位,l低4bit小数位。clk:工作时钟,就是系统时钟cle盯:平方累加器的清O信号,由使能产生模块产生;6./N求均值模块,本处N=16340。为保证精度,被除数需要扩位,低比特补O。rcg【31:0】ma』eg;reg[3l:O】are吕always@(posedgeclk)bcginif(rst)be西nma』g‘;0;j』eg<=0;cndel∞if(fach)be百nma_rel,<={ma』a_叫27:O】,4rboooO};a』g<-{4』砒a【20:o】,11’b00000000000);∞delsebeginma』乎=2ma』eg;aJreg<_aJ汜吕即d饥dMa』e毋32bit。{Ma-da眦27:O】,4’O).高20bit整数位,低12bit小数位。a-rrcg:32bit。{a_.data[20:0】,Il’bO}。高17bit整数位,低15bit小数位I甜柏16340以上两个信号在做ch信号指示下,存入计算完成的∑拜和∑I儿I。 北京邮电人学硕士论文第五章LDPC编码的硬件实现ldi订e衄data{di记eadat8em血ta:脚』eg/N=E(J,;).32bit.高14bit是o,小数位。eadata:marcg,N=E(I,,D。32bit.高14bit是0,小数位。14’h3FD4=163407.平方模块,采用乘法器SaUaIe中间6bit整数位,低12bit中间3bit整数位,低15bituu呐ua喊.d眦缸ea-da协【17:O】),.datab(ea-data【17:O】),.代刚“squ姗data));d北培:datab:cadata[17:O】.只取有效为参与计算.rcsuJt(squaredata).E2(Iy,I)。36bit.高6bit整数位,低30bit小数位。8.除法模块,采用除法器,为保证精度,被除数低位补O;补O程序:rcg[39:0】s∞rc吕reg【55:O】锄arcg;al、张ys@(poscdgec墩)beg.mi坟rsObeg.m锄areg‘20;s翩L托g(=O;endelse。begill锄u.eg<={锄a-d州17:O],38.110000000000);sea』g<_{squa吼data,4.b()ooO);end43 北京邮电大学硕士论文第五章LDPc编码的硬件实现end除法器程序divuut—diV(.n啪e“锄a』曲,.denom(sea』曲,.quoti∞t(qq),.r锄ain(r));n啪盯:f锄a.data[17:0】,38-bO)高6整数位,低50小数位deIlom:{square-data,4rb0)。高6整数位,低34小数位quoti印t,:低16bit小数位,bitl6是l,其余bit是OZ=QuotieIlt[16:6】9.由z求系数P=扩Z+z.卜b4Z+c本模块采用查表法,z集中在1.2~1.6之间。精度1/2n8.要把这些数转化为2进制,需要乘以2—10,所以z需要10bic小数位,1bjt整数位。输出p含有4bit整数位,12bit小数位Z劬m1lfbl0011001100to11-b110011001lOassi印addFZ-11tbl0011001100;rDmuut—rom(.addr(addr),.clk(clk),.dou“para))addr:只读rom地址,根据z的值作为地址求出para。Para:2/占2lO.乘法器llr(yi)=fi矗).out+pamalways@Qoscdgedk)beginif∞t)pararcg<=o;clseif【fillish)pamreg<=(p盯a};e】sep啦reg(==pam他吕endmulL6nal1nnmult-fiml(.data£oamreg),.datab(6f.o』ut[6:O】),.rcsult(dout—abs));p卸iJeg:当fiIlish=1时,将pam存入pamrcg;fi随out【6:0】:从fifo中输出的原来的数,因为是符号+绝对值,所以取绝对值参与乘法。Doutabs:LLR估计结果的绝对值。 北京邮电大学硕士论文第五章LDPC编码的硬件实现11.截取译码需要7bit。最高位符号位,与fifoout最高位相同;整数位3bit,判断DouLabs的整数位,大于等于7时,取7,,J、于7时fi札out【18:16】;小数位3bit,fif咖ut【15:13】私si印猢司out^曲s【22:19】;船signdo叫aaa刮fb0000)?(fi如ut【7】,douLabs【18:13】):狮fo.JDut【7】,3fblll,dout_-abs【15:13】);本设计特别要注意本组数据一定要与本组系数对应上,相乘的时候一定要同步,在项层模块中生成几个同步信号,可以由计数器产生。保证每一组数据只取前16340个数据参与参数计算。剩下12拍用于计算。下一个桢同步信号来时将参数与FIF0输出数据相乘。5.13结果分析结果分析:分别取R寻1,0.5。E州O=o,O.5,l,1.5,2.。十组数据,每组数据10桢。导入matlab生成的测试向量,经过moddsiln仿真,然后与matlab仿真的数据进行比较1.R=1/2Eb/No=司2.R=1/2Eb,No=劬.5Pa珀=2/si锄a“2:(mallab)(modelsinl)1.9007ll1.89921.9061501.89922肿89“1.99391.8571111.830l1.9714321.94601.7609331.76321.8305061.80761.7813721.76321.7874041.78541.9794941.970010桢平均误差(误差要小于O.125)0.0903Pam=2/si鲫a^2:(manab)(modclsiIn)2.1456102.14262.1755742.16822.0854172.06742.1237442.11742.1846862.16822.0382882.04272.2036502.19412.1437562.11742.1248612.11742.1179752.1174lO桢平均误差(误差要小于O.125) 北京邮电大学硕士论文第五章LDPc编码的硬件实现3.R-1/2Eb肘o:l(matlab)2.4358672.4690342.5122182.26390l2.4307192.4824662.3658202.6392962.3790“2.378302(modeIsim)2.43602.464l2.49222.24612.40822.464l2.35332.63702.38062.380610桢平均误差(误差要小于O.125)O.08195.R=l,2Eb/N伽-2Para.2/si舯a^2:(maflab)(modelsim)3.22373l3.205l3.1752ll3.17163.2018773.20513.1594773.13843.0946503.07253.1286263.13843.1689423.13843.2573493.23903.2713523.23903.2555803.239010桢平均误差(误差要小于O.125)0.1023O.07414,R=l/2El悄O=1.5Pam=2/sigma^2(matlab)2.7189112.75991l2.7791202.7952352.8723292.5534862.6414872.6948292.6496512.786098(modelsim)2.69632.75682.75682.75682.88042.52082.63702.66652.63702.756810桢平均误差(误差要小于0.125)0.09656.R=lEb,No==oPa功=2/si弘l{p2:(manab)(fnodclsim)1.93396l1.92241.9713671.94601.9349091.92241.8158041.80761.8687791.87601.9468791.92242.0207971.99391.9558731.94601.9203001.89921.8376641.830110桢平均误差(误差要小于O.125)O.0914 北京邮电大学硕上论文第五章LDPc编码的硬件实现7.R=lEb小O=o.5Pam=2/si舯a^2:(matlab)(modelsim)1.92660l1.92242.1511922.14262.0328802.01811.7850451.76321.9085171.89922.0053051.99392.0126732.01811.9087841.89921.8931851.87601.9298701.922410桢平均误差(误差要小于O.125)O.07879.R=lEb/NO=1.5P锄=2/sigma^2:(matlab)(modclsh)2.1566452.14262.1212552.11742.2939582.29932.2759252.27272.3024702.29932.3823522_38062.2213332.22002.26220l2.24612.1675012.16822.23lOOO2.2200lO桢平均误差(误差要小于O.125)0.07468.R=lEb/NO=lPa拍=2/si肿a^2:(matlab)(model咖1)2.1420702.11742.3454ll2.32622.2221972.194l2.1208642.11742.0574732.04272.2201732.194l2.0910422.06742.16786l2.16822.1343312.11741.9805141.970010桢平均误差(误差要小于O.125)O.0847lO.R=1Eb,No:2P鼬-2/sigma^2:(matlab)(modelsim)2.4519352.43602.5129932.49222.2679812.246l2.3663052.35332r3750182.35332.5334022.52082.3538992.35332.4536382.43602.3465052.32622.4263342.408210桢平均误差(误差要小于O.125)0.0774 北京邮电大学硕士论文第五章LDPc编码的硬件实现由结果可知误差在可承受范围内。另外,在除法器的使用上应该注意,xilinx的触发器使用移位减法实现,所以时延较长。本设计使用的是altera的芯片,除法器使用级数展开的方法算出,时延较短。本设计的运算处理时间不满足xili腿除法器的时延要求,如果要用)【ilinx芯片,则每一桢数据的样本需要减少,以保留更多时间用于计算。5.2LDPC编码器的设计与实现5.2.1理论基础设K为信息比特,M为校验比特,N为编码后的比特,线性分子码中N=【KM】,G为生成矩阵,H为校验矩阵,K·G:.N,H-N7=o,H矩阵是一个m×n阵,分解为m×k阵凰,m×m阵H,。【HIH2】×[KM】7=O,HlK7=H2M7求出M7=H2“HlK7根据H矩阵和信息比特可求出校验比特,进而求出编码后的比特。·校验矩阵是关键,采用l/2码率,k=511×16,m=5ll×16,n-5ll×32。·H.矩阵由256个51l×51l的子矩阵构成,这16×16个子矩阵构成的矩阵中每行有4个非0阵,每列有4个非O阵,共64个非O矩阵,其余矩阵为O阵。对单个非O阵,是由单位矩阵通过行列置换得到。·H,矩阵也是一个16×16个子矩阵构成的矩阵,对角线上的子矩阵是下三角阵,其余子矩阵为0阵。如图5.2所示,H.矩阵由单位矩阵构造而成,结构如下阴影部分是单位矩阵通过列变换生成的新矩阵,这些矩阵互不相同。白色部分为O矩阵。这样做目的是使H1矩阵中l的分布满足随机性,最大限度减少3.3.3中影响译码性能的环的出现,保证性能足够优秀。 北京邮电大学硕士论文第五章LDPc编码的硬件实现图52Hl矩阵结构图如前3_3.1所示,校验矩阵的校验部分采用下三角阵,在DⅦ.s2标准中本图中整个矩阵的下半部分都是全一阵。为了减轻码重,降低复杂度,在DvB.TH中仅仅在本图中阴影部分保留全一阵。 北京邮电大学硕士论文第五章LDPc编码的硬件实现▲L▲kLLLLkLLkkLL▲图5.3H2矩阵结构图5.2.2LDPc编码模块的设计和实现输入511×16:8176比特待编码的信息数据,在输入本组信息比特的同时处理上一组数据,并且输出以前已经处理好的数据。所以假设信息比特码率为R输出的编码后数据码率为2R处理数据时考虑到时延问题码率提高到2.5R。由于校验矩阵本身比较复杂,所以实现起来消耗的硬件资源比较多。总共用了两个长度8176、位宽l比特的双口RAM(RAMll,RAMl2);80个长度为51l、位宽l比特的双口RAM(RAM20l~凡蝴216,RAM30l~RAMl5);一个长度为16352、位宽l比特的FⅢO。具体设计框图如下 北京邮电大学硕士论文第五章LDpc编码的硬件实现图5.4LDPC编码设计框图·使能生成模块:生成各个模块需要的使能信号波形方针如下:5l 北京邮电大学硕上论文第五章LDPc编码的硬件实现1珥)ut:rst:复位信号dkl:与输入数据同步时钟cll(2:生成校验比特的时钟,频率是clkl的2.5倍clk3:读出编码后数据的时钟,频率是clkl的2倍output:∞船m11_、盯’朋阳m12_、w数据读入的两个RAM的写使能印r锄11rd,胁舢12rd:数据读入的两个RAM的读使能∞mrrl20lwT~∞砌1216w:信息编码的64个I认M的写使能∞舢20lr;d~锄船11216rd:信息编码的64个RAM的读使能m础301盯一∞脚11315盯:校验编码的15个R八M的写使能∞恤T1301rd~∞r锄315rd:校验编码的15个RAM的读使能锄右fo耵:编码输出的FIFO写使能∞fiford:编码输出的FIFO读使能·地址生成模块生成数据读入模块r锄1l,r锄12的读写地址,在读写使能等于1时,地址信号累加,如波形图所是。 北京邮电大学硕上论文第五章LDPC编码的硬件实现addrr锄ll、花舢11写地址:addrr锄12wr:mml2写地址:addr舳11rd:锄ll读地址:addrmml2rd:r锄12读地址:信息编码模块,使用ram201—翻m2“.写入地址在写使能有效时累加,读出地址是一个伪随机序列,起到交织编码的作用.每4个ram公用一个写使能,公用一个写地址。addr珊n201、Ⅳ卜addrraIIl216盯:mIl20l~ram264写地址:addrmm201rd—addrralll2“I.d:m120l~眦11264读地址:以某一组为例姗20l—彻m264同时读出数据,读地址随机序列,下图以ram20l—fam213为例校验编码与输出校验比特模块使用r锄30lol5,起到缓存的作用,写使能公用曲瑚m3J盯,所以公用写地址addrmm3-、vr。15个姗依次读出,他们的读使能依次有效,读地址从O累加到511,分别为addr』锄30l—一~addr咖315-一。 北京邮电大学硕¨仑文第五章LDPC编码的硬件实现以addrram305rd为例,如下图·数据读入模块使用两个双口RAM,ramll和r锄12,采用乒乓操作,一块砌存入数据,另一个ra|Il读出已经存入的上一组数据。作用是缓存数据,采用异步操作,保证数据安全。r锄ll硼。锄1l(.add嘣addrr锄ll-、呐,.dina(din),.wea(1rbl)'.饥a(∞锄11J哪,.clka(c岫),.addlb(addrr锄l1—rd),.eIlb(朗姗11-rd),.dkb(cll【2),.doutb(r锄11_dout),.siIlita(璐t),.siIlilb(rst));raml21nnr帅12(.addra(addrnmll2—wr),.dina(din),.wea(1fbl),.朗a(即r锄12J盯),.clka(clkl),.addrb(addu’锄12—rd),.e11b㈣r啪l2-rd),.clkb(clk2),.doutb(r锄12_dout),.sinita(rst),.s“tb(rst));·信息编码模块使用64块双口RAM,埘1120l—伸m2“.输入数据为数据读入模块的输出数据。读写同步操作,使用clIC2。Hl矩阵如图5.2所示,第一行从左到右命名为埘11201—伯m204,第二行从左到右为埘n205叶am208,其余命名以此类推。∞瑚11201wr.addr埘n201w表示存入第一组511个数据,对应矩阵第一列的衄201,r锄209,mrn229,触257。这四个姗公用∞衄11201wT.addrram20l、】盯作为写使能和写地址。其余列类似。读出时,在翱ram2rd有效时64个舢同时读出,读地址是一个随机序列,周期511,起到交织编码的作用。R锄l'mm2,r锄3—m4这4个mm的输出再相加,其余行的4个ram也采用这样的操作。共输出16路数据。·校验编码与输出校验比特模块校验编码矩阵相乘等效于信息编码模块16路输出每一路数据时延一拍以后再与自己相加舢300din《=ram300di玎+Tam20ldout竹锄1202dout+ 北京邮电大学硕士论文第五章LDPC编码的硬件实现撇1203-dout-呐m204-dout;船111301_din<=舢30l_diIl竹am205_dout竹anl20tdout+姗207dout.P珊11208_dout;埘11315_dirl<:=raIIl315_din+瑚1261』out奸姐262_douc+瑚n263-dout+r锄12“jout;由于16路数据同时需要输出,所以将瑚1300diIl首先输出到编码后数据输出模块,同时将其余15路存入RAM301015共15个RAM。输出姗300din以后再将其余15个RAM数据按顺序依次输出。·编码后数据输出模块使用一个长为16352的FIFo,读写使能如图所示tifouut』颤.d叫丘鲫岫,.1)1.r∞(目_矗)_、耵),.町-clk(cll(2),.州皿』fo-_rd),.rd』lk(cll【3),.dout(dout),.aillit(rst));,fifo首先在信息编码模块输入511×16bits信息位的时候,将信息比特存入FIF0,然后存入ralll300din,最后存入其余15个RAM数据按顺序依次输出。F球。在cll【3驱动下源源不断读出编码后比特流,所以读使能enfi白rd=1. 北京邮电丈学硕士论文第六章结论々展单第六章结论与展望LDPc码是作为一种新的编码方式,由于其校验矩阵具有稀疏的特点,使得它的译码复杂度与码长呈线性的关系,而性能却很接近sh蛐on的极限,所以得到了人们更多的注意。本文在对LDPC码进行研究的时候,主要完成了以下几个方面:首先从校验矩阵和二分图两个方面介绍了LDPc码的定义,以及LDPc码的分类和优缺点;然后介绍了LDPc码的结构及其编码思想,给出了LDPc码的一些原始构造方法,并根据u)Pc码的特点及目前LDPc码编码时存在的缺点,设计了基于单位矩阵的LDPc码,该构造方式利用了分组交织器,使得构造出来的LDPC码含有很少的环,提高了码的性能。另外,u)Pc码与其他技术的结合也是近几年的一个研究热点,比方说与0FDM结合,与空时码结合。空时分组码具有高分集增益的特点,而LDPC码具有高编码增益的特点,所以把二者结合起来,也成为LDPc码的研究重点。LDPC码是信道编码技术发展的一个新的里程碑,它以卓越的性能和线性的译码方法,得到了人们的广泛重视,它的出现,必将为第四代移动通信技术带来新的发展。 北京邮电大学硕上论文参考文献【2】【3】【4】[5】【6】【7】【8】[9】[10】【11】【12】【13】参考文献RobcrtJ.McEliece.1k11l∞ryOfhlf011Ilati∞锄dCodin辱Addis∞一Wesley,Reading,M气1977.C.E.Sh删lon,AM砒锄atical111eoryofCommunjcation,BellSyst锄1砒.J.,v01.27,pp.379屯3,Jul弘1948I乙WHa删嘶ng.EnDrDetec曲g锄dErrorCo盯I埘iIlgCod髓.BdlSyst锄Tech.J.,vol_29,pp.147·160,l950.P卸lC.H铘hey,NtllonyEphf锄id部,andR锄kl(1l撕乱Pe面肌衄∞ofRs·BcHconcm猢tcdcod嚣缸dBcHsin画e-stagecod鹤on缸hltafc瑚ceSatclliteC11黝c1.IEEE№actio鹏∞Commullicado邺.V01.Com-35,NO.5,May1987,p550-556.J.Viterbi.EnwBo岫dsofC∞volutionalCod铭锄d锄舡yIllpIoticallyoptilll啪DecodingAJgo一ⅡlI玛IEEETrallsacti阻0IlIIlfoⅡnatioIL111e0Ⅸv01.13,pp.260-269,1967.CzUngeIboeckCll锄dCoding、vimMllltil“el/Pha∞Si印alin吕IEEETmsacti∞.011IIlfo册ati∞.Th鳅y'25(1):55-67,J吼1982.正EESt锄dard802.1la.1999.Partll:WirelessLANMedilⅡnAcc鼯sCofIⅡol(MAC)andPhysi∞lLayef(P啪Specificatio衄Higll-specdPhysicalLay盯inthe5GHzBm也RudigerUrbanl【e.Mod锄CodiIl911beory.EPFLDSC—LTHC,Jun鼯,2001.GD.Fom吼ConcatenatedCod髂.PhD111嚣is,M皿1966.C.B㈣u,A.Glavie暇,觚dP11litiIIlajshilna.Ne盯Sha曲onLiⅡ血E玎0r_Co眦6ngCoding锄dDccodillg:T讨bo·COdcs.IEEEICC’93,G%“a,Switz甜锄d,May93,pp.1064-1070.DaIl’R印11aeli,M锄b%IEEE,andYo锄Z删.C伽曲iIledTu曲oEqllalizationandTIlrboDecod抽吕IEEECommuIlicatio璐.Lc肚ers,、,01.2,No.4,A砸11998,p107一109.Qin曲llaLi,)(iaodongWan岛锄dCost勰N.Ge0喇ad鹤.TurboMulti璐crDet∞Ⅱonfor1、Irbo—CodedCDMAiIlMultipatllFadingCh枷els.IEEE协actionsonⅥ蛳cIll盯1砒nology,v01.51,No.5,S印.2002,p1096—1108.WilleIleggerSerge.cdma2000PhysicalLayer:AnoveⅣiew.Joumalof 北京邮屯大学硕}论文参考文献【14】【15】[16】【17】【18】【19】【20】【2l】【22】【23】[24】[25】【26】ColllIn血c撕om孤dNet、vorks,2000,2(1):5-17N.Wibe吗H.A.Loelig%andR.KBt眦Cod鹤andItcraliveDecodingonG锄eralEuro.Tmsactions.Teleco衄.V01.6,pp.513-525,1995.D.J.C.MacKay.GoodEITor.Co嗽曲gCod铝B笛cdonV哪Spa稻eMa砸c%,IEEEillfo.111eoⅨv01.IT45,pp.399—43l,M矾m1999.R.GGal】ag既Low-DcIls时P鲥妒CheckCod岛.Ⅱ也Tr趾sactio璐∞Illf.0肋ation111∞Ⅸpp2l-28,J锄.1962.R.GGall4孵Low—DellsityParity-CheckCodes.C锄晰dge,MaSsachllsetts:M.U:Press.1963.D.J.C.Mackay'Good㈣r-c0盯cctingcod髓b够edonveryspar∞m删c∞,IEEETr哪.onhforInalionllle0Ⅸv01.45,March1999:399-43l【^lby’Mi乜锄ach%Shohollalli卸d咖.Anal”isof10wdeIls时cod鼯锄diIllproVcddesi印s懈ingirregIllar伊aphs【J】,illProc30tllA衄u.AcMsylIlpTheoryofComportin舀1998:249—258T.砌chardsoll,A.Shoh01lallia11dR.Urballl【e.Desi印ofpmV如lygoodlow.dens时p撕ty-checkcod鼯.IEEEInt锄a石onalSymposi啪on111fjnllation111e0ⅨJllIle2000:199S静YouIlgChun岛PHDlll鼯is:0Ilt11eCo鹏眦ionofSomeCapad咿ApproachiIlgCodingSch咖铬,M珥S印t,2000B胁L屿ⅪaodongW抽岛K—shnaR.NarayaIlamLDPC·B硒cdSpaceTimeCodedOFDMSystemsoV盯Co册latedFadingCh跚els:PerfbrIIl锄ceAnalysisandReceiverDesi印.IEEETr锄.OnCommunicaliom,、,01.50,NO.1,J锄mry2002:74—88MarcPc.Foss耐盯,MiodmgMihaUe“c锄dHideI【iImai.RcduccdC0mplcx时Itera廿veDecodingofL0w-Defls时P撕tyCllockcod嚣B嬲ed∞BdicfPropag撕on.IEEE胁acti咄∞Comm眦icatio邶,v01.47,no.5,May1999,pp.673·680D.J.C.MackLy’SilmonT.、聃lson粕dM.C.Davey.ComparisonofConsnllctio璐ofIn哪!arGallagefCodes.IEEETransactionsoncoI姗u血catio邶,voI47,no10,oct1999,pp.1449-1454.M.Q【mby,M.Mitze衄ach%M.A.Shokroll枷,觚dD.A.Spidm锄.PracticalLoss-resilli肌tCodes.IIlProceedingsofthe29ⅦA加ualSyTnposi啪on111eoryofComputin昌pp.150-159,1997.VladislavSomkine,F砌11l【R.1(sdlischangandSubbPasupathy.58 北京邮电大学硕士论文参考文献【27】【28】【29】【30】GaUag盯Codesf-orCDMAApplicatioIls—PanI:Gellefal也ations,CO邶仃uctioI硌.锄dPerfo埘旧nceBounds.IEEE1hnsacti咖onCon如unicatiom,V01.48,∞.10,Oct2000,pp.1660一1668.En四ingY的,Pay锄PaI【zad,BorivojeNil【olic锄d‰tAnantIl咖.Hi曲lllmugllputLow-de邶nyP撕妒checkDcood盯觚Ilitoctu-瞄.G10bec锄2001,No.1,Nov200l,pp.3019—3024.http://www.n耐on.oonl,products/、,ectoLasphtIp://www.vocal.com,press-rde船e/020212bpr.htnl.ETsIEN302307V1.1.1(200伽6),Eufope觚St锄dard(Telccommunicatioms耐cs),Di百talⅥdcoBroadc嬲廿ng(DⅦ):SecondgeIl训ion劬ming灿ctll】rc’ch锄c1codillgandmodulationsyst锄sforBroadc丛tiIlg,ImeractiVeS盯vic器,NewsGam萌ng锄domerbroa曲觚dsatelliteaplpli硎。璐.【3l】The111t咖atioIlalFon蛐∞FutureMobile1’elecomm岫icatio∞&China_EUPostCon胁瑚∞Beyond3Gs111eHi曲TechnologyRe∞arch锄dDevdopmemC∞tefofMOsT(Hn①C)兀r兀yREC00rdiIlationco珊lllitt∞of863Pro孽am(FuTURE)’Con胁1ccproc∞dings,Nov.20一22,2002,B蜘in吕C址眦【32】RM.T觚n乱AR。cursivcApproachtoLowC0mpl既时Cod器.IEEETr锄sacti咄Onh面姗ati∞.n∞Ⅸvol27,pp.533·547,Sept.1981.【33】M.GLuby'M.Mitz黜nach盯,M.A.Sbokrollah'D.A.Spiellll粗.hIlprovedlow-de∞毋P撕t州leckCod馏UsillgI丌e删l缸Gmplls,h怕血ation111co哆IEEETm璐actio璐on’v01.47,Issue2,pp.585—598tF曲2001.【34】T.鼬chardson.M.shohollalli,锄dR.uI=baIl】ce.D∞i印ofC印acityApp∞achillgIrregIllarLclw-D黜时P撕ty-Cllec.kCod髓”.IEEETra邶actio璐onIIlfb胁ationTh。0哆V01.47.pp.619-637.Feb.2001【35】RGGallag瓯Low.D锄ityParity—C11eckCod舒【J】mETr锄sIIlfomation111e0Ⅸ仃-8,no.1,J卸uary1962:21·28【36】M.Len咖aier锄dkS.zigaIlfimv,”ongeneralizcdlow·denS竹p耐ty-checkcodesb鹤edH锄ⅢdI培componemcod嚣.Aug鸺t1999lEEECo删叭micationLctt既v01.3.orⅡlo.pp.248-250,【37】J.Boutro璐,O.Potlli%andQZemor'GeneralizedlowdeIls时(Ta衄哪codesinProc.ICC99,HoustoIl'.Tulv1999[38】J.Ros翎thalaIldP.O.Vontobd.Consnllctio邶ofLDPCcodesusing 北京邮电大学硕上论文参考文献【39】【40】【42】R锄柚uj锄graphs觚did馏丘omM缸苫ul舯rocccdingsof38t11AllatonCon胁lceonCommIlIlicatioIlsCon仃ol孤dComputin昌Octobcr2000卢开澄,卢华明.组合数学.北京:清华大学出版社,2002nlom笛J.鼬chardsonandRudigerL.UrbarIke.EmcientEncodingofLow.D∞sityP捌似CheckCod髓.IEEETramactio璐Onhlf0彻ationThe0哆、b1.47,NO.2,pp.638-656,Febnlary200l“SNRMismatch锄d0同i∞EstimationiIlT1lrb0Decodin岔’ToddA.SuInme瑁mldsteph∞GWilson,M锄ber,IEEE1'm衄actiollsonCommuIlicatio∞,Vbl.46,N0.4,Ap—l】998 北京邮电大学硕+论文致谢致谢我在两年半的研究生的学习中,得到信息论教研室老师和同学们非常大的帮助,在此首先表示衷心的感谢。首先对我的导师吴文礼教授表示诚挚的谢意。在攻读硕士的两年半时间里,吴老师在我的学习和研究工作中始终给予我大力支持和悉心指导。吴老师渊博的知识、开拓的思路、孜孜不倦的精神和严谨的治学态度以及执著的敬业精神深深地感染了我,在此表示衷心地感谢。感谢信息论教研室的林家儒教授、吴晓非教授、马会明老师、牛凯老师、贺志强老师、别志松博士、梁栋博士等诸位老师和学长长期以来对我在学习生活、项目工作等各方面的支持和指导。感谢我的各位同学,特别是在微散项目组的师兄师姐和同学,同时,在课题的研究过程中,在项目组的讨论中,他们的思想和方法给我提供了许多新的思路,有了他们的帮助和支持,我学到很多知识。最后我要深切地感谢我的父母和女友陆清霞对我的支持。再次向所有帮助过我的人表示深深地感谢。6l LDPC编码的研究与硬件实现 作者: 唐启荣 学位授予单位: 北京邮电大学 本文链接:http://d.g.wanfangdata.com.cn/Thesis_Y1158769.aspx

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档

相关文档