（信号与信息处理专业论文）Ⅰ型pa码与规则ldpc码的性能对比研究.pdf

摘要 乘积积累码( p a 码) 是由单校验乘积码和递归卷积码串行级联而成的一种 码型，具有规则的结构、优越的性能、很低的编译码复杂度，并且码率可以在 1 2 1 之间灵活调整。p a 码分为i 型和i i 型，其中i i 型p a 码是i 型p a 码的 一种特殊情况，本文重点研究i 型p a 码。 近几年，人们发现l d p c 码以比t u r b o 码更接近香农限的误码率性能和复杂 度很低的迭代译码算法而具有广泛的应用前景。l d p c 码已经成为新一代移动通 信系统和卫星通信系统中信道编译码技术的重要选择方向之一，也有学者提出用 l d p c 码取代数据存储系统中的r s 码。所以比较分析p a 码与l d p c 码的性能，将 具有重要的意义。 本文在理解因子图与和积算法原理的基础上，分别研究了l d p c 码和i 型p a 码的编译码原理，并用先进的码型分析工具e x i t 图分析了规则l d p c 码和i 型 p a 码的门限值，从理论上证明了i 型p a 码具有比规则l d p c 码更好的渐进性能。 然后用软件仿真对比了i 型p a 码和规则l d p c 码在a w g n 信道下的误码率性能， 其中译码算法分别采用了和积算法与最小和算法。发现在两种译码算法下，都存 在这样一个结论：无论是高码率( 7 8 码率) 还是中等码率( 1 2 码率) ，当码 长增加时，i 型p a 码的性能逐渐赶上并超过规则l d p c 码，这正好与理论分析的 结果一致。同时本文还比较了i 型p a 码和规则l d p c 码的译码复杂度，得到：在 采用和积算法时，i 型p a 码的译码复杂度低于规则l d p c 码。 此外，i 型p a 码还具有线性时间的编码复杂度，即编码复杂度与码长成 正比，而l d p c 码的编码复杂度与2 成正比。在硬件实现上，i 型p a 码不需要 像l d p c 码那占用很多的存储空间来存放校验矩阵信息。而且，i 型p a 码还可以 灵活地改变码率和码长，这也是l d p c 码所不具备的。 可以预见，在码率高于1 2 的应用场合下，i 型p a 码将会是规则l d p c 码的 一个很好的替代码型。 关键词：乘积积累码；低密度奇偶校验码；迭代译码 a b s t r a c t p r o d u c ta c c u m u l a t e( p a )c o d e sa r es e r i a lc o n c a t e n a t i o no fa s i n g l e p a r i t y c h e c k b a s e dp r o d u c tc o d e ，a ni n t e r l e a v e r ，a n dar e c u r s i v e c o n v o l u ti o n a lc o d e p ac o d e sh a v er e g u l a rs t r u c t u r e ， g o o dp e r f o r m a n c e ， l o wc o m p l e x i t ya n df l e x i b l er a t ea d a p t a t i o nf o ra l lr a t e sa b o v e1 2 p a c o d e si n c l u d ep a ic o d e sa n dp a i ic o d e sw h i c ha r es p e c i a lc a s e so fp a i c o d e s t h i st h e s i sm a i n l ya n n l y z e sp a ic o d e s r e c e n t l y ，i th a sb e e nf o u n dt h a tl o wd e n s i t yp a r i t yc h e c k ( l d p c ) c o d e s h a v eaw i d e ra p p l i c a t i o nf o rt h e i rc l o s e rd i s t a n c ef r o ms h a n n o nl i m i ta n d l o w e rd e c o d i n gc o m p l e x i t yt h a nt u r b oc o d e s a sar e s u l t ，l d p cc o d e sh a v e b e e nc o n s i d e r e da so n eo ft h eg o o dc h o i c e sf o rc h a n n e lc o d i n gi nt h en e x t g e n e r a t i o nw i r e l e s sc o m m u n i c a t i o ns y s t e ma n ds a t e l l i t ec o n ：n u n i c a t i o n s y s t e m a n di tw a sp o i n t e do u tt h a tl d p cc o d e sw i l lr e p l a c er sc o d e si n t h ef u t u r es t o r a g ed e v i c e s t h e r e f o r e ，i ti ss i g n i f i c a n tf o rp e r f o r m a n c e s o f p ac o d e sa n dl d p cc o d e st ob ea n a l y z e da n dc o m p a r e d b a s e do nt h ec o m p r e h e n s i o no ft a n n e rg r a p ha n ds u m - p r o d u c ta l g o r i t h m ， t h i st h e s i sa n a l y z e st h ee n c o d i n ga n dd e c o d i n ga l g o r i t h mo fp a ic o d e s a n dl d p cc o d e s w it han o v e lt o o ln a m e de x i tc h a r t ，t h et h r e s h o l d so fp a i c o d e sa n dr e g u l a rl d p cc o d e sa r ei n v e s t i g a t e dt op r o v et h e o r e t i c a l l yt h a t p a ic o d e sh a v eb e t t e rc o n v e r g e n tp e r f o r m a n c e t h ep e r f o r m a n c e so fb o t h p a ic o d e sa n dr e g u l a rl d p cc o d e sw i t hs u m - p r o d u c td e c o d i n ga l g o r i t h ma n d m i n s u md e c o d i n ga l g o r i t h ma r es i m u l a t e du n d e ra d d i t i v ew h i t eg a u s s i a n n o i s e ( a w g n ) c h a n n e l s s i m u l a t i o nr e s u l t sa tm e d i u mr a t e ( 1 2r a t e ) a n d h i g hr a t e ( 7 8r a t e ) s h o wt h a tw i t ht h ei n c r e a s i n go fc o d e w o r dl e n g t h ， t h ep e r f o r m a n c e so fp a 。ic o d e sg r a d u a l l yc a t c hu pw i t ha n de v e ne x c e e d r e g u l a rl d p cc o d e s ，w h i c hi sc o n s i s t e n tw i t ht h et h e o r e t i c a la n a l y s i s t h ed e c o d i n gc o m p l e x i t i e so fp a ic o d e sa n dr e g u l a rl d p cc o d e sa r ea l s o c o m p a r e da n di t i sf o u n dt h a tt h ed e c o d i n gc o m p l e x i t yo fp a 。i c o d e si s l o w e rt h a nt h a to fr e g u l a rl d p cc o d e sw i t hs u m - p r o d u c td e c o d i n ga l g o r i t h m m o r e o v e r ，t h ee n c o d i n gc o m p l e x i t yo fp a ic o d e si sp r o p o r t i o n a lw i t h c o d e w o r dl e n g t hn ，b u tt h ee n c o d i n gc o m p l e x i t yo fr e g u l a rl d p cc o d e s i sp r o p o r t i o n a lw i t hn 2 a n dt h ee n c o d e ro fap a ic o d ei sc h e a pf o r i m p l e m e n t i n gs i n c ei td o e sn o tr e q u i r ea d d i t i o n a ls t o r a g eo fag e n e r a t o r m a t r i xn e e d e df o ral d p cc o d e m e a n w h il ep a ic o d e so w nr a t e l e n g t h a d a p t a t i o nw h ic hr e g u l a rl d p cc o d e sd on o th a v e b a s e do nt h e s er e s u l t s ，itc o u l db ef o r e s e e nt h a tp a ic o d e sw illb e ag o o da l t e r n a t i v et or e g u l a rl d p cc o d e si nf u t u r ed i g i t a lc o m m u n i c a t i o n s y s t e m sa tr a t e sa b o v e1 2 k e y w o r d s ：p r o d u c t sa c c u m u l a t ec o d e s ：l o wd e n s i t yp a r i t yc h e c kc o d e s ： i t e r a t i v ed e c o d i n g 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。本人在论文 写作中参考的其他个人或集体的研究成果，均在文中以明确方式标明。本人依法 享有和承担由此论文产生的权利和责任。 声明人( 签名) ： 娴年r 月河日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大学有权保留 并向国家主管部门或其指定机构送交论文的纸质版和电子版，有权将学位论文用 于非赢利目的的少量复制并允许论文进入学校图书馆被查阅，有权将学位论文的 内容编入有关数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密的 学位论文在解密后适用本规定。 本学位论文属于 1 保密() ，在年解密后适用本授权书。 2 不保密( ) 作者签名：卣更日期：砌 年 f 月 苫日 导师签名：2 于日期：习年厂月z e t 第一章绪论 第一章绪论 本章在简要介绍了纠错编码理论的发展历史及研究现状的基础上，提出了本 文研究的课题及其意义和方法，并给出了文章的结构。 1 1纠错编码理论的发展历史 1 9 4 8 年，美国贝尔实验室的c l a u d ee s h a n n o n 在贝尔技术杂志上发表了 题为“am a t h e m a t i c a lt h e o r yo fc o m m u n i c a t i o n ”的论文n 1 ，这是一篇关于现 代信息和编码理论的奠基性论文，它的发表标志着现代信息与编码理论这一学科 的创立。s h a n n o n 在该文中提出了信道编码理论，即任一通信信道都有一个参数 c ，称之为信道容量，如果通信系统所要求的传输速率r 小于c ，则存在一种编 码方法，当码长n 充分长并采用最大似然译码时，系统的错误概率可以达到任意 小。虽然s h a n n o n 只是给出了一个存在性定理，但却开创了信道编码理论这一富 有活力的研究领域，此后，编码科学家们一直朝着s h a n n o n 指出的方向努力，寻 找s h a n n o n 提出的“好码 成为编码科学家们不懈追求的目标。 上个世纪5 0 年代到6 0 年代，科学家们主要研究各种有效的编、译码方法， 这个时期奠定了线性分组码的基础。如：1 9 5 0 年h a m m i n g 发明了h a m m i n g 码， h a m m i n g 码是一种能纠正一个错误的完备线性分组码；此后又出现了b c h 码的编 译码方法，b c h 码是循环码的一个子类，具有较好的码特性；同时，还出现了卷 积码及序列译码方法，卷积码不同于上面提到的分组码，它是一类非分组码；并 且，通过理论分析给出了纠错码的基本码限等。这个时期是纠错码从无到有迅速 发展的年代。 2 0 世纪六七十年代，这个时期科学家们主要研究的方向开始从“数学家的 游戏 转向重视编码技术在实际系统中的应用研究。这个时期出现了许多有效的 编译码方案，比如：门限译码、迭代译码、软判决译码，卷积码的维特比译码。 尤其是维特比译码的出现为纠错码的实用化前进了一大步。卷积码以其好的性 能，好的实时性，被首次用于卫星通信系统中。值得一提的是1 9 6 2 年g a l l a g e r 还提出了一种线性分组码低密度奇偶校验码( l o wd e n s i t yp a r i t yc h e c k i 型p a 码与规则l d p c 码的性能对比研究 c o d e s ，简称l d p c 码) 2 1 他提出了用迭代译码的方法来进行译码，但是由于当 时计算机仿真水平的限制，这种码字的性能没有得到完全的体现。这个时期代数 码的理论日趋成熟，各种纠错码的理论问题也得到讨论，如码的重量分布、译码 错误概率和不可检测概率的计算、还有信道的模型化等。 7 0 年代到8 0 年代，由于大规模集成电路的迅速发展，为纠错码的大规模实 用打下了坚实的基础，如美国7 0 年代发射的“旅行者”号宇宙飞船中就成功的 用了纠错码技术，使宇宙飞船能从遥远的太空传回清晰的照片。同时，由于数字 信号处理技术的发展，纠错码在通信系统中的应用也得到关注，使得纠错码广泛 用于实际的通信系统中。 9 0 年代到现在，纠错码理论日趋完善。t u r b o 码4 5 6 1 的出现引起了人们对 迭代译码的热情关注，使得各种现代的高效纠错码理论相继出现，完善了s h a n n o n 信道编码理论。 1 2 高效纠错码及其研究现状 从s h a n n o n 信道编码定理可知，随着分组码的码长或卷积码的约束长度的增 加，系统可以取得更好的性能( 即更大的保护能力或编码增益) ，而译码应该采 用最大似然( m l ) 译码。但是，众所周知，最大似然译码算法( m l d a ) 的复杂性 随码长n 指数增加，当n 较大时，m l d a 几乎物理不可实现。因此，必须研究新 的编译码方案。 一种方法就是采用级联码构造具有较大等效分组长度的纠错码，并且允许将 最大似然译码分为几个较简单的译码步骤，这样便得到一个次优而实际可行的译 码方案。如f o r n e y 的串行级联码，乘积码嗍等。 另一种用次优算法来逼近m l 算法的方法是迭代译码方法。1 9 9 3 年t u r b o 码 的出现，引起人们对迭代译码技术的热情关注。t u r b o 码巧妙的将卷积码和随机 交织器结合起来，实现了随机编码的思想。同时，采用软输出迭代译码来逼近最 大似然译码。仿真表明：如果采用6 5 5 3 6 的随机交织器，并且进行1 8 次迭代， 则在e b n 0 o 7 d b 时，码率为1 2 的t u r b o 码在a w g n ( a d d i t i v ew h i t eg a u s s i a n n o i s e ) 信道下的误比特率b e r 1 0 。5 ，非常接近s h a n n o n 限( 1 2 码率的s h a n n o n 限是o d b ) 。1 9 9 5 年，d a v i dm a r k e y 和n e a l 再次发现了采用迭代译码的l d p c 2 第一章绪论 码的优越性能，能比t u r b o 码更接近s h a n n o n 限嘲。重复累积码( r a ) n 们等相继出 现的“类t u r b o 码”均采用的迭代译码方法，可以说迭代译码方法已成为构造高 效纠错码的首选译码方案。 目前，以迭代译码为基础的高效纠错码成为了业界的主要研究对象，人们不 再像以前那样把过多的精力集中在以代数为基础的代数码上，而是寻找新的纠错 码的认识方式，即以t a n n e r 图妇为基础发展起来的码的可视化方法：因子图以 及基于图中边上信息传递的迭代译码算法，还有用于寻找码字性能限的数值化方 法如密度进化n 2 1 与e x i t 图n 3 1 等优化设计方法。所设计出来的这些高效纠错码都 具有共同的特点，就是纠错性能好，占用的额外带宽不多，并且编译码的复杂度 通常是可以接受的，因此能被广泛用于各类的传输系统中。 综上所述，现代高效纠错码为了实现高效纠错的目标，不是采用用级联码构 造随机长码的方法，就是采用迭代译码的方法，或者二者均采用，从而可以实现 或近似实现s h a n n o n 所提出的“随机好码”方案。值得一提的是，2 0 0 1 年j l i 设计出的乘积积累码( p r o d u c ta c c u m u l a t ec o d e ，简称p a 码) 钔就是结合了以 上两种方法。该码是由单校验乘积码和递归卷积码串行级联而成的一种码型，具 有规则的结构、优越的性能、很低的编译码复杂度，并且码率可以在1 2 1 之 间灵活调整。本文将重点研究p a 码及其与规则l d p c 码的性能对比。 1 3 论文研究的意义和方法 j l i 在文章 1 4 中只对比了p a 码与t u r b o 码的性能，发现在a w g n 信道下， 1 2 码率以上的p a 码比t u r b o 码有更低的错误地板，并且译码复杂度比t u r b o 码低。事实上，l d p c 码以其比t u r b o 码更接近香农限的误码率性能和复杂度很 低的迭代译码算法而具有更广泛的应用前景。目前，l d p c 码已经成为新一代移 动通信系统和卫星通信系统中信道编译码技术的重要选择方向之一，也有学者提 出用l d p c 码取代数据存储系统中的r s 码引。所以比较分析p a 码与l d p c 码的性 能，研究p a 码在一些通信系统中是否优于l d p c 码，将具有重要的意义。 p a 码分为i 型p a 码和i i 型p a 码，其中i i 型p a 码是i 型p a 码的一种特 例，而且只有在码率高于0 8 8 时，i i 型p a 码性能才比i 型p a 码好一点n 钔，所 以本文选取i 型p a 码进行研究具有较普遍的意义。在l d p c 的码型选择方面，因 i 型p a 码与规则l d p c 码的性能对比研究 为p a 码具有规则的结构，于是选择同样具有规则结构的规则( 3 ，6 ) l d p c 码( 1 2 码率) 和规则( 4 ，3 2 ) l d p c 码( 7 8 码率) 与之进行比较。 就研究方法来说，首先研读相关的专题论文，在掌握因子图及和积算法、i 型p a 码及l d p c 码编译码原理的基础上，采用理论分析和实验论证相结合的方法。 理论分析方面，引入e x i t 图方法，比较分析i 型p a 码和规则l d p c 码的门限值； 实验论证方面，借助w i n d o w s x p c 平台搭建i 型p a 码和规则l d p c 码的编译码系 统，仿真对比分析i 型p a 码与规则l d p c 码在不同码长、不同码率下的误码率性 能。 1 4 论文的结构 本文具体内容安排如下： 1 、第一章简要阐述了纠错码的发展历程，高效纠错码的提出、发展与当前 研究状况，并给出了本文研究的意义和方法，以及全文的内容轮廓。 2 、第二章介绍了因子图及和积算法的基本原理，为理解l d p c 码和p a 码的 编译码原理打下基础。 3 、第三章介绍了二进制l d p c 码的编译码原理。 4 、第四章详细介绍了p a 码的编码结构和译码算法，并在保证性能的前提 下对译码算法进行了一定的改进。 5 、第五章介绍了e x i t 图优化设计方法的原理，并用该方法分析比较了i 型p a 码和规则l d p c 码的门限值。 6 、第六章分析比较了在a w g n 信道下，i 型p a 码与规则l d p c 码在各种码长 和码率传输下的性能，并比较了两者的编译码复杂度。 7 、最后总结全文，并给出作者在攻读硕士期间从事的科研工作和发表的论 文，以及相关的参考文献。 4 第二章因子图与和积算法 第二章因子图与和积算法 本章讨论了因子图的定义及和积算法的表示和工作原理，为第三章和第四章 用因子图与和积算法研究l d p c 码和p a 码打下基础。 2 1因子图 在1 9 8 1 年t a n n e r 的论文 1 1 中介绍了一种可以用来表示码字的图形，称为 t a n n e r 图。t a n n e r 图包含两类节点，其中一种代表的是码元节点，另一类代表 的是校验元节点，然后通过边连接这两种不同的节点，并且同种节点间不能有直 接的边连接。如果给定一个码字的码元数和它的校验方程，则用t a n n e r 图可以 唯一的确定该码字。在t a n n e r 图表示中，码的译码算法是可以用明确的公式反 映并可程式化进行，所以有很强的可实现性。举个例子，比如g a l l a g e r 所提到 的l d p c 码瞄3 就是可以用t a n n e r 图表示的。 t a n n e r 图本质上来说是用码字的校验方程来表述码字。w i b e r g , l o e l i g e r 和k s t t e r 等胡将t a n n e r 图扩展为网格图，与t a n n e r 图的最大区别在于网格图 还包含了码字的状态。人们把这种网格图称为t a n n e r - w i b e r g - l o e l i g e r 图。 k s c h i s e h a n g ，f r e y 和l o e l i g e r 指出t a n n e r - w i b e r g l o e l i g e r 图( 在f r e y 的 论文中把它叫做因子图，它具有更广泛的意义，下文就以因子图作为名称) 并不 只是适用于编码理论，它还可以应用在人工智能、m a r k o v 模型、b a y e s i a n 网络、 神经网络等等众多的领域n 6 1 。 2 1 1 因子图的定义 在因子图中有两类节点，一种是变量节点，另一种是函数节点。变量节点所 代表的变量是函数节点的自变量，并且同一类节点间无边的直接连接。 图2 1 表示的是一个有五个自变量的函数g 的因子图。根据数学的知识我们 知道任意一个函数都可以进行因式分解。现在假定函数g 可以分解成几个“局部 函数”之积的形式坞1 ，即： i 型p a 码与规则l d p c 码的性能对比研究 她，恐，毛，x 4 ，) = 六( 五珑心珑( 再，恐，毛珑也，而珑如，) ( 2 1 ) 由( 2 1 ) 式我们做出相应的因子图，如图2 2 所示，局部函数节点与它相关 联的自变量节点用边连接。该因子图清晰的表达了全局函数g 是局部函数无到 五的乘积。 2 1 2 边缘函数 图2 1 五自变量函数g 的因子图表示 ，a，l，c，d，| 图2 2 函数g 的因子图表示 在图2 1 中反映的是全局函数g ( ) 。而我们感兴趣的往往是通过这个全局函 数计算出的各边缘函数季( 薯) 。举个例子，对于而的任何可能取值，我们仅关心 这个露函数的估计值，设为： 季( 而) =g ( 而，屯，屯，x 4 ，x 5 ) ( 2 2 ) 屯，而，黾，砖 由此可见，喜( 而) 是函数g ( x t ，x 2 ，屯，x 4 ，x 5 ) 当变量为而黾时的和函数。 现在将( 2 1 ) 式代入上式运算就可以将其化为和的形式，有： 季( 五) = 六( 而) 厶( 屯) 五( 五，x 2 ，而) 厶( 屯，毛) 五( 而，) 韦( 而) 五( 吃) 五( 葺，屯，而) 厶( 而，硝) 五( 屯，) 怕。训 6 第二章因子图与和积算法 很明显，( 2 3 ) 式计算会异常复杂，所以我们将通过一些数学知识将其化简，为 了简化计算，首先作一些必要的数学定义： z ( 屯) = 石( 屯，毛) ( 2 4 ) 则，由： 我们可以得到： a ( x 3 ) = z f d ( 工3 ，_ ) ( 2 5 ) 施 工( 屯) = 石( 毛) 正( 毛) 六( 五，x 2 ) = z c ( x , ，j r 2 ，而) 嵋( 而) 石( 而) = 以( 而m ( 再，j c 2 ) 毛 最终，我们可以由无( 而) 和六( ) 来计算季( 五) ： ( 2 6 ) ( 2 7 ) 雷( 毛) = 以( 五) 以( 而) ( 2 8 ) 比较( 2 3 ) 式与( 2 8 ) 式，我们可以很清楚的看到计算季( 五) 得到了很大程度 的化简。这种化简的思想是基于将一个复杂任务分解成多个子任务的方法，每个 子任务对应到因子图上就是一个函数节点。这使得其计算不需要来自因子图其他 部分的信息，且传送其计算结果仅由这些局部函数的自变量来承担，从而简化了 计算，其具体算法可由后面介绍的和积算法实现。 从上面的一个简单实例可以看到，因子图具有非常良好的可视化效果。并且 可以通过一定的方法把较为复杂的问题转化为一系列只与本地函数有关的局部 问题加以求解，降低了各函数的互相关性。在因子图中，函数节点对每个相邻 变量节点，由其它相邻变量节点求和计算边缘函数后传递至该变量节点：变量节 点对每一个相邻函数节点，将其它相邻函数节点传递的边缘函数求积后传递到该 函数节点，从而实现了迭代计算。 2 2 和积算法 f r a n kr k s c h i s c h a n g 和j f r e y 在他们的论文 1 7 中不仅提出了因子图， 还有另一个重要贡献一一和积算法( s l i m p r o d u c t ，a l g o r i t h m ) ，并指出作为一种 i 型p a 码与规则l d p c 码的性能对比研究 通用的消息传递算法：和积算法实际上包含了大量的实际译码算法( 前向后向算 法，v i t e r b i 算法，p e a r l s 传播算法等) ，实际译码算法都可由和积算法框架导出。 2 2 1 和积算法的表示 和积算法本质上是一种消息传递算法，和积算法可从全局函数计算出各个不 同的边缘函数。 联系到上一节的因子图，通过和积算法计算应用在因子图上的函数雪( 薯) 有： 季( x f ) = g ( x l ，x 2 ，工，x ) ( 2 9 ) x 其中f l ，2 ，n ，w l ，2 ，n ) f 。 为了简化符号，作如下定义： 厂( 毛，x 2 ，吒) 上薯- - e ( 五，屯，吒) ( 2 1 0 ) 其中w l ，2 ， j ，称函数为除开薯的部分和函数。 我们仍然以上一节的计算g l ( x 。) 为例。从上节的推导的结果( 2 3 ) 式，有： 蜀c 西，= 无c 五，乏( 厶c 屯堍c 五而毛，( 乏厶c 弓， ( 乏五c 弓，黾， ( 2 ) 2 ) ，称为行重。如图3 1 所示，就是一个规则的( 1 2 ，3 ，4 ) l d p c 码的校验矩阵。 根据线性分组码h 矩阵的定义可知，矩阵的每一行表示一个校验方程：c h e c k ； 矩阵的每一列表示一个变量而受到哪些c h e c k 的约束。图3 1 的例子中，第一行 1 2 第三章l d p c 码原理 表示的校验方程c h e c k l 为：毛0 气0 而0 黾= o ( 0 表示模2 加) ，第一列表示 变量五受到c h e c k 2 、c h e c k 5 、c h e c k 7 的约束。 h = 0 01001 1 10000 l ：l00100o0o0l 0 c 00l0 0 00l l l0 alo00lloolo 0 1 1 0l0 000l00l0 a 00ll0 0 0l00l l ：o01 l0l00o00 1 0 1 000 0l0l0 0l l 0 cl lo o oo0l l0 o l 变量葺所受约束关系 图3 1 ( 1 2 ，3 ，4 ) l d p c 码的校验矩阵 c h c c k l 在第二章讨论了全局函数、局部函数以及变量之间的关系可以用可视化的因 子图方法来表示，9 0 年代中期科学家们将因子图的方法用到了l d p c 码上。对于 规则( n ，j ，k ) l d p c 码：每个变量都受j 个校验方程的约束，因此每个变量点 连接j 个校验点；每个校验方程约束着k 个变量，因此每个校验点与k 个变量点 相连。l d p c 码的因子图一边为变量点，一边为校验点，故l d p c 码的因子图也被 称为：二部图( b i p a r t i t eg r a p h s ) ，同时定义每个点发出的边的个数为这个点 的度。图3 2 所示就是( 1 2 ，3 ，4 ) 规则l d p c 码的二部图，其中方格表示校验 点，圆圈表示变量点。从l d p c 码的二部图中可以看到，所有变量点发出的边的 数目必然等于所有校验方程所接收的边的总数。那么对于l d p c 码( 1 1 ，j ，k ) ，若假 设i n 为校验方程的个数，即校验矩阵h 的行数，则以下等式必然成立： 刀，= ，纷x k ( 3 1 ) 图3 2 ( 1 2 ，3 ，4 ) l d p c 码的因子图 校验点 变量点 i 型p a 码与规则l d p c 码的性能对比研究 由于l d p c 码是以校验矩阵h 为特征的，不同的校验矩阵h 对应了不同的码 字集合。因此，l d p c 码的编码首先需要设计校验矩阵h ，同时这也是l d p c 码编 码的关键。 对于规则的l d p c 码( n ，j ，k ) ，在码长1 3 一定的情况下，主要的参数选择为j 与k 。目前的研究结果表明，性能最好的规则l d p c 码是( n ，3 ，6 ) 码。根据式( 3 1 ) 得知，参数n ，j ，k 确定后，则可以得到校验方程的数目n l ，那么校验矩阵h 的大 小就可确认为聊刀。l d p c 码校验矩阵h 的一般构造步骤如下：首先生成一个m 刀 的全0 矩阵，然后随机地将每列当中的j 个0 换成l ，每行当中的k 个0 换成1 。 但在随机置1 的过程中，必须避免以下两种情况的出现n 们： ( 1 ) 出现长度为4 的环 如图3 3 ，当校验矩阵h 当中出现长度为4 的环时，对应的因子图如图3 4 ， 种长度为4 的短环结构会导致消息在两组点之间的反复传递，而难以得到更新， 与迭代译码思想的初衷所违背，是必须清除的一种结构。理论分析表明，最小环 的长度为6 的情况下，码字的最小距离为4 。而随机构造的l d p c 码的最小距离 是随着分组长度，即码长的增加而线性增加的。 图3 3 具有长度为4 的环的校验矩阵 校验点 变量点 图3 4 具有长度为4 的环的因子图 1 4 l 0 0 0 d 0 0 l l 0 第三章l d p c 码原理 ( 2 ) 变量点所连接的校验方程过于集中 当变量点所连接的校验方程过于集中时，常常导致l d p c 码错误地板的发生。 例如在图3 5 中，变量点的度为3 ，但其中三个带阴影的变量点总共只连接了5 个校验方程；除了最右边的一个校验方程以外，其它4 个校验方程中，每个都连 接了两个阴影的变量点。因此，如果这三个阴影的变量点都出错时，左边4 个校 验方程都不能检测到错误的存在。但是当分组长度增大时，这种拓扑结构出现的 可能性也随之减少。 校验点 变量点 。国ooo 国oo 图3 5 变量点所连接校验方程过于集中的二部图 3 2 2 由校验矩阵h 生成l d p o 码宇 上一小结说明了构造校验矩阵h 的基本流程和原理，在获得校验矩阵h 后， 就可以根据校验矩阵h 来进行编码，从而得到相应的码字。 ( i ) 常规编码 根据校验矩阵h 得到相应的生成矩阵g ，假设信息源为s ，则编码生成码字 为u = s g 。这种编码方式是以牺牲运算复杂度为代价的。当分组长度为1 3 时， 其编码复杂度为d ( 刀2 ) ，若应用在移动通信当中，这种传播时延对于语音通信而 言是无法忍受的。同时计算复杂度也会使得存储器的数量过多，从而提高通信设 备的成本。为了简化运算复杂度，科研工作者们提出了很多简便算法。但是这些 算法均要求校验矩阵h 具有一定的特殊形式，因此在实际应用当中，应根据全局 条件来进行选择。 ( 2 ) 具有系统形式的h 矩阵的快速编码 由编码理论可知，具有系统形式的校验矩阵h 对应的生成矩阵g 也具有系统 形式，得到的码字u 也是具有系统形式的码字。现假设编码前的信息源为s ，编 码后的校验位为c ，编码后信息位s 位于码字u 的后部，即u = f c l s l ；假设校 i 型p a 码与规则l d p c 码的性能对比研究 验矩阵h 的大小y 寸m x n ，并具有系统形式日- - a i b 】，其中a 是- - ) p m x m 的单 位矩阵，b 是一个m 一r n ) 的矩阵。运用编码理论及矩阵运算可得下式： u h r ：0 j c a r + s b r ：0( 3 2 ) 由此等式可得到：c = s b7 似r ) ，因为a 为单位矩阵，故又可简化为： c = s b r 。 这种编码方式要求校验矩阵h 具有系统形式，简化了运算复杂度，但却是以 牺牲l d p c 码的稀疏特性为代价的。因为系统形式的校验矩阵h 要求具有一个 m x m 的单位矩阵，这必然使得校验矩阵h 的其余部分必须承担余下的所有1 元 素，从而使得这部分显得相对比较密集，并不能很好地达到l d p c 码原本所要求 的稀疏特性。 3 3l d p c 码的译码原理 3 3 1l d p c 码的古典译码算法 最大似然概率译码无疑是二进制信道的最佳译码方案，译码错误率也是使用 最大似然译码概率译码来分析的。但是在实际的应用当中，尤其是码长比较大的 情况下，采用最大似然概率译码所需要的硬件复杂度，存储器个数和时延等是难 以承受的。因此如何在运算复杂度与译码性能之间取得平衡是评价一个译码算法 优劣的标准。 作为l d p c 码的首创者，g a l l a g e r 于1 9 6 2 年提出了两种古典的译码算法， 前者基于硬判决，后者基于软判决。 ( 1 ) 硬判决古典译码算法 译码器的输入为硬判决所获得的初始值1 或0 ，译码器计算所有的校验矩阵， 如果某个变量点参与的校验方程出现了错误，并且错误的数目超过一个预定值， 就改变这个变量点的值。计算完整个分组的所有变量点后，再利用改变后的值进 行下一轮的计算，直到所有的校验方程都满足为止。 在校验方程的监督点比较少的情况下，这个方案还是比较可行的。因为大多 数校验方程都只会含有一个或者没有传输错误，所以当一个变量点参与的大多数 校验方程都出错时，这个变量点错误的可能性就非常大了。 1 6 第三章l d p c 码原理 ( 2 ) 软判决古典译码算法 在硬判决译码当中，变量点在进入译码器之前先进行了一次判决，译码器输 入的是某个变量点为1 或者为0 的值；而软判决译码则不同，变量点在进入译码 器之前并不进行判决，译码器输入的是某个变量点为0 或者为1 的概率。假设某 个变量点在经过信道以后存在两种情况，一种为1 0 的可能判决为0 ，9 0 的可 能判决为1 ；另一种为5 0 的可能判决为0 ，5 0 的可能判决为1 。硬判决译码 对这两种情况的区别是视而不见的，它只根据预先设定的判决门限进行判决；而 软判决译码则很好地保留了这两种情况的区别，为译码器的成功译码提供了更多 的外信息。 阐述此古典软判决译码时，首先引入一个g a l l a g e r 定理。 定理1 ：只代表经过信道传输后，第d 个变量点为1 的初始概率( 跟信道自 身的特性有关) 。对于规则的l d p c 码( n ，j ，k ) ，最代表第i 个校验方程中第，个变 量点为1 的概率，那么 鬟r r x o 端2 警斜舞k - i 高 12 p a ) 3 ) = 1 j y ，s 】 乞_ 上il 一丌一 为了证明这个定理，需要用到如下的引理： 引理1 ：一个独立的m 个比特的序列，第，个比特为1 的概率为只，则整个 序列中出现偶数个l 的概率为：旦掣，出现奇数个1 的概率为： l n 三。1 - 2 p t o 2 此引理在此直接引用，不予证明。现对定理1 证明如下： p r x d = l i j ，) ，s 】= p r x a = l 】 而= l 时满足j 个校验方程的概率 2 乞兀 h = l 时满足第i 个校验方程的概率 ：只n 第i 个校验方程的其它k 一1 变量还有奇数个l 的概率 嘶l l 埋刊 4 ) 1 7 i 型p a 码与规则l d p c 码的性能对比研究 同理可得：pr【勤：。iy)，sl：(1一只)ijli下1+1-i：；0-2p,)l ( 3 5 ) i 譬1 l 二 | 将式( 3 4 ) 与( 3 5 ) 相除，则得到了式( 3 3 ) ，定理l 得证。 通过定理l 的运算可以得到每个变量点为0 和为1 的概率比值，如果这个比 值大于1 ，则这个变量点在本次迭代中判为0 ；如果这个值小于1 ，则判为1 。经 过一次迭代以后，每个变量点的概率比值都会得到更新，并得到一组新的结果 x l 。用此新的结果与校验矩阵h 进行相乘，如果为0 ，则代表着译码成功，否 则转入下一次迭代。同时系统也设定一最大迭代次数，如果超过这个次数仍无法 译码成功，则放弃继续译码，输出最后一次迭代译码结果。 g a l l a g e r 为了表示这样一种迭代译码的思想，采用了图3 6 所示的树形图 来表示。图中d 点表示译码的起始点，为了计算d 点的条件概率，需要计算j 个 校验方程。图中的实线表示的正是校验方程。第一层的每条横线有k 一1 个点， 代表这个校验方程的其他k 一1 个变量点。 惫一lo t b 汀 d 秽t s i n 五腻 l 蛾- - e t m c k 警眦 d 图3 6 迭代译码的树形图表示 3 3 2l d p o 码的现代译码算法 正 进入9 0 年代，通过引入因子图来表示l d p c 码的结构，并引用人工智能中的 b p 算法，最终发展成为了l d p c 码的现代译码算法信度传播( b p ，b e l i e f p r o p a g a t i o n ) 算法，它本质上就是一种和积算法。 因子图与信度传播算法是紧密结合的。在图3 7 所示的因子图中，圆圈表示 变量点，方格表示校验点；边上所传递的信息定义为m e s s a g e ，分为从校验点到 变量点，与从变量点到校验点两种。其中从校验点到变量点传递的信息为0 ( r 二。) ，其物理意义为：第n 个变量点为0 ( 或1 ) 时满足第m 个校验方程的概 第三章l d p c 码原理 率；从变量点到校验点传递的信息为q o ( q 1 蛳) ，其物理意义为：通过除了第m 个校验方程以外的其它j - 1 个校验方程所得到的第1 2 个变量点为0 ( 或1 ) 的概 率。 q o ( q l 眦 图3 7 信度传播算法示意图 ( t 。) 信度传播算法延续了古典算法中的迭代思想，它的主要改进为：在计算变量 点满足校验方程的概率时，不再采用奇数个或者偶数个1 的方式，而是采用了全 概率的公式。因为当分组很大，通常有达到1 0 7 时，不可排除的总会有某个变量 点出错，如果它受约束的所有校验方程都产生了偶数个错误，就会使得