LDPC编码的研究与硬件实现

北京邮电大学硕士学位论文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】PBPBased算法、APPBased算法等。5、结合实际工作，介绍LDPC编码的FPGA实现方法和LLR估计算法的FPGA实现方法。介绍了实际应用中编码的码矩阵特点，并提出针对性的实现方法，并用FPGA实现并作出modelsim仿真。关键词：LDPC码，Tallller图，稀疏矩阵构造，置信传播算法，FPGA北京邮电大学硕士论文摘要RESEARCHoFLDPCCoDINGANDDEVELoPMENToNHARDWAREABSTRACTShaIulonderel叩edf锄ousinterruptedchallIlelcodingtheoD，inl948UnderSh锄ontheory，moreandmorcchannelcodingmethodwhichareclosetoSh籼on1iIllitedarcdevelopedandusednowFro】moldmethodsuchasBCHcoding，Algebmcode，RScodeandconv01utionalcodingt0Tu曲codingandLDPC(10wdensityparitycheckcodes)coding，thec印abilityisgetclosetosh锄onlimitedLor-D即sityParity-Check(LDPC)Codesareacl嬲sofch籼elcodesbasedongrapllsanditemtivedecodingwhosepeffb皿anceisVeryclosetotheShaIlnon1inlitwithlowcomplex时aIldhavestrongerrorcon仃olstren昏hInthisdissertation，t11ethcorydesignandapplicationofLDPCcodcsarestudied，whichinvolveSblockcodesprinciples，codestmctIlre，decoding，constmctionofsparsep撕tycheckmatrix，densi够evolutionand印plicationsofLDPCcodes111isanicleprovidcmethodstodevcl叩itbasedonFPGA111eminworkSandi衄oVatioIlsare勰f01lows：1The如nd锄entalsOfinfomationtlleorychannelcodingandthedevelopmentfromtheo可t0practiceofch锄elcodingarcgcneratedAndtheintroductionofShannonchannelcodingtheoIyandchannelcodingmemodsclosedtoSha肌onlimited，especiallymedeVelopofLDPCcoding2ThestructurcofLDPCcodesisstudiedBasedonttlematrixrepresentation，T撇erdegreedistributionofLDPCcodes，meparametersofi玎egular觚dregularcodcsaredeflned3Researchtheconstmctionoflowdesitypatitymat血fromLDPCcodes，includingi仃egularalldrcgularcodesThisarticlein仃oduceGallager，BIBDandMackaymethodsandalsoirregularmethodAccordiI培topanice，italsointroducesscveralpmcticalmethods，suchas北京邮电大学硕论文摘要subtrianglemethod，rotational石methoda11dunitmatrixmethod4ThedecodingofLDPCcodesisstudiedHarddesitiondecodingisstudiedBasedontheprobabili哆domainandtheloglikelihoodratiodomainofBPdecodingofLDPCcodes，themodifiedBPdecodingalgorjthmsarepaidmoreattentionto，includingtheAPP：UMPBP-Based，APPBasedal窟orithms5Accordingtopmcticalwo咄thedevelopofLDPCcodingandLLRevaluationindecodingusingFPGAareintroduccdTllestmctureofpmcticalmatrixa11dhowtomakeittoFPGAchipareshownandModelsimsirnulationKeywOrds：Low-Dens时Pari妒CheckCodes，Tanncr鲫h，sparSeparity-checkmatrix，BeliefPropagation，FieldprDgramma【blegatesamy独创性(或创新性)声明本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名：唐宙&日期：兰竺隍塑塑关于论文使用授权的说明学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。(保密的学位论文在解密后遵守此规定)保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论文注释：本学位论文不属于保密范围，本人签名：麈笸整导师签名：誓秦弓扩，jL叭戎l】，tot适用本授权书。日期：竺生塑整望日期：垫监兰墨整旦北京邮电大学硕士论文第章绪论第一章绪论11Shannon信道编码定理假设一个通信系统，信源序列【，=(U，u：，以)，各个分量是统计独立同分布的随机变量，取自有9个符号的集合。设)(-(五，五，以)是相应的信道输入，Y气E，E，E)是信道的输出，而【，=(Ul，u2，【，。)是接收者根据Y对U的估计。对此系统传输质量的要求是对所有的i，有P(U，U，)c系统，则最终错误概率占巧(1一云)o(16)即当速率高于信道容量时不能实现可靠通信。而在速率R小于信道容量c时，Sh锄on指出，可以通过编码来实现任意可靠(占是任意小的数)的通信，称为信道编码定理【I】描述如下：每个信道具有确定的信道容量c。对于任意占O和R11k，码率，1一竺。构造一个维数为mn的矩阵H，通过高斯消元法将其变成如下形式E，=【月一言月一I)尸；H】(22)如果H是满秩的，变换后不存在全O的行。由以上变换可以得到系统形式的生成矩阵G=【只加圳，。】，信息序列“=【“。，“：，】通过c=IlG映射为码字c。虽然H是稀疏的，但是矩阵P通常不是稀疏的，编码过程中需要存储P的元素，存储6北京邮电大学硕士论文第二章LDPc码的结构量较大。同时，编码的运算量是码长的二次方的形式，在码长较大时。需要采取措施降低复杂度。212Ta肌er图表示除了用校验矩阵表示LDPC以外，还可以用双向的图模型表示u)Pc码l。T姐n盯图”4是一种双向图，可以用G=E)表示，其中v是节点的集合，矿=U以是维数为mn的校验矩阵，=(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图如图21所示，具有10个变量节点和5个校验节点，每个变量节点都有2条边，每个校验节点都有4条边。c1c2c3c4c5blb2b3b4b5b6b7b8b9b10图21校验矩阵的Tann目图表示213度的表示点变量节点U)PC码的校验矩阵和Ta皿er图是等价的，对应的是一个LDPC码C，而一个LDPC码的集合可以用度数分布或码生成函数表示。设最大变量节点的度为7北京邮电大学硕L论文第二章LDPc码的结构d，最大校验节点度数为d。；丑(n)表示与度数为i2的变量(校验)节点相连的边数在总的边数中所占的比例，由此构造多项式正A(工)=丑工“三2(23)p(J)=岛工“1，一2其中A(1)=p(1)=1。五(J)，户(石)称为度数分布或码生成函数。设总边数目为E，度数为i的变量(校验)节点占总变量(校验)节点的比例为口，(6)。如变量节点数为n，校验节点数为m，则有五，=!：!：!E岛：翟兰(24)岛。jU唧由于q=l，6f=1拈嘉2嘉2高2高但5)铲筹：生(26)q2参2商2。6参2嚣伍7)同时可知码率为，：l一竺：1一二I!：!兰(28)以jA(J)出一因此，码长n，度数分布旯(J)，p(工)决定了码率和校验方程的个数，对应的是一个码的集合，记为c“(A，p)。满足度数分布五(J)，p(x)的校验矩阵有很多个，不同的构造方式得到的校验矩阵的性能是不同的，有关矩阵构造问题在第三章中讨北京邮电大学硕上论文第二章LDPc码的结构22规则LDPC码和非规则LDPC码如果校验矩阵的各行中非零元素的个数是相同的，各列中非零元素的个数也是相同的，此时LDPC码为规则码。此时，伽ner图中所有变量节点具有相同的度d，所有校验节点具有相同的度t。此时，其度数分布为纵曲爿?-I从而=一1、总边数E=耐，=耐。(210)码率为，：尘竺：l一竺：1一拿(211)万一4。与规则码对照，如果校验矩阵的各行中非零元素的个数是不相同的，各列非零元素的个数也是不相同的，此时LDPC码为非规则码非规则码的结构由其数分布决定，式(212)是度数分布为A(工)=O4工+O6工2，以功=O缸2+O4，的非规则码的校验矩阵，下图22是其T趾n盯图。日=blb2b3b4b5b6b7b8b9b10b11b12图22一种非规则码的Ta衄日图9节点变量节点(212)1OOOOOO1lOOOO1lO1O1l1O0O0OOO1OO1OlOOOOOO1OlOl1OOlOOOO1O1OOOOOOlOO1OOOlOOOOOlOOO1OOOOOOOllOOOOlOlOOOOOlOOlOOO北京邮电大学硕士论文第二章LDPc码的结构23规则码和非规则码的性能比较通过仔细选择码的度数分布，非规则码的性能比规则码的有较大的提高，采用优化度数分布的非规则u)Pc码的性能已经超过了1I】rbo码。非规则码的性能优于规则码，可以从LDPC码的译码过程解释p4。U)PC码的译码是一种Ta盯图上的置信传播算法，有关比特为O或l的置信消息在节点上处理后沿着校验节点和变量节点之间的边传递。初始时，变量节点接收信道传送的初始消息，每一个校验节点收集与其相邻的变量节点的外部消息，处理后传向与其相邻的变量节点：然后进行变量消息的处理，每一个变量节点收集所有的消息后进行判决，如不能正确译码且没有达到最大迭代次数，则将外部消息再传回与其相邻的校验节点继续迭代。下图是规则码的译码过程示意图。如第一次迭代的校验消息处理时，校验节点cl传向变量节点b1的消息是来自与cl相邻的变量节点b2b3，b4，不包括b1传向c1的消息。然后进行变量消息的处理，如变量节点b1收集初始消息及从校验节点c1c2传来的消息，处理后进行判决。所有的变量节点判决后，如译码错误，则变量节点继续将外部消息传递给与其相邻的校验节点。如bl传给cl的消息来自初始消息和c2，不包括上次cl传给bl的消息。这个消息传递过程一直进行，直到正确译码或达到最大迭代次数。因此，译码时，从变量节点的观点来看，与之相连的校验节点越多越好，变量节点的度数越大，它就能从更多的相邻校验节点处得到更多的置信信息，可以更加准确的判断出它的正确值：但从校验节点的观点看，恰恰相反，与校验节点相邻的变量节初始消息点越少越好，校验节点的度数越小，它能给相邻的变量节10北京邮电大学硕士论文第二章LDPc码的结构变量消处理初识消息b10图23规则码的译码过程示意图点提供的消息置信度越高。由于变量节点和校验节点具有相同的总的边数，故对于这两种矛盾的要求，非规则码可以更灵活地实现折衷。在非规则码的译码过程中，度数高的变量节点接收到的置信消息多，迅速实现正确译码，它们可以给相邻的校验节点传送更加有效的信息，而这些校验节点又可以给与它们相邻的度数更小的变量节点更多的信息，从而产生波浪效应。度数高的变量节点首先正确译码，接着是度数稍低的变量节点，然后是度数更低的，如此继续下去，直到译出所有的变量节点。24本章小结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码的结构。31规则LDPC码规则u)PC码是LDPC码中最简单的形式，早在1962年，Gallag盯就提出了其构造方法，但是限于当时的条件和人们认识的水平，这种码一直未受到人们的认可。多年以后，当LDPC码再次走进人们的视眼的时候，这种码的构造方法开始层出不穷，下面我们将着重介绍几种构造方法。311Gauager的构造方法1962年，Gallag盯在文献【3a中提出了一种构造(n，j，k)规则LDPc码的方法，我们把这种方法构造出来的u)PC码称为Gallag盯码。该方法的具体思想是：首先构造一个每列只有一个“1“，每行有k个“1”的子矩阵H。，然后对H。进行(j1)次随机的列置换，分别得到(j1)个子矩阵，利用这j个子矩阵得到校验矩阵H，这样得到的校验矩阵码长为n，行重为k，列重为j，其结构如下所示：日=日。刀2(乩)万(风)(31)其中I矩阵日。的列置换。下面我们给出一个(20，3，4)u)Pc码的矩阵形式，如图所示，从矩阵的结构我们可以更清楚地理解Gallager的构造方法。北京邮电大学硕t论文第三章LDPc码校验矩阵的构造110O0OO01O0OO0O0OOO0O0OO0O11l1O0OO0OOOO0OOOOOO011llOOOOO0O0O00OOO0OO1l11OOOOOOOOOOOOO0OOOOO1OOO1OOO1OOO1OOO1OO0lOO0lOOO000O10OO10OOO0OO10OO1OO0OOOlOOO0O11l1OOOOOOl000OO10OlOOlOOOOO00O1OOO1O1OO0OOllOOOO1OOO0010OOOO1OOO1OO0OlO0O1OOOOlO0OOO0lOO0O1OO0O1O0O00100OOl0O0OlO0OO1O0lO00O0O0lOOO0l00OOlOOO0l图31码长为20，列重为3，行重为4的正则码的校验矩阵对上述U)PC码，给定校验矩阵后，如果校验矩阵的行是线性无关的，那么编码的码率为l一姜，相反，若校验矩阵的行是线性相关的，那么编码的码率要大于l一车，也就是说，任何一个gallagcr码的码率都不会小于l一手。疗石312广义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，且要求Nn为一个整数；(2)该矩阵对应的列重为“1”、行重为k”：(3)为了使所生成的GLD码对应的校验矩阵中没有任何两个子码有多余一列的非零元素是重叠的，我们要求Nnn。有了构造矩阵H。以后，我们把H。作为子矩阵的块对角矩阵来形成第一个子矩阵1，该矩阵的行重和列重与矩阵风的相同；接着对1，进行a1)次列置换得到(j1)个子矩阵1，日2，日，最后把这j个子矩阵从上到下依次排列得出矩阵H，下图为广义LDPc码校验矩阵的结构图，其中石。(2茎fs，)代表一个随机的列置换(即对H，进行随机列置换)。1=风000O风OOOO风OOOO风日1日2=石2(日1)H3=乃(H1)H7=石J(日1)图32广义LDPC码校验矩阵的结构图313Mackay的构造方法Mackay在构造校验矩阵时，引入了一些重量为2的列来降低整个校验矩阵的重量，以减少Ta加盯图中循环的数量，由此减少译码算法受到圈的影响，但是引入重量为2的列会导致低重量码字的出现，需要采取措施减少其出现的概率。为此，Mackay给出了如下的构造方法“”构造法lA：对于MN的矩阵，我们可以随机地构造，使其列重为j(如j=3)。行重尽可能相同，且任意两列重叠的1的个数不大于l。图33给出了码率为l2，列重j=3的构造。北京邮电大学硕士论文第三章LDPc码校验矩阵的构造MoN图33码率为三，列重j=3的构造，、弋j图34构造法2A严生的矩阵构造法2A：利用该构造方法构造的校验矩阵，前些列列重为2，且这些列由两个Z等等的单位矩阵构成。如图24所示，任何一列中都没有重叠的“1”。剩余的(一警)列是随机构造的，其列重为3，每行l的个数尽可能一致，且整个矩阵中任意两列重叠的1的个数不大于1。图24为码率为13的码的构造结构。构造法1B和2B：分别从利用构造法lA和2A构造出来的矩阵中删除一小部分列，使得对应新矩阵的二分图中没有小于某个长度1(如1)的圈，这两种方法我们分别称之为1B和2B。314组合学构造法组合学构造法是一种基于组合数学中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)kcz产，d，(41)式中，b为第i次迭代的门限值，d，和d。分别为变量节点和校验节点的次数，其中，z，=l一2ng(_y，)=【半】【三r。适当地选择b，可使p，+。最小，若b，为使(42)不等式成立的最小整数，p。将取得最小值。业4燃r小1)一【l一(12pj)小1j”一如果算法应用于次数分布对为(五，p)的非规则码，则有结果肌-一纠，鼽1卜A“川-训氖7b钔川(43)式中，d，为变量节点的最大次数，6JJ为随节点和迭代次数变化而变化的门限值。使p，+-最小化的岛J是满足如下(44)式的最小的正整数。塑4掣r”(44)pollp(12pj)J、北京邮电大学硕士论文第四章LDPC码的译码42BP译码算法建立在Ta衄盯图上的LDPC码，其BP译码的每次迭代包括两步：校验节点的处理和变量节点的处理，可参照图23。在每次迭代中，所有校验节点从其相邻的变量节点处接收消息，处理后，再传回到相邻的变量节点然后所有的变量节点进行同样的过程。最后变量节点收集所有可以利用的消息进行判决。在LDPc码的译码过程中，每一个校验(或变量)节点可以看作是一个处理器，所有校验(或变量)节点的处理可以同时进行，因此利用并行结构可以构造高速LDPc码的译码器。但是，并行处理硬件电路面积大。相反，1urbo码的译码是串行的，对硬件电路要求低，而译码延时长。根据消息的表示形式，BP译码可以分为概率BP算法和LLRBP算法。概率BP算法的消息是用概率形式表示，是BP算法的通用形式，可以适用与非二进制的L【)Pc码的译码。而对二进制u)Pc码，消息可以表示为对数似然比形式，相应的译码算法称为LLRBP译码。421概率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的概率是寺+寺兀(12仇)，a中包含奇数个1的概率是寺一寺兀(12p。)扣l厶二t-lGallager定理：尸(c，=OIy，S)P(q=1Iy，墨)肛q，ecV由引理1，可知白(o)=丢+昙兀(12#)。(1)：昙+寻兀(12只，)在比特概率-，E、f-jE月UPF相互独立时，Gallager定理给出了后验概率”P的计算方法。根据引理1Gallager定理可改写为：P(c，=Oy，置)P(q=lly，墨)：半熙。，2F丽竹0的(o)=(1一只)兀“o)。一7码：|(47)(1)=暑兀州1)、因此，BP译码步骤总结如下(为表示方便，消息符号中的上标表示迭代次数)：初始化计算信道传递给变量节点的初始概率P。(1)，P(0)=l-P。(1)i=1，2，n。然后对每一个变量节点i和与其相邻的校验节点jc(i)，设定变量节点传向校验节点的初始消息黧卜：?(48)g(1)=只(1)、7迭代处理st印1校验节点消息处理对所有的校验节点j和与其相邻的变量节点iR(j)，第1次迭代时，计算第j个校验节点传向第i个变量节点的消息矧北京邮电大学硕士论文第四章LDPc码的译码巧o(o)=寺+寺兀(129铲(1)q。1l、7杈1)=1一o(o)=寺一寺兀(129矿(1)reR，st印2变量节点消息处理对所有的变量节点i和与其相邻的校验节点jC(i)，计算第i个变量节点传向第j个校验节点的消息衫(o)=岛只(o)兀嘴(o)。=”。(410)(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码，算法可以检测不正确的码字。422LLRBP算法如果概率消息用似然比表示，则得到LLRBP算法，大量的乘法运算可以变为加法从而减少运算时间。为此需要定义对数似然比(Lut)消息如下：信道勰消觚驴109器-log鬻搿校验节点传向变量节点的消觚俨109器变量节点传向校验节点的消觚-l。g嚣北京邮电大学硕士论文第四章LDPC码的译码变量节点收集到的所有消息工(吼)-l。g豢等(49)重写为l一2白(1)=l+兀(12(1)利用恒等式伽【111工=事；，伽【lIl哇l。烈风A)=岛一A=l一2p。，(风+A=1)及对数似然比的定义，式(412)可化为锄(三撕，=飘鼬c圭埘而式(4101可化为(412)(413)工(幻)=工(只)+兀三(414)J、qV因此，LUtBP算法总结如下：初始化计算信道传递给变量节点的初始概率似然比消息UP)，1=l，2，n。然后对每一个变量节点1和与其相邻的校验节点jc(i)，设定变量节点传向校验节点的初始消息00(吼)=(曰)迭代处理stcpl校验节点消息处理：对所有的校验节点j和与其相邻的变量节点iR(j)，第1次迭代时，计算第j个校验节点传向第i个变量节点的消息鼬(抄c白，)=。飘蛐c圭瑚，、(415)乜瑚时L现劬c知伪JsteD2变量节点消息处理对所有的变量节点i和与其相邻的校验节点jEc(i)，第1次迭代时，计算第i个变量节点传向第j个校验节点的消息心o()=三(曰)+兀00(o)(416)st印3译码判决对所有变量节点计算硬判决消息北京邮电大学硕士论文第阴章LDPC码的译码00(吼)=(曰)+兀of)(o)jEc。(417)若0(g，)O，则cf_0，否则cJ-1停止r若日c=O或者达到最大迭代次数，则结束运算，否则从stcp1继续迭代。423AwGN信道下的初始消息下面推导常用的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鬲嘉(418)g(0)=Pr(cf20l乃)=P“2+1l乃)2方4_9)证明：M一=等产=丛铲：旦Q!兰三型!丛墨三型p(yI而=1)P“而=1)+p(，I=一1)P“而=一1)(420)南=北京邮电大学硕士论文第四章LDPc码的译码得证。由此，LLRBP译码的初始消息为_劬卜以彤。101忑高礼g一_109(exp学)=等43降低复杂度的BP算法(421)BP算法以其优越的性能和较低的复杂度得到了广泛的应用。为了得到一定条件下的译码性能与复杂度的合理折衷，MarcPCFossorie和Jin曲uCheIl等提出了几种简化的LLRBP算法，仅通过加法运算来完成LDPC码的译码，大大降低了译码的实现复杂度。下面分别介绍。431迭代APP算法在变量节点的处理中，只有加法运算，但是可以进一步降低算法的实现复杂度。如果用LLRBP算法中的(吼)代替(吼)参与校验消息的迭代，也就是(吼)不仅用于硬判决，而且用于求解校验消息，此时BP算法简化为迭代的APP(apost耐谢probabi】ity)算法。这样计算，传递的变量消息之间引进了相关性，传递的变量消息就不再是外部信息，但是此时仅仅需要计算和存储一个变量消息的数值，可以大大降低算法的复杂度。432UMPBPBased算法(最小和或最大积)tallllx，taIlll。(x)是奇函数，具有以下性质：tanh(工)=sgn(工)tallll(IxJ)ta【】11。1(力=s印(工)tanh1(1工I)由此LLRBP算法中校验节点的处理可表示为(422)北京邮电大学硕士论文第眄章u)Pc码的译码三(，f)=2taIlh。1(兀tallll(寺工(钆”)rE正U=2taIllll(兀s印(三(g”兀tallll(寺I(gq)I)feun一、j-=2(兀s烈(g吖)-tallll。1(兀taIltl(寺I三(g吖)聊(423)oV。u-由于taIll【x1)在。到1之间取值，而且是x的单调递增函数，故，飘蛐(三似训z砾鼬(三愀们加5tanh(言删马(I(g一)1)(424)工(。)-，飘8鲥地伪黑(，)|(425)如果用上式作为LLRBP算法中的校验节点消息的处理，则称为最小和(Mins啪)算法或最大积(MaxProduct)算法。与LLRBP算法相比，此时校验节点的迭代只有比较运算与加法运算，大大降低运算量。对AwGN信道，初始LLR消息中的因子丢对迭代过程没有影响，可以忽略，因此BPB船ed算法不需要信道的估计，所以也称为UMP(UnifomlyMostPaw砷11)BPB够ed算法。433APPBas酣算法如果在校验消息和变量消息的计算过程中，都进行简化，将BPBed算法与迭代APP算法结合在一起，得到APPBased算法。总结如下：初始化计算信道传递给变量节点的初始概率似然比消息【胛。)，i1，2，n。然后对每一个变量节点i，设定变量节点传向校验节点的初始消息0(g，)=三(鼻)=y迭代处理step1校验节点消息处理：对所有的校验节点和与其相邻的变量节点iR0)，第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继续迭代。同样APPB嬲cd算法不需要信道的估计，所以也称为uMP(unifonlllyMostPowermll算法。44本章小结Gallager首次提出的概率软判决迭代译码，可以看作是伽ner图上的置信传播(BP)算法，也称为和乘积算法或消息传递算法。从因子图角度，可以构建广义的和乘积算法，很多算法都可以看作是因子图上的和乘积算法。建立在Ta仰er图上的LDPc码，其BP译码的每次迭代包括两步：校验节点的处理和变量节点的处理。所有校验节点从其相邻的变量节点处接收外部消息，处理后，再传回到相邻的变量节点；然后所有的变量节点进行同样的过程。最后变量节点收集所有可以利用的消息进行判决。根据传递的消息的不同，BP译码有概率BP译码和LLRBP译码LLRBP译码传递的是对数似然比消息，适用于二进制码。验证译码算法常用的通信系统环境是AWGN信道下采用BPsK调制，根据信道噪声的概率分布和接收符号，可以推导出u)Pc译码所需要的初始消息。通过修改LDPC译码的校验消息处理和变量消息处理可以获得降低复杂度的译码算法。变量节点接收所有的校验消息来进行迭代，简化为APP算法，降低存储量：变量消息传递给校验节点时，用变量消息的最小值代替总的乘积运算，简化校验消息处理过程，得到BPB鹤ed算法，降低计算量，损失一点性能；APP算法的变量消息处理与BPB勰cd算法的校验消息处理结合，得到APPBased算法。北京邮电大学硕士论文第五章u)PC编码的硬件实现第五章LDPc编码的硬件实现U)PC编码是一种接近仙农极限的信道编码，他在数字电视标准DvBS2、DVBTH、80211n、80216中得到广泛运用。我有幸参与了一个DVB-TH标准下的信道编码的FPGA实现。下文对我所负责的Lut估计模块和LDPc译码模块的硬件设计做简要介绍。51BPSK调制下的LLR计算的实现511理论分析由上文413司知，软信思的计算方法如F：根据信遭观测值y-，(1f_)估计噪声方差(万2)，并且计算厶豫(y。)=等，将输入的观测值以16352个数为一组压入FIFo，在压入的同时将数据取绝对值送入累加器与平方累加器处理16340个数作为样本估算出方差，其余数不处理，留下时间算出争具体算法是：a求出E(Iy，I)和E(y。2)。bZ芦E(yz)E2(1y。I)，cB一340516Z2+659548Z236184，d吉剐南参考资料【4j求出系数砉，再与F球。读出的该组16352个数分别相乘得出等。512LLR模块的设计。输入数据Yi，按照长度N分组，其中N是2的n次幂，n是自然。这一组数据北京邮电大学硕论文第五章LDPC编码的硬件实现算出一个系数，再分别与Yi相乘，依次输出。设计框图如下：图51u且估计设计框图1控制信号产生模块：根据上电复位复位和一个桢同步信号，由计数器产生以下各个模块的控制信号always(posedgedk)elses诅rt=16342)deaPo=1；elseelseclear=O：38北京邮电大学硕士论文第五章LDPc编码的硬件实现be百nsyncreg=sync；if【syIlc)s切疗_l；end北gt1；|黾研rc7：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；elrden可dcn；end由上到下，各信号为：cll(：系统工作始终，与输入数据同步；fst：复位信号，在上电时复位了，正常工作rs仁0；sync：桢头信号，每桢有16352个输入值，在每桢的开头与第一个数同时出现北京邮电大学硕上论文第五章LDPc编码的硬件实现的高电平，表示一桢的开始。syllcreg：将syIlc信号延时一拍。目的是在第二桢来的时候让计数器在桢头信号时为O；cnt：计数器，啦!6351循环；右msh：在每桢最后一拍的完成指示信号。作用是存储运算出来的系数；做ch：在累加器和平方累加器算完16340次累加和平方累加之后将结果缓存的指示信号；clear：在触ch信号存下结果后将累加器和平方累加器清零，准备下一次计算；avai：在每桢前16340拍让累加器和平方累加器工作的使能信号；start：当复位后出现第一个桢头信号时置一；啊髓：FIF0写使能。starl以后，第二个桢头信号来时，t也已经和sync对齐了，FIFO开始存入数据，wT曲=1并且一直保持；rd舅：FIFO读使能。在写入数据一桢以后，将数据读出，岫l-l并且一直保持；2FIFO模块：储存N个数据，N=2“。一共使用16352个数，所以通过控制FIFO读写使能控制第一组有效数据存满以后开始读数据，然后不停的读写，将上一组数据读出来，实现缓存的功能。din：系统输入的数据啊；fi旬out：矗fo缓存一桢的数据后。输出的上一桢的yi；clk：fifo时钟，就是系统时钟；rst：fifo复位信号，就是系统的复位信号：忻蛆：写使能，由使能产生模块生成rd皿：读使能，由使能产生模块产生3取绝对值模块，Input；北京邮电丈学硕士论文第五章u)Pc编码的硬件实现din【7：o】：输入的yidinabs：输入是正数，daca0叶=datain；负数时，输入数据采用符号位+绝对值形式的话，直接符号位取反，补码时dafa01】仁loooooooodataill。硼si印din-abs=(dill【7】)?l，bO，din【6：O】)：din如果补码则是9blo0000000din4平方累加器。需要平方累加器的使能信号。用顶层模块计数器产生。使用ipcore，乘法累加器实现。这种方法存在的问题是：数据是连续的，本组数据输入完成以后，紧接着后面的数据就要进来，没有空余时间清理本组数据，所以16352个数据，取前16340个参加参数的计算，由使能信号控制。din_sel：输入的每桢前16340个IyJI。当avai=l，输入diLabs，否则输入0；鹊si印d嗵舅l=a