LDPC码的应用

2010年第4期大众科技No.4,2010(总第128期)DA ZHONG KE」I( Cumulatively No 128)LDPG码的应用尹芳滕舟〔桂林电子科技大学信息与通信学院,广西桂林541004)【摘要】LDPC码是迄今为止实验中最接近 Shannon极限的信道编码,也是下一代宽带移动通信系统中纠错码的主要备选方案。文章介绍了LDPC码的特点和优势,综述了LDPC码的编码结构及其优化、译码及其优仳、性能分析、码的工程实现和实际应用,分析了LDPC码的应用前景【关键词】LDPC码;二分图;校验矩阵;BP算法;EX∏图【中图分类号】TN9112【文献标识码】A【文章编号】1008-1151(2010)04005002Gallager在1962年提出的低密度奇偶校验码Tanner图中最短循环的长度称为图的 girth。LDPC码的( Low-Density Parity- Check Codes,LDPC是一类可以用稀 Tanner图和校验矩阵一一对应。疏矩阵或二分图定义的线性分组码。它具有非常好的特点:2.LDPC码的优化性能逼近香农限,描述方便,易于进行理论分析,译码简单码的结构决定了码的性能。目前关于LDPC码的构造方法且可并行操作,适合硬件实现。近年来LDPC码以其优异的性能、简洁的形式以及良好的应用前景,非常适合在未来的移有很多。对于长码、中长码,短码具有不同的构造方法,其中主要可以分为两大类:其一,随机构造和伪随机构造;其动通信系统中使用,因此吸引了广大研究人员进行了深入研结构化构造方法。码的随机性越好码的性能越好,但是随机究。现在许多正在拟定的通信标准都更多的关注了LDPC矿例如宽带无线接入协议E802.16、中国国家地面数字电视性码的编解码和硬件实现比较困难,一般只用于理论仿真和标准以及卫星通信标准DVB-S2已经采纳LDPC码比较。结构化构造方法可以分为代数构造方法和组合方法一)LDPC码的结构和优化代数方法中包括基于有限几何的构造方法和基于循环置换矩1.LDPC码的表示阵的方法。LDPC码是一种线性分组码,它的名字来源于其校验矩阵LDC的译码主要分为硬判决译码和软判决译码。软判决的稀疏性,即校验矩阵中只有数量很少的元素为“1”’大部译码主要采用迭代译码。如置信传播(B)算法和对数域置分都为“0”。正是由于校验矩阵是低密度矩阵,才能构造出信传播(LR)算法。BP译码的每次迭代包括两步:校验节点具有低复杂度、高性能的LDPC码。 Gallager最早给出了正则的处理和变量节点的处理。在每次迭代中,所有校验节点从LDPC码的定义,具体来讲正则(规则)LDPC码的校验矩阵H满相邻变量节点处接受信息,处理后再传回到相邻的变量节点足下面三个条件:(1)H的每行有p个“1”;(2)H的每列有λ个“1”,A≥3;(3)与码长n和H的行数相比,p和λ都然后所有的变量节点进行同样的过程;最后变量节点收集所有可以利用的消息进行判决。LLR算法将BP算法中大量的乘很小l1110000000。。00000。0法运算变成了加法运算,大大降低了译码算法的复杂度00。1111000000001码的优化包括编码的优化和译码的优化。要消除校验矩00000 00 0阵中的短环,特别是四环。可以采用结构化编码避免环,如准循环方法构造的QC-LDPC码、基于均衡不完全区组0010设计构造的BIBD-LDC码、光正交00C-LDPC码、 Turbo码结010。构的LDPC码(TS-LDPC码)等。如果采用随机化编码,如Gallager码、 Mackay码、PEG码,可以采用一定的编码方法。。。00。0。消除其中存在的短环,如四环、六环图1(20,3,4)LDC码的校验矩阵(二)性能分析DPC码除了用校验矩阵描述外,也可以由其二分图即LDPC码的性能分析方法主要分为三类:密度进化Tanner图表示。( Density Evolution)理论、高斯近似( GaussianApproximation)和EXIT图( ExtrinsicTransform Chart)。1.密度进化在LDPC码的译码过程中,存在一种阀值现象,或者成为门限效应,即在信道噪声水平低于某个阀值时,随着码长趋于无穷大,码的错误概率可以任意逼近零,否则错误概率将大于一个正的常数。 Richardson等人通过分析传递信息的概率密度的进化情况,发现在和积译码算法的每次迭代信息传图2(20,3,4)矩阵的 Tanner图中国煤化工【收稿日期】201001-20CNMHG【作者简介】尹芳(1985-),女,湖北咸宁人,桂林电子科技大学信息与通仁子九土,九月向为无线通信。递中出现错误信息的部分可以递归地表示成LDPC码的度分布和概念上不再有什么秘密,因此在知识产权和专利商不再有序列和信道参数的函数。迭代计算节点间传递信息的概率密什么麻烦。这些优点使得LDPC码在信道条件较差的无线移动度函数的方法就成为密度进化。他们通过研究递归函数证明通信中展现出了巨大的应用前景,非常适合于在未来的移动了阀值现象的存在性并给出了一种搜索好的节点度分布对的通信系统中实现。现在许多正在拟定的通信标准都更多的关数值优化技术。密度进化不仅应用于BEC信道,还可以扩展注了LDPC码到ISI信道,并由分析二进制LDPC码扩展到多进制LDPC码,近年来,LDC码的很多研究成果表明LDPC码时一类性能但是密度进化运算复杂度很高。优异的好码。LDPC码比 Turbo码在技术上更具有优势,更能2.高斯近似适应未来无线通信系统的要求。由于对LDPC码深入研究较晚晩,利用密度进化理论来计算阀值和寻找好的度数分布的算3G标准未采用,但基于LDPC码极有可能成为4G通信系统的法复杂度是相当大的,特别对于信息概率密度函数是多维的应用方案,日前已经有很多系统采用LDPC码。如802.1la、信道来说,密度进化算法就过于复杂而难以处理。为提高密802.11n、802.3an、802.16e、DVB-S2等标准都采用了LDPC度进化算法的计算速度, Chung等人采用高斯近似的方法,即码根据中心极限定理可以近似认为节点间迭代的信息的概率密(四)结语度函数是符合高斯分布的,这样讲迭代计算的多为问题转化除了优化编解码方法外,LDPC码还可以与调制、级联为跟新高斯密度均值的一维问题,极大简化了分析和计算信分集合并、链路自适应、跨层优化等技术结合以达到更优的道参数阀值的复杂度,而且可以快速的搜索和优化非规则性能。LDPC码由于LDPC码不仅有逼近香农限的良好性能,而且编译码3.EXIT图复杂度较低,结构灵活,因此成为第四代通信系统强有力的译码收敛性是指接收到的码字是吗能够通过迭代方法渐竟争者,具有巨大的应用潜力,将在深空通信、光纤通信近正确码字,如果能够接近则说明收敛,ⅨXIˆ曲线( Extrinsic卫星数字视频和声频广播、磁/光/全息存储、移动和固定无Information transfer Chart)是从互信息角度分析译码器线通信、电缆调制解调器和数字用户线(DSL)中得到广泛的的收敛性。互信息( mutual information)可以充分反映译应用。码器输入输出的相关性,它的特性:(1)互信息是最准确的【参考文献】统计变量;(2)互信息也几乎是鲁棒性最好的统计变量们袁东风,张海刚LDPC码理论与应用[M].人民邮电出版就是说互信息不会随着信道、调制解调器等变化而有很大变社,2008.化。因此,采用互信息来观察密度进化过程,比采用其他参[2]文红符初生LDPC码原理与应用M]电子科技大学出版数跟踪密度进化过程要简单而且有效。EXIT图比密度进化方社,2006.法计算量要小得多[]袁东风张海霞宽带移动通信中的先进信道编码技术[M]J(三)LDP码的应用北京邮电大学出版社,2004LDPC码的应用有4个明显优势:首先,LDPC码具有一套[4] Nicholas Bonello, Sheng Chen, Lajos hanzo. Construction of较为系统的优化设计方法、更强大的纠错能力和更低的地板Regular Quasi-Cyclic Protograph LDPC Codes Based on效应。其次,由于LDPC码译码不基于网络,迭代译码算法为Vandermonde Matrices].IEEE Transactions on vehicular并行算法,可以实行完全并行的操作,便于硬件实现,延时technology July 2008远远小于 turbo码的串行迭代译码算法。第三,LDPC码本身[5] Eran Sharon, Analysis of Low- Densty Parity-Check Codes即有抗突发差错的特性,不需要引入交织器,避免了可能带Based on EXIT Functions[] IEEE Transactions on来的延时。第四,LDPC码是上世纪60年代发明的,现在理论ommunicationsAugust 2006一一一一一一一一一一一一一二二二二一上接第64页)理.在通过随机方法产生光线后,因为随机的效果性而会有噪声存在,在光照部分可以细分,而反射面到随机使用蒙特卡罗的随机光能汇集可以使计算量减少来满足光线未到达部分则不用再细分。其中,分层思想涉及到波形实时情况下渲染帧数的提高,但由于随机性使其从显示上来因素细分和块面细分两方面内容看,还有噪声的存在;分层概念的引入则是为了弥补噪声的(1)波形因素F。需要投射面的波形因素F到足够存在,在有噪声部分使分层面块变大,计算精度降低,模糊,小否则就再分F下一步的工作是让随机光能汇集产生的噪声结合新的方法来满足实时光照要求。足m=()(-()2+(+…),r为块的面积,R是点到块中心的距离,并且r远远小于R【参考文献】(2)面块规则。面块可以借用二叉树型结构,如图2。[1 GoralC M, T orance K E et a Modeling the interaction of light通过规则:一个块只能访问其同层但不直接相邻的块,并且between diffuse surfaces]. Computer Graphics 1984, 18(3)只能访问其父块直接相邻的节点中的那些子块.通过这两条2 Cohen F, donald P. reenberg; Hemi-cube a radiosity规则,可以看到如块b在图2中能访问的块就是块f:同理块a能访问的块就是块d。[3] KaiyaJ T, et al. T he R endering Equation[]. ACM Sig GraphComp Graph, 1986.(四)结语[4]Cohen M F,通过对物体表面分层化照射渲染和使用蒙特卡罗随机光to fast radios中国煤化工rh,19824源汇集的方法可以实时的实现全局光照效果,在节约渲染时5] Gregary),FraCNMHGatang solution to间和图形处理器时间和性能的条件下,达到了比较令人满意dffureintereiedu