（通信与信息系统专业论文）低密度校验码中几个关键问题的研究.pdf

摘要 低密度校验码是种逼近香农限的好码，由于其校验矩阵的稀疏特性，采用迭 代译码算法，它的译码仅具有线性时问复杂度，所以目前l d p c 码己成为信道编 码理论界的研究热点之一。本文在现有理论的基础上，对l d p c 码进行了深入的 研究，获得了一些成果。主要内容包括： 1 阐述了l d p c 码的定义及因子图模型，以b s c 信道为例，具体介绍了消 息传递译码算法，并给出了其译码收敛条件的分析。讨论了影响l d p c 码性能的 重要因素一围长，进而介绍了提高l d p c 码性能的几个方向。 2 详细介绍了l d p c 码的置信传播译码算法，对l d p c 码迭代译码原理进行 了讨论，并具体给出了最小和算法与不同量度上的和积算法。阐述了密度进化理 论，并分析了译码过程中存在的闽值现象。然后介绍了密度进化理论在l d p c 码 优化方面的应用。 3 概述了l d p c 码的常见构造方法。包括最早由g a l l a g e r 提出的构造方法、 m a c k a y 对其改进的构造方法、基于有限几何、图论及群论上的构造方法等。最后， 在分析、研究现有构造方法的基础上，基于代数中的完全剩余系，作者提出了一 种代数构造方法，使得l d p c 码对应因子图上的围长为8 ，并采用计算机对其性能 进行了仿真，结果表明该码能够取得比较理想的译码性能。 关键词：低密度校验码因子图消息传递围长置信传播 a b s t r a c t l o w d e n s i t yp a r i t yc h e c k ( l d p c ) c o d e s a r eg o o de r r o r - c o r r e c t i n gc o d e s ，w h i c h c a na p p r o a c hs h a n n o n sc a p a c i t yl i m i t d u et ot h es p a r s i t yo fi t sc h e c km a t r i x ，l d p c c o d e sc a nb ed e c o d e do n l yw i t hl i n e a rt i m ec o m p l e x i t yu s i n g i t e r a t i v e d e c o d i n g a l g o r i t h m t h e r e f o r e ，l d p cc o d e sh a v eb e c o m e o n eo ft h em o s ta t t r a c t i v ef i e l d si nt h e c h a n n e lc o d i n gc o m m u n i t y b a s e do nt h ee x i s t i n gk n o w l e d g eo fl d p cc o d e s ，t h i s d i s s e r t a t i o nd o e sf u r t h e rr e s e a r c ho nl d p cc o d e s s e v e r a lr e s u l t sa r eo b t a i n e d ，w h i c h a r eo u t l i n e da sf o l l o w s ： 1 t h ed e f i n i t i o na n dt h ef a c t o rg r a p hm o d e lf o rl d p cc o d e sa r es m n m a r i z e d m e s s a g ep a s s i n gd e c o d i n ga l g o r i t h mi sp r e s e n t e di nd e t a i l s o nb s cc h a n n e l ，a n dt h e c o n v e r g e n c ec o n d i t i o n so f t h ea l g o r i t h ma r ea n a l y z e d a ni m p o r t a n tf a c t o rn a m e dg i r t h i sd i s c u s s e d ，w h i c hi m p a c t st h ed e c o d i n gp e r f o r m a n c eo fl d p cc o d e su n d e rm e s s a g e p a s s i n ga l g o r i t h m t h e ns e v e r a ld i r e c t i o n sa r eg i v e nt oi m p r o v et h ep e r f o r m a n c eo f l d p cc o d e s 2 b e l i e f p r o p a g a t i o nd e c o d i n ga l g o r i t h mi ss y s t e m a t i c a l l ys u m m a r i z e d ，a n dt h e p r i n c i p l eo fd e c o d i n gf o rl d p c c o d e si sd i s c u s s e d s u m p r o d u c ta l g o r i t h mo ns e v e r a l d i f f e r e n tm e t r i c sa n dm i n s u ma l g o r i t h ma r ed e t a i l e d d e n s i t ye v o l u t i o nt h e o r yi s s p e c i f i e da n di sa p p l i e dt ot h ea n a l y s i s o nt h et h r e s h o l do fd e c o d i n g ，t h r o u g hw h i c h g u i d a n c e c a l lb e p r o v i d e d t oo p t i m i z e i r r e g u l a rl d p c c o d e s 3d e t a i l e di n t r o d u c t i o no ff a m i l i a rc o n s t r u c t i o nm e t h o d sf o rl d p cc o d e si s p r e s e n t e d i t i n c l u d e st h em e t h o d so fg a l l a g e ra n d m a c k a y a n d s o m eo t h e r c o n s t r u c t i o nm e t h o d sb a s e do nf i n i t eg e o m e t r y , g r a p ht h e o r ya n dg r o u pt h e o r ya r ea l s o d e p i c t e d a na l g e b r a i cc o n s t r u c t i o nm e t h o df o rl d p c c o d e sw i t h8 - - g i r t hi s p r o p o s e d b a s e do n c o m p l e t er e s i d u es y s t e m s i m u l a t i o nr e s u l t ss h o w t h a tt h e s ec o d e sc a na c h i e v e b e a e r p e r f o r m a n c e t h a n r a n d o m l y c o n s t r u c t e d r e g u l a r l d p cc o d e so v e ra w g n c h a n n e l k e y w o r d ：l o w - - d e n s i t yp a r i t y - c h e c kc o d e s f a c t o rg r a p h m e s s a g ep a s s i n g g i r t h b e l i e fp r o p a g a t i o n y 5 8 3 8 9 2 创新性声明 本人声明所呈交的沦文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技火学或 其他教育机构的学位或证书而使用过的材料。与我一n - i ：作的同志对本研究所做 的任何贡献均已在论文中作了明确地说明并表示了谢意。 本人签名：越日期本人签名：玉_ 童致日期 关于论文使用授权的说明 z 一年t 。 本人完全了解两安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍为两安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其他复制手段保存论文。( 保密的论文 在解鬻后遵守此规定) 本人签名：主邀日期至! ! 垒! ： 导师签名： 兰：童1 日期21 么! z 第一章绪论 1 第一章绪论 本章首先简要介绍了数字通信系统及信道编码定理，回顾了信道编码理论与技 术的发展历程，然后介绍了信道模型与信道容量，简述了低密度校验码的提出、 发展和研究现状，最后介绍作者在攻读硕士学位期间的研究工作，给出了全文的 内容安排。 1 1 1 数字通信模型与香农定理 l - 1 数字通信与信道编码 现代社会的发展离不开信息，因此，信息的传输即通信在现代社会中起着越 来越重要的作用。通信系统的基本目的在于将信息由信源高效且可靠( 有时还需安 全) 地传送到信宿。其应用领域包括深空通信、光纤通信、移动和固定无线通信、 因特网f i n t e m e t ) 数据传输和数据存储等。但是，我们知道，信息传输的通道一信道 中不可避免地存在各种各样的噪声与干扰，使得信宿接收到的信息总会出现不同 程度的差错，从而可能降低通信可靠性。传统的观念认为：功率受限的情况下， 在有扰信道上实现无差错信息传输的唯一办法是使传输的速率为零。1 9 4 8 年，贝 尔实验室年轻科学家c l a u d ee s h a r m o n ( 香农) 发表了一篇题为通信的数学理论 的论文改变了人们传统的看法，为现代通信和信息论的发展奠定了理论基础【1 1 。香 农首次阐明了在有扰信道中实现可靠通信的方法，指出实现有效而可靠地传输信 息的途径是编码。根据s h a n n o n 的信息理论，数字通信系统的基本组成如图1 1 所 示【2 1 。 区卜匡习巫丑蚯壬 区) _ 压三 亟 妪蛰祧惴道 |i 丽 编码信道 图1 1 数字通信系统模型 香农将通信系统分成信源、编码器、信道、译码器和信宿五部分”，如图i 1 阿安电子科技人学硕士学位论文一低密度校验码中几个关键问题的研究 所示，其中编译码器是整个通信系统的核心部分。编译码器又分别被分成了信源 编码器、信道编码器以及信源译码器和信道译码器四个部分。 s h a n n o n 信道编码定理认为：对任意一个平稳离散无记忆有噪信道，都有一 个与之对应的固有量，称之为信道容量。只要信息的传输速率低于信道容量，总 可以找到一种编码方法，使得差错概率可以任意的小；反之，如果信息的传输速 率超过信道容量，则不存在这样的编码方法。这就是著名的信道编码定理。信道 编码定理表明，信道容量j 下好等于信息传输速率的上确界，任意给定的信源都有 一个称为熵( e n t r o p y l 的量，它表征了信源的平均不确定性p j 。 定理1 1 ( 信道编码定理) ：任意离散输入无记忆平稳信道存在信道容量c ，对 于预期的任一数据速率r 0 ，有可能设计一对编译码器， 以保证该信道中速率为月的数据传输具有小于p 的译码错误概率。 对于一个确定的信道，即带宽一定时，香农证明了信道容量c 取决于传输信 号的信噪比值s n r ，信道容量c 是信噪比值s n r 增函数。设一个信道容量c 确 定时，当信息传输速率r 无限逼近c ，这时为了实现无差错传输所需要的最小信 噪比s n r 被称为香农( 容量) 限。 该信道编码定理指明，在有扰信道中，通过编码，只要信息传输速率小于信 道容量，就有可能实现任意可靠的信息传输。但是，此定理的证明是存在性证明， 而没有给出编码的具体方法。 1 1 2 信道编码理论的发展历程 自从香农提出信道编码定理以来，由于信道编码定理证明的非构造性，而逼近 香农容量限编码的具体构造方法则没有给出，因此，众多学者争相寻求逼近香农 容量限纠错码的具体构造方法，并且逐渐形成了信息论的一个重要分支一信道编 码理论。 信道编码定理指出：在容量为c 的信道中，对于任意信息传输码率r c ，总 存在码长为，码率为r 的信道编码方式，其最大似然译码的误码率上限为 以2h 7 1 , ( ，e ，( r ) 为信道可靠性函数 4 , 5 , 6 1 。香农在信道编码定理的证明中引用了 三个基本条件：1 、采用随机编码方式；2 、码字长度趋于无穷大；3 、采用最大 似然译码算法。并指出一个随机选择的码以很高的概率为好码。然而对于随机码 的最大似然译码，其译码复杂度g 与所传输的信息比特数呈指数关系，即为 g “e x p ( n r ) 。显然，误码率p ，随着码长趋于无穷大而趋向于0 的同时，译码 复杂度g 以指数增长，可见随机码是一种不实用的码。 m a c k a y 在他的文章【7 中指出，纠错码从性能上可分为好码和坏码，其中好码 又分为当误码率为任意小时，码率逼近容量限的非常好码和码率可达到的最大值 第一章绪论 小于容量限的一般好码；所谓坏码指的是只有将码率降为o ，才可使误码率为任意 小的编码方式；然而只有编译码时问为码长多项式的码字才是可实用的。在香农 定理提出的五十多年里，寻找实际可译的非常好码，一直是信道编码理论研究的 关键问题。 纠错码从构造方法上可分为分组码( b l o c kc o d e s ) 并i i 卷积码( c o n v o l u t i o n a lc o d e s ) 两大部分。在分组码方面，第一个分组码是1 9 5 0 年发现的能纠正单个错误的 h a m m i n g 码：在整个5 0 年代，基于代数理论又发现了多个短码长的分组码，如 1 9 5 4 年g o l a y 发现的g o l a y 码以及r e e d 和m u l l e r 发现的r m 码，p r a a g e 在1 9 5 7 年发现的循环码等。最有意义的是b o s e 和r a y - c h a u d h u r i 在1 9 6 0 年，h o c q u e n g h e m 在1 9 5 9 年发现的能纠多个错误的b c h 码，以及r e e d 和s o l o m o n 在1 9 6 0 年发现 的非二进制r s 码。其后发现的分组码主要有1 9 7 0 年的g o p p a 码和1 9 8 2 年的代数 几何码。然而不幸的是，在所有这些分组码中，除了g o p p a 码和代数几何码中存 在个别达到g v 限【8 】的渐进好码外，其它码字都不是渐进的好码。需要指出的是， 分组码的译码主要采用基于代数的硬判决译码。 卷积码最早由e l i a s t 8 ，1 提出，它具有动态格图结构，可用有限状态机来描述其 状态。由于缺乏有效的理论研究工具，对卷积码的有效研究成果不是很多，对于 性能好的卷积码，主要借助于计算机进行搜索来获得。与分组码不同，卷积码的 译码采用概率译码，由于译码算法的简单、实用和易于实现，卷积码被广泛应用 于实际工作中。 1 9 6 6 年，f o m e y 提出了级联码( c o n c a t e n a t e dc o d e s ) 。一般采用精心选择的r s 码作为级联码的外码，卷积码或小域上的分组码作为级联码的内码。f o m e y 的研 究表明，级联码在译码复杂度没有显著增加的前提下，较大程度地改善了码的性 能。 根据对接收信号处理方式的不同，纠错码的译码可分为硬判决译码和软判决译 码。硬判决译码是基于传统纠锚码观点的译码方法：解调器首先对信道输出值进 行最佳硬判决，然后将判决结果送入译码器，译码器根据这一判决结果，利用码 字的代数结构来纠正其中的错误。与硬判决译码相比，软判决译码则充分利用了 信道输出波形信息：解调器将匹配滤波器生成的一个实数值送入译码器，由于这 个实数值包含了比硬判决更多的信息，译码器可以通过概率译码充分利用了这些 信息，从而使译码具有更大编码增益。与硬判决译码相比较，软判决译码在a w g n 信道上有2 3 d b 的编码增益，在衰落信道中编码增益要超过此值【8 , 9 , 1 1 】。由于解调 器向译码器输入的是实数值，这种软判决译码又被称为软输入( s o n i n p u t ) 译码。 软判决译码有两类基本的译码算法：一类是最小码字错误概率软判决译码，如 f o m e y 的广义最小距离译码( g m d ) ，c h a s e 算法和v i t e r b i 算法等i s 。另一类是最小 符号错误概率软判决译码，如b c j r 的前向后向最大后验概率( m a p ) 译码算法 西安电子科技人学硕士学位论文一低密度校验码中几个关键问题的研究 及本文将要讲述的和积译码算法等。 显然，考虑到级联码的外码也可采用软判决译码，那么需要对内码的软判决译 码进行修改。在级联码中，内码采用软输入译码，输出仍然是硬判决信息，从而 使得外码无法充分利用内码的译码信息，如果将内码的输出改成反映译码可能性 的概率值来表示，这样就可以让外码也采用软判决译码算法译码，进而改善整个 译码的性能。这种对软判决译码进行修改的算法被称为软输出( s o f t o u t p u t ) 译码。 软输出译码算法主要有逐符号m a p 算法和修正v i t e r b i 算法，如s o v a 等 1 2 , 1 3 1 。 构造接近香农容量限的纠错码一直是信道编码理论研究的理想目标，但直到 2 0 世纪9 0 年代以前，这个目标却是可望不可及的。在t u r b o 码出现之前，所有的 纠错码性能离香农限还有很大的一段距离，甚至无法超越计算截止速率r 。当码 率r r o 时，译码算法的复杂度是有限的，平均错误概率为p 。 2 的l d p c 码，进一步提高了l d p c 码的泽码 性能。 m a c k a y 和n e a l 重新发现l d p c 码优异性能的同时，s i p s e r 和s p i e l m a n 的线 性复杂度扩展图码( 2 6 和w i b e r g 的博士论文“c o d e sa n dd e c o d i n g o ng e n e r a lg r a p h s ” 使人们重新认识到g a l l a g e r 码的巨大潜力，并且人们对“基于图的码”产生了极 大的兴趣 2 ”。进一步的研究结果表明，非规则图上的和非二元的l d p c 码具有更 好的收敛性，性能更佳，r i c h a r d s o n 等的研究表明l d p c 码的性能已经相当接近 s h a n n o n 容量限f 1 9 , 2 0 , 删。 w i b e r g 等结合对t u r b o 码和网格的研究，把t a n n e r 图推广到具有隐含状态变量 的码图( w i b e r g 图) 上，他们的图模型还允许使用更一般性的量度( m e t r i c ) 作为代价 函数，从而适用于非均匀先验概率分布模型或有记忆信道模型。他们证明：最小 和算法是v a 算法的直接推广，和积算法是b c j r 算法的直接推广。从此，许多著 名的译码算法，包括v a 算法、s o v a 算法、b c j r 算法、g a l l a g e r 计算树译码算 法等，都认为是基于t a n n e r 图模型的消息传递算法的特例【2 l 】。 k s c h i s c h a n g 等分析和对比了一系列的图模型和相应算法后，建立了一个通用 的因子图( f a c t o rg r a p h ) 模型。所有的图模型本质上是要表达一个全局函数到一组局 部函数乘积的有效分解，与之相应的算法则是局部函数进行迭代计算得出全局函 两安电子科技大学硕十学位论文一低密度校验码中儿个关键问题的研究 数边界的一个过程。因子图能够表示包括贝叶斯网络、马尔可夫随机域( m r f ) 、 t a n n e r 图在内的任何图模型，基于因子图的和积算法可以描述p e a r l 置信传播、快 速傅立叶变换、b c j r 前向后向算法、v a 算法以及l d p c 码的迭代大数判决算法， 甚至可以描述基于高斯图的卡尔曼( k a l m a n ) 滤波器。码的因子图表示提供了一个关 于迭代译码的一般性框架【2 引。关于基于图模型的迭代译码算法可以参阅文献 2 9 ， 3 0 1 。另外，也可基于有限域上欧几里德几何( e u c l i d e a ng e o m e t r y ) 和射影几何 ( p r o j e c t i v eg e o m e t r y ) 来构造l d p c 码【j “。 对l d p c 码的研究发现，迭代译码存在阈值( t h r e s h o l d ) 现象，即消息的迭代传 递和进化存在一个或多个不动点。因子图上小环减小译码复杂度的同时，也恶化 了闽值。这种现象首先是由g a l l a g e r 在研究规则l d p c 码时发现的 1 7 , 1 8 】，l u b y 等 引入非规则图改进了阈值【3 2 j ，r i c h a r d s o n 等系统建立了无环路图上的密度进化理 论，分析了不动点的存在性和收敛条件，证明了巨大有环随机图的闽值逼近无环 图的集中( c o n c e n t r a t i o n ) 定理【2 0 l ，并用来指导非规则码的设计【1 9 】。c h u n g 等应用高 斯逼近原理，用单一参数分析了l d p c 码的密度进化问题【3 3 1 ，简化了非规则码度 序列分布的优化。 1 4 本文主要研究内容及安排 作者结合国家自然科学基金、与韩国三星公司合作项目，在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 码的译码收 敛问题。最后讲述并分析了影响译码性能的重要因素环，指出了提高l d p c 码性能的方法。 第三章详细系统地阐述了l d p c 码的置信传播算法译码，给出了最小和算法与 不同消息测度空间上的和积算法，最后讲述了密度进化理论，并介绍了其在l d p c 码优化方面的应用。 第四章深入地研究了l d p c 码的构造。介绍了g a l l a g e r 与m a c k a y 的构造方法， 并概述了一些常见的其它构造方法，诸如，图论构造方法，几何构造方法，群论 构造方法等。最后，基于数论中的完全剩余系，提出了一种低密度校验码的代数 构造方法，使l d p c 码具有较大围长，仿真结果显示，在低信噪比区域其性能优 于随机构造的l d p c 码。 第五章总结了全文的研究工作，并指出了进一步的研究方向。 第二章低密度校验码的描述与译码原理 第二章低密度校验码的描述与译码原理 本章系统地介绍了l d p c 码的定义及因子图表示，简述了l d p c 码的译码思 想，介绍了消息传递( m e s s a g e p a s s i n g ) 算法，并以b s c 信道为例，给出了规则 与非规则l d p c 码消息传递译码算法的收敛分析。最后介绍了提高l d p c 码性能 的几个方法。 2 1l d p c 码的定义及因子图表示 2 1 1l d p c 码的定义及因子图描述 线性分组码可以由一个校验矩阵嚣。，等效描述，所有码字x = ( 一，x 2 ，x 。) 均 满足h x 。= 0 7 。校验矩阵的每一行表示一个校验约束关系z ，即所有非零元素对 应的码元变量x ，满足一个校验方程：校验矩阵的每一列表示一个码元变量参与的 校验约束关系，当列元素不为零时，表示该码元变量参与了该行的校验约束。码元 变量与校验方程之间的关系称为结构。为了研究、分析方便，下面主要对二元l d p c 码进行讨论。 l d p c 码是线性分组码，它具有稀疏的校验矩阵，即校验矩阵中非零元素的数 量很少。当矩阵的行和列中“l ”的数日分别固定为p 和兄( 五3 1 时，称为规州 l d p c 码，否则，称为非规则l d p c 码。g a l l a g e r 最早定义的二元( n ，五，p ) l d p c 码是码字长度为、设计码率为疋= 1 一旯p 的线性分组码，其校验矩阵日。的 每- - n 都包含旯个“1 ”。每一行都包含p 个1 。由于满足这个结构条件的校验 矩阵不唯一，所以具有参数( ，a ，p ) 的l d p c 码构成了一个码集合。 设一个( j v ，且，p ) 码c 具有校验矩阵风，。，= ( ) 。，其因子图模型可以表示为 一个二部图( b i p a r t i t e ) 。码字向量x = ( 薯，x 2 ，x n ) 表示为一组变量节点 x ，j = 1 ，2 ，) ，对应于校验矩阵的各列，而校验约束则表示为一组校验节点 z ，f _ 1 ，2 ，m ) ，对应于校验矩阵的各行。当且仅当忽，= 1 时，变量节点x ，与 校验节点z ，之间有一条边相连，节点x ，与z i 之间互称相邻节点，其间的连接边称 为两个节点的相邻边。对规则l d p c 码，校验矩阵各行中“1 ”的数目均为p ， 各列中“l ”的数目均为a ，因此，因子图上每个变量节点具有a 条入射边，即度 数为五；每个校验节点具有p 条入射边，即度数为p 。总计，因子图上共有 e = n a = m p 条边。令集合m ( ，) = i ：魄= 1 ) 表示变量x ，的受约束范围：令 ( j ) = ，：曩，= 1 表示约束关系五的约束范围。 图2 1 ( a ) 是一个( 8 ，2 ，4 ) 短码的校验矩阵及校验方程组，图2 1 ( b ) 是相应的因 两安电子科技大学硕士学位论文一低密度校验码中几个关键问题的研究 子图模型。该图表示了校验约束的全局函数，( 而，x 2 v x s ) ，也称为码特征函数。 每一个校验节点五表示一个局部约束函数，( “：，( f ) ) ) 。全局函数因式分解为 ( x 1 ，x s ) = 石( _ ，x 3 ，x8 ) 厶( x 2 ，x 3 ，x 5 ，x t ) a ( x , ，x 2 ，x 4 ，x 7 ) a ( x 4 ，x 5 ，x 6 ，x8 ) ( 2 1 ) 1o 01 11 0o 1o lo o1 01 o1 1o oo l1 o1 1o l0 ol ( a ) 校验矩阵和方程 x i + x 3 + x 6 + x 9 2 0 + + x 5 + x 7 = 0 + 恐+ + x 7 = 0 + + 工6 + x 8 = 0 ( b ) 因子图 图2 1 ( 8 ，2 ，4 ) l d p c 码的校验系统及因子图表示 如下定义一个二值指示函数，把布尔逻辑命题p 映射到g f ( 2 ) 上【2 9 】： f 1p ：t u r e 【p - 1 ip：false(2-2) 式( 2 - 1 ) 中的各个函数均为指示函数，其中全局函数对应的逻辑命题为“x 是 一个码字”，每个局部函数对应的逻辑命题分别为图2 1 ( a ) 中的校验方程。因此 式( 2 一i ) 又表示为 x c 】= 【五+ x 3 + + = o x 2 + 屯+ x 5 + x 7 = 0 五+ x 2 + 确+ x 7 = o 】 十鼍+ + = 0 ( 2 - 3 ) 观察因子图2 1 ( b ) ，由于其中的边为无向边，所以容易发现图中存在有长度为 4 的循环路径( ，z 。) 、( z 。，) 、( ，毛) 、( z 4 ，) ，我们称为4 - 环。图2 1 ( b ) 的因 子图实际上是一个有环t a n n e r 图。在矩阵的第一行与第四行中，“l ”出现在第六 列与第八列，形成了一个矩形，在校验矩阵中，这样的矩形对应因子图上的4 一环。 类似地，此因子图中还存在其它4 环。采用置信传播算法迭代译码时，这种短环 路将极大地影响码性能。码的最小汉明( h a m m i n g ) e e 离及距离谱取决于环路的分 布情况。因此构造码时，应该尽量消除短环路1 1 7 1 8 】。 实际上，l d p c 码的因子图表示中，e 条边对校验节点的入射关系和对变量 节点的入射关系可以看作是相互置换，所以一个特定的码可看作一个随机置换， 反映边对变量节点与校验节点入射关系的对应。如果不限制变量节点和校验节点 第二章低密度校验码的描述与泽码原理 度数，那么随机置换函数有可能导致变量节点和校验节点各自的度数不再恒 定，这时入射边分布表示为一对度数分布序列兄= ( a ，屯) 和 p = ( 日，几) p2 1 ，其中 ；和b 分别表示度数，变量节点的入射边比例和度数f 校验节点的入射边比例，以和也分别是最大变量节点度数和最大校验节点度数， 度序列上也可以用多项式旯 ) = l x 川和p ) = p ，x 1 表示，这时设计码率 踟咖一s i , * * 4 i i 坝蛐小陲础) 溪计p 。， 显然，分布多项式退化为丑0 ) = x 扛。和p 0 ) = x 川时，变量节点和校验节点的 度数分别恒定为z 和p ，相应的码就称为( j v ，五，p ) 规则( r e g u l 砷l d p c 码，否则称 之为非规贝1 ( i r r e g u l a r ) l d p c 码。 2 1 2 后验概率分布与因子图 设c 为时间离散信道上的一个分组码，发送码字为x = 瓴焉，粕) ，接收码 字为y = ：，帕) 。设p ( x ) 表示发送码字x 的先验概率，那么根据全概率公式， 信道输入和输出向量的联合概率( 密度) 函数为f ( x ， ，) = p ( x ) f ( y i x ) ，其中 f ( y 1x ) 是发送码字x 时接收y 的条件概率( 密度) 函数或似然函数。给定信道输出 y ，码字集合c 的后验概率( a p p ) n 度p ( x l 力与联合概率函数( 工，y ) 成比例， 即【3 4 l p ( x ij ，) = f ( x ，y ) f ( y ) * f ( x ，) 。 ( 2 - 5 ) 如果此离散信道是平稳无记忆信道，则式( 2 5 ) 可以进一步表示为 ( ，ix ) = f o s i , y ：，, y nl x i , x 2 ，。) = 兀厂叱i x ，) ， ( 2 6 ) j = l 其中厂( j ，fx ，) ，j = 1 ，是平稳信道的标量转移概率密度函数。 码字x 允许服从任何分布【2 ”。如果假定先验概率p ( x ) n - - t g 数，即所有码 字被等概选取，那么结合形如式( 2 - 1 ) 的码特征函数，可以表示为 2 9 , 3 4 1 1 p 瓴孵一而卜高f ( x j , x ：，剐( 2 - 7 ) 因此，联合概率函数f ( x ，y ) 可以比例表示为 m f ( x t , x z ，而巩z ，”) * 兀f x ( x 。：t ( f ) ) ) 兀厂o ，眄) 。( 2 8 ) 两安电子利技大学硕十学位论文一低密度校验码中几个关键问题的研究 将( 2 8 ) 代入( 2 5 ) 得到后验概率测度，即给定信道观察y 时，工c 的后验概 率为 m p ( x ij ，) = ，( 吨：后( f ) ) ) i - i ，奶，( 2 9 ) i = 1 j = i 其中，口是使，。p ( xf ，) = 1 的归一化因子。 x l ，饥i 而) y l z lz 2 图2 2l d p c 码的后验概率测度因子图 在表示l d p c 码校验约束的因子图上，增加接收变量节点 乃 及信道转移函 数节点 厂( 乃ix 伪，得到如所示的表示码字后验概率分布e ( xi ，) 的因子图3 4 1 。 图2 2 中，黑圆点表示校验约束节点，对应于图2 1 中的校验节点：黑方块表示 转移函数节点；圆圈分别表示发送变量节点和接收变量节点。 2 2 消息传递算法 译码算法是决定信道编码性能及其应用的重要因素。但是通常分组码的译码 复杂度与码长成指数关系，码长增加到一定程度后，译码将变得不能实际实现。 l d p c 码则不同，由于其校验矩阵稀疏的特点，对它的译码可以采取高效的译码 算法消息传递算法( m a s s a g ep a s s i n g ) ，使锝其译码复杂度与码长成线性关系。 消息传递算法是一种工作在图论基础上的译码算法，在其工作过程中，消息 在二部图上沿着边在变量节点与校验节点之间来回传递，因此称为m a s s a g e p a s s i n g 算法。 2 2 1 规则l d p c 码的消息传递算法及收敛分析 我们以b s c 信道下为例，介绍l d p c 码的m a s s a g ep a s s i n g 译码算法。在一 个编码对应的二部因子图中，每个变量节点x 存储一个比特的硬判决信息( 错 误概率为p ) ，且与之相连接的每一条边( x ，= ) ，对应地存储一比特x 节点信息的 第二章低密度校验码的描述与译码原理 猜测信息g ，该猜测信息与该变量节点无关，且此信息在译码迭代中逐次更新。 需要指出每次迭代过程中，边( x ，z ) 都要在两个方向上分别传递信息。迭代过程如 下( 1 8 , 3 5 ： ( 1 ) 变量节点信息更新与传递： 如果是首次迭代，令g 。= 。如果不是首次迭代，如下更新& ：上一次迭 代中节点x 除z 以外的相邻校验节点发送给x 的信息都相同，将g 。：置为该值；否 则，置为t 。 在两种情况下，节点，r 都将g 。，发送给校验节点z 。 ( 2 ) 校验节点信息更新与传递： 校验节点z 将它在本次迭代中从除x 以外的相邻变量节点收到的信息进行异 或运算，并把结果发送给节点x 。 下面我们直观解释一下上述算法。设z 为节点x 的某相邻校验节点，它将除工 外的相邻变量节点接收的信息值进行异或运算，并将结果值发送给x ，这相当于 校验节点z 根据除x 节点外的相邻变量节点提供的信息向节点x 提出它的要求。 但是x 节点并不一定响应该要求。如果x 节点除= 以外的所有校验节点都向x 提出 相同的要求，那么x 响应该要求，并将该要求值作为x 的猜测信息传递给校验节 点2 ，参与z 的校验检查，类似地节点将利用该信息及从其它节点获得的信息向 其它的节点提出新的要求。如果除z 外x 的其它所有相邻校验节点向x 提出的要求 不全相同，列叫不响应任何要求，并将它的初始值t 发送给校验节点z 。 令n 表示第i 次迭代节点x 发送给节点z 错误信息的概率，译码开始迭代以前 有p 。= p 。下面我们将分析b 随迭代次数增加的演变规律。 在第j 次迭代结束的时候，设节点x 除z 以外的另一节点z ，如果除x 以外的 相邻变量节点中有任意偶数个发送给节点z 。错误的信息，那么发送给x 的要求信 息仍然是正确的。由于每个发送给z 的信息的错误概率为b ，那么易得接收到偶 数个错误的概率为 口：! ! = 旦旦2 ：! ! ! 二垦二旦2 1 ：! ：! ! ! 二! 翌：! ( 2 - 1 0 ) 22 式( 2 1 0 ) 中奇数项相互抵消了。由( 2 1 0 ) 可得，在第i + 1 次迭代时，节点x 接 收到错误的初始信息，但发送出正确信息的概率为 岛 幽拿显 z ( 2 1 1 ) 相似地，第i + 1 次迭代中，节点z 接收封正确的初始信息，但发送出错误信息的 概率为 西安电子科技人学硕士学位论文一低密度校验码中几个关键问题的研究 ( 1 - p o ) 坐：娶监 一 由上可得p 。用只表示的递推公式： p ，。= p o - - p o 三掣】2 _ i + ( 1 一风) 【 ( 2 1 2 ) ! 二! ! 二! 旦芝p t ( 2 - 1 3 ) 2 。 由此就可以找到所有使n 单调下降并收敛到0 的值的上界p + 。 前面的译码规则要求，对节点x ，只有除节点z 以外的所有校验节点都对x 节 点提出相同的校验要求时，x 节点才响应要求，并发送该信息到z 节点参与新 轮的校验；否则，发送初始值- 给z 。事实上，我们可将这一要求适当放松：设 定一门限值6 ，对节点x ，如果x 除了z 之外的相邻校验节点中至少有6 ，个在上一 轮迭代中对x 提出相同的要求，那么变量节点x 就响应该要求，并且在本次迭代 中将该信息发送给节点z ；否则，发送初始值一给z 。其余的译码算法保持不变。 对修改后的算法可利用类似于公式( 2 1 3 ) 的推导方法，得到p 的递推计算公式。 为方便起见，令g ，= l 一2 b ，并定义函数： p ( ，) = ! 芸】【与牛“ ( 2 - 1 4 ) 一岛蒿( 7 1 p 1 只卅”岛，荽卅棚，引z 彤， 适当选择4 ，可使只+ 与p 相比是递减的，换句话说，该算法向着正确的译码方 向进化。最佳的鱼是满足下式的最小正整数： 一1 - p os 【等譬丝等p “t ( 2 - 1 6 ) p o 一。1 一( 1 2 p ，) 9 。1 6 j 是p 的增函数。 如果b 足够小，对式( 2 - 1 6 ) 来说，兄为偶数时，鱼取值为, t 1 2 ；五为奇数时， 6 i 取值为( a + 1 ) 2 。应用这样选定的包值，公式( 2 1 6 ) 可表示为【1 8 】 r 丑一1 1 m b + l = p 0 1 一1l ( 七一1 ) 2p s2 + 高阶小项；五为奇数 ( 2 - 1 7 ) i 丁j p 一= p 。 j ：1 c 七一- ，；p ；+ 高阶小项； 五为偶数。c z t s ， 第二章低密度校验码的描述与译码原理 容易发现，对足够小的p o ，选择适合大小的岛，随着消息沿着因子图中的边 传递持续进行，n 将持续减小，如果码长无限长，只将减小至零。实际应用中， 我们预先设定一个迭代次数的最大值，随着迭代的进行，要么变量节点的猜测值 满足了所有校验节点的约束，这时该算法成功译码，要么因为迭代次数到达了预 先设定的最大值而失败。 2 2 2 非规则码的消息传递算法及收敛分析 设非规则码的度序列分布为( ，五，k ) 与( p l ，仍，既) ，其中兄，和p ，分别 表示度数，变量节点的入射边比例和度数i 校验节点的入射边比例，z ，和谚分别 是最大变量节点度数和最大校验节点度数，也可用多项式五 ) = 五，x 1 和 p = 口x “1 表示。 非规则码的译码算法与规则码的译码算法基本相似。但是需要考虑节点具有 不同的度数。仍然从边( x ，z ) 的角度来考察译码过程。第i 次循环结束时，设z 。为x 除z 以外的另一校验节点，如果z 除x 外其它相邻变量节点有偶数个发送给z 错 误的信息，节点= 将发送给x 正确的信息。由于每个比特信息错误发送给z 。的概 率为p i ，若z 。次数为i ，则接收到偶数个错误的概率为( 1 + ( 1 2 p ，) 1 ) 2 ，但z 1 次 数未知，其次数为f 的概率为n ，取均值得错误概率为 壹一三掣：i 掣：! 旦f 享! 里( ：一。) 与式( 2 - 1 0 ) 对照，( 2 - 1 9 ) 可认为是考虑到z 具有度序列分布时( 2 10 ) 式的推广，式 中1 2 p ，是p ( x ) 的参数。与前面规则l d p c 码相似，如果上轮迭代中，变量节点 x 除= 外的相邻校验节点至少有缸个发送给x 同样的要求值，那么节点刊哿沿着 边( x ，z ) 将该值发送给校验节点z ，否则，x 发送初始值匕给校验节点z 。注意现 在节点的门限值依赖于它的度数，当然，鱼也受迭代次数的影响。 为了分析译码过程，考虑一条随机边( x ，z ) 。它是度为，的变量节点入射边的 概率为五，。与前面相似，同样定义= 1 2 p , ，函数y 同公式( 2 1 4 ) 中的定义， 我们可得芦的递推公式为 陬，确一喜伽，笺( _ 1 扣的工d + ( 1 - p o ) 善( 7 t i l 卜触a u 小z 锄， j = 1 f _ 缸，l = 电， 曲安电子科技人学硕士学位论文一低密度校验码中几个关键问题的研究 我们需要选择6 j ，以使p 。比p i 小，即使b 向正确的译码方向进化。与公式( 2 - 1 6 ) 相似，最佳的6 ，是满足下式的最小正整数阔： 生丑 生生坚；粤严一- ( 2 - 2 1 ) p 。1 一p ( 1 2 b ) 1 注意( 2 2 1 ) 中，值2 包，一，+