（通信与信息系统专业论文）ldpc码译码器fpga实现研究.pdf

哈尔滨丁程大学硕十学位论文 摘要 l d p c 码以其接近s h a n n o n 极限的优异性能在编码界引起了轰动，成为 研究的热点。随着研究的不断深入和技术的发展，目前，l d p c 码已经被多 个通信系统定为信道编码方案，并被应用到第二代数字视频广播卫星 ( d v b s 2 ) 通信系统中。由于l d p c 码译码过程中所涉及的数据量庞大，译 码时序控制复杂，如何实现l d p c 码译码器成为了人们研究的重点。 论文以基于f p g a 实现l d p c 码译码器为研究目标，主要对译码算法选 择、译码数据量化、定点数据表示方式、译码算法关键运算单元的f p g a 设 计和译码的时序控制进行了深入研究。首先分析了l d p c 码的基本译码原理 和常用译码算法。然后重点分析了b p 算法、l o g b p 算法、最小和算法和归 一化最小和算法，并对四种译码算法的纠错性能和译码复杂度进行比较论证， 选出适合硬件实现的译码方案。结合通信系统，对译码算法进行仿真分析， 确定了译码算法的各个参数值和译码量化方案。 在系统仿真分析论证的基础之上，以归一化最小和译码算法为理论方案， 利用硬件描述语言编写译码功能模块，并基于f p g a 实现了固定译码长度的 l d p c 码译码器，利用m a t l a b 和m o d e l s i m 分别对译码器进行了功能验证 和时序验证，最后模拟通信系统完成了译码器的硬件测试。 关键词：l d p c 码；f p g a ；归一化最小和算法；译码器 哈尔滨t 程人学硕士学位论文 a b s t r a c t l d p cc o d eh a sr e c e i v e dg r e a ta t t e n t i o na n db e c o m ear e s e a r c hh o ts p o td u e t oi t sn e a rs h a n n o nl i m i t e dp e r f o r m a n c e w i t ht h ec o n t i n u o u sr e s e a r c ha n dt h e d e v e l o p m e n to ft e c h n i q u e ，l d p cc o d eh a sb e e nc o n f i r m e da sc h a n n e lc o d i n g s c h e m eb ys e v e r a lc o m m u n i c a t i o ns y s t e m s ，a n db e e na p p l i e di nt h ed v b s 2 s y s t e m t h ep r o c e s so fl d p cd e c o d i n gi n v o l v e s v a s t m e s s a g e ，a n d h a s c o m p l i c a t e dt i m i n gs e q u e n c e s o ，h o wt oi m p l e m e n tt h ed e c o d e rw i t hh a r d w a r e e f f e c t i v e l yh a sb e c o m ea r e s e a r c hk e y s t o n e i no r d e rt o i m p l e m e n tt h el d p cd e c o d e rb a s e do nf p g a ，s o m ek e y t e c h n o l o g i e sh a v eb e e ns t u d i e di nd e t a i l ，s u c ha sd e c o d i n ga l g o r i t h m ，d a t a q u a n t i z a t i o n ，f u n c t i o nm o d u l ed e s i g na n dt i m i n gs e q u e n c e f i r s t l y , t h i st h e s i sh a s a n a l y z e dt h ep r i n c i p l e sa n dg e n e r a la l g o r i t h m so fl d p cd e c o d i n g s e c o n d l y , t h i s t h e s i sh a sc a r r i e dd e t a i l e dt h e o r ya n a l y s i so nb pa l g o r i t h m ，l o g b pa l g o r i t h m ， b p b a s e da l g o r i t h m ，a n dn o r m a l i z e db p b a s e da l g o r i t h m ，t h e nb a l a n c e dt h e c o r r e c t i n gp e r f o r m a n c ea n dd e c o d i n gc o m p l e x i t y , f o rp i c k i n go u tt h em o s t s u i t a b l ea l g o r i t h mf o ri m p l e m e n t a t i o n t h i r d l ya n a l y z e dt h e m a j o rf a c t o r s a f f e c t i n g t h el d p cd e c o d i n gp e r f o r m a n c e ，a n dd e t e r m i n e dt h e q u a n t i z a t i o n s c h e m et h a tm e tp e r f o r m a n c ed e m a n d e dt h r o u g hs i m u l a t i o n m o d u l eo fd e c o d i n g f u n c t i o nh a sb e e nd e s i g n e db yv e r i l o gh d ll a n g u a g e ，a c c o r d i n gt on o r m a l i z e d b p - b a s e da l g o r i t h m a n dt h ed e c o d e ro ff i x e dc o d el e n g t hh a sb e e ni m p l e m e n t e d o nf p g a s o m ev e r i f i c a t i o nh a sb e e ne x e c u t e di nm a t l a ba n dm o d e l s i m ，a n d t h eh a r d w a r et e s t i n gh a sb e e nc o m p l e t e di ns i m u l a n tc o m m u n i c a t i o ns y s t e m k e yw o r d s ：l d p c c o d e ；f p g a ；n o r m a l i z e db p b a s e da l g o r i t h m ；d e c o d e r 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和 文献的引用已在文中指出，并与参考文献相对应。除文 中已注明引用的内容外，本论文不包含任何其他个人或 集体已经公开发表的作品成果。对本文的研究做出重要 贡献的个人和集体，均己在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 作者( 签铋稍宇 日期：加驴孑年；月乡e t 哈尔滨t 程大学硕+ 学位论文 第1 章绪论 随着数字通信技术的发展，现代社会对各种通信业务的需求增长迅猛， 数字通信系统既要有高标准的传输质量，又要具备较大的传输容量，这就 对通信的可靠性和有效性提出了更高的要求。为保证通信传输的低差错率， 信道编码已经成为通信系统中必不可少的关键技术。频带是通信系统宝贵 而紧张的资源，在带宽受限的环境下，通信的有效性显得更加重要，优良 的信道编码不仅纠错性能突出，而且传输码率要高，以加强通信系统的可 靠性和有效性。 1 1 课题的背景及研究意义 通信的基本目的在于将信息由信源高效、可靠、安全地传送到信宿。 早期的人们普遍认为：通信系统的可靠性与有效性之间是一对很难调和的 矛盾。1 9 4 8 年，s h a n n o n 发表了信息和编码理论的奠基性论文通信的数 学理论，首次阐明了在有扰信道上实现可靠通信的方法，指出实现有效而 可靠地信息传输的途径就是通过编码。根据s h a n n o n 的信息理论，数字通 信系统的基本组成如图1 1 所示。 图1 1 数字通信系统模型 图1 1 中信道编译码部分是以特定的控制手段，引入适量冗余比特，以 哈尔滨下程大学硕十学位论文 i-_i 克服信息在传输过程中受到的噪声和干扰影响。根据s h a n n o n 提出的信道 编码定理，对任意一个平稳离散无记忆有噪声信源，都有一个固定的量， 称之为信道容量，记做c 。从s h a n n o n 信道编码定理可知，在信息传输速 率r 不大于信道容量c 的情况下，从码组长度趋于无穷大的码集合中随机 的选取编码码字，并且在接收端译码采用最大似然译码算法时，译码错误 率可趋于零。这种无差错传输必须满足以下3 个基本条件： 1 采用随机性编译码。 2 编码长度l 一，即分组的码组长度无限。 3 译码过程采用最佳的最大似然译码( m l ) 方案。 虽然该定理仅仅是一个存在性定理，没有给出具体实现差错控制编码 的方法，但却从理论上给出了纠错码的理论极限，同时也指明了纠错码研 究的方向和目标。 几十年来，无数的学者尝试着构造能达到s h a n n o n 限而译码复杂度又 低的编码方案。1 9 6 2 年g a l l a g e r 首次提出了低密度奇偶校验( l o w d e n s i t y p a r i t y c h e c k ) 列2 1 ，简称l d p c 码，其纠错性能优异，但受到当时研究手段 的限制，并没有引起重视。9 3 年c b a r r o u 等人提出t u r b o 码删，震惊了整 个编码界。学者研究发现t u r b o 码实质上是一类特殊的l d p c 码，其接近 香农极限的性能h 1 引发了学术界的研究热潮。随着对l d p c 码理论研究的不 断深入，许多通信标准将l d p c 码做为信道编码方案。 d v b s 2 标准首先巧删7 1 采纳l d p c 码作内码的级联码，可在接近香农限 o 7 1 0 d b 处无误码工作。编码后普通帧码长6 4 8 0 0 b i t s ，短帧码长1 6 2 0 0 b i t s ， 有1 1 种码率可选：1 4 ，1 3 ，2 5 ，1 2 ，3 5 ，2 3 ，3 4 ，4 5 ，5 6 ，8 9 ，9 1 0 。 利用l d p c 码码率高、纠错性能好的特性，传输容量增益比d v b s 标准提 高3 0 。之后，国际电信联盟( i t u ) 提出了一种用于a d s l 的高速率二进制 l d p c 码捧1 ，仿真表明这种l d p c 码具有非常接近香农( s h a n n o n ) 限的性能， 尤其对高斯信道下的突发错误有很强的纠错能力。随着无线通信系统中数 据量的增加，国际电气电子工程师协会将l d p c 码写入i e e e 8 0 2 1 6 e ( w i m a x ) 2 哈尔滨：r 程大学硕十学位论文 协议一1 ，同时，在编码部分，增加了对l d p c 码的支持。为了降低l d p c 码 的编码复杂度，i e e e 8 0 2 1 6 e 中给出了一种具有准循环特性的l d p c 码的校 验矩阵，这样既避免了矩阵求逆的运算，同时也节约了校验矩阵的存储空 间，使得编码过程变得十分简单，从而使长码的产生变为现实。 国内的一些通信协议也将l d p c 码做为信道编码方案。我国数字电视 传输标准川建设备选方案中，广电总局的t i m i 方案性能较好。该方案的最 大技术亮点就是采用了l d p c 码的信道编码技术。此外，我国广电总局提 出的中国手机电视标准c m m b ( c h i n am o b i l em u l t i m e d i ab r o a d c a s t i n g ) 的核 心传输技术s t i m i 采用了l d p c 编码、基于时隙的帧结构和o f d m 调制技 术、逻辑信道技术、用于快速同步的信标技术等一系列先进的技术，此标 准已经成为推荐性行业标准。 国内外研究组织对l d p c 码的探索广泛展开，l d p c 码的巨大的应用潜 力日益显现，本文就是基于这种背景，在低信噪比信道情况下，结合连续 相位调制( 如m s k ) ，研究l d p c 码译码算法，并基于f p g a 硬件平台设计 l d p c 码译码器。高码率的l d p c 码传输可靠性好，是通信系统信道编码的 理想选择之一，研究l d p c 码译码算法对提高通信有效性具有重要意义。 利用f p g a 实现译码器，可以为l d p c 码译码器的工业级芯片设计和a s i c 设计提供备选方案，并为l d p c 码通用译码器的实现提供参考。 1 2l d p c 码译码的研究现状 g a l l a g e r 不仅提出了规贝d j l d p c 码的构造方法、编译码算法以及最小汉明 距离分析方法，而且提出了一种全新的译码思想”1 1 。这种译码思想主要有三 个显著特征： 1 是一种迭代译码算法，具有全并行结构； 2 是一种软判决( s o f t d e c i s i o n ) 译码算法； 3 适当设计译码算法的计算法则，可使译码复杂度随码长, 的增加而线性 的增加。 哈尔滨i ：程人学硕七学他论文 以上三点为l d p c 码译码算法的理论研究指出了方向。 1 2 1l d p c 码译码的理论研究 通信系统相同的情况下，l d p c 码的译码性能由校验矩阵和译码算法决 定，编码业界的许多学者一直积极研究校验矩阵的构造方法和译码算法的 改善方法，并取得了大量非常有意义的成果。 在校验矩阵的构造方面，m a c k a y 和n e a l 一“1 2 1 利用随机构造的t a n n e r 图 生成了一类规则l d p c 码，发现采用和积译码算法的规则l d p c 码在长码 时具有逼近s h a n n o n 限的性能，纠错性能甚至超过了t u r b o 码，这一结果 引起了信道编码界的极大关注。在m a c k a y 的研究成果激励下，t h o m a s j r i c h a r d s o n 和r l u r b a n k e 等人提出利用密度进化( d e n s i t ye v o l u t i o n ) 方法 研究l d p c 码，分析了消息传递译码下l d p c 码的容量3 1 ，探讨了要获得 高效编码器如何确定校验矩阵矩阵稀疏度的问题，以及如何构造码，使编 码时间与码块长度实际上符合线性关系( 线性时间编码) ，而非通常认为的 平方关系。他们设计出逼近s h a n n o n 限的非规则l d p c 码，论述了l d p c 码的有效编码方法，对l d p c 码的研究和应用作出了极大的贡献。2 0 0 1 年， c h u n g 构造的校验矩阵生成了一类非规则l d p c 码，其性能距香农限仅有 0 0 0 4 5 d b 钉，这一成果引发了学术界对l d p c 码的研究热潮。随着研究的深 入，校验矩阵的构造方法被不断创新，d a s p i e l m a n t 州开发了一种试探法， 来寻找非正则l d p c 码参数的好的分布，据此构建了在很低信噪比下误码率 低于t u r b o 码的码率为1 陀的l d p c 码。x i a o y uh u t 1 提出了一种性能优异 的随机构造方法，p e g ( p r o g r e s s i v ee d g e - g r o w t h ) t a n n e r 图构造法，这种 方法以增加g i r t h 为目的，是一种构造t a n n e r 图的简单有效方法，它以尽可 能保持大的g i r t h 为目的，逐个增加变量节点和校验节点的边。清华大学的 h u ac h e n 和z h i g a n gc a o 叫提出了一种改进的p e g 构造算法，该方法构造 的校验矩阵具有严格集中的校验节点度数，仿真表明即使在要求严格集中 的校验节点的条件下，尤其在高信噪比下，规则和非规则的l d p c 码都表 4 哈尔滨一i j 程大- 7 ：硕十学位论文 一 一一 一一i i i!_iimi i； i ； 现出良好的性能。 随机法构造的l d p c 码校验矩阵虽然令l d p c 码的纠错性能十分优秀， 但却给l d p c 码的硬件实现造成难度，为了l d p c 码能够应用于实际，就 要有意识的减少校验矩阵的随机性。2 0 0 3 年，f o s s o r i e r 提出一种伪随机的 构造方法，利用单位矩阵的循环移位矩阵构造校验矩阵卯，提高了l d p c 码实用性。2 0 0 6 年，z h i y o n gh e 构造出结构化非规则校验矩阵昭川，定义了 一类纠错能力很强的非规则l d p c 码，经过适当的设计，完全可以用于硬 件实现。目前，如何构造译码性能优异、结构规律性强的l d p c 码校验矩 阵仍然是业界研究的热点。 l d p c 码的译码算法实质是一类信息传递算法( m e s s a g ep a s s i n g ) p 。从 对译码信息的处理角度可分为以下两类： 1 基于硬判决的译码方法1 ，主要有：位翻转译码算法( b f ) 和加权位 翻转译码算法( w b f ) 。 2 基于软判决的译码算法，具体有：概率b p 算法、l o g b p 算法、 最小和( b p b a s e d ) 算法瞄5 1 、迭代a p p 算法、a p p b a s e d 算法、n o r m a l i z e d b p b a s e d 算法、o f f s e tb p b a s e d 算法印1 、联合校验变量处理( h y b r i dc v p r o c e s s i n g ) 修j 下的l d p c 译码算法等。 实用价值强的译码算法不仅要有良好的译码性能，而且要有尽量小的 计算复杂度。目前的研究表明，硬判决译码算法虽然译码复杂度低，译码 延迟相对较小，但其译码过程中引入了较多的信息精度损失，译码性能往 往达不到通信系统的要求。软判决译码算法译码性能优良，然而，其译码 复杂度较高，需要处理的译码信息较多，为译码器的硬件实现带来许多困 难。 针对以上问题，l d p c 码的研究机构进行了积极探索，美国夏威夷大学 的m a r c e c f o s s o r i e r 研究小组在有关信息传播算法方面的研究中提出两种 b p 算法的简化算法，可快速迭代译码，只有实数的加法运算，不需要信道 的先验信息，可获得良好的性能和复杂度之间的平衡伫丌。t h o m a s 哈尔滨r 程大学硕士学位论文 j r i c h a r d s o n 和r l u r b a n k e 采用密度进化理论( d e n s i t ye v o l u t i o n ) ，有效地 分析了消息传递译码下l d p c 码的容量、分析出一大类l d p c 译码算法的 性能限4 1 。由于l d p c 码的码字间距离会随码长增大而增加，使其译码错 误均可被检测，这个特点具有很高的实用价值，如在a r q 体制下可实现无 误传输。 此外，l d p c 码采用迭代译码机制，如何减少译码延迟也是在实际应用 中必须解决的问题。e s h a r o n 和p r a d o s a v l j e v i c 提出改进l d p c 码的译码 信息传递机制m 1 ，有效减小l d p c 码译码延迟，为l d p c 译码算法研究指 出了新的方向。 1 2 2l d p c 码的硬件实现研究 工业界已经有l d p c 译码芯片问世。其中，处于领先地位的f l a r i o n 公司推 出的基于a s i c 的v e c t o r - l d p c 解决方案使用了约2 6 0 万门，内存为1 9 0 k b ，最 高可以支持5 0 0 0 0 b i t 的码长，0 9 的码率，最大迭代次数为1 0 ，译码器可以达 至t 1 0 g b p s 的吞吐量，其性能已经非常接近香农限，可以满足目前某些通信业 务的需求。a h a 公司、d i g i t a lf o u n t a i n 公司也都推出了自己的译码解决方案。 学术研究机构在l d p c 码译码器实现方面也做了大量工作，主要成果包括 b l a n k s b y 和h o w l a n d 使用a s i c 技术实现的码长为1 0 2 4 b i t ，码率为l 2 的l d p c 码译码器，以及z h a n gt o n g 基- 于f p g a 设计的码长为9 2 1 6 b i t ，码率为1 2 1 拘 规则( 3 ，6 ) l d p c 码译码器p 0 1 。 l d p c 码硬件译码器的研究已经取得了一定进展，但目前的研究成果远 远不能满足实际应用的需要。与连续相位调制技术相结合的l d p c 码译码 器目前正处于研究阶段，没有开发出可应用的产品，本文设计的译码器主 要用于调制方式属于连续相位调制的通信系统。 1 3 本文的主要研究工作及内容安排 本文结合连续相位调制技术，以l d p c 码硬件译码器为研究目标，从 6 哈尔滨一i ：程火学硕士! 学位论文 _im 提高译码性能和降低译码算法实现复杂度两个方面入手，以现有的l d p c 码译码算法为基础，研究出宜于硬件实现的译码算法。对通信系统进行了 深入的仿真分析论证，确定影响译码性能的各个参数值以及系统的量化方 案。完成译码器各个功能模块设计，并基于f p g a 实现l d p c 码译码器。 最后模拟通信系统，对l d p c 码译码器进行测试。本文具体内容安排如下： 第l 章，主要介绍课题的研究背景、意义及目前研究现状。 第2 章，主要对l d p c 码的译码算法进行研究，简要介绍了l d p c 码的 基本概念和l d p c 码的硬判决译码算法，深入研究l d p c 码的软判决译码 算法，对各软判决算法进行仿真分析，比较不同算法的译码复杂度，通过 适当改进，为译码器的硬件实现确定算法方案和参数值。 第3 章，结合通信系统和m s k 调制对译码算法进行仿真，比较不同量 化方式对纠错性能的影响，分析不同量化范围和量化阶数条件下，l d p c 码 译码算法的性能，确定通信系统的量化方案。 第4 章，根据译码算法给出硬件译码器设计方案。详细介绍译码器的设 计思想、数据处理功能模块结构和时序逻辑控制机制，基于f p g a 硬件平 台实现l d p c 码译码器。模拟测试系统，信源、l d p c 编码、m s k 调制、 信道和m s k 解调采用软件实现，l d p c 码译码用硬件实现，完成译码器的 硬件测试。 7 哈尔滨r 程大学硕十学位论文 第2 章l d p c 码的译码研究 l d p c 码是一类可以由稀疏校验矩阵定义的线性分组码，具有非常优异 的纠错性能。本章首先简要介绍l d p c 码的基本原理和基本概念，之后研 究l d p c 码的译码算法，深入分析影响l d p c 码译码性能的因素。 2 1l d p c 码的定义 l d p c ( l o w d e n s i t yp a r i t y c h e c kc o d e s ) 码，即低密度奇偶校验码，是 一类特殊的线性分组码，它通过一个生成矩阵g 将信息序列映射成发送序 列，也就是码字序列。对于生成矩阵g ，完全等效的存在一个奇偶校验矩 阵h ，所有的码字c 都应该满足校验方程，即h * e t = 0 。其校验矩阵h 中 绝大多数元素为0 ，只有少部分为1 ，即h 是稀疏的。相对于行与列的长度 ( m ，n ) ，校验矩阵h 每行、列中非零元素的数目( 称作行重、列重) 非常少， 即这种码的校验矩阵中包含多数的0 而仅有少数的1 ，这也是l d p c 码之所 以称为低密度码的原因。 二元域l d p c 码可表示为( 甩，k ，w r ) 的形式，其码长为，z ，校验矩阵h 中 列重为比，行重为。也就是说，每个编码比特会参与比个校验方程，而 每个校验方程含有个编码的比特。如果校验矩阵的各行中非零元素的个 数是相同的，各列中非零元素的个数也是相同的，这种l d p c 码称为规则 码。如果校验矩阵的各行、各列中非零元素的个数是不相同的，此时l d p c 码称为非规则码。 2 1 1l d p c 码的优势 l d p c 码的最大特点是性能接近著名的s h a n n o n 信道编码定理中所指出 信道容量( 即香农限) ，其纠错性能甚至超过了3 g 中应用的t u r b o 码。与t u r b o 码相比，l d p c 具有以下优点： 哈尔滨j i ：程人学硕十学位论文 1 可以达到很高的码率。l d p c 码可以达到0 7 、0 8 甚至0 9 的码率， 而目前使用的t u r b o 码的码率大都是1 3 。 2 译码速率快。l d p c 码具备全并行译码结构，可以达到很高的译码速 度。 3 不可检测错误少。由于l d p c 码码字之间的码距较大，使得它译码过 程中出现不可检测错误的概率很小。 4 发生“地板效应 ( e r r o r - f l o o r ) 的概率低。随着信噪比的增加，t u r b o 码误码率的下降趋势将趋于平缓，即出现所谓的“地板效应”。但是l d p c 码发生这种现象的概率低得多，这使得l d p c 码在深空通信或光纤通信中 更具优势。 5 l d p c 码可以采用基于硬判决的迭代算法，虽然性能比软判决差，但 实现复杂度很低。t u r b o 码译码在迭代时必须传递软信息，因此无法使用硬 判决算法。 6 由于校验式的存在，使得l d p c 码的译码过程中能够确定码字是否正 确，这样不仅可以省掉c r c 编码，而且可以采用动态终止算法来减少迭代次 数。 2 1 2l d p c 码的t a n n e r 图描述 t a n n e r 最早用二分图研究l d p c 码，因此，又将表示l d p c 码的二分 图称为t a n n e r 刚2 1 1 。t a n n e r 图是一个节点由无向分支连接的图，且其节点 可以分为两类，分支只能连接处于不同类中的节点。在t a n n e r 图中，两类 节点分别为疗个变量节点( 或信息节点) 和m = 刀一k 个校验节点。当且仅 当，= l 时，在变量节点f 和校验节点，间存在一个分支连接。这样对 ( ”，屹，w ，) 规则l d p c 码，图中有w ，( 力- k ) = w c 9 1 个分支，每个变量节点有雌 条分支连接，每个校验节点有w ，条分支连接。 例如，一个( 8 ，4 ) 线性分组码，w c = 2 ，w ，= w c ( n m ) = 4 ，1 - i 矩阵形 式为： 9 哈尔滨- r 干y 人学硕十学位论文 h = 1l o 0 lo 01 ll 1l 11 01 o 0 11 o 0 lo 0 o 0 0 l0 0l ( 2 1 ) 其t a n n e r 图如图2 1 所示，可以发现变量节点x 0x ，x ：和x ，与校验节 点厶相连，因为在h 矩阵的第0 行中h o o = h o ，= h 0 2 = h o ，= 1 ( 其它都是0 ) 。 校验节点z ，厶，六和六，分别对应了h 矩阵的第l ，2 ，3 和4 行。注意， 因为c h t = 0 ，所以对每个校验节点，其相连的变量节点表示的码元之和为 0 ，每个校验节点实际上对应一个校验方程。同样可以通过列来构造t a n n e r 图，例如，变量节点x 。与校验节点磊和相连，因为在h 矩阵的第0 列中 h o o = 啊。= 1 。对于任意一个节点，与它有分支连接的节点成为它的相邻节 点。任意两个相邻节点之间的连接边，称为两个节点的邻接边。连接一个 节点分支数目称为该节点的阶( 或度) 。 变量节点 图2 1 ( 1 0 ，5 ) 线形分组码h 矩阵的t a n n e r 图 这个例子中的t a n n e r 图是规则的：每一个变量节点的阶为2 ，每一个 校验节点的阶为4 。可以看到这是与w 。= 2 和w ，= 4 一致的，并且通过这个 例子可以清楚地看到m w ，= n w 。 1 0 哈尔滨。l j 程大学硕十学位论文 2 1 3 校验矩阵中的环 在t a n n e r 图中，一个长为g 的环( 圈) 是一个能够回到起点的包含z 个 分支的闭合路径。在图2 1 中，粗实线表示的是一个长为4 的环。图的最小 环长称为图的围长( g i r t h ) 。显然，二分图中可能的最短的环长为4 ，对应 到h 矩阵中就是h 矩阵的一个子阵，其四个角都是1 ，如图2 2 所示。环( 特 别是短环) 会对译码性能产生负面影响p 。因为l d p c 码的译码采用迭代 译码，其算法的推导是基于假设在节点间传递的信息统计独立，当有环存 在时，某一节点发出的信息经过一个环长的传递会被传回本身，从而造成 自身信息的叠加，破坏了独立的假设，影响译码的准确性。设计校验矩阵 时，应尽量减少短环对码的性能的影响。 二分图的最短环 验节点 变量节点 信道编码的译码算法是决定其性能和应用前景的一个重要因素。线性 分组码的译码复杂度与码长成指数关系，当码长增大到一定程度后，复杂 度的增加将是不可控制的。但l d p c 码由于其校验矩阵的稀疏性，使得译 码算法的复杂度和码长成线性关系，克服了分组码在码长较长时所面临的 计算复杂度问题。 g a l l a g e r 在提出l d p c 码的同时给出了两种迭代译码算法：硬判决( b i t f l i p p i n g ) 和软判决算法。前者计算复杂度很低，只需要模二和运算，但其 哈尔滨t 程大学硕十学位论文 | 1 i 译码性能不理想，后者虽然性能更好，但复杂度较大。对于硬判决算法， 由于其译码性能不能满足课题研究的需要，本章只做原理性介绍。软判决 译码算法本质是基于t a n n e r 图的消息传递m p ( m e s s a g ep a s s i n g ) 算法。1 9 9 6 年，m a c k a y 和n e a l 提出了b p ( b e l i e fp r o p a g a t i o n ) 算法，也称为 s u m p r o d u c t 算法，其译码性能比硬判决算法好的多，但译码复杂度较高。 l o g b p 算法p 纠是b p 算法的对数域形式，在一定程度上降低了译码复杂度。 f o s s o r i e r 对b p 算法作了进一步研究，提出了b p b a s e d 算法，降低了b p 算法的复杂度，但造成了译码性能的损失。为了改善b p b a s e d 算法因为校 验节点上的简化处理而造成的性能损失，j c h e n 进一步提出改进算法：采 用归一化的近似最佳b p b a s e d 算法( 亦称为归一化最小和算法) 。本章将 主要研究上面提到的几种软判决译码算法。 2 2 1l d p c 码硬判决译码算法 考虑二元输入无记忆信道，令y ， o ，1 为对应于第f 个变量节点的接收 值。硬判决译码的主要思想是翻转最少的y ， o ，l 使所有n k 个校验方程满 足。当h 是低密度时，这一过程最为简单。因为每个校验方程只涉及很少的 比特，而每个比特也只涉及很少的校验方程。l d p c 码最简单的译码方法是 比特翻转法( b i tf l i p p i n g ) ，它是一种硬判决算法。其译码的主要原理是：如 果发生错误，校验方程不满足，根据接收信息的有关规则，改变一些比特的 值( o 1 ) ，然后判断是否满足校验方程，如果满足校验方程，则译码输出，否 则继续迭代，或者已达到最大迭代次数则被迫停止译码，给出译码输出口1 。 b f 译码操作简单，硬件很容易实现，但性能要差于软判决的概率译码。b f 译码算法的流程如2 3 图所示。 哈尔滨1 i 程大学硕十学位论文 图2 3b f 算法流程图 这种算法只有模二和运算和比较大小的运算，因此译码速度较快。并且 具有迭代结构，硬件实现比较简单。但是译码性能较差，因为每次迭代译码 选择巳最大的变量节点翻转，若同时有好几个这种节点，就可能使迭代进入 一个循环，不能正确译码。 哈尔滨j i 程大学硕士学位论文 2 2 2l d p c 码软判决译码算法 2 2 2 1 置信传播算法( b p ) 建立在t a n n e r 图上的l d p c 码，其b p 译码算法的每次迭代要经历两 步p 3 1 ：校验节点的更新和变量节点的更新，整个更新过程可参考图2 4 。 初始消息 图2 4 规则l d p c 码的译码过程示意图 1 4 更 新 哈尔溟j ：程大学硕十学位论文 在每次迭代中，所有校验节点从其相邻的变量节点处接收消息，处理后， 再传回到相邻的变量节点，然后所有的变量节点从其相邻的校验节点处接收 消息，处理后，再传回到其相邻的校验节点。最后变量节点收集所有可以利 用的消息进行判决。在l d p c 码的译码过程中，每一个校验( 或变量) 节点 可以看作是一个处理器，所有校验( 或变量) 节点的处理可以同时进行，因 此利用并行结构可以构造高速l d p c 码的译码器。根据消息的表示形式，b p 译码可以分为概率b p 算法和l o g b p 算法。概率b p 算法的消息是用概率形式 表示，是b p 算法的通用形式，可以适用于非二进制的l d p c 码的译码。而对 二进制l d p c 码，消息可以表示为对数似然比的形式，相应的译码算法称为 l o g - b p 译码。 1 概率b p 译码算法 假设信道为均值为0 ，方差为盯2 的高斯白噪声信道，以( 五，x 2 ，) 表示 b p s k 调制后的码子序列，以( m ，y 2 ，儿) 表示接收到的信号，则有 ”= 葺+ ，其中f = l ，2 ，刀。在介绍具体的b p 译码算法之前，首先要介绍 所用到的有关符号的含义： c k j g f ( 2 ) ：莉个含有c ，的校验方程的第k 位，c 为信息序列； x “= ( 一1 ) 啊：经b p s k 调制后每个码字映射为传输序列x ； y 材= + n k ，其中是加性噪声，y 为接收序列： 只= p r ( c j = 1im ) ：接收到y ，后判断发送比特( 或变量节点) 为c ，= 1 的 后验概率； 吃= p r ( c 酊= lly 茸) ：接收到y 暂后判断包含c ；的第j f 个校验方程中的第k 个比特为c 。，= 1 的后验概率； r j ，( b ) ( b = 0 ，1 ) ：表示校验节点_ 传给变量节点f 的外部概率信息，即在 给定信息位及其它信息位具有独立概率分布条件下，校验方程，满足的概率； 鲂( 6 ) ：表示变量节点f 传给校验节点- ，的外部概率信息，即在得到所有 校验节点和信道的外部信息后，判断变量节点c 。= b 的概率； c ( i ) ：表示与变量节点f 相联接的校验节点的集合，c 。= 乞，：h ；1 j ； i 情刀；浜i ，栏人坝十字何论又 i ii 尺( f ) ：表示与校验节点相联接的变量节点的集合，r j = f ：h j i = 1 j ； c ( f ) j ：表示除_ ，外与变量节点i 相连接的校验节点的集合； r ( 歹) f ：表示除i 外与校验节点_ 相连接的变量节点的集合； s ：表示事件码字c 中所有比特满足包含码元c ，的。一致校验方程 引理1 ( g a l l a g e r ) - 设有肌个独立二元比特的序列a = ( 口l ，口2 ，a 。) ，其 中，p r ( a 。= 1 ) = 最，则口含有偶数个1 的概率为m 1 p r ( 吼= o ) = i 1 + 寺兀( 1 - 2 p 。) ( 2 - 2 ) k = l 厶 厶七= l 对应的口含有奇数个l 的概率为百1 一吾n ( 1 2 最) 。 【证明】 ( 采用归纳法) 当m = 2 时， p r ( p w n ) = p r ( 口。口：= o ) = 鼻最+ ( 1 一只) ( 1 一只) = 至i + 丢( 1 2 e ) ( 1 2 b ) 假设式( 2 2 ) 对m = l - 1 成立，对z = a l + 口2 + + a 工，则有 p r ( 乙= 0 ) 2 p “z l l0 a l = o ) = 三+ 圭 1 2 p r ( z 上一。= 1 ) 】( 1 2 p r ) = 拄 1 _ l + 辑”2 删啦) 5 e 虫”2 只， 定理1 ( g a l l a g e r ) ：设信道为无记忆信道，并给定信道观测矢量y 和事件 s ，后c ，的似然比n 2 1 糕pr(c 1 ys = 半盟，= l ，) 只怂 1 6 静1+1-i(1-2prj)ie ( 弱， 呀f， 、 1 一兀( 1 2 只川 p 叫 l e 盼、ji 哈尔滨1 ：稃人学硕十学位论文 证明】由贝叶斯准则，有 p r ( c ，= 0ij ，s 。) p r ( c ，= 1j ，s ，)p r ( s ，jc ，= 1 ，y ) ( 2 4 ) 给定c ，= 1 ，如果包括c ，的校验方程的其他，一1 b i t 中包含奇数个1 ，则 对c ，的校验满足。由引理1 可知，在第个校验方程中其余，一1 b i t 中有奇 数个1 的概率为 丢一丢1 - i o 一2 p i t j ) ( 2 - 5 ) i e v j i 在独立假设下，所有( o ，个校验全部满足的概率是每个校验满足的概率 之积，则有 吣l c f 划2 啡一1 骡f ( 也) j ( 2 - 6 ) “：j l ，i ，、i j 类似地，有 p r ( 北训= 兀j e c i 陪圭，职，( ，戗) j ( 2 _ 7 ) i 厶 ，。e 哆， 将式( 2 - 6 ) 和式( 2 7 ) 代入式( 2 4 ) ，就得到了定理l ，证毕。 从前面的描述中，可得到b p 算法中校验节点的更新规则1 因此，根据引理1 又可将定理1 改写为 !糍=1-：e,，v。l。【_frj,(o)ii pr(c 1s 11 1 r j , ( 1 ， ( 2 - 9 ) 一= = - li 一， ，= iy ，)只脚i) l 、7 1 7 名 q 、， 、 p 耳， 卯 弛 一 一 0 1、 册缈 12一乙 ，卜2。2 12一2 = = d 0 0 哈尔滨t 程大学硕十学位论文 即变量节点的更新规则p 4 1 k ( o ) = 0 - e ) 兀“o ) 一j 裂 ( 2 1 0 ) i q u ( 1 ) = 丌( 1 ) 、7 l r e c f i j 由此，根据以上函数，可将b p 译码步骤总结如下( 为表示方便，消息 符号中的上标表示迭代次数) ( 1 ) 初始化嗍3 5 3 q g o f ( 0 ) = l 一只= p r ( x i = + l i y j ) = g o 矿( 1 ) = = p r ( x j = - 1 l y ，) = 1 + e x p ( - 2 y , o 2 ) ( 2 11 ) l 、7 1 + e x p ( 2 y ，o r 2 ) ( 2 ) 所有分支并行进行以f 操作 弘( 0 ) = 越。珊1 嘲h 吖( 1 ) ) i ，- ( 1 ) = 1 一r t f ( o ) m 朋) = ( 1 - p ) 兀，7 ( o ) k ( 1 ) ：咖揣 l j e c i j 归一化，有 卜= 蒜 【q t o ( 1 ) = l 9 7 ( o ) 对所有i 计算 q f ，( o ) = k ，o - e , ) 兀，7 ( o ) 阿( 1 ) = k ，p 兀，7 删 l j e ( 3 常数k ；的选择应使0 7 。( 0 ) + q 。一( 1 ) = 1 。 ( 2 - 1 2 ) ( 2 - 1 3 ) ( 2 - 1 4 ) ( 2 1 5 ) 哈尔滨t 程大学硕十学位论文 对任意i ， 扣黔“甏。“ ( 2 - 1 6 ) ( 3 ) 如果h t = 0 或是达到最大的迭代次数，停止；否则转步骤。 研究表明，如果对应于h 矩阵的图中没有环，当迭代次数趋于无穷时， q ( 0 ) 和q ( 1 ) 将收敛于c ，的后验概率。由于步骤，本算法将以近于1 的概 率检测出无法纠正的错误。整个b p 算法流程可以由图2 5 表示： 图2 5b p 译码算法流程图 1 9 i 哈尔溟i