[硕士论文精品]高吞吐量ldpc码编码构造及其fpga实现

摘要第I页高吞吐量LDPC码编码构造及其FPGA实现摘要低密度校验码（LDPC，LOWDENSITYPARITYCHECKCODE）是一种性能接近香农极限的信道编码，已被广泛地采用到各种无线通信领域标准中，包括我国的数字电视地面传输标准、欧洲第二代卫星数字视频广播标准（DVBS2,DIGITALVIDEOBROADCASTINGSATELLITE2）、IEEE80211N、IEEE80216E等。它是3G乃至将来4G通信系统中的核心技术之一。当今LDPC码构造的主流方向有两个，分别是结合准循环（QC,QUASICYCLIC）移位结构的单次扩展构造和类似重复累积（RA,REPEATACCUMULATE）码构造。相应地，主要的LDPC码编码算法有基于生成矩阵的算法和基于迭代译码的算法。基于生成矩阵的编码算法吞吐量高，但是需要较多的寄存器和ROM资源；基于迭代译码的编码算法实现简单，但是吞吐量不高，且不容易构造高性能的好码。本文在研究了上述几种码构造和编码算法之后，结合编译码器综合实现的复杂度考虑，提出了一种切实可行的基于二次扩展（DEX,DUPLEXEXPANSION）的QCLDPC码构造方法，以实现高吞吐量的LDPC码收发端；并且充分利用该类码校验矩阵准循环移位结构的特点，结合RU算法，提出了一种新编码器的设计方案。基于二次扩展的QCLDPC码构造方法，是通过对母矩阵先后进行乱序扩展（PEX，PERMUTATIONEXPANSION）和循环移位扩展（CSEX，CYCLICSHIFTEXPANSION）实现的。在此基础上，为了实现可变码长、可变码率，一般编译码器需同时支持多个乱序扩展和循环移位扩展的扩展因子。本文所述二次扩展构造方法的特点在于，固定循环移位扩展的扩展因子大小不变，支持多个乱序扩展的扩展因子，使得译码器结构得以精简；构造得到的码字具有近似规则码的结构，便于硬件实现；（伪）随机生成的循环移位系数能够提高码字的误码性能，是对硬件实现和误码性能的一种折中。摘要第II页新编码器在很大程度上考虑了资源的复用，使得实现复杂度近似与码长成正比。考虑到吞吐量的要求，新编码器结构完全抛弃了RU算法中串行的前向替换（FS,FORWARDSUBSTITUTION）模块，同时简化了流水线结构，由原先RU算法的6级降低为4级；为了缩短编码延时，设计时安排每一级流水线计算所需的时钟数大致相同。这种码字构造和编码联合设计方案具有以下优势相比RU算法，新方案对可变码长、可变码率的支持更灵活，吞吐量也更大；相比基于生成矩阵的编码算法，新方案节省了50以上的寄存器和ROM资源，单位资源下的吞吐量更大；相比类似重复累积码结构的基于迭代译码的编码算法，新方案使高性能LDPC码的构造更为方便。以上结果都在XILINXVIRTEXIIPRO70FPGA上得到验证。通过在实验板上实测表明，上述基于二次扩展的QCLDPC码构造和相应的编码方案能够实现高吞吐量LDPC码收发端，在实际应用中具有很高的价值。目前，LDPC码正向着非规则、自适应、信源信道及调制联合编码方向发展。跨层联合编码的构造方法，及其对应的编码算法，也必将成为信道编码理论未来的研究重点。关键词低密度校验码，重复累积码，编码器，现场可编程门阵列ABSTRACT第III页CODECONSTRUCTIONANDENCODERIMPLEMENTATIONOFHIGHPAYLOADLOWDENSITYPARITYCHECKCODEABSTRACTLDPCCODESPERFORMCLOSETOTHESHANNONLIMITITHASBEENWIDELYADOPTEDBYSTANDARDSINTHEFIELDOFWIRELESSCOMMUNICATION,INCLUDINGDVBTH,DVBS2,IEEE80211NANDIEEE80216ELDPCCODESHAVEBECOMEONEOFTHEKEYTECHNOLOGIESIN3GANDEVENTHENEXTGENERATIONCOMMUNICATIONNETWORKTODAY,THEREARETWOPOPULARWAYSOFCONSTRUCTINGLDPCCODES,NAMELYSINGLEEXPANSIONCODECONSTRUCTIONANDREPEATACCUMULATELIKECODECONSTRUCTION,BOTHOFWHICHTAKEADVANTAGEOFTHEQUASICYCLICSTRUCTURECORRESPONDINGTOTHETWOKINDSOFLDPCCODES,TWOPOPULARENCODINGALGORITHMSAPPLY,NAMELYALGORITHMBASEDONGENERATIONMATRIXANDALGORITHMBASEDONITERATIVEDECODINGTHEALGORITHMBASEDONGENERATIONMATRIXCANACHIEVEAHIGHPAYLOAD,WHILEITCONSUMESLOTSOFREGISTERSANDROMTHEALGORITHMBASEDONITERATIVEDECODINGCANBEEASILYIMPLEMENTED,WHILELDPCCODESWITHRELATIVELYHIGHPERFORMANCEAREHARDTOCONSTRUCTAFTERADETAILANALYSISOFTHEABOVECONSTRUCTIONMETHODSANDENCODINGALGORITHMS,WITHCONSIDERATIONTOTHECODECCOMPLEXITY,AFLEXIBLECONSTRUCTIONMETHODCALLEDDUPLEXEXPANSIONISPROPOSEDTOACHIEVEAHIGHPAYLOADTAKINGADVANTAGEOFTHEQUASICYCLICSTRUCTUREOFTHESPARSEHMATRIX,ANEWENCODERALGORITHMISALSOPRESENTEDDUPLEXEXPANSIONCODECONSTRUCTIONISUSUALLYREALIZEDTHROUGHAABSTRACT第IV页PERMULATIONEXPANSIONONMOTHERMATRIXFOLLOWEDBYACYCLICSHIFTEXPANSIONONBASEMATRIXFORFLEXIBLECODERATEANDCODELENGTH,MULTIPLEPERMULATIONEXPANSIONFACTORSPEXANDCYCLICSHIFTEXPANSIONFACTORSCSEXSHALLBESUPPORTEDBYCODECTHEFEATURESOFDUPLEXEXPANSIONCODECONSTRUCTIONILLUSTRATEDINTHISARTICLELIEINFIXEDCSEXFACTORANDFLEXIBLEPEXFACTORS,FACILITATINGDECODERIMPLEMENTATIONAPPROXIMATEREGULARLDPCCODE,MAKINGCODECCOMPLEXITYLOWPSEUDORANDOMCHOSENPEXFACTORS,IMPROVINGPERFORMANCETHUS,THISSPECIFICDUPLEXEXPANSIONCODECONSTRUCTIONACHIEVESAGOODTRADEOFFBETWEENHARDWARECOMPLEXITYANDPERFORMANCETHENEWENCODINGALGORITHMHASENABLEDRESOURCESHARINGWHEREVERPOSSIBLE,WHICHMAKESTHEENCODERCOMPLEXITYINLINEARPROPORTIONTOTHECODELENGTHFULLYCONSIDERINGAHIGHPAYLOAD,THEFORWARDSUBSTITUTIONINRUALGORITHMISREMOVEDMEANWHILE,THENUMBEROFPIPELINESTAGESHASBEENREDUCEDFROM6TO4INORDERTOREDUCETHEENCODINGLATENCY,ALLPIPELINESAREDESIGNEDTOCONSUMEAPPROXIMATELYTHESAMENUMBEROFCLOCKSCOMPAREDTORUALGORITHM,THISPROPOSEDSCHEMEISMOREFLEXIBLETOSUPPORTMULTIPLECODERATESANDCODELENGTHSWITHMUCHHIGHERPAYLOADCOMPAREDTOTHEALGORITHMBASEDONGENERATIONMATRIX,ITCONSUMESMUCHLOWERREGISTERANDROMRESOURCES,THUSACHIEVESAHIGHERPAYLOADPERUNITRESOURCECOMPAREDTOTHEALGORITHMBASEDONREPEATACCUMULATESTRUCTUREANDITERATIVEDECODINGALGORITHM,ITISMUCHEASIERTOCONSTRUCTTHECODESWITHHIGHPERFORMANCEALLTHERESULTSHAVEBEENPROVENBYXILINXVERTEXIIPRO70FPGAUPONBOARDLEVELTESTING,RESULTSSHOWTHATTHEABOVEDUPLEXEXPANSIONCODECONSTRUCTIONANDENCODERDESIGNOFLDPCCODECANACHIEVEAHIGHPAYLOADWITHRATHERLOWRESOURCESITENJOYSAFAIRLYHIGHMERITINPRACTICALAPPLICATIONNOWADAYS,IRREGULAR,FLEXIBLEANDJOINTSOURCECHANNELMODULATIONLDPCCODEDESIGNHASBECOMETHEFOCUSOFFUTURERESEARCHANDTHECONSTRUCTIONMETHODOFJOINTSOURCECHANNELMODULATIONCODEANDITSCORRESPONDINGENCODINGALGORITHMWILLCONTINUETOBESTUDIEDINDETAILKEYWORDSLDPC,REPEATACCUMULATE,ENCODER,FPGA上海交通大学学位论文原创性声明本人郑重声明所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名日期年月日上海交通大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密，在年解密后适用本授权书。本学位论文属于不保密。（请在以上方框内打“”）学位论文作者签名指导教师签名日期年月日日期年月日第一章绪论第1页第一章绪论伴随着集成电路的飞速发展，以及摩尔定律的延续，上世纪90年代初，信道编码迭代译码的方法再一次受到人们广泛的关注。随着TURBO码12、TURBO乘积码3（TPC,TURBOPRODUCTCODE）的横空出世，以及LDPC码的重新发现，香农极限不再是遥不可及的，人们把信道编码向着极限推进了一大步。本章将从信道编码基本理论开始，简述信道编码的概念，从而引出本文的重点LDPC码，并对其基本概念、发展情况以及应用前景作简要介绍。11信道编码基本理论现实生活中，信息的传递难免受到信道的干扰，特别是无线通信系统中，信道的不确定性导致了接收端接收信号质量的下降，信道编码存在的目的就是尽量减少接收端错误接收的信息比例，从而做到信息的可靠传输。信道编码的容错能力，是通过在传输码字中增加冗余实现的。冗余的作用是加大有效码字之间的距离，这样接收端就能把有效码字和无效码字区分开来。最佳的接收方法是最大似然的译码方法，在收到当前码字后，通过统计所有有效码字发送的可能性，将可能性最大的那个有效码字判为接收到的正确信息。一般认为，有效码字集合中任意两个码的距离越大，则这个码的性能越好。在几种特殊类型的码中间，这种距离是可以衡量的。例如线形分组码就能用最小码距DMIN来衡量其优劣，同样地，卷积码的优劣就能用自由距离DFREE来衡量。然而，最大似然的译码方法，在实际中却是难以实现的。它的求取一般涉及遍历整个有效码字空间的操作，现实中仅可能对短码长的码采用，其余情况下采用的都是一些次最优的，计算较为简单的算法，以降低译码复杂度，然而这样会牺牲一定的误码性能。这些简化的译码算法，并非很多时候都和最大似然算法保持着相当的性能差距，迭代译码方法的出现使得人们找到了一种次最优的译码算法，随着硬件技术的发展，这一算法在今天终于成为了现实，而它最成功的应用当属LDPC码。第一章绪论第2页12LDPC码简介LDPC码是低密度校验码（LOWDENSITYPARITYCHECKCODE）的简称，最早由RGGALLAGER45在1962年提出，当时由于硬件技术的限制，其重要性没有为人们所广泛认识。直到上世纪90年代前，学术界只有为数不多的学者发表了相关的论文，这些人包括MARGULIS6、TANNER7以及ZYABLOV和PINSKE8等。随着迭代译码方法在TURBO码上的成功应用，MACKAY910、NEAL10和WIBERG11又分别重新发现了LDPC码。LDPC码是一种线性分组码，顾名思义，校验矩阵的稀疏性是它的特点所在。LDPC码最先使用了循环迭代的方法进行译码，使现实可行的译码算法在性能上迅速逼近最佳算法，使信道编码技术向香农极限又迈进了一步。根据校验矩阵的某些特征，可以对LDPC码进行分类。如果校验矩阵是由一系列循环移位方阵拼接而成的，则称之为准循环移位LDPC（QCLDPC）码；如果校验矩阵右边的方阵仅有主对角线和一条次对角线上的元素非零，则称之为重复累积（RA）码；如果校验矩阵所有的行重和列重相同，则称之为规则码，反之，则称之为非规则码。规则码有其相应的表示方法，一般记作N,DV,DC，其中N表示码长，DC表示行重，DV表示列重。这里给出了一个12,3,6规则LDPC码的校验矩阵，如图11所示。011101000011110101010100101010001011110010111000000100111110001011100101H图11一个12,3,6规则LDPC码的校验矩阵FIG11ANHMATRIXEXAMPLEOFA12,3,6REGULARLDPCCODE13LDPC码的发展概况自从上世纪90年代LDPC码被重新发现以来，学术界对它的研究就遍地开花，一直如火如荼的进行着。在误码性能方面，SHOKROLLARI、SPIELMAN、LUBY、MITZENMACHER和STEMANN等人研究了二进制擦除信道（BEC,BINARYERASURECHANNEL）和二进制对称信道（BSC,BINARYSYMMETRICCHANNEL）下LDPC码的误码性能，并证明了在BEC信道下，随着码长的增第一章绪论第3页长，利用置信传播算法（BPA,BELIEFPROPORGATIONALGORITHM）1213译码的LDPC码的性能将逼近香农极限。URBANKE和RICHARDSON等人用密度演化（DE,DENSITYEVOLUTION）的方法研究了LDPC码结合置信传播译码算法在其它信道下的误码性能，指出LDPC码在其它很多信道中的传输速率都能趋近于信道容量。文献14对瑞利衰落信道中的LDPC码进行了性能分析，并且提出了相应的构造方法，得到了一种误码性能优于TURBO码的LDPC码。文献1516结合了LDPC码与OFDM两种先进技术，提出了一种在MPSK调制下的OFDM系统中LDPC码的译码算法，并给出了性能分析。在码字构造方面，人们从LDPC码的最小码距着手，通过有限几何的方法得到了一些性能相当接近香农极限的LDPC码17181920，文献21从译码角度出发，结合译码器硬件结构，提出了一种码构造的方法。为了编码器实现方便，HUIJIN，DIVSALAR以及MCELIECE等人提出了RA22码，这种码的特点在于编码直接，非常适合低传输速率场合。伴随着RA码的出现，一系列类RA码23迅速涌现，它们无不有着编码器设计简单的优点，为LDPC码构造的发展提供了另一个方向。在编码方面，RICHARDSON和URBANKE最先提出了将校验矩阵下三角化的想法24，以使编码复杂度降低到与码长近似成正比的程度。沿着这个角度出发，文献25在构造时就将校验矩阵设计成下三角形式，但是这样做减少了校验矩阵的随机性，势必会影响误码性能的提升。之后HUIJIN，DIVSALAR等人从码字构造方面开创了简单编码器的架构22，为人们实际寻找更简单的编码方法开辟了蹊径。随着准循环移位结构日渐成为LDPC码的主流，ZONGWANG,LI和SHU，LIN等人提出了基于生成矩阵的编码算法26，作为QCLDPC码编码的普适算法有着举足轻重的地位。最近SHAQFEH和GOERTZ又提出了基于迭代译码的编码算法27，对于某些特殊的校验矩阵而言，编码算法可以变得和RA码一样简单。在译码方面，置信传播算法一直占据着主流的地位。但是由于其复杂度仍然较高，因此一系列简化算法应运而出，其中包括最小和算法、改进的最小和算法和分层的改进最小和算法等。结合不同信道和调制方式，一些更简单的迭代算法也有着应用空间，比如一些硬判决、软判决相结合的译码算法2829。随着分层迭代译码思想的出现，LDPC码译码器的吞吐量得以提升。文献30实现了最大净吞吐量1GBPS的译码器，当然它是建立在硬件全并行的基础上的，H矩阵的每一行和每一列都被固定成一个硬件处理单元，将置信传播算法直接映射到了硬件上。文献31对TURBO码和LDPC码的译码复杂度进行了比较，指出LDPC码译码器实现起来更简单。文献32对LDPC码译码器的定点化进行了讨论。第一章绪论第4页14LDPC码的应用前景LDPC码的最大亮点是其接近香农极限的误码性能，这在当今强调低辐射、低功耗的时代背景下显得尤其重要。对于无线通信而言，终端设备一般具有体积小、携带方便、能耗低的特点。无线设备的续航能力正日益为人们所重视，因此如何降低上行通信中的发射功率和下行通信中的接收功率就成了人们当务之急，降低发射功率带来的必然结果是降低接收机的信噪比，使得接收变得异常困难，而因为LDPC能在接近于香农极限的性噪比条件下正常工作，因此它能够得到广泛的认可。国际上，LDPC码已经被列入IEEE80211N、IEEE80216E等标准；在欧洲，LDPC码已被用于第二代卫星数字视频广播标准（DVBS2）；在我国，数字电视地面传播标准已经正式颁布并于今年8月强制执行，这标志着LDPC码已经正式走入国人的生活。当然，我们也不能忽视了LDPC码在其他电子领域的应用。例如采用LDPC码进行压缩和加密数据。在现今TB级的大容量硬盘中，为了延长硬盘使用寿命、降低硬盘功耗，需要降低硬盘中的信噪比，这样就会对编码和纠错算法提出很高的要求，LDPC码有望解决这个难题。如今在信道编码这一领域，LDPC码面临的潜在竞争来自于TURBO码以及TURBO乘积码等几种同样基于迭代译码的信道编码。拿TURBO码作对比，LDPC码的优势在于译码的并行性，而TURBO码的译码难以并行实现。另外，LDPC码的译码要比TURBO码方便，结构也更简单。然而，除了RA码和一些类似RA结构的码以外，其余LDPC码的编码复杂度仍然比较高，这可能是制约LDPC码发展的一个重要瓶颈。15本章小结本章首先简要介绍了信道编码的基本理论，进而引出了LDPC码，给出了其基本原理、发展概况和应用前景。一般情况下，信道编码的最佳译码方法是最大似然算法，在接收到一个码字时，它通过计算所有有效码字的发送概率并取最大的那个码字来实现最佳译码，然而这样的复杂度一般来说是不能接受的。迭代译码的引入为人们找到了一种次最优的译码方法，由于硬件实现复杂度的关系直到上世纪90年代才为人们所关注。LDPC码由于其校验矩阵是稀疏的，因此在一次迭代中信息传递的次数不会很多，从而非常适合迭代译码，代表着信道编码技术新的发展方向。第一章绪论第5页截止目前，LDPC码已经被我国采用到数字电视地面传播标准中，并且IEEE80216E（WIMAX）、IEEE80211N以及DVBS2也已率先采用了这一编码技术，可见其有着广阔的发展前景。LDPC码比起TURBO码有着天然的并行优势，因此它将是下一代无线通信系统中最具有竞争力的信道编码方案。第二章LDPC码译码算法第6页第二章LDPC码译码算法简介迭代译码方法的可行性长久以来一直是LDPC码没能得到重视的主要原因，人们试图从硬件和算法两方面改变这样的情况。自从摩尔定律提出之日起，至今一直是有效的，当半导体技术顺利攻克45纳米后，在未来10年内，摩尔定律仍然是可以依赖的，这也就为迭代译码算法提供了硬件上的保障。与此同时，人们也尽可能地降低迭代译码算法的复杂度，由于算法复杂度与性能之间总保持着一种折中关系，因此如何在性能不损失很多的前提下找到简化的译码算法也就成了人们努力的方向。本章将首先介绍基于TANNER图的LDPC表示方式，然后给出经典的信息传递译码算法（MPA,MESSAGEPASSINGALGORITHM），其中将简要介绍置信传播算法及其几种比较常用的简化算法。21LDPC码的TANNER图表示线性分组码既可以用它的生成矩阵G来表示，也可以用校验矩阵H来表示，对于LDPC码来说，由于校验矩阵是稀疏的，因此更容易用来表示，我们从以下汉明码的校验矩阵看起1010101H0110011000111121把H矩阵的每一列看作一个重复码，对应一个比特节点XI；把H矩阵的每一行看作一个类奇偶校验码，对应一个校验节点FI；把H矩阵中J行I列的非零元素看作连接上述比特节点XI和校验节点FJ的一条边。于是，对应式21，可以得到图21所示的TANNER图7。图中用等号表示一个比特节点，用加号表示一个校验节点。第二章LDPC码译码算法第7页F1F2F3X1X2X3X4X5X6X7图21TANNER图示例FIG21ANEXAMPLEOFTANNERGRAPH显然，迭代译码时信息的传递是以TANNER图中的边为介质的，而LDPC码以其稀疏的校验矩阵大大降低了TANNER图中边的数量，进而降低了迭代译码的复杂度，因此LDPC码的出现使得基于TANNER图的迭代译码算法得以真正有效地应用。那稀疏的结构会不会影响LDPC码的误码性能呢LDPC码所引入的稀疏矩阵对于迭代译码性能的损失是很小的。假设实际传输需要达到信道容量的1倍（这里是某个趋近于零的正常数），可以证明当趋向于零的时候，校验矩阵H中“1”的个数只需要有NLN1/的数量级，基于TANNER图的迭代译码质量就不会明显下降，这里N是LDPC码码长。稀疏的校验矩阵带来的好处是，在趋向于零的情况下，每比特译码迭代总复杂度的数量级为1/LN1/；而在最大似然译码算法中，当传输速率趋近信道容量时，这个复杂度函数是1/的指数函数。因此，LDPC码迭代译码的理论基础是非常充实的。22信息传递算法信息传递算法是一种常用的LDPC译码算法，其中置信传播算法（BPA，BELIEFPROPAGATIONALGORITHM）是目前已知误码性能最好的LDPC译码算法。首先我们看一下比特节点和校验节点分别是如何工作的。第二章LDPC码译码算法第8页A1A2E3A4A5E6图22信息在比特节点和校验节点的计算示意图FIG22ILLUSTRATIONOFINFORMATIONPROCESSINGATBITNODE图22给出了信息在比特节点和校验节点的计算示意图。其中比特节点的外信息E3由式22决定，校验节点的外信息E6由式23决定123121211AAEAAAA226343411EAAAA23图中比特节点接收除了目标校验节点外其余所有校验节点传递的外信息以及信道信息，计算后将互信息传递给目标校验节点。校验节点接收除了目标比特节点外其余所有比特节点传递的外信息，计算后将互信息传递给目标比特节点。这里，式22和23只是作示例用，实际情况下比特节点和校验节点的输入可能远远大于两路，本章稍后部分将会作详细介绍。在所有的信息传递算法中，置信传播算法是最常用的，对它稍作修正还能得到许多简化算法。221置信传播算法如式22、23所指出的那样，置信传播算法在TANNER图的边上传递的并不是硬值，而是概率值，它是一种软值，相对硬值保留了更多的信息，相应地使译码性能得到很大提高，所牺牲的复杂度也还是可以接受的。为了说明置信传播算法，首先给出一些符号定义，并假定发送码字C的每一个比特具有独立的分布1JJIRIH，表示H矩阵第J行中非零元素列位置的集合；第二章LDPC码译码算法第9页1JJIRIIHI，表示H矩阵第J行中，除了第I列外非零元素列位置的集合；1IJICJH，表示H矩阵第I列中非零元素行位置的集合；1IJICJJHJ，表示H矩阵第I列中，除了第J行之外非零元素行位置的集合；PR1/IIIPCY，表示在信道接收信息YI前提下，信息节点I取1的概率；IJQB表示在已知除第I个校验方程外其他所有校验方程以及信道的信息时，发送码字ICB的概率；JIRB表示当ICB时，第J个校验方程被满足的概率。2211概率域上的置信传播算法初始化对于每一对满足HIJ1的I,J，令22/101PR1|1IIJIIIYQPXYE2422/11PR1|1IIJIIIYQPXYE25第一步对每一个校验方程J以及相应的每一个RJ中的I，计算以下两个概率度量11012122JJIIJIRIRQ26110JIJIRR27第二步利用上一步计算所得的0JIR和1JIR更新概率值0IJQ和1IJQ，对于每一个J进行以下计算010IIJIJIJIJCJQKPR2811IIJIJIJIJCJQKPR29第二章LDPC码译码算法第10页其中，常数IJK是归一化系数，使得011IJIJQQ；0IJIJCJR表示信息比特取值为0时所有的校验方程得到满足的概率；1IJIJCJR表示信息比特取值为1时所有的校验方程得到满足的概率。第三步对于每一个I，计算比特I取值为0和1的后验概率0IQ和1IQ010IIIIJJCQKPR21011IIIIJJCQKPR211其中，常数IK是归一化系数，使得011IIQQ。硬判输出对于每一个I，进行如下判决11050IIIFQCELSE212如果此时0TCH，则译码成功并停止迭代；否则判定此次译码失败，若此时的迭代次数少于最大预设迭代次数，则回到第一步；若达到最大迭代次数仍未成功，则宣告译码失败。实际应用中，由于概率域上的置信传播算法涉及的大多是乘法操作，因此不利于硬件实现，一个自然的想法是利用取对数的方法将乘法转化为加法，因此就得到了下述对数域上的置信传播算法。2212对数域上的置信传播算法在进一步研究对数域上置信传播算法前，需要在已有定义的基础上，增加对数域上相应概念的定义。来自信道的信息定义为PR1|LOGPR1|IIIIIXYLCXY；在比特节点上，定义0LOG1IJIJIJQLQQ，IJIJSIGNLQ表示输出互信息的符号位，IJIJLQ表示输出互信息幅度的绝对值；第二章LDPC码译码算法第11页在校验节点上，定义0LOG1JIJIJIRLRR；译码器输出定义为0LOG1IIIQLQQ；这些都是概率比的对数值，称它们为对数似然比（LLR，LOGLIKELIHOODRATIO）。此外，定义函数11LOGTANHLOG21XXEXXENULL，当X0时，容易证明1XX213以下过程描述对数域置信传播算法初始化对于每一对满足HIJ1的I,J，令22/IJIILQLCY214第一步对每一个校验方程J以及相应的每一个RJ中的I，计算以下对数域度量JJIJIJIJIRIIRILR215第二步对于每一个J，利用第一步的计算结果，计算以下对数域度量IIJIJIJCJLQLCLR216第三步对于每一个I，计算IIIJIJCLQLCLR217硬判输出对于每个I，进行如下判决100IIIFLQCELSE218如果此时0TCH，则译码成功并停止迭代；否则判定此次译码失败，若此时的迭代次数少于最大预设迭代次数，则回到第一步；若达到最大迭代次数仍未成功，则宣告译码失败。从上述算法过程中可见，对数域上的置信传播算法只涉及加减法和查表操作，比较适合硬件实现。然而，由于式215的查表复杂度直接决定了对数域上置信传播算法的实现复杂度，因此对该式的简化将有助于译码算法复杂度的大幅降低。第二章LDPC码译码算法第12页222最小和算法由于置信传播译码算法的复杂度集中在215式的计算上，因此寻找一种简单函数来逼近式215的结果会是比较理想的。根据函数X的特性，JIJIRI的值可以用最小的IJ所对应的IJ的值来近似，于是MINMINJJJJJJIJIJIJIJIJIJIJIRIIRIIRIIRIIRIIRILRII219这就是“最小和”的原意。然而，对置信传播算法的简化必然会带来算法性能上的损失，包括收敛速度和误码性能，为了最大程度上弥补这些损失，人们又在最小和算法的基础上提出了一些改进算法。223各种基于最小和算法的改进算法由函数X的性质可知，最小和算法会得到比真实JIJIRI值更大的结果，因此人为加入加性或者乘性因子可以修正这种误差，从而改善译码的性能，这一类算法统称为改进的最小和算法（MMSA,MODIFIEDMINIMUMSUMALGORITHM）。仿真证明改进的最小和算法能够小幅提高译码器的误码性能。由于改进的最小和算法的收敛速度和置信传播算法几乎一样，因此在某些需要高速译码的领域，人们又引入了分层的改进的最小和算法（LMMSA,LAYEREDMODIFIEDMINIMUMSUMALGORITHM）。分层的概念就是把原先的一次迭代分解为现在的几次小迭代，虽然几次小迭代所需要的总的时钟数和原先一次迭代的时钟数相同，但是这几次小迭代之间是有信息互通的，虽然这样做会少量增加译码器的硬件资源，但是由于LMMSA算法可以使收敛速度增加一倍，即置信传播算法20次迭代等价于LMMSA算法的10次迭代，因此从吞吐量的角度上来看仍然有着非常大的改善。鉴于置信传播译码算法的变体还有很多种，在此不再一一列举。23本章小结本章从LDPC的TANNER图表示开始，介绍了最常用的LDPC码迭代译码算法第二章LDPC码译码算法第13页信息传递算法。其中一类置信传播算法目前广泛地应用于各类LDPC码译码器中。221给出了置信传播算法在概率域及对数域上计算的具体步骤，由于它传递的是软信息，因此比一般传递硬值的译码算法需要更多的量化资源，但是由于软信息得到了保留，因此误码性能有大幅的提高。由于传统的置信传播算法复杂度仍然较高，因此在硬件实现上一般采用最小和算法代替。为了补偿最小和算法带来的性能损失，又引入了加性或乘性因子，使最小和算法性能非常接近对数域的置信传播算法。由于改进的最小和算法收敛速度不够快，在要求高吞吐量的领域一般采用分层的改进最小和译码算法，虽然这样做会增加硬件资源，但是单位吞吐量所需的资源消耗仍然是下降的。迭代译码的出现使得LDPC码在实际应用中具有了接近香农极限的误码性能，这也促使LDPC码跻身各大通讯标准中。在介绍完LDPC码基本译码算法后，下一章起将介绍本文的重点高吞吐量LDPC码编码构造及其编码器实现方法。第三章主流LDPC码构造方法与编码算法第14页第三章主流LDPC码构造方法与编码算法比起TURBO码而言，LDPC码在译码方面有着并行和简单的结构，然而较复杂的编码结构始终是摆在LDPC码构造者面前的难题。尽管有普遍适用的LDPC编码算法存在，但是由于其较高的复杂度，以及很少考虑资源的复用，一般在实际中不能直接采用，因此简单的编码算法仍然需要基于特殊的码字构造。本章将简要介绍当今主流的码字构造及其相应得编码算法，这也是第四章提出的一种高吞吐量LDPC码构造和编码的基础。RU算法作为最先提出的普适的LDPC码编码算法，为后来很多编码算法奠定了基础，许多码构造和编码算法是通过在RU算法上作改进实现的。RU算法也是本文提出的编码算法的基础，31将会简要介绍RU算法。现在的LDPC码构造，一般都是建立在循环移位结构的基础上的。这样的构造需要对基矩阵作单次扩展，其中基矩阵一般根据理论优化得到的度分布对确定校验矩阵的行重和列重，所作的单次扩展则确定校验矩阵的细节，一般会尽量使校验矩阵满秩。优化校验矩阵环长的过程同时存在于确定基矩阵和单次扩展之中。然而即使本质上都采用基于循环移位结构的单次扩展方法，目前各大标准中所使用的构造仍然可以明显地分为两个方向第一种方法根据优化理论得到的度分布对，或者某些优化环长的算法，例如边增长（PEG,PROGRESSIVEEDGEGROWTH）算法确定基矩阵。我国数字电视地面传输标准中使用的就是这种码构造方法。32将对这种构造方法作相应的介绍，并且给出一种基于生成矩阵的编码算法，这种算法可以解决几乎所有该类码构造的编码问题。第二种方法对基矩阵的非零元素位置作了一定的规定，如要求最右边的方阵非零元素占满主对角线和一条次对角线等。这种方法是受到RA码结构的启发，它的编码复杂度和RA码相近，但是其吞吐量比传统RA码要高很多，原因在于引入了并行的累加结构，并且它的译码器也比传统RA码容易实现。由于基于生成矩阵的编码算法对于寄存器和ROM资源需求很大，并且和码长的平方成正比，在码长很长时就不适用了，因此类似RA码的构造算法非常适合长码长情况。IEEE80211N、IEEE80216E以及欧洲的DVBS2标准中使用的就是这种码构造方法。33将对这种构造方法作简要介绍，并且给出相应的基于迭代译码的编码算法。第三章主流LDPC码构造方法与编码算法第15页31RU算法作为一种线形分组码，LDPC码可以使用信息比特S与生成矩阵G相乘的方法得到编码后的码字C，即CSG。这样做的缺点是很明显的，由于G矩阵是通过对H矩阵进行某些非线性操作得到的，因而一般是一个非稀疏的矩阵，而且很难保证有什么规律，因此这种做法没有利用到H矩阵的任何特性，包括最明显的稀疏特性，是很不经济的。既然从上述生成矩阵的方程式出发不能得到一种简单的编码算法，一个很自然的想法就是从校验方程式HCT0T出发进行编码。RICHARDSON和URBANKE在文献24中回答了这个问题。他们指出，针对任何一个普通的校验矩阵H，只需要对其进行一次软件上的简单预处理，使它变成一种类似下三角阵的结构，就能进行简单编码了。并且这种编码算法的复杂度在大多数情况下近似与码长成正比，因此它是一种具有普适意义的简单LDPC码编码算法。311RU算法RU算法主要分为三个阶段预处理阶段、编码阶段和码字交换阶段。假设H矩阵是MN维的，预处理通过对校验矩阵H作行交换和列交换，目的是把H矩阵变为如图31所示的类似下三角的矩阵，其中矩阵A的大小为MGNM，矩阵B的大小为MGG，下三角矩阵T的大小为MGMG，矩阵C的大小为GNM，矩阵D的大小为GG，矩阵E的大小为GMG。同时需要保证由DBET1所定义的矩阵是可逆的，如果本次预处理时不可逆，则可以将矩阵B、D所在的某些列进行内部交换或者与矩阵A、C的某些列互换，并进行下一次试探，直到满秩为止。由于预处理涉及的矩阵操作只涉及初等变换中的行交换和列交换，因此，经过预处理后的矩阵H矩阵仍然是稀疏的。第三章主流LDPC码构造方法与编码算法第16页ABCDETMNGNMMGGMG图31经行交换、列交换后的类似下三角校验矩阵HFIG31THEREFORMEDPARITYCHECKMATRIXHINAPPROXIMATELYLOWTRIANGLEFORM经过处理后的矩阵H也是MN维的，由图31可知，矩阵H可以表示成如下形式EDCTBAH31为了推导简单，以下将H记作H，事实上从校验方程式的角度上看，使用H和H的区别只是在于是否需要对C进行一次列交换，由于在RU编码的第三阶段码字交换阶段会对C进行从H到H的逆向列交换过程，因此这两次列交换过程在计算推导时完全可以认为是透明的。在式31两边同时左乘下三角矩阵1IOETI，得到ODBETCAETTBAHIETOI11132由校验方程式可知，编码后码字C满足HCT0T。在此对C进行分割，令CS,P1,P2，其中S表示信息位，P1和P2联合表示校验位，实际中分别对应矩阵B、D和T、E所在的列，则校验位的P1长度为G，P2长为MG。由校验方程式，可将32式作如下分解120TTTASBPTP331110ETACSETBDP34定义矩阵DBET1，于是得到校验位P1和P2的表示式第三章主流LDPC码构造方法与编码算法第17页111TTPETACS35121TTTPTASBP36至此完成了RU算法的编码计算过程，以下我们简单分析RU算法的编码复杂度。在式35中，由于1是大小为GG的非稀疏矩阵，因此35式的计算复杂度与G2成正比。同样地，在式36中，T1是大小为MGMG的非稀疏矩阵，但是由于T本身是下三角的，因此T1也是下三角的，于是其与向量的乘法可以使用文献24提出的前向替换的方法来简化。这样，RU算法的编码复杂度就可以减少到ONG2，所以在编码预处理阶段，要求G尽可能的小，也就要求下三角阵T的维数尽量大。RU算法的编码流程如图32所示，除去输入输出级的话，一共需要6级流水线。被A乘被C乘被T1乘被E乘被B乘被1乘被T1乘信息比特S流水线分级异或异或校验比特P2校验比特P1图32RU编码算法流程图FIG32FLOWCHARTOFRUENCODINGALGORITHM第三章主流LDPC码构造方法与编码算法第18页312RU算法的优缺点RU算法从校验方程式出发，绕开了非稀疏的生成矩阵对LDPC码进行编码，充分利用了校验矩阵稀疏的特点，是LDPC码第一种比较理想的编码方式。不仅如此，它通过有限的两种初等变换求得一个维数较大的下三角方阵，利用其逆矩阵也是下三角的特点，应用前向替换将非稀疏矩阵与向量的乘法简化，使得整体计算复杂度从ON2降低到了ONG2。但是，RU算法的缺点也是比较明显的。首先，RU算法的流水级安排不合理，这里指的是每一级流水线所消耗的时钟数相差比较大。拿码长为1536的LDPC码来说，算上输入、输出两个缓存级，流水级所需的时钟数从1095到3906不等，这就会导致某些流水级长时间不在工作状态，降低了硬件的利用效率。其次，在1没有被强制设计为某些特殊简单矩阵的情况下，它与向量的乘法没有办法做任何简化，这会使RU算法在支持自适应编码时显得力不从心。最后，前向替换方法是一把双刃剑，在解决了下三角非稀疏矩阵与向量乘法的同时，也引入了串行的计算结构，使得目标向量中下一个分量的求解依赖于该向量之前求得的所有分量，因此前向替换必须一位一位进行，大大限制了吞吐量的提升，这一点和33所介绍的一种传统RA码的累加结构是类似的。综上所述，在硬件资源有限的前提下，RU算法只适合应用在吞吐量要求不太高、码长不太长、不要求自适应编码的场合。然而在结合了准循环移位结构后，对其算法作一些改进能得到一些非常实用的算法，因此RU算法的理论指导意义很大。32基于生成矩阵的编码算法RU算法的普适性使得它能够解决一般LDPC码的编码问题，从31的介绍中我们可以看到，RU算法考虑的只是校验矩阵的稀疏性，它不对校验矩阵作任何其它假定，于是当校验矩阵仍存在某种其他规律时，RU算法显然是不能预计的。正是由于RU方法存在的这一不足，使得它与实际理想LDPC的编码算法仍有一定距离，这也促使人们往校验矩阵上施加更多的约束，以达到简化编码算法的目的。随着准循环移位结构的流行，人们开始重新审视基于生成矩阵的编码方法。此时的生成矩阵已经不再是那种没有规律的非稀疏阵，在某些条件下，生成矩阵也具有了准循环移位结构的特点。这种构造及编码方法的典型应用在于我国的数字电视地面传输标准。本节将会简单介绍基于单次扩展的QCLDPC码以及针对这一类码的基于生成矩阵的第三章主流LDPC码构造方法与编码算法第19页编码算法。321基于单次扩展的QCLDPC码首先给出一些关于QCLDPC码的基本定义。若一个方阵可由单位矩阵经循环右移N位后得到，那么这个矩阵称为循环移位单位阵（CSI,CYCLICSHIFTIDENTITY）；一般地，若一个方阵除去第一行后的每一行都可由该方阵上一行经循环右移一位后得到，并且第一行是最后一行经循环右移一位后得到，那么这个方阵称为循环移位阵（CSM,CYCLICSHIFTMATRIX）。进一步，如果将ZPEX个大小相同的循环移位单位阵和ZPEXZPEX1个相同大小的零阵拼接得到方阵，并且该方阵的行重、列重均为1，那么这个方阵称为准循环移位单位阵（QCI,QUASICYCLICIDENTITY）；一般地，如果将ZPEXZPEX个大小相同的循环移位阵或者零阵拼接得到方阵，那么这个方阵称为准循环移位阵（QCM,QUASICYCLICMATRIX）。显然，准循环移位单位阵是一种特殊的准循环移位阵。文献26证明了准循环移位阵的加、减、乘、求逆运算（如果存在）所得仍是准循环移位阵。如果一个LDPC码的校验矩阵由且仅由大小相同的循环移位阵或零阵拼接而成，那么此LDPC码称为QCLDPC码。假设H矩阵的基矩阵大小是MN的，一般MN。图33给出了QCLDPC码校验矩阵的模型，其中HI,J1IMJN,1为大小相同的循环移位阵或者零阵。H1,NH2,NH2,1H1,1HM,NHM,1H2,2H1,2HM,2H1,N1H2,N1HM,N1图33QCLDPC码校验矩阵FIG33PARITYCHECKMATRIXOFQCLDPCCODE第三章主流LDPC码构造方法与编码算法第20页322基于生成矩阵的编码算法基于生成矩阵的编码算法前提是构造出具有类似于图33的具有循环移位结构的生成矩阵，即使在绝大多数情况下，该矩阵不是稀疏的。假设上述HI,J的大小是ZCSEXZCSEX的，即循环移位扩展的扩展因子是ZCSEX。文献26分别