（通信与信息系统专业论文）ldpc码解码技术研究及实现.pdf

东南大学硕士学位 龟文 摘要 低密度奇偶校验码( l d p c ) 码是由g a l l a g e r 在1 9 6 2 年首先提出l | l 匀一种纠错码，在沉赢了多年 之后，最近又重新成为道信技术研究的热点。l d p c 码是一种具有稀疏校骑矩阵的线性分组码，研 究结果袤明，采罔姑代的概率译玛弊法，l d p c 码可以达到接近番农极限特性能。本论文主簧对i d p c 鹳的译码算法和硬件实现进彳亍了较深入的研究。 本文研究r 在白高斯噪声情道下，l d p c 码的1 种主要邀代译码算法。这些算法包 苫：g a l i a g e r 的b f 算法、w b f 算法、可信度传播( b p ) 算法、蛐一化的b p b o s e d 算法等等。在w b f 算法的基 础上，论文提出t 一种新鼢选代译码算法( w s - w b f 算法) ，该算法在基本不增加孽码复杂度的情 况下，对译码睦自有较大的提高。为了打破基于b f 的并个算法中的i n f i n i r el o o p ，论文还提出了一 种更易丁蜜现的p a r l i a ll o o pb r e m 算法，同样提高了译码性能。我甘j 给出了l d p c 羁袁这些不硒译 码算法下的堤码率、误j 蛳率和选代次数的仿真结累。同时，本文对l d p c 译码器的关键参数、硬件 实现中的定点最化与字长精度问题进行了济a 的研究，给出了对译码器硬什实现具有参考意义柏研 究结集。 屠后，论文讨睡了l d p c 码译码器的硬件宴现，分析丁三种主要的硬 牛实现结构；全并行结构、 部分并行结构、串行结构。随机构造的l d p c 码，由 二棱验矩晔中嚣零元素分布的随机雌，根难采 用部分并行结构。本文介绍了种码和译码器联合殴汁、适台采用都分并行结构译码的面向v l s i 的l d p c 码构造方法。这种构造方法不仪能够阡低译码器硬什实现的复杂度，还可以逼近随机椅造 l d p c 码胸性能。为了验证竣构造方法，我甜j 在v i r t e x i l 6 0 0 0 系列p p g a 上实现了码长为2 3 0 4 、码 率为1 彪的正则l d p c 码泽码器。全部设计采用v e r i l o g 语言捕述，当最犬选代次数为1 0 次，详硝 嚣的鞋钵麴率为6 5 m h z 时，译码速率达到5 0 m b p s 。 关键词：低密度奇偶校螳码，迭代译码，可信度传播掉法，j o i n t c o d e a n d d e c o d e r 设计方法，f p g a 东南大学硕士学位论文 a b s t r a c t l o w d e n s i t yp a r i t y - c h e c k ( l d p c ) c o d e sw e r ef i r s td i s c o v e r e db yg a l l a g e ri nt h ee a r l y1 9 6 0 sa n d r e c e n t l yh a v eb e e nr e d i s c o v e r e da n dg e n e r a l i z e dt h i sc l a s so fc o d e sd e c o d e d w i t hs o f t - i ns o f t o u t ( s i s o ) i t e r a t i v e d e c o d i n gp e r f o r m sa m a z i n g l yw e l l s i n c et h e i rr e d i s c o v e r y , d e s i g n ，c o n s t r u c t i o n ，d e c o d i n g ， a n a l y s i sa n da p p l i c a t i o n so f l d p cc o d e d h a v eb e c o m e f o c a lp o i n t so f r e s e a r c h a m o n g t h e m ，t h ed e c o d i n g a l g o r i t i n na n d i t si m p l e m e n t a t i o na r et h ef o c u so f t h i st h e s i s i nt h i st h e s i s ，s e v e r a li t e r a t i v em e s s a g ep a s s i n ga l g o r i t h m sf o rl d p cc o d e s ，s u c ha sg a l l a g e r sb i t f l i p p i n g ( b f ) a l g o r i t h m ，w e i g h t e db fa l g o r i t h m ，b e l i e fp r o p a g a t i o n ( b p ) a l g o r i t h ma n dn o r m a l i z e d b p b a s e da l g o r i t h me t c ，a r ec o n s i d e r e d a so d eo fc o n t r i b u t i o n so ft h i st h e s i s ，a l li m p r o v e dd e c o d i n g a l g o r i t h mb a s e do i l t h ew b fa l g o r i t h m ( w s w b f ) i sp r o p o s e d c o m p a r e dw i t hw b f a l g o r i t h m ，i t a c l d e v e sc o n s i d e r a b l ei m p r o v e m e n tw i t ha l m o s tt h es a n l ec o m p l e x i t y i no r d e rt ob r e a kt h ei n f i n i t el o o pi n t h eh a r dd e c i s i o na l g o r i t h m ，ap a r t i a ll o o p - b r e a ka l g o r i t h m ，w h i c hi sm u c he a s i e rt oi m p l e m e n t ，i sa l s o i n c l u d e di nt h i st h e s i s a tt h es a i i l et i m e ，s o m e k e yp a r a m e t e r sa n df i n i t ep r e c i s i o na n a l y s i sf o rt h eh a r d w a r e i m p l e m e n t a t i o n o fl d p cd e c o d e rh a v eb e e n p e r f o r m e dc o n s i d e r i n g t h et r a d e o f fb e t w e e nh a r d w a r e c o m p l e x i t ya n d e r r o r p e r f o r m a n c e e v e n t u a l l y , t h ea r c h i t e c t u r e sf o rm eh a r d w a r ei m p l e m e n t a t i o no f l d p c d e c o d e r , i n c l u d i n gf u l lp a r a l l e l a r c h i t e c t u r e ，p a r t l yp a r a l l e l a r c h i t e c t u r ea n ds e r i a l a r c h i t e c t u r e ，h a v eb e e na n a l y z e d am e t h o d ，w h i c h j o i n t l yc o n c e i v i n g c o d ec o n s t r u c t i o na n dd e c o d e r a r c h i t e c t u r e i si n t r o d u c e dt oa p p r o a c ht h ee r r o r p e r f o r m a n c eo fp s e u d a r a n d o ml d p cc o d e st h a te x a c t l yf i t1 0h i g h s p e e dp a r l l yp a r a l l e ld e c o d e ra n d l o w c o m p l e x i t y e n c o d e r i m p l e m e n t a t i o n t o d e m o n s t r a t et h i s j o i n td e s i g nm e t h o d o l o g y , af p g a i m p l e m e n t a t i o no f2 3 0 41 2r e g u l a rl d p cc o d ei sr e a l i z e du s i n gx i l i m x l l 6 0 0 0d e v i c e t h ed e s i g ni s d e s c r i b e di nt h ev e t i l o gh a r d w a r ed e s c r i p t i o nl a n g u a g e ( h d l ) a r t ds y n l i f y w a su s e dt os y n t h e s i z et h e v e r i l o gi m p l e m e n t a t i o n b yp e r f o r m i n gm a x i m u m1 0 d e c o d i n gi t e r a t i o n s ，t h ed e c o d e rc a l l a c h i e v ea m a x i m u mb i tt h r o u g h p u t o f 5 0 m b p s k e yw o r d s ：l o wd e n s i t yp a r i t y c h e c kc o d e s ，i t e r a t i v ed e c o d i n g ，b e l i e f p r o p a g a t i o na l g o r i t h m ，j o i n tc o d e a n dd e c o d e r d e s i g nm e t h o d o l o g y , f p g a 儿 y b 44443 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究j f 作及取得的研究成 果。尽我所知，除了文中特别加以标注汞1 致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过 的材料。与我同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了酣意。 研究生签名：狴日 期：硅! ! 垒 ，2 东南大学学位论文使用授权声明 东南大学、中国科学技杏信息研究所、国家图书馆有权保留本人所送交学位论文的 复e i ，f q 一和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名：导师签名：趣l _ _ 期：卯乒3 ，： 苎二里竺堡 一 第一章绪论 通信的目的是把对方不知道的消息及时可靠的传送到对方，但在数字通信系统中，可靠和快进 往往是对矛盾。若要求快速，则必然使得每个数据码元所占的时间缩短、波形变窄、能量减小， 从而在受到干扰后产生错误的可能性增加，传送消息的可靠性减低。若要求可靠，传送消息的速率 就必须变慢。因此。如何合理的解决可靠性与速度这一对矛盾，是正确设计一个通信系统的关键问 题之。纠错编码正是在解决这对矛盾的过程中不断发展起来的。 信 羼i 产生的原始数字序列魁无法直接检测和纠i e 错误的，我们需要在序列中添加冗余的信息， 利用它们进行检错和纠错。纠错编码在数字通信中的作用，就是检测和纠正传输错误，我们使用纠 错编码的目的就是要在尽可能少的添女b 冗余度的同时，最大他纠错编码的能力。1 9 4 8 年，香农建立 的信息论【1 1 确定了纠错编码抗干扰能力的极限。香农定理指出了纠错编码能够有效纠错所需的最小 比特信噪比，我们称之为香农限。寻找能够实际应用的逼近香农限的编码方案和译码算法就成了纠 错编码理论的最终目标。 1 1 近香农限的纠错编码 香农信道编码定理肯定了逼近香农限的编码方案的存在，但并来说明如何找到符合要求的编码 方案。为了找到逼近香农限的编码方案，上世纪五十年代到六十年代初，人f f 、j 相继研究了两大类纠 错编码：线性分组码和卷积码。线性分组码以代数中的群论、域论等理论为数学基础，他们的译码 方法通常是大数逻辑和捕错译码。卷积码在编码过程中引入了寄存器，增加了码元之间的相关性， 在相同复杂度的条件下可以获得比分组码更高的编码增益。卷积码的译码算法主要有序列译码算法 和维特比( v i t e r b i ) 算法。实际应用中，无论是分组码还是卷积码大多采用短码，圆为它们的译码 复杂度与码长成指数关系，随着码长的增加，译码的计算量极大的增加，基本不可能实用。令人失 望的是，要达到香农限，纠错码的码跃必须足够长所以上述的短码都难以达到逼近香农限的目标。 到了上世纪八十年代到九十年代初，经过几十年的研究和实践，纠错编码理论和技术取得了突 飞猛进的发展。1 9 9 3 年，c b e r r o r 等人在i c c 9 3 会议上提山了t u r b o 码 ”，它巧妙的将卷积码和随 机交织器结合在一起，实现了随机编码的思想。采用软输入、软输出的迭代译码算法，这种编码能 够在码长较长时逼近香农的理论极限，目前较为流行的t u r b o 码译码算法主要有；m a p 算法、 l o g m a p 算法、m a x l o g - m a p 算法和s o v a 算法。仿真结果表明，在a w g n 信道和b p s k 橱制下， 如果采用6 5 5 3 5 的随机交织器，并且进行1 8 次迭代，则在e j n o o ，7 d b 时，码率1 2 的t u r b o 码的 误比特率( b e r ) 1 0 一，逼近了香农限的性能( 1 2 码率的香农限约为o d b ) 。t u r b o 码被看作是1 9 8 2 年t c m 技术问世以来，信道编码理论所取得的最大成就，具有里程碑的意义。 在t u r b o 码获得巨大成功的启发下，另一种具有相似特性的纠错码复活了，这就是低密度奇偶 校验( l d p c ) 码。l d p c 码是g a l l a g e r 码的推广，1 9 6 2 年，g a l l a g e r 在中提出了一种编码，现在 通常椽为g a l l a g e r 码，这种编码由于校验矩阵的稀疏性，使得译码的复杂度只与码长成线性关系， 当码k 较k 时，仍然可以进行有效的译码。然而当时人们普遍认为级联码更容易实现，忽视了g a t t a 烀r 东南大学硕士学位论文 码的存在。d j c m a c k a y 、m n e a l 和n w i b e r g 等人对g a l l a g e r 码重新进行了研究，发现g a l l a g e r 码 虽然性能较t u r b o 码略有差距，但它同样具有逼近香农限的性能。在g a l l a g e r 码的基础上，他们进 一步研究了多元域上的l d p c 码吲，发现多元域上的g a l l a g e r 码较二元域上的码的性能有较大提高， 且域的阶数越高编码的性能越好。m g l u b y 和m m i t z e n m a c b e r 等人从另一个角度对g a l l a g e r 码进 行了推广，提出非正则l d p c 码【6 1 ，这种纠错码的性能能够赶上甚至超过t u r b o 码。 l d p c 码和t u r b o 码有着许多相似的地方在它们的构造方法中存在许多随机排列的元素，表 现出随机码的特性。此外，两者的译码算法也存在着惊人的相似。n w i b e r g 在他的博士论文口3 】中， 构建了迭代译码算法的一个通用结构，通过研究，n w i b e r g 发现l d p c 码的迭代译码算法和t u r b o 码的迭代译码算法都可以用这一通用结构解释。l d p c 码的迭代译码算法是基于可信度传播的， m c e l i e c e 、m a c k a y 和c h e n g 在 7 1 中认为t u r b o 码的迭代译码算法可以看作p e a l 的可信度传播算法 ( b e l i e f p r o p a g a t i o n ) 的一个特例。 1 2研究l d p c 码的意义 l d p c 码和t u r b o 码都已经被证实，是可以实际应用的，性能接近香农限的纠错编码。但相对 于t u r b o 码，l d p c 码有着明显的优势： 可以达到很高的码率。l d p c 码可以达到07 、0 8 甚至0 9 的码率，而目前使用的t u r b o 码的码率大都是1 3 ，1 2 。 泽码速率快。l d p c 码基于可信度传播的译码算法本质上是并行算法，有利于硬件的并行 实现，可以达到很高的译码速度。例如，f l a r i o n 技术公司例已开发了l d p c 编、译码器产 品，称为v e c t o rl d p c 。采用f p g a 实现，时钟频率1 0 0 m h z ，码长l = 1 0 0 0 0 ，码率r = 0 9 ， 编码器利用6 4 k 逻辑门和1 3 1 d 3 存储器时，编码速率可达19 g b p s ；译码器使用3 2 0 k 逻辑 门和3 8 k b 存储器时，译码速率为3 8 4 m b p s 。采用a s i c 实现，时钟频率3 2 5 m h z ，码长 l - 5 0 0 0 0 ，码率r = 0 9 ，泽码器使用2 6 m 逻辑门和1 9 0 k b 存储器时，可工作在1 0 g b p s 。 不可检测错误少。由于l d p c 码码字之间的码距较大，使得它译码过程中出现不可检测错 误的概率很小。 发生“平板效应”( e r r o r - f l o o r ) 的概率低。随着信噪比的增加，t u r b o 码误码率的下降趋势 将趋于平缓，即出现所谓的“平板效应”。但是l d p c 码发生这种现象的概率低得多，这使 得l d p c 码在深空通信或光纤通信中更具优势。 理论分析简单。不同于t u r b o 码，l d p c 码有简单的数学模型，理论分析相对简单。目前， 对l d p c 码的译码性能分析已经有了一些较为完善的理论，但t u r b o 码的性能还缺乏有效 的理论解释。 l d p c 码可以采用基于硬判决的迭代算法，虽然性能比软判决差，但实现复杂度很低。t u r b o 码泽码在迭代时必须传递软信息，因此无法使用硬判决算法。 由于校验式的存在，使得l d p c 码的译码过程中能够确定码字是否正确，这样不仅可以省 掉c r c 编码，而且可以采用动态终止算法米减少迭代次数。 2 。 第一章绪论 当然，没有一种技术是十全十美的，与上面的优点相对应，l d p c 码也存在一定的问题。这些 问题制约了l d p c 码的广泛应用，如何有效的舸决它们，成为纠错编码领域研究的热点。 编码复杂度高。虽然最新的研究表明l d p c 码可以在线性时间内编码，但其复杂度相对于 t u r b o 码来说仍然过大，更加无法和卷积码等即时编码的纠错码相比。 中短码长的l d p c 码性能不理想。l d p c 码性能的优越性通常在码k 较长时才能体现，当 采用中、短长度的l d p c 码时，由于编码时短长度闭合环路的存在，会在某种程度上降低 译码性能。 低码率情况下性能不理想。由于低码率的纠错码抗衰落的性能较好，因此大多数移动通信 系统采用码率较低的纠错码，但是低码率l d p c 码的性能与t u r b o 码相比处于卜- 风。 当l d p c 码译码器采用全并行结构时，虽然译码速率很高，但硬件资源消耗太大。实际应 用中更可能采用的方案是部分并行结构，目前，适用于部分并行结构的l d p c 码的构造方 法还不完善。 综上所述，尽管l d p c 码有着卓越的- 陛能，但仍有很多阅题有待解决。研究l d p c 码仍然具有 十分重要的实用价值。 1 3l d p c 码的研究现状 自从1 9 9 5 年m a c k a y 发表文章【4 1 使得l d p c 码被重新认识以来，许多研究人员都投入到l d p c 码的研究之中，从1 9 9 9 年开始这方面的研究文献人量山现。经过几年的研究，l d p c 码的理论和应 片j 研究取得了不小的进展，还有一些工作正在进行，下面从几个方面介绍一下l d p c 码的研究成果 零j 主要研究方向【4 ”。 l | 3 1 l d p c 码的编、解码 l d p c 码所面临的一个主要问题是其较高的编码复杂度和编码延时。如果采用普通的编码方式， l d p c 码具有二次方的编码复杂度，在码长较长时这是难以接受的。t j r i c h a r d s o n 和r l u r b a n k c 在文献。”】中给出了一种利用校验矩阵的稀疏性对校验矩阵进行一定的预处理后，在线性时间内编码 的有效算法，初步解决了l d p c 码编码的复杂度问题。s l i n 等在1 1 1 中提出一种具有循环码特性的 l d p c 码，它同样具有稀疏的校验矩阵，编码可以通过线性移位反馈寄存器来完成，实现了具有线 性复杂度和线性延时的编码。 l d p c 码的译码算法是影响其性能的一个重要因素。研究发现，在理想的编码条件下，即编码 结构中没有闭合环路时，b p 算法与最大似然译码算法效果一致。但是，在码长有限的情况下闭合环 路的存在是必然的，这时b p 算法与最大似然算法有一定的差距。如何在不造成过高译码复杂度的 情况卜，缩小这个差距是l d p c 码的一个研究课题。硬判决算法虽然性能比b p 算法差，但译码复 杂度很低，十分适合在光纤通信等信道条件较好的系统中应用。针对硬判决译码算法的改进也同样 引起人们的兴趣。另一方面，针对非高斯的低质量信道上译码算法的研究也已经展开，如瑞利衰落 信道、部分响应信道、和i s i 信道等 1 4 】。 变塑奎堂塑主兰堡堡塞 一 1 3 2l d p c 码的设计方法 中、短码长的l d p c 码，如果编码结构中有较短闭合环路存在，会大大降低陛能，因此在构造 l d p c 玛时必缏避免较短闭合环路的出现。现有的构造方法主要有两种：一种是进行类似构造隧机 码那样的大范围搜索。搜索方法是根据r i c h a r d s o n 等人提供的局部优化和全局优化搜索方法”，它 们的搜索量相当大，需要借助汁算机完成，更完善有效的搜索算法有待进一步的研究；另一种l d p c 码设计方法是利用一些已有的数学结论进行构造，主要有组台构造法【1 “、有限几何构造法”、群论 构造法旧和图论构造法渊。 通过上述方法构造的l d p c 码的校验矩阵中非零元素分布具有随机性，译码器不具备采用部分 并行结构的条件，实用性较著。为了解决这一问题。文献“”提出一种从译码角度考虑的l d p c 码构 造方法( d e c o d e r - f i r s tc o d ed e s i g n ) 。这种码的泽码器可以采用部分并行结构，但译码器设计中仍然具 有很多随机数发生器，真正实现时复杂度还是很高，同时它的编码器实现也比较复杂。针对这一领 域的研究方兴未艾，拥有广阔的前景。 1 3 3l d p c 码的实现和应用 除了上面提到的f l a r i o n 公司推出了基于f p g a 和a s i c 的l d p c 编、解码器外，基于d s p 的 l d p c 编、解码器也已经研制成功。同时，由于l d p c 码性能的优越性，使其有望在通信中得到 广泛的应用。目前在第四代移动通信中使用l d p c 码的提案已经提交；而l d p c 码在d s l 、a d s l 2 ”、 深空通信及磁记录介质【”i 等信道上的研究正在展开：此外在与t c m ，基于l d p c 的时空码l 等与 其他技术结合方面的研究也在进行中。 1 4本文的主要内容 本论文选择l d p c 码的译码作为主要研究方向，仿真了a w g n 信道下不同译码算法的性能。本 文在w b f 算法的基础上，提出了一种改进的l d p c 译码算法( w s w b f 算法) ，同时针对基于b f 的各个算法中出现的i n f i n i t el o o p ，提出了一种简化的l o o pb r e a k 算法，进一步提高译码性能。论文 的最后，我们研究并探讨了l d p c 码译码器的硬件实现。 论文共分五章，本章为绪论，简单介绍了l d p c 码的发展、优缺点和研究现状。第二章详细阐 述了l d p c 码的一些基本概念，包括l d p c 码的二分图结构和l d p c 码的闭合环路等，同时基于不 同的方面对l d p c 码进行分类。第三章中，我们重点讨论了l d p c 码的主要译码算法，内容从硬判 决和软判决两个方面展开。在本章中，我们提出了种改进的w b f 算法：w s w b f 算法，并对 c o m p l e t e l o o p - b r e a k 算法进行简化，提出了p a r t i a l l o o p - b r e a k 算法。仿真结果表明，两者结合可以取 得很好的译码陛能。第匹| 章研究了l d p c 码译码算法的定点化，并给出了利用非均匀压缩来节省存 储资源的最优方案。本章主要针对的是两种适台硬件实现的算法：w s w b f 算法和归一化的 b p b a s e d 算法。第五章给出了l d p c 码译码器的三种主要结构：全并行、串行、部分并行结构，分 析它们的特点，最后重点介绍一种同时考虑码的构造和译码器结构、适合采用部分并行结构译码的 l d p c 码构造方法，并在v i r t e xi i 系列f p g a 上进行验证。 4 一 第二章l d p c 码的简介 第二章l d p c 码的简介 低密度奇偶校验码本质上是一种线形分组码，它通过一个生成矩阵g 将信息序列映射成发送序 列，也就是码字序列。对于生成矩阵g ，完全等效的存在一个奇偶校验矩阵，所有的码字序列y 构成了日的零空间，即h y l = 0 。 l d p c 码的奇偶校验矩阵日是一个稀疏矩阵，相对于行与列的睦度( m ) ，校验矩阵每行、列 中非零元素的数目( 我们习惯称作行重、列重) 非常小，这也是l d p c 码之所以称为低密度码的原 因。由于校验矩阵日的稀疏性以及构造时所使用的不同规则，使得不同l d p c 码的编码二分图( t a n n e r 图) 具有不同的闭合环路分布。而二分图中闭合环路是影响l d p c 码性能的重要因素，它使得l d p c 码在类似可信度传播( b e l i e f p r o p a g a t i o n ) 算法的一类迭代译码算法下，表现出完全不同的译码性能。 当爿的行重p 和列重y 保持不变或尽可能的保持均匀时，我们称这样的l d p c 码为正则l d p c 码， 反之如果列、行重变化差异较大时，称为非正则的l d p c 码。l u b y ，m i t z e r m l a c h e r 等在文献【6 1 中证 明了正确设计的非正则l d p c 码的性能要优于正则l d p c 。根据校验矩阵h 中的元素是属于g f ( 2 ) 还是g f ( q ) ( q = 2 9 ) ，我们还可以将l d p c 码分为二元域或多元域的l d p c 码。文献【1 1 的研究结 果表明，多元域l d p c 码的性能要比二元域的好。正是因为l d p c 码的校验矩阵非常稀疏，它的码 字还具有较大的最小码间距和较好的码间距离分布，这一点可以和完全随机构造的，即0 和1 等概 分布的校验矩阵所决定的线性分组码相比较。f 面我们分别讨论l d p c 码的上述几个重要特性。 2 1 l d p c 码的二分图结构 对于任何一种线形分组码，t a n n e r 在口4 1 中提出了一种简单的表示形式：编码二分图( t a n n e r 图) 。 l d p c 码的二分图由两类节点组成：变量节点( v a r i a b l en o d e ) 和校验节点( c h e c kn o d e ) ，分别对应 于校验矩阵h 中的列和m 行。同一个集合内部的节点没有连线，只有属于不同集合的两点之问 可能有连线，每一条连线对应于校验矩阵中的1 。为了方便，我们借用g a l l a g e r 对l d p c 码的表 示方法：将码长为，行重、列重分别为p 和y 的l d p c 码称为( ，y ，p ) l d p c 码。式2 1 是 某个( 8 ，2 ，4 ) l d p c 码的校验矩阵和相应的校验方程，根据校验矩阵我们可以画出它的二分图( 图 21 ) 。图中变量节点集合( v 1 ，v 2 v 8 ) 和校验节点集合( c ，c 2 c 4 ) 内部不存在相连的边，但两类节 点之间存在着连线。变量节点和校验节点之间存在连线意味着该变量比特参加了此校验式，也就是 校验矩阵某一行中1 的位置。我们将每个节点上的连线数目称为该节点的次数( d e g r e e ) ，图2 1 中，变量节点的次数( d ，) 为2 ，校验= 宵点的次数( d ) 为4 。 11 1o 01 o 0 oo 0l 11 10 1o 01 10 o1 ( 2 1 ) 0 o o o 一一 = i l = 竹n 坼 0 o 0 o “心鸭你 o o o o n 唯心n 0 0 o o h h 比如 东南大学硕士学位论文 图2 1 的二分图结构中，四条租线构成了一个有向的闭合环路，由v l 起始，经过q 斗毪呻c 2 最后返回v 1 。在一个l d p c 码的二分图中，每个节点都会存在许多这样的闭合环路，我们将其中长 度最小的一个称为该节点的最小环长( s h o r t e s te y r i e ) 。二分图中所有节点的最小环长中，长度最小 的称为二分图的最小圈长( g i r t h ) ，上例的二分图中，g i r t h 与变量节点1 的最小环长相等，都是4 。 图2 1( 8 ，2 ，4 ) l d p c 码的二分图 l d p c 码二分图结构中g i r t h 的大小对l d p c 码的译码性能有很大影响。t & m ：e r l “】认为g j 幽的妖 度将直接关系到l d p c 码码字的最小码距，并给出了最小码距的下界与百n h 的关系式： d d ( d - ，1 ) ( 7 、- 1 ) g - 2 ) 、4 - 1 + 生 ( d 一1 ) ( r 一1 ) _ 2 ) 州 2为奇数d-i ( r - 。d - ： y “一1 一 d d 竖笔尘恶掣 啦为偶数。1 ( d 1 ) ( y 一1 ) 一 。 其中，d 为l d p c 码的最小码距，g 为l d p c 码的g i r t h ，为变量节点的次数，d 为二分图中子码 ( s u b c o d c ) 的最小码距。从公式中可以看出，g i r t h 的长度越大，l d p c 码的最小码距越大，译码睫 能也就更好。仿真结果表明，如果二分图中存在长度为4 的g i r t h ，l d p c 码的误码率性能将会很差， 所以我们在构造l d p c 码的校验矩阵时，要尽量避免二分图中出现g i r t h 为4 的情况。 l d p c 码的译码算法主要是迭代译码算法，因为某些节点存在闭合环路，当迭代次数较多时 到达这些节点的信息不再满足统计独立的特性，从而使得译码性能与最大似然算法有一定的差距。 因此，我们在设计l d p c 码时，在保证g i r t h 大于4 的情况下，各个节点的最小环长越大越好。令人 惊奇的是，即使二分图中存在不少这样的闭合环路，但只要g i r t h 大于4 ，l d p c 码应用迭代译码算 法依然可以取得较好的误码率性能。g a l l a g e r p 认为造成这种现象的原因是：随着迭代次数的增加， 独立性产生的影响越来越小，而且趋向于相互抵消，当迭代次数到达一定的次数，闭合环路影响译 码结果的可能性很小。 图2 2 是不同码陡l d p c 码的最小环长分布，从图中可以看出，随着码长的增加，拥有较短k 度闭合环路的：点越来越少。例如，码长为1 1 5 2 的l d p c 码，最小环长只有两种：6 和8 ，而长度 为6 的：肖点占了3 9 。当码睦增加到9 2 1 6 ，二分图中已经没有长度为6 的闭台环路，最小环为 1 0 的节点有5 0 。最小环长的分布状况可以作为衡量l d p c 码结构好坏的一个准则，二分图结构中 第二章l d p c 码的简介 短长度的环占的比重越少，l d p c 码的译码就越接近理想中无圈( c y c l ef r e e ) 的假设。当l d p c 码 的码长趋向于无穷，其编码二分图结构可以看作近似无圈，l d p c 码在b p 算法下的译码性能也就完 全等效于最大似然译码。 o-h岫，h帅m 图2 2不同码长l d p c 码的最小环长分布 2 2 正则与非正则l d p c 码 在l d p c 码的校验矩阵中，如果行列重量固定为( p ，) ，郎每个校验节点有p 个变量节点参 与校验，每个变量节点参与，个校验节点，我们称之为正则l d p c 码。g a l l a g e r 最初提出的g a l l a g e r 码就具有这种性质。从编码二分图的角度来看，这种l d p c 码的变量节点次数全部为y ，而校验节 点的次数都为p 。我们还可以适当放宽上述正则l d p c 码的条件，行列重量的均值可以不是一个整 数，但行列重量尽量服从均匀分布。另外为了保证l d p c 码的二分图上不存在眭度为4 的圈。我们 通常要求行与行以及列与列之间的交叠部分重量不超过1 ，所谓交叠部分即任意两列或两行的相同 部分。我们可以将正则l d p c 码校验矩阵h 的特征概括如下： 、的每行行重固定为p ，每列歹重固定为y 。 2 、任意两行，两列之间交叠部分重量最多为l 。 3 、行重p 和列重y 相对于日的行数m 、列数n 很小，h 是个稀疏矩阵。 4 、正则l d p c 码的最小码率，可以通过下式计算： ，= ( n m ) n = 1 一m n = 1 一y p ( 2 3 ) 在正则l d p c 码的校验矩阵中行重和列重的均值保持不变，所以校验矩阵中1 的个数随着码 长的增加而线性增长，整个校验矩阵的元素个数则成平方增长。当码k 达到一定长度时，校验矩阵日 是非常稀疏的低密度矩阵。对于正则的l d p c 码，m a c k a y 在m 中给出了以下两个结论： t 、对于任意给定列重大于3 的l d p c 码，存在某个小于信道传输容量且大干零的速率，当码 - 7 一 东南大学硕士学位论文 长足够长时，可以实现以小于r 且不为零的速率无差错的传输。也就是说任意给定一个不为零的传 输速率，存在一个小于相应香农限的噪声门限，当信道噪声低于该门限且码长足够长的时候，可 以实现以r 速率无差错的传输。 2 当l d p c 码的校验矩阵日的列重 ，不固定，而是根据信道特性和传输速率来确定时，则一 定可以找到一个最佳码，实现在任意小于信道传输容量的速率下无差错的传输。 对于l d p c 码的每个变量节点来说，当它参与的校验式越多，即次数y 越火，则它可以从更多 的校验节点获取信息，也就可以更加准确的判断出它的正确值。对于日的每个校验节点来说，当它 涉及的变量节点越少即次数p 越小，则它可以更准确的估计相关变量节点的状态。这种情况对于正 则l d p c 码来说是一对不可克服的矛盾，于是l u b y ，m i t z e n m a e h e r 等人就引入了非正则l d p c 码的 概念。 在非正则l d p c 码的编码二分图中，两个集合内部的节点次数不再保持相同，即每个变量节点 参与的校验式数目或每个校验式中含有的变量节点数目不再保持均匀，而是有意设置部分突出的变 量节点和校验节点。在译码过程中，那些参与较多校验式的变量节点迅速得到它们的正确译码信息， 这样它们就可以给相邻的校验节点更加有效的概率信息，而这些校验节点又可以给与它们相邻的次 数少的变量节点更多的信息。整个译码的过程呈现出一种波状效应，次数越高的变量节点首先获得 正确信息，然后是次数较低的节点，然后依次往下，直到次数最低的变量节点。正是这种波状效应， 使得非正则l d p c 码获得比正则l d p c 更好的译码性能。理论上的极限性能仅仅比香农限高 0 0 0 4 5 d b 的非正则码次数分布对已经找到。 为了描述非正则的l d p c 码，我们需要定义相应的次数分布，节点的次数分布和边的次数分布 是两种常用的次数分布。节点的次数分布以( n ) 定义为次数为i 的变量( 校验) 节点在所有变量( 校 验) 节点中所占的比例。边的次数分布元( a ) 定义为与次数为i 的变量( 校验) 节点相连的边数占 总边数的比例a 若( d ，。，d 。一) 为变量节点和校验节点中的蹑大次数，则有 ( 2 4 ) 根据l d p c 码的编码二分图，每条边两端总对应一个变量节点和校验节点，所以有( 2 5 ) 式。 n + 矾= m + d 。，乏= f 。以，乏= i + p i 一一d y d 对应的非正则l d p c 码的最小码率 d d ，= 1 一( f + 一) ( f + n ) ( 2 5 ) ( 2 6 ) l | b h i i y h 第二章l d p c 码的简介 n ( 一) 和厦( 形) 存在如下的换算关系 i 4 y ：= d v 。97 ，i 4p ? = d ：4 净j ( 2 7 ) 例如有；n 的变量节点的次数为3 t 吉的变量节点次数为4 ，还有壹变量节点的次数为5 我们可n a i l - - 组向量来表示该非正则l d p c 的节点次数分布 尹= ( 7 i , y 2 , y 3 , y 4 , y 5 ) = ( o ，0 ，；，百1 ，瓦5 ) 。 类似的我们还可以用边的次数分布来描述 一 ! 31 - 4三n *