（计算机软件与理论专业论文）非规则ldpc码的局部消环技术及其相关技术的研究.pdf

非规则l d p c 码的局部消环技术及其相关技术的研究 摘要 近年来，首先由g a l l a g e r 发现，后来s i p s e r 、m a c k e y 等人重新发现的低密度奇 偶校验( l d p c ) 码以其接近香农限的性能和相对简单的译码结构而得到信道编码界的 广泛关注。短环的存在是导致l d p c 码产生错误平层效应的主要原因，本文对消除短 环以及其相关问题进行了较为系统的研究。 本文主要内容如下： 1 ) 详细介绍了一种非常有效地计算边缘函数值的方法。利用函数因式分解图的 模式，当函数的因式分解图为树时，通过消息传递算法能非常有效的计算边缘函数的 值。本论文指出l d p c 码的译码问题可以建模为该模式，并给出了无记忆二进制信道 下的译码中的消息传递规则。基于此，指出当一类l d p c 码的对应的t a n n e r 图为树 时，并不能得到让人满意的译码性能。因此，要得到具有较好性能的l d p c 码，必须 允许环的存在。 2 ) 创新性地提出了局部消环方法。由于非规则码的译码渐进性能超过了规则码， 同时非规则码中环对于度数小的节点的影响要大于度数大的节点，所以通过局部优先 的准则来保证度数小的节点之间的环最大化是非常有意义的。针对这点，本文基于矩 阵乘法和图中路径的对应关系，通过确定交换节点之间的边的方法，创新性地提出了 两种实现局部消环的方案。并对局部消环做了以下几个工作： 2 1 ) 提出了两种实现局部消环方案的具体算法，并指出实际运行中方案一的可行 性大于方案二。 2 2 ) 算法简化与复杂度分析，得出算法对于长码也是实际可行的。 2 3 ) 给出了一个局部消环的理论极限。仿真结果表明该理论极限不是紧致的，但 具有一定的指导意义。 2 4 ) 试验仿真。仿真结果表明局部消环相比于整体消环对l d p c 码的译码性能有 一定增益。 关键词：局部消环；低密度奇偶校验码( l d p c ) ；消息传递；围长 r e s e a r c ho nt h e l o o pr e m o v a la m o n gt h el o w d e g r e e n o d e sf o ri r r e g u l a rl d p cc o d e sa n di t s r e l a t e d t e c h n i q u e s a bs 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 s - - - f i r m d i s c o v e r e d b yg a l l a g e r a n d r e d i s c o v e r e db ys i p s e re t a la n dm a c k a ye t a l h a v ec r e a t e dm u c hi n t e r e s tr e c e n t l ys i n c e t h e ya r es h o w n t oh a v ear e m a r k a b l ep e r f o r m a n c ec l o s et ot h es h a n n o nl i m i to v e ra d d i t i v e w h i t eg a u s s i a nn o i s e ( a w g n ) c h a n n e l s t h ee x i s t e n c eo fs h o r tl o o pl e a d i n gt ol d p c c o d e sa r ee r r o r - p i n gl a y e re f f e c to ft h em a i nr e a s o n s t h i sa r t i c l es y s t e m a t i c a l l ys t u d i e dt h e l o o pa n d r e l a t e di s s u e s t i l i sa r t i c l er e a d sa sf o l l o w s ： 1 ) ad e t m l e di n t r o d u c t i o no fav e r ye f f e c t i v ee d g ef u n c t i o nv a l u ec a l c u l a t i o nm e t h o d u s ef u n c t i o nf a c t o r i z a t i o nm a pm o d e ，w h e nt h ef u n c t i o no ft h ef a c t o r i z a t i o np i c t u r ei sa t r e e ，t h r o u g ht h em e s s a g ep a s s i n ga l g o r i t h mc a nb ev e r ye f f e c t i v ef o rc a l c u l a t i n gt h ev a l u e o ft h ee d g ef u n c t i o n p o i n t e do u tt h a tt h el d p cc o d ed e c o d i n gp r o b l e mc a l lb em o d e l e d f o rt h a tm o d e la n dg a v ead e c o d i n go ft h em e s s a g et r a n s m i s s i o nr u l e sf o rt h eb i n a r y m e m o r y l e s sc h a n n e l f i n a l l y , w h e nt h ec o r r e s p o n d i n gt a n n e rp i c t u r es h o w st h et r e e t y p e l d p cd e c o d i n gp e r f o r m a n c es h o u l dn o tb es a t i s f i e d s ot h ee x i s t e n c eo fr i n gi sn e c e s s a r y f o r t h eg o o dl d p cc o d e 2 ) p u tf o r w a r dt h ei n n o v a t i v em e t h o d so fl o o pr e m o v a lf r o mp a r t i r r e g u l a rc o d e s d e c o d i n gp e r f o r m a n c et h a nt h er e g u l a rc o d e ，b u ta l s ob e c a u s eo fl o o pf o ras m a l ld e g r e eo f t h en o d ei sg r e a t e rt h a nt h ei m p a c to fl a r g ed e g r e en o d e s ，s og i v ep r i o r i t yt oe n s u r i n gt h a t l o o p sa m o n gt h el o wd e g r e en o d e sh a v et om a x i m i z ei sm e a n i n g f u l o nt h i sp o i n t ，t h i s p a p e r , b a s e do nm a t r i xm u l t i p l i c a t i o na n dg r a p ho ft h ec o r r e s p o n d e n c eb e t w e e nt h ep a t h s t h r o u g ht h es w i t c h i n gn o d e sb e t w e e nt h ee d g e s ，w ep r o p o s et w oi n n o v a t i v e i m p l e m e n t a t i o np r o g r a mo fl o o pr e m o v a lf r o mp a r ta n ds o m ejo bt od ot h ef o l l o w i n gf o r t h el o o pr e m o v a lf r o mp a r t ： 2 1 ) g i v et w ol o o pr e m o v a lf r o mp a r tp r o g r a mi m p l e m e n t a t i o ns p e c i f i ca l g o r i t h m ， i i a n dp o i n t e do u tt h a tt h ea c t u a lo p e r a t i o no ft h ep r o g r a mi sm u c hl a r g e rt h a no n ep r o g r a m o ft h ef e a s i b i l i t yo ft w o 2 2 ) a n a l y s i so ft h ea l g o r i t h mc o m p l e x i t y , d e r i v e da l g o r i t h mf o rt h el o n gc o d ei s a l s or e a l i s t i c 2 3 ) g i v eap a r t i a le l i m i n a t i o no ft h et h e o r e t i c a ll i m i t s i m u l a t i o nr e s u l t ss h o wt h a t t h et h e o r e t i c a ll i m i ti sn o tc o m p a c t ，b u th a sac e r t a i ns i g n i f i c a n c e 2 4 ) s i m u l a t i o n s ：t h es i m u l a t i o nr e s u l t ss h o wt h a tl o o pr e m o v a lf r o mp a r tc o m p a r e d t ot h eo v e r a l le l i m i n a t i o no ft h el d p cc o d ed e c o d i n gp e r f o r m a n c eg a i nm u s th a v e k e yw o r d s ：l o o pr e m o v a lf r o mp a r 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 s ； m e s s a g ep a s s i n g ；g i r t h i i i 浙江师范大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他 机构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 已在论文中作了明确的声明并表示了谢意。本人完全意识到本声明的法律结果 由本人承担。 诺为、匆 嗍矽7 娩日 学位论文使用授权声明 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有权保 留并向国家有关机关或机构送交论文的复印件和电子文档，允许论文被查阅和借 阅，可以采用影印、缩印或扫描等手段保存、汇编学位论文。同意浙江师范大学可 以用不同方式在不同媒体上发表、传播论文的全部或部分内容。 保密的学位论文在解密后遵守此协议。 作者签名：寺知，韧导师签名端榭渺期珈7 年6 月乙r 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管理条 例。我的学位论文中凡引用他人已经发表或未发表的成果、数据、 观点等，均已明确注明并详细列出有关文献的名称、作者、年份、 刊物名称和出版文献的出版机构、出版地和版次等内容。论文中未 注明的内容为本人的研究成果。 如有违反，本人接受处罚并承担一切责任。 承诺人( 研究生) 崔免 指导教厩端赫陟 1 1 信道编码回顾 1绪论 低密度奇偶校验码是目前信道编码界研究比较热的一种编译码方案，因此有必要 谈谈信道编码的意义。 实际信道都是有噪声的，如何在非理想的噪声信道上实现理想的通信是通信的基 本问题。显然通过提高信道的物理特性，可以降低噪声对通信可靠性的影响。然而这 些物理方面的改进会迅速提高通信信道的成本，而且这种成本的增加可能是无法承受 的。信道编码理论给出了另一条( 更有意思) 途径：我们依原样接受给定的噪声信道， 再将通信系统加在其上，以便能够检测并纠正信道所引起的差错。如图1 1 所示，我 们在信道前添加了编码器，并在信道后添加了译码器。编码器通过在源消息s 中以某 种方式加入冗余信息，将它编码为发送消息t 。信道则在发送消息上叠加上噪声，产 生被接收信息厂。译码器利用编码系统所引入的已知冗余信息，推断出源信号s 或被 叠加的噪声 信源 图1 1 信道编码模型 通过提高信道的物理特性只能使成本越来越高，而信道编码解决方案能够将噪声 信道变成可靠通信信道，其代价是要求编码器和译码器具有一定的计算能力。因此信 1 绪论 道编码可以让我们在较小的代价下实现非理想噪声信道上的理想通信。 香农限( s h a n n o nl i m i t ) 是衡量特定信道编译码方案的主要衡量标准之一，是 信道编码方案理论上的一个极限，人们一度认为香农限只是个理论值，并不能真正实 现。l d p c 码是一种实用的信道编码方案，近十几年来以其接近香农限( s h a n n o nl i m i t ) 的优秀性能和译码方面的低复杂度( 编码方面已经有了相当大的进展，但相比于另一 类接近香农限的t u r b o 码还有一些差距) 引起了人们极大的兴趣，并且l d p c 码已经 应用于光通信、深空通信、卫星通信、无线通信、高速d s l 、磁光全息存储等领 域，并很有可能成为4 g 移动通信系统的纠错编码标准方案。 1 2 信道模型 本文所有讨论都是在离散无记忆信道上展开的，其它信道的情况是以后的工作重 点。 离散无记忆信道q ：由一个输入信号集磊、和一个输出符号集考v 和一组对每一 个x 磊的条件概率分布p ( y i x ) 来描述。 一些有用的信道模型包括以下几种： 二进制对称信道： 磊= 0 ，1 ) ，氛= o ，1 ) ，具体如图1 2 所示。 o 1 o 1 图1 2 二进制对称信道模型 p ( y = o l x = o ) = l - f ；p ( y = oj x = 1 ) = 厂； p ( y = lj x = o ) = 厂；p ( y = 1 卜= 1 ) = 1 一厂； 二进制删除信道： 邑2 o ，1 ) ，够2 o ，? ，1 ) ，具体如图1 3 所示。 2 1 绪论 o0 9y 1 图1 3 二进制删除信道模型 p ( y = o b = o ) = l - f ；p ( y = o 卜= 1 ) = o ； p ( y = ? k = o ) = 厂；p ( y = 7 i x = 1 ) = 厂； p ( y = l l x = o ) = 厂；p ( y = 1 i x = 1 ) = l - f ； 高斯信道：高斯信道是一个普遍的实际信道，其输入输出都是连续的的实数。对于一 个实输心和一个实输出y ，已知x 咖的条件分布是一个高斯分布： 脚，= 击唧卜x 么2 n ， 很多实际信道可以建模为高斯信道，这个信道有时也被称作加性高斯白噪声信道 ( a w g n ) ，本文最后一节的仿真结果就是在该信道下进行的仿真。 1 3 低密度校验码的提出、发展和现状 1 9 4 8 年，美国贝尔实验室的香农( c l a u d ee s h a n n o n ) 在贝尔技术杂志上发表了 题为通信的数学原理的论文【l 】，这是一篇关于现代信息理论的奠基性文章，他的 发表标志着现代信息论与编码理论这一学科的诞生。香农在该文中指出：任意的通信 信道都存在一个参数c ，称之为信道容量。如果通信系统所要求的传输速率r 小于c ， 则存在一种编码方法，当码长充分大，译码采用最大似然译码时，系统的差错概 率可以任意的小，这就是著名的信道编码定理。这一定理的数学证明解决了误码存在 性的问题，并为后人用构造性方法去寻找好的纠错码指明了方向。 迄今，信道编码已发展了5 0 多年。2 0 世纪5 0 6 0 年代，科学家们主要研究各种 有效的编、译码方法，这个时期奠定了线性分组码的基础。如：1 9 5 0 年汉明t 2 发明 了汉明码，它是一种能纠正一个错误的完备线性分组码；此后 1 绪论 又出现了b c h 码【3 】的编译码方法，b c h 码是循环码的一个子类，具有较好的编码特 性；同时还出现了卷积码及其序列译码方法。 2 0 世纪6 0 7 0 年代，是信道编码发展过程中最为活跃的时期。如果说早期的编码 研究主要是数学家的游戏的话，则这个时期人们越来越重视编码理论在实际系统中的 应用研究。这个时期不仅出现了许多有效的编码方案，而且还出现了门限译码、迭代 译码、软判决译码和卷积码的维特比译码等。值得一提的是1 9 6 2 年g a l l a g e r t 4 】还提出 了一种线性分组码低密度奇偶校验码( u ) p c ) ，这种码采用迭代译码的方法来进行 译码，但是由于当时计算机仿真水平限制，这种码的性能没有得到充分的体现。 t a n n e r 5 】于1 9 8 1 年提出了用于理解信道编码理论的t a n n e r 图，t a n n e r 是自1 9 6 2 年g a l l a g e r 提出l d p c 码和迭代译码技术后继续长期关注迭代译码和l d p c 码的学 者之一。现在，t a n n e r 图已经广泛应用于信道编码理论中。 从2 0 世纪9 0 年代到现在，以t u r b o 码【6 】编译码技术的出现为标志，信道编码理 论日趋完善，并进入成熟阶段。t u r b o 码的出现引起了人们对随机编码方式和迭代译 码的关注，从而使得各种现代的编码理论相继出现，完善了香农信道编码理论。t u r b o 码的出现是首次对香农提出的非构造性问题的构造性回答。而在1 9 9 6 年，两位l d p c 码的追踪研究者m a c k a y 和n e a l 7 】重新发现了l d p c 码的优越性能，继而人们发现最 好的不规则l d p c 码的性能超过了迄今为止知道的最好的码( t u r b o 码) 。t u r b o 和 l d p c 码的出现，加深了人们对随机编码方式和迭代译码的全面理解，掀开了信道编 码理论的新篇章。 进入九十年代，l u b y 掣8 。9 】提出的非规则l d p c 码将l d p c 码的概念推广。 非规则l d p c 码的性能不仅优于规则l d p c 码，甚至还优于t u r b o 码的性能，是 目前己知的最接近香农限的码。r i c h a r d s o n 和u r b a n k 1 0 - 1 1 】也为l d p c 码的发展做 出了重大的贡献。首先，他们提出了一种新的编码算法，在很大程度上减轻了随机构 造的l d p c 码在编码上的巨大运算量需求和存储量需求。其次，他们发明了密度进 化理论，能够有效的分析出一大类l d p c 译码算法的译码门限。仿真结果表明，这 是一个紧致的译码门限。最后，密度进化理论还可以用于指导非规则l d p c 码的设计， 以获得尽可能优秀的性能。 l d p c 码具有巨大的应用潜力，将在深空通信、光纤通信、卫星数字视频、数字 水印、磁光全息存储、移动和固定无线通信、电缆调n 解调器和数字用户线( d s l ) 4 1 绪论 中得到广泛应用。m c h i a i n 等对l d p c 码用于有记忆衰落信道时的性能进行了评估。 b m y h e r 提出一种速率自适应l d p c 编码调制的方案用于慢变化平坦衰落信道，经 推广还可以用于f e c a r q 系统。f l a r i o n 开发的集成了v - d l p c 的f l a s h o f d m 移动 无线芯片组已可用于基于p 的移动宽带网。v l c a lt e c h n o l o g i e s l t d 提出了一种 用于w l a n 的l d p c t u r b o 不对称解决方案，即下行链路采用l d p c 码，上行链路 采用t u r b o 码。研究表明采用该方案后用于i e e e 8 0 2 1 1 a b g w l a n 移动终端的电池 寿命可延长至原来的4 倍。工业界也已经有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 万门， 最高可以支持5 0 0 0 0 的码长，0 9 的码率，最大迭代次数为l o ，译码器可以达到1 0 g b p s 的吞吐量，其性能已经非常接近香农限，可以满足目前大多数通信业务的需求。a h a 公司、d i 百t a lf o u n t a i n 公司也都推出了自己的编译码的解决方案。 1 4 本文选题和内容安排 1 4 1 本文选题 p e a r l 的置信传播算法【1 2 】是目前计算方面最可行的l d p c 码的译码算法。该算法 通过在l d p c 码所对应的t a n n e r 图的变量节点和校验节点之间传递概率信息找到和 原始码字最接近的码字。如果一个l d p c 码所对应的t a n n e r 图中没有环，该算法计 算方面总是可行的。但是好的l d p c 码必定存在着环。置信传播算法在l d p c 码所对 应的t a n n e r 图中反复的迭代，直到其收敛为一个解或者译码失败而停止。环的存在 会使一个错误位的值传播回这个错误位，加强了其被判定为错误位的可能性，阻止了 算法纠正该错误位的能力。对于长度很长的环，这个效应被分散，对译码性能影响不 大，而短环的存在会严重影响l d p c 码的译码性能。因此，消去l d p c 码中的短环是 构造高性能l d p c 码重要的一步。 度数高的节点由于其有更多的路径来更新信息，其抵抗信道中的错误的能力相比 于度数低的节点要强。因此首先保证度数低的节点之间的环最大化，再保证整个 l d p c 码的环最大化。通过这个步骤构造出的l d p c 码相比于只保证整个l d p c 码的 5 1 绪论 环最大化所得到的l d p c 码性能方面更优。本文主要讨论了一种通过交换边首先保证 度数低的节点之间的环的长度最大化，然后同样也是通过交换边，在不改变度数低的 节点之间分布情况的前提下使整个l d p c 码的环的长度最大化。仿真结果表明该过程 能改善l d p c 码的性能。为了讨论方便将上述方法称之为局部消环。 1 4 2 本文内容安排 本文安排如下：第二章介绍了l d p c 码的基本概念，着重介绍了环的概念；第三 章介绍了函数边缘化和l d p c 码的译码；第四章给出了局部消环的具体实现方法，讨 论了局部消环算法的复杂度问题，并给出了局部消环的一个上界；第五章为全文总结 和展望。 6 2 1码和码率 2l d p o 码的基本概念 信息本质上是离散的，很自然也很方便用有限域来描述信息。其中最重要的是二 进制域尼：包含两个元素 o ，1 ，以及运算模2 加法和模2 乘法( 0 斗o = 1 + 1 ：o ；0 + 1 = 1 ； 0 - 0 = 1 。0 = - 0 ；1 1 = 1 ) 。 定义2 1 ( 码) ：一个最上长度为甩，基数为m 的码c 是一个有肘个砑中元素的集 合。例如： c ( n ，m ) = 缸【1 1 ，一m 1 ，0 肼】霹，1 扰m 码中元素称为码字，参数刀称为码长。 例2 2 ( 重复码) ：重复码定义为c ( n = 3 ，m = 2 ) = 0 0 0 ，1 1 1 。 上例中介绍了二进制码，二进制码中的元素由f 2 = o ，1 ) 中的元素组成。有时为 了方便，也将f z 中的元素看作 1 ，。标准的映射是：0 ”+ 1 ，1 付- 1 。 定义2 3 ( 码率) ：一个码c ( ，l ，旧的码率r ：l l 0 9 2 m 。它表示每传递一个符号中包 刀 含的信息的位数。 定义2 4 ( 汉明重量和汉明距离) ：令u ， ，霹。一个码字“的汉明重量w 定义为 “中1 的个数。两个码字u ， ，的汉明距离c l ( u ，d 定义为u 和1 ，中不同位数的个数。 定义2 5 ( 最小汉明距离) ：令c 为一个码。它的最小汉明距离以c ) 定义为： d ( o = m i n d ( u ，d ：材，1 ，c ，u 嵋( 2 1 ) 7 2l d p c 码的基本概念 2 2 线性码 一个码c 如果其对于加法和乘法运算时是封闭的，即： a x + 口x c ，v x ，x c 和v a ，a 忍 则该码为一线性码。 对于一个线性码c ，其最小汉明距离吠c ) 等于c 中所有非全零码字中的最小汉明 重量： d ( c ) = m i n d ( x ，x ) ：x ，x c ，x x ) = r r f i n d ( x - x ，o ) ：x ，x c ，x x 7 = m i n w ( x x ) ：x ，x c ，x x ) = m i n w ( x ) ：x c ，x 0 ) 。 因为一个长度为，z 的线性码是露的子空间，所以存在一个整数k ，0 k 刀，c 为k 维的。这表明c 中包含有i 尼i 后个码字。下文的叙述中，用 ，z ，k ，明表示一个码 长为n ，维数为k ，最小汉明距离为d 的线性码，习惯上用称由c 中一个线性无关的 基组成的矩阵g 为生成矩阵。相反地，给定一个秩为k 的g 硭煳，可以通过g 定 义一个线性码c ( 回： c ( g ) = x 霹：x = u g ，甜劈) ( 2 2 ) 一般地，许多生成矩阵定义了同一个线性码。 对每一个线性码，定义一个对等码： c 干= 1 ，岁：r ，丁= o ，v xec = v ，罗：g v r = o r )( 2 3 ) 很容易证明c 。也是一个线性码，同样其也有一个生成矩阵，记为日，日也被称作c 的校验矩阵。由c 和c 的关系，可以得到c 也可由日的解空间来定义： c = xe ， x = u g ，“，) = x ，罗：h x 丁= o 丁)( 2 4 ) 由校验矩阵日来定义线性码c 是非常有用的，后面都会用h 来定义低密度奇偶 校验码。 8 2l d p c 码的基本概念 2 3 低密度奇偶校验码 2 3 1l d p c 码的校验矩阵表示 l d p c 码是一种线性分组码，它的名字来源于其校验矩阵日的稀疏性，即校验 矩阵中只有数量很少的元素为l ，大部分都为0 。g a l l a g e r 最早给出了规则l d p c 码 的定义，具体来讲规则l d p c 码的校验矩阵日满足下面三个条件： 1 ) h 的每行有p 个1 ； 2 ) 日的每列有入个1 ，a 3 ； 3 ) 与码长拧和日的行数相比，p 和入都很小。 图2 1 给出了( 2 0 ，3 ，6 ) l d p c 码的校验矩阵一个例子。 h = illll1 llll 1 1 l1l111 l1 11 l l 1l11ll 1ll l l l 11l11l lll1 l l l1llll 1l1ll 1 图2 1 ( 2 0 ，3 , 4 ) 矩阵 与规则码对应的是非规则码，非规则码中每行、每列的1 的个数是不同的。研究 指出非规则码相比于规则有着更优的性能。 2 3 2 l d p c 码的t a n n e r 表示和度分布函数 l d p c 码在几乎被遗忘的3 0 多年中，z y a b l o v 、p i n s k e r n 劓、m a r g u l i s n 钔以及 t a n n e r 等少数学者却在不同的领域直接或间接地对l d p c 码做着研究，并且他们的 研究成果对于今天的研究进展起着举足轻重的作用。t a n n e r 提出的用二分图来表示 一个低密度的线性分组码的方法，成为l d p c 码的主要分析工具。 对于每一个校验矩阵h ，都对应着一个t a n n e r 图。一个校验矩阵h 对应的t a n n e r 9 2l d p c 码的基本概念 图是一个二部图，它有玎个变量节点，对应为朋拘列数，m 个校验节点，对应为卸拘行 数。校验节向与变量节点f 之间有一条边相连当且仅当= 1 。因为很多校验矩阵对 应着同一个码c ，所以同样对于c 有很多t a n n e r 图与其对应。虽然很多t a n n e r 表示着同 一个码，但从消息传递算法( 第三章中有详细描述) 的角度看，它们是不一样的。 图2 2 为图2 1 中所示校验矩阵对应的t a n n e r 图。 图2 2 ( 2 0 ，3 ，4 ) 的t a n n e r 图 非规则码在文献 9 ，1 5 中被介绍，在文献 8 ，1 6 中被进一步研究。对于一个非规则 l d p c 码，其节点的度由某个度分布决定。这样，一个非规则l d p c 的t a n n e r 图表示中， 可能半数变量节点的度数为3 ，半数为5 ，半数校验节点的度数为6 ，半数为8 。 假设一给定的l d p c 码的码长为n ，度数为i 的变量节点的个数为人f ，则有 f 人f - 刀。同样用毋表示度数为i 的校验节点的个数，则有f i a f = n ( 1 - r ) p 为该 l d p c 码的设计码率) 。因为总边数是一定的，所以f i a 产f 嵋。为了表述方便， 引入如下记号： a ( 加窆即，雌) ：芝毋x ( 2 5 ) i = 1 i = 1 a | 和尸为z 的非负多项式，x 的i 次方的系数代表度为i 的节点的个数。从这些 定义，我们很容易得到如下一些关系： a ( 1 ) 钏，p ( 1 ) = 椰叫，m ，尸) = 1 一器，a ，( 1 ) _ p ，( 1 ) ( 2 6 ) l o 2l d p c 码的基本概念 下图为 7 ，4 ，3 汉明码对应的二部图，其对应的度分布为： a ( x ) = 3 x + 3 x 2 + 工3 ， c 工，= 号x + 号x 2 + 专x 3 ， 户( x ) = 3 x 4 ， r ( x ) = x 4 。 图2 3 【7 , 4 ，3 】汉明码对应的二部图 3 2 7 6 5 4 3 2 1 3函数边缘化及l d p c 码的译码 本章主要是关于这样一个问题：如何边缘化一个多元函数? 令人惊异的是，大 量的计算问题可被建模为该问题，本文主要关注的l d p c 码的译码问题即可建模为该 模式。 3 1 分布律 令助一个数域( 考虑f = r ) ，令a ，b ，c ，分布律表示为： 口6 + a c = a ( b + c )( 3 1 ) 如果这个简单的定律运用恰当，可以很大程度上减少计算复杂度。例如计算甜q 岛， 可通过，q ，哆计算，可以通过因式图的结构系统地利用分布律的优点，从而降 低计算复杂度。 例3 1 - 考虑函数厂其因式分解表示为： 厂( 五，x 2 ，x 3 ，x 4 ，x 5 ，讫) = z ( 五，x 2 ，恐) 五( 五，x 4 ，x o ) a ( 知) 五( _ ，x 5 )( 3 2 ) 假设我们对计算厂关于五的边缘化感兴趣，为了表述方便，将其记为厂( 五) ： 厂( 五) = 厂( 五，x 2 ，x 3 ，x 4 ，毛，x d - - 芝y ( 五，恐，x 3 ，x 4 ，x 5 ，讫) 其中表示对该函数在除去省略号代表的变量后所有自变量上求和。假设所有的 白变量都在一个有限集合中取值，记其) - yx ，如果假定所有的操作( 加法，乘法，函 数计算，) 都需要同样的时间，则通过穷尽法来计算厂( 五) 的复杂度为o ( i x l 6 ) 。但 是如果利用函数的因式分解表示，n - 叮：g g j f ( x m ) 写为： 厂c x - ，= 磊石c 1 ，娩，恐， 吾以c 心， 专五c 1 ，确， ( 吾厶c 确，玛， 给定，计算第一个因式可在o ( 1 x j 2 ) 复杂度内完成，第二个因式只由自变量_ ，墨和 1 2 3 函数边缘化及l d p c 码的译码 氏决定，可以通过如下方法有效计算。对于- 的每一个值( 已给定) ，计算 而厶( _ ，黾) 和六( 五，_ ，x 6 ) ，乘上五( _ ) ，然后在_ 上求和。由此，计算 第二个因式复杂度为o ( i x l 2 ) 。因为有i x l 个取值，所以总的计算复杂度为o ( i x l 3 ) ， 相比于通过穷尽法来计算厂( 五) 的复杂度为o ( i x l 6 ) ，复杂度有着惊人的降低。 3 2 因式分解图的表示 考虑一个函数与其因式分解，对函数的因式分解按如下步骤构造一个与其联系 的因式图。对于每一个自变量，画一个变量节点( 圆形) ，对于每一个因式，画一个 因式节点( 方形) 。用一条边连接一个变量节点和一个因式节点，当且仅当该变量节 点在该因式中。图3 1 为例3 1 的因式图。因式图是一个二部图，节点可分为两部分， 变量节点和因式节点。只有变量节点和因式节点之间有边相连，而变量节点和变量 节点之间，因式节点和因式节点之间没有边相连。例3 1 所对应的因式图是一个树， 该图中没有环，即任意两个节点之间只有一条路径。下节将证明，对于一个没有环 的因式图( 因式树) ，存在一个非常有效的消息传递算法边缘化该因式图对应的函数。 图3 1 例3 1 的因式图 王璺望堡垡垦! 旦坚塑塑堡堡 例3 2 ( t a n n e r 图) ：考虑如下由校验矩阵定义的线性码： x t x 2x 3x 4x sx 6x 7 f ，1 1010 0 0 、 h = 10 011010j o o ol1o 1 j 令f 2 表示二迸制域 o ，1 ) ，令x = ( 魂，娩，妁，心，坞，x t ) ，考虑函数 f ( x l ，x 2 ，妁，x 4 ，镌，x 6 ，x t ) 从霹到 o ，1 ) cr ，定义如下： f ( x l , x 2 , x 3 , x 4 , x s , x 6 , x 7 ) = 1 忙哪) = 氍如甏。0 ： 厂可被因式分解为： f ( x l ，吃，巧，心，鸭，即) = 1 五+ j r 2 + ：o ) 1 k + + 气：o ) 1 k + 毛+ 为：o 每一个l ) 为一个指示函数：如果大括号内的条件满足则取值1 ，否则取值0 。函 数厂有时也被称为码成员函数，因为其检验一个长为7 的二元组是否为疗所定义的码 的码字。舶因式图如图3 2 所示，该图被称作的t a l l n e r 图。 1 五+ 艺+ ：o 1 毛+ _ + 吒：0 图3 2 日的因式图 1 x 4 + x 5 + x 7 = 0 从上面的例子容易想到，对于线性分组码都有一个t 猢e r l 虱表示。 j 4 彤 澎 彤 澎 彤 研 3 函数边缘化及l d p c 码的译码 3 3 边缘化的迭代计算 考虑一般的函数g 的因式分解，假设其因式图为一个树( 由定义知必为二部树) 。 假设要求g 关于变量z 的边缘化：g ( 三) = z g ( z ，) 。厂般可以因式分解为下面形式： g ( z ) = 兀k 【g k ( z ) 】 ( 3 3 ) k = l 因为g l e n 式分解图为一个二部树，所以该形式有一个性质：每个因式鲰中都含有z ， 但是其它变量只出现在一个因式中。很容易说明这个性质：假设该性质不成立，则必 有另外一个变量属于两个因式，这意味着这两个因式除了通池有条路径相连，还有 另外一条路径，但是这和g 的因式图为一个二部树矛盾。 例3 1 中厂的( 3 3 ) 形式的因式分解： f ( x l ，) = 【石( j c l ，x 2 ，x 3 ) f z ( 而，x 4 ，) 兀( x 4 ) f 4 ( x 4 ，x s ) 】 该例中胙2 ，图3 3 为上述讨论的一般函数的因式分解形式，图3 4 为是具体的例3 1 的 因式分解。 眩， 歌】 g d 图3 3 一般函数的因式分解 3 函数边缘化及l d p c 码的译码 蚴】 图3 4 例3 1 的因式分解 考虑每个因式鲰( z ) 只共享一个变量，利用分布律得： kk g ( z ) = 兀 g k ( z ，) - 兀 鲰( z ，) 】( 3 4 ) zz 七= 1k = l z 简言之，z g ( z ，) 的边缘化等于聊g k ( z ，) 边缘化的乘积。对于( 3 4 ) 式， 例3 1 有： f ( x 1 ) = 石( x l ，x 2 ，妁) ( x l ，x 4 ，x 6 ) f 3 ( x a ) a ( x 4 ，x s ) 】 简单地应用分布律，将导致计算复杂度不可忽略地降低，可以利用上面的思想 对每一项g k ( z ，) ，继续递归地利用分布律来降低计算复杂度。 一般来说，每一个鲰本身也是一些因式的乘积，图3 4 中每个g 的因式框在一个 椭圆内。因为因式图是一个二部树，每一个鲰必然有如下的形式： g k ( z ) = 厅( z ，z l ，z j ) he h j ( z j ，) 】 。x 。，= l 核 ： 一 因式 其中z 只出现在“核” ( z ，z l ，z j ) 中，每一个变量z ，至多出现两次出现在“核 中，至多一次出现在某一个因式乃( 勺，) 中。所有其它变量对于每个因式来讲都是 唯一的。对于例3 1 有： 1 6 3 函数边缘化及l d p c 码的译码 五( 两，确，堍( x 4 ) f 4 ( x 4 ，x s ) = 办( 魂，x 4 ，x 6 ) 眈( x 4 ) f 4 ( x 4 ，吗) 1 k ，j 、- _ 、，_ - ，叫 核 气 上述提到的一般函数的因式分解在图3 5 中，图3 6 是特例3 1 的因式分解。 z l g k 图3 5 一般函数进一步的因式分解 进一步利用分布律得到下式： 蚴 图3 6 例3 1 的进一步因式分解 g k ( z ，) = h ( z ，z 1 ，z j ) 兀 五，( z j ，) 】 zzl = i = 三五c z 角，幻，j 矗= l 乏乃c 乃， z l z ，i 1 7 ( 3 5 ) 、百丽萄呦一虱 3 函数边缘化及l d p c 码的译码 简言之，边缘函数z 鲰( z ，) 的值等于首先计算核h ( z ，z l ，z j ) 乘上边缘函数 一h j ( z j ，) ，然后在除变量z 外所有变量上求和。 容易看出每一个因式h j ( z j ，) 与原来的函数g ( z ，) 有着同样的形式，因此我们 能将边缘函数的计算继续分解为更小的步骤。这个递归过程可一直继续，直到二部 树的叶子节点结束。边缘函数的计算与上面讨论的过程反过来，从叶子节点开始， 一步一步向上计算。下节将详细讨论这个计算过程，该计算过程被称作消息传递算 法。将边缘函数看作消息，每个节点对消息进行处理。校验节点处理消息如( 3 5 ) 式， 变量节点对于消息的处理只简单地将消息点乘。 下面讨论一下通过二部树，利用消息传递算法从叶子节点到根节点从下至上计 算边缘函数的初始化。在叶子节点，初始化非常简单，在校验节点有着一般的形式 ( z ) ，则一：g k ( z ) = ( z ) ，即校验节点的初始化传递的信息为函数本身。为了找 到变量节点初始化传递信息，考虑一个简单的例子：计算厂( 五) = 一。厂( 五，屯) ，这 里恐为叶子变量节点。由消息传递规则( 3 5 ) 有厂( 五) 的边缘化等于 。厂( 五，恐) ( 屯) ，( 恐) 为初始化时叶子变量节点而传递给核厂( 五，恐) 的信息， 容易得到该信息为常数函数l 。 3 4 消息传递算法 从上节可以看到，当一个函数对应的因式图是一个树时，通过树结构，边缘化 问题可以一步一步地分解为越来越小的计算任务。 这个特性产生了有效计算边缘函数的消息传递算法，该算法通过在树的边上传 递消息。消息是x 匕的函数，或者i x i 长度的向量。消息代表着局部边缘函数的值， 这些值联合在一起就得到了整体函数的边缘化。消息传递算法从叶子节点开始，消 息向上传递，一个节点收到了来自其孩子节点的消息后，处理这些信息，然后传递 给其双亲节点。 例3 3 ( 例3 1 中厂的消息传递算法) ：图3 7 给出了消息传递算法计算厂的边缘化的 3 函数边缘化及l d p c 码的译码 值的详细步骤。左上图表示函数的因式