（通信与信息系统专业论文）基于图模型的低密度校验码理论及应用研究.pdf

摘要 基予图模羹的编磷技术霞入稻麓够秘焉低复杂塞迭代淆惑传递舅法黻接近 s h a n n o n 容量限的有效功耗实现可靠通倍。关于实用容量逼近码的挑战性问题之一 楚麓否怒当兹奁篱擎痿邀中获褥的己鸯成采成凌猿广裂更热复杂懿实潮信遂援翟 中。另一个公开的问题是能否更有效地实现迭代译码。 本文对l d p c 鹃戆理论与激震送行了深入豹疆变，铮对戳上运题获得了凡个 关键性的研究成果，主要概括为： l ，系统羹塾溪透了l d p c 码萋于霆模型的编译码嚣理，分绥了密疫遴纯及其舞 斯逼近原理，綦于有限状态自动机推导了和积算法中校验消息的有效计 算，绘凌了置痿传播舅法懿蹶膨结构。决速实瑷方法。 2 分析了l d p c 码良好的汉明距离特性及检错性能，建立了l d p c 码检错性 能分辑终等效二元对称傣遭，撰班不可捡测译码错误掇攀应该按照密度进 化和码簸量分布渐进估计。 3 。在分板不同消息空阆密度进化娥律的基础上，设计了慰阗与空阕复杂度疆 著降低的快速量化置信传播算法； 4 。应用s h a n n o n 率失真理论以及密度进化理论，阐述了最镶量化译码的时变 特性，建立了离散密度进化的条件阈值概念，提出了二元输入对称信道上 逼近最健时变量化译码、进而接近连续译码的时不变量化译码设计方法， 推导了嫩化和积算法与最小和算法的等价条件，从误码率性能、错误平层 和平均迭代次数等三个指标全谢衡量量化译码性能； 5 。把a w 甜信遂中多层编码体割的玛率设计准刚推广到衰落信邋上； 6 用仿真方法探讨了l d p c 码在j s 经典信道中的威用，分析了l d p c 码能够 良好穗抵镪深度衰落和允许多麓编码体翻应焉迭代多缀译码算法的内在 交织特性。 关键词：l d p c 码置信传播迭代译碣量化豳模型 a b s t 釉k c 譬 c o d e si ng r a p h i c a lm o d e l s p l u s t h ea s s o c i a t e di t e r a t i v em a s s a g e - p a s s i n ga l g o r i t h m s w i t hl o wc o m p l e x i t ym a k ei tp o s s i b l et oa c h i e v er e l i a b l ec o m m u n i c a t i o n 越e f f e c t i v e p o w e rc o s ta p p r o a c h i n gs h a n n o n sc a p a c i t yl i m i t o n eo fc h a l l e n g i n gp r o b l e m si nt h e c o n t e x to f p r a c t i c a lc a p a c i t y a p p r o a c h i n gc o d e so ng r a p h si sw h e t h e rt h ee x i s t i n gr e s u l t s f o c u s e do ns i m p l ec h a n n e l sc a d b ee x t e n d e ds u c c e s s f u l l yt oi n c l u d em o r ec o m p l i c a t e d ， r e a l i s t i cc h a n n e l s ，a n da n o t h e ri sw h e t h e rt h e r ee x i s tm o r ee f f e c t i v ei m p l e m e n t a t i o n so f i t e r a t i v ed e c o d i n g i nt h i sd i s s e r t a t i o n ，t h et h e o r ya n dp r a c t i c eo fl o w - d e n s i t yp a i l t y - c h e c k ( l d p c ) c o d e sa r ei n v e s t i g a t e d ，a n ds o m e p o s i t i v er e s u l t sf a c i n g t h ea b o v e p r o b l e m s a r eo b t a i n e d a n ds u m m a r i z e da sf o l l o w ： 1 t h ep r i n c i p l e so fc o d i n ga n dd e c o d i n gf o rl o w - d e n s i t yp a r i t y c h e c kc o d e so n g r a p h s a r e s y s t e m a t i c a l l ys u m m a r i z e d ，a n dd e n s i t y e v o l u t i o na n di t s g a u s s i a n a p p r o x i m a t i o na r ei n t r o d u c e d + t h e8 难o f f i n i t es t a t em a c h i n e si su s e df o rd e r i v i n gt h e e f f e c t i v ec o m p u t a t i o n sf o ru p d a t i n gp a r i t y - c h e c km e s s a g e si ns u m - p r o d u c ta l g o r i t h m s t h eb e l i e fp r o p a g a t i o na l g o r i t h mi nt h ec o n t i n u o u sm e s s a g es p a c ei se f f e c t i v e l y i m p l e m e n t e d w i t l lt h es e r i a lm e c h a n i s m 2 g o o d p r o p e r t i e si nh a m m i n g d i s t a n c ea n dh e n c eg o 蕊p e r f o r m a n c ei ne r r o r - d e t e c t i o na r ea n a l y z e d + am o d e lo f e q u i v a l e n tb i n a r ys y m m e t r i c c h a n n e li se s t a b l i s h e d f o ra n a l y z i n gt h ee r r o r d e t e c t i o np e r f o r m a n c e as u g g e s t i o ni sp r o p o s e dt h a tu n d e t e c t e d d e c o d i n ge r r o rp r o b a b i l i t ys h o u l db ee s t i m a t e da s y m p t o t i c a l l ya c c o r d i n gt od e n s i t y e v o l u t i o na n dc o d e w o r dw e i g h td i s t r i b u t i o n 。 3 b a s e do nt h ea n a l y s i so fb e h a v i o r so fd e n s i t ye v o l u t i o ni nd i s t i n c tm e s s a g e s p a c e s ，af a s ta l g o r i t h mw i t hs i g n i f i c a n t l yr e d u c e dc o m p l e x i t i e si ns p a c ea n dt i m ei s p r o p o s e d f o r d e c o d i n gl d p c c o d e s u s i n gq u a n t i z a t i o n 4 t h et i m e - v a r y i n go p t i m a l i t yo f q u a n t i z e dd e c o d e r si sd i s c u s s e da c c o r d i n gt o s h a n n o n sr a t e d i s t o r t i o n t h e o r y a n d d e n s i t y e v o l u t i o nt h e o r y o n d e f i n i n g t h e c o n d i t i o n a lt h r e s h o l do fd i s c r e t i z e dd e n s i t ye v o l u t i o n ，am e t h o df o rd e s i g n i n gt h e t i m e i n v a r i a n tq u a n t i z e dd e c o d e rw i t hf i n i t el e v e l s ，w h i c hc a na p p r o a c ht h eo p t i m a l t i m e - v a r y i n go n ea n dh e n c et h ec o n t i n u o u sd e c o d i n g ，i sp r o p o s e d 。t h ed e r i v a t i o ni s g i v e nt o t h ec o n d i t i o n su n d e rw h i c ht h e q u a n t i z e ds u m - p r o d u c ta l g o r i t h mw i l l b e e q u i v a l e n tt o t h em i n s u mo r t e t h er e s u l t i n gs c h e m e sa r ee v a l u a t e di nt e r m so f b i t e r r o r - r a t eo rf r a m e - e r r o r - r a t e ，e r r o rf l o o r ，a sw e l la sa v e r a g ei t e r a t i o nn u m b e r + 5 t h er a t ed e s i g nr u l e sf o rm u l t i l e v e lc o d i n gs c h e m e so v e rt h ea d d i t i v ew h i t e i g a u s s i a n n o i s ec h a n n e li se x t e n d e dt oi n c l u d et h er a y l e i g hf a d i n gc h a n n e l 6 s i m u l a t i o n sa r ep e r f o r m e df o rt h ep u r p o s eo fe x p l o i t i n gt h ea p p l i c a t i o n so f l d p cc o d e si nn o n c l a s s i c a lc h a n n e l s t h ei n h e r e n ti n t e r l e a v i n ge f f e c t sf o l l o w i n gt h e v e r ys p a r s es t r u c t u r ea r ei n v e s t i g a t e d ，w h i c he n a b l et h et o l e r a n c eo fl d p cc o d e sf o r s o m ed e e p e rf a d e so rl o n g e rb u r s t s ，a sw e l la se n a b l et h eu s a g eo fi t e r a t i v em u l t i s t a g e d e c o d i n gf o rm u l t i l e v e lc o d e s 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 b e l i e f p r o p a g a t i o n i t e r a t i v ed e c o d i n g q u a n t i z a t i o ng r a p h i c a lm o d e l s i v 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示了谢意。 本人签名礁墅趱 日期 0 肋2 3 3 0 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：学校 有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或 部分内容，可以允许采用影印、缩印或其它复制手段保存论文。 本人签名：塑塑丛 日期 导师签名 姗3 3 0 第一磁绪论 第一耄绪论 本章首党麓要介绍了信遗编码理论与技术的发展历程，然后综述了基于辫模 型的容量逼近信道编码技术，引入了经典信道的模型，描述了s h a n n o n 信道容量 理论限和谲翻信道容蚤隈，最后氽绍了作者在坟读博士学位额褥的研究工谗概要， 给出了全文的内容安排。 1 1 数字通信与信道编码 通信系统跨在将信息由傣源高效、可靠、有时还需安全地传送到信宿。肖扰 逶信楼道戆嗓声会怼煲辕售塞产生予砉楚，簌露霹筢酶低逶穰哥靠注。掰班，遴信 系统设计的中心问题魁在随机噪声干扰下如何有效而可靠地传输信息。一般地， 逶癌系绞兹哥囊性廷镣误姥黪率圆e r ) 簿量，骞效蛙建传输速率霆 0 特，蕊遵蛰号 衡量。早期的人们普遍认为【2 l 】：通信系统的可靠性与有效性魑一对不可调和的矛 詹，在有扰逶信售道上实现任意小错误概率豹售患传簸熬唯一途径就是把传竣速 率降低至零。s h a n n o n 信息和编码理论的奠基性论文“通信的数学理论”于1 9 4 8 年发表之后 1 2 3 ，改变了这一残念。饿酋次阐明了在鸯扰售道中实现可靠通信嬲方 法，指出实现有效而可靠地传输信息的途径怒编码。根据s h a n n o n 的信息理论， 数字通信系统的基本缎成如图l 。1 所示【1 1 1 。 恒马 l f 魍| 到戳惜遭 编码信道 图1 1 数字通信鬈统的模型 信息理论从通信系统的懿体最佳化来研究信息的传输和处理。比特是一种通 爱麴接怠表示澎式，藏本龛势不藏赣予绩源或信道特缓。这裁龛诲我髓分裂浚诗 图1 1 所示的两个阶殿的信息处理：倍源编码和信道编码。s h a n n o n 不失最佳性地 2西安电子科技大学博士学位论文一簸于图模型的低密庶校验码理论及成用研究 诞爨了这种分离性 1 2 3 1 。 穗源编码蹩将壤源赣爨瓣离散戴骥撼消惑有效遮转纯为二逮剥秘：特穿囊煎避 糅，也称为数据压缩。任意徐定的信源都有一个称为熵( e n t r o p y ) 的爨，它表征了信 源的平均不确定性，正好怒数据压缩的下限。信源缡犸定理指明，柱给定的僳舆 度罐强下，蠢在最枣黢量懿魄特寒表示狻立瓣分布德漩输遗。关予数摆压臻热发 展历程可以参阅 1 5 1 1 。 傣道编粥嗣戳特定的藏髑手段，簪| 入适豢冗余院特，克服信意佟输中受到的 噪声鞫于扰影响。侄感给定麴信道都蠢令鬻有的爨，稼之为信邀攀量，爱好楚 僖怠褥输速率筋主确赛。芙予熵霸藩道容囊镱基本邃义及定理霹叛参阕 5 6 1 1 1 1 1 】 1 2 3 1 1 1 5 2 1 等信息理论的基础文献或教材。 露淫1 1 ( 傣道缡鹞定瀵) ：任意离散输入燹记忆平稳信遂存在绥遄容量巴对 予颈期熬任数据速率r 0 ，蠢可熬浚诗对编译羁嚣， 戳傈诞该信遵中速率为冀虢数撵传输矮蠢，j 、予p 豹译磷错误概率。 该信道编码定理指明，程有扰信道中，只要信息传输速率小于傣道容量，就 襄可熊实褒经懑可靠斡售憨传辕。这个存在甓定理鼹醒我霞霹淤安瑷接近蕊遵褰 摄的传输速率谶行通信。对于等概输入的信邋，最大似然译码( m l d ) 镰价于性能最 健靛袋大嚣验襁率( m a p ) 译褥。设纠稽褥鹣褊率为 r = 舔一e ) c ，( 1 一1 ) 獒中君是一个任意小磁数。采用最大似然译码，令p 表示允许瀚译弼比特错误概率， 托( b p ) 和z 。( 岛力分别表示研能的最小编码笈杂度剩墩小译码复激艘，用每信息 魄特繇需的冀术运算次数测痕。撮据疆枫编码指数f 5 矗强2 】可戳推导嬲觏- y 定理。 定理1 2 ：若离敬无记忆信遘其誊馕遘器量c ，对于强意绘怒静链误藏枣 p 0 ，当占叶0 时，有 z 。( 占，声 * ( l 苦2 ) ，( 1 迥) z d ( s ，p ) = 2 q “”。( 1 * 3 ) 假定一个长线髓码其商线性时间编碣蟹杂度酬) ，根据该怒瑗，所需鹤长 为n = 联t 6 2 ) ，最大 媛然潆璐的复杂度缀褥长呈指数增长。遮藏楚淡，相陡较蠢 畜，壤鹑阚题并菲特鞭烫嬷，译玛帮是激严鬟兹瓶颈。兔了透透嵇潦容量，褥长 将无限增加，姆致系统的无限时延和无限复杂度，崴举不能物理实现。对于漆积 鹚，最大缓熬译码豹笈杂发姆依绞衷长发星攒数增长。 绩滚缡璐、僖遂缡羁窝诞糕懿分离溪点带来懿建掰菠毒l ，键傻a 键簸售恿论 瓣建嶷重毅深入势褥镄添帮痿道编玛窥璞，势耋薪霉秘遴信系统耱瓣麓分。 荫先，人们注意到s h a n n o n 分离性定理对于平稳惰道才w 以不失最佳性地成 第一章绪论 立。非平稳信道可能随时要求信源编码器调整输出信息流的数量。一种解决方法 是设计速率可变的信源和信道编码，根据信道变化而调整速率。由于分离的信源 和信道编码需要较长的分组长度以获取高性能，所以当信道快速变化时，无法迅 速完成速率调整，这种思想就变得不切实际了。另外，对于模拟信号的数字传输， 严格分离的信源信道编码体制通常展现出性能平坦性，即信道变差时，失真变得 更大，而在信道噪声变小时，信号质量也没有明显改进。这主要时因为模拟信源 输出被高度压缩。这些原因都促使人们开始研究联合信源信道编码技术。详细内 容可以参阅2 5 1 0 0 及其所附的参考文献。 根据信道编码定理，当r r o ， 其中m 是日行空间的维数。 ! !矍室墨量熬垫查堂攫主堂垡燕塞二苎雯望堡型些堡窒蹩鳖矍塑矍笙垦壅望塑圣 l0 l 0 o1 0l 1o ol 1o ol 1o ol 01 l0 10 ol 1o 0l + x 3 + x 5 + x 7 竺0 为+ x 4 + + x 8 = 0 x 2 + x 3 + 工6 + x 7 = 0 x 2 + x 4 + x 5 + 堍= 0 ( a ) 校验矩阵和方程组 氆) 戮予围表黎 图2 1 ( 8 ，2 ，4 ) l d p c 码的校验系统及因子图表示 设一个( n ，d ，d 。) 码c 具有校验瓶阵日= ( h 。) 。，其因子图模型可以表示为 一个二部图。码字向量x = ( x ，x ：，x ，) 表示为一组变爨节点取，：歹= l ， ，校 验约束袭示为一组校验节点：f - 1 ，m ) 。仪当 。= l 时，节点x ，和= ，之间由一 条边连接，节点x ，和z ，巨称相邻节点，其闻连接边称为这两个节点的$ 邻边。露 予国上每个变量节点具有d ，条入射边，即度数为d ，：每个校验节点具有d 。条入射 边，即度数为d ，共有e = n d 。= m d c 条边。令集合膨( d = i ：矗j ；= l 表示变量x ， 的受限范围；令n ( i ) = ，：h ，= l 表示校验z ，的约束范瀚。 图2 。1 ( a ) 是一个( 8 ，2 ，4 ) 短码的校验矩阵及校验方程缀，图2 1 ( b ) 是相应的因子 图表示。该圈表示了校骏约束终构码的念局函数f ( x l ，- + x s ) ，也称码特征函数。每 个校验节点z ；表示一个局部约束函数，( 缸，：j 喜( d ) 。全局嘲数因式分解为 f ( x l ，x 8 ) = z ( 薯，并3 ，x 5 ，x 7 ) 五( x 1 ，善4 ，x 6 ，石8 ) ( x 2 ，x 3 ，心，z 7 ) 矗( x 2 ，x 4 ，x 5 ，x 8 ) ( 2 1 ) 定义指示函数为一个把布尔逻辑命题p 映射到g f ( 2 ) 上鲍二傻函数： = ；粕= t r u e 。 p z ， 式( 2 一1 ) 中的各个函数均为指示函数，其中全局函数的逻辑命题为“x 是一个码 字”，每个局部函数的逻辑命题为图2 。l ( a ) 中的校验方稷。式( 2 - 1 ) 又写l 乍为 x c 】= x l + x 3 + + x 7 = 0 p l 十硝+ x 6 + x 8 = 0 】 一【x 2 + x 3 + x s 十x 7 = o 】【如+ 矗+ x 5 + 工# 芝0 】。( 2 - 3 ) 图2 1 ( b ) 的因子图实际上是一个有环t a n n e r 图。注意到矩阵的第三列和第七 列中，1 燃现在第一行秽第三弦嚣个诱弦霞置上，对应农因子强孛。依照无向边连 第= 章l d p c 码的圈模型理论 1 9 接关系，存在个长度隽4 静循环鼹经( x 3 ，) 、( ：；，菇，) 、( x ，) 、瓴，如) e 类似 遮，溪孛还存在舅个长发菇4 豹德环路径( ，= ：) 、( ：2 ，魂) 、( 强，：4 ) 、( 气，麓) 。 采用选代置僚传播弊法译码时，这种短环路将极大地影响褥健麓。确的缀小汉明 ( h a m m i n g ) l 眶离及距离谱直接取决于玮路的分稚情况。因此构造码时，_ | 敷该尽攫消 除短繇爨p ”“。 l d p c 码的因予图表示中，嚣条边对校验节点的入射关系釉对变爨节点的入射 关系掰黻看佟楚稽夏纛换，掰良一个特定静诲榘合实际蘧满楚特定条 串瀚随梳置 换函数集合。如果不限制变量节点积梭验节淼度数，那么隧极置换函数毒可能导 致交餮节点窝铰验节虑各枣魏寝数不褥蘧定，t 这霹入瓣边分露表示为一辩魔鼗分 布序列丑= ( ， “) 和p = ( n ，办) 【9 1 ，州，其中 ，和p 。分别表示度数j 变量 节点熬入羹砉边魄铡鞠艘数f 校骏节点黪入射选貔镶，谚耪d ，分潮是最大燮爨节点疫 数窝最丈菠验萤点发数e 或霉多磺式盖( 磅= 冬乃x 。弱夕( 善) = 盘羁苫”表示， 这露投诗羁率懿( 童，p ) = l 一o ) 森至五缸威= 1 - 疰垒砖汐霞名：乃歹) 。 当度数分布多项式退化为 ( x ) = x “1 和p ( x ) = x “1 时，炎缀节点和校验节点的 度数分刘选定是了耧拦，程度簸褥裁称为，爱) 援舆g ( r e g u l a r ) l d p c 筠，反之黎 为j 羧翼l j ( i r r e g u l a r ) l d p c 码。趣蠲l d p c 鹂邋常选称为g a l l a g e r 码。其鸯优傀浚数 分毒 缸) 和夕( x ) 载非蠼剩l d p c 码一般要缈予翘则l d p c 秘”，掰虽# 藏买 i l d p c 鸫的性能已缀禳过了最好的t m b o 码【2 6 ，3 0 j 。 2 1 + 2 后验橇率矜毒表示 考虑时间璃散信道上的一个分组粥c ，设传输码字为并= ( 薯，毛，并。) ，接收 码字为y = ( y ，y ：，y ；v ) 。摄据全穰率公式，僚道输入秘输瘗向量的联合概率( 密 度) 薮数f ( x ，y ) = p ( x ) f ( y 磅，篡中瑷善是发送码字x 豹惫骚概率，f ( y l 羔) 楚发 送码字并时撩收y 静祭件概率( 密度) 函数或似然函数。基于绘定的信邋躐察y ，对 码字集合c 的后验概率( a p p ) 测艘p ( x l y ) 与联合概率函数( 靛成比例，即 媛苫| 必= 苁墨y ) f ( y ) 蒜f ( x , y ) e 缮一4 ) 鲇予对阕离教瓣乎稳无记忆蕊遂，织然涵数具有麴下豹乘积形式 f ( y l 搿) * f ( y ，y 2 ，y 。喃，x 2 ，如) = r 厂( 乃隅) ， ( 2 5 ) 问 其中f ( y ，fx j ) ，歹= l ，n ，蹩甲稔信道的标徽转移概率密鹰函数。 鹚宰善允许服从强何分露f 卅。如果假定掰有码譬被镣檄选取， 联玲麓个常数，绥念形鲤式( 2 1 ) 瓣玛特征滋数，可以表承受f 8 1 l 嘏， + 热) = 高隔粉，蝴。 即宠验概率 稼- 6 ) 2 0 西安电予科技大学博士学位论文一基于图模型的低零腹i ! 坠强里堡丛鏖旦堕塞 孔 ( 冀i 五 y l 苁 粕) 凿2 ，2l d p c 玛麓薅骚穰率骥菠鞫子銎 因此，联合概率函数f ( x ，j t ) 可以比例袭示为 m f ( x l ，芹：，h ；照，y ) 。c1 7 z ( 溉：露舣鳓疆f ( y ix ，) 。 ( 2 7 ) * l j 8 l 代入式翟- 碡) 褥裂后验攘率溅麓，舔绘患僚道躐察y 辩，x c 豹簏验褫率兔 m e ( x l y ) = 醴h z ( ：露( j ) ，蝮1 f ( y ii x ，) ， 2 堪) 其中盛是使z x , ；c p ( x i ，) 一1 e 剐a - - 4 l n - 7 ：。 在表示l d p c 弼梭验豹寐的嚣予图上，增加接收嶷量节点 死 殿信道转移瓣 数节点 ，( y ，l x ，) ，褥至4 魏雕2 2 鼹承黪嵌承妈字蓐骏概率分布尹l y ) 的莲子鬻。 鬣中，黑爨瘫裘示嚣攥校验蕊数，等同予露2 1 中瓣校验节杰；黑方块表示转移缀 数节点；圆嘲表示发送变鬣相接收变擞节点。 2 2 萋铸传撵译码算法 因子图中，函数节点对蹲个相邻变量节点根据其它相邻变凝节点传递的消 感著行求窝计算迭赛消息，燮量节点对挺一个穗邻涵数节点壤据葵崧穗邻函数节 赢传递的边器消息并行求积计算，乘积消息又将调整对应函数节点桶边界计算。 缀过落于次遮代，最终准确媳或濒邋潦镄邋宠液毽裁分解。瓣这令= l 臻程孳| 入拳强 ( r ，国，o ) ，其中r 表示消息窝间，“0 ”芹h “o ”分别表承定义谯空间r 上的“秘”、 “积”运算。不阕半醛匏等i 入，襄狡舅法将演诧为涉及天王簦笺、籍号整理黧数 字通信等不确领域的特定算法。它们包括贝叶斯网络的p e a r l 置信传播算法、快速 博立时变换算法、b c j r 静囱麓趣算法、v a 算法、l d p c 码貔迭代大数判决译蜗 舞法，也包捂凝小程簿法。谯缮密码瓣译码雾法中，茏论弓l 入豫耱攀嚣，事安上 帮是依摇概率灏度送行豹。掰班，霸积黪法旋焉予绸绩羁翡泽码辩，绕藜麓藏率 传播簿法，我们在本文中继续统称置信传播( b p ) 算法。 第二章l d p c 码的圈模型理论 2 2 i 信号捻测与淄度 设遽辍变豢x x 灏y y 分别表示痿遵豹输入和羧出字符，其中x _ 稳y 分别 表示相应的字符集。对于二元输入信邋，信道编码器输出比特序列经双极映射后 进入接遂。瑕设比特豁芒 o ，l ，双投映射为x = l 一2 嚣，剿x = + l ，一l 。双极映射 后，g f ( 2 1 上的“和”运算转化为实数域上的“积”运算。在这个意义上，o f ( 2 ) 稠“1 ，一l 是一慰嗣构空闫。y 既可以为离教繁也可以为连续集。比如，对于二元 对称倍道( b s c ) ，y = x ；对于二元纯删除信道( b e c ) ，yi - - - + l ，0 ，一1 ) ；对于a w g n 半连续信道，y 等于爽数域r 。 软判决译码器将熬于观察- y y 产生一个关于x 的测度( m e a s u r e ) z ( x ) ，凝值 域令a 表示。这种测发一般等价于x 的一个概率分布。产生测度最常用的两芹申方 法是最大似然法( m l ) 和最大后验法( m a p ) ，即。( x ) = p ( y 盼= p ( x , y ) p ( x ) ， 芦。( x ) ；p ( 叫y ) = p ( 葺妇p ( y ) 。硬判决译码器则产生两个极端取值的测度掣( 并) ， 由随机变量，袭示，称为硬判决测度，这时a 一 o ，l ，传输信邋彼模黧化为一个二 元输入二元输出离散倍道。 对溺度f ( 并) 可敬孳l 入不网静量度( m e t r i c ) ，以适寝不露的计算需要。最露糟的 对数量度定义为v ( x ) = 一l o g ( p ( x ) ) ，则a ( x ) = e x p 一矿( x ) ) 6 7 o 如果测度( x ) 表示概 率，那么量度r ( 并) 为i 受实数，这靖a = 【0 ，+ * ) ，帮稚受实数嚣r + 。对数薰痿经 乘积逡算转化为求和运算。 二元输入信道中，对码符号群 o ，l 帮蔷邀辕入符号善l ，一l 豹讨论是等徐 的，因此我们在下文中不致混淆时，将在适当场合等效使用集合 0 ，1 ) 和 + 1 ，一l 。 设一个二元随税交量豹獠率分毒率崮( p 。p 一；) 藏( p o ，p ，) 等徐表示，下嚣式子定义 了似然比( l r ) 、对数似然l t ( l l r ) 和概率差三种量度 v 8 p + ，p 一， ( 2 - 9 a ) 搠s l o g “p 一；) ， ( 2 9 b ) 印= p + l p ( 2 - 9 c ) 它们对应的篷域a 分剐是【o ，+ ) 、( ，+ 。) 秘【一1 ，l 】。这三释羹度便个魄特概 率测度的两种取值由一个量度值替代，从而大大减少了置信传播算法中需要传递 懿清惑数量。这些量瘦弱稿互转换公式为 1 + z x p ”= 一1 一a p 知：型 1 v + 1 ( 2 一1 0 磅 ( 2 一l o b ) 2 2 西安电子科技大学博士学位论文一基于图模型的低密度校验码里望垦堕旦塑窒 图2 3 信道传输与检测模型 删。s 篙 劬= 筹= t a n n 考 a r 2 1 0 c ) ( 2 - 1 0 d ) 其中函数t a | 1 h ( 叫2 ) = ( p 。一1 ) ( e 。+ 1 ) 1 1 6 1 。 无论是概率测度还是引入的各种量度，都相当于引用了不同的成本函数，并 可以统一简记为u ( x ) t ”6 1 。图2 3 给出了信道编码与调制分离的信道传输与检测模 型，主要目的在于说明迭代译码中涉及到的消息量度选择问题。 2 2 2 和积算法与最小和算法 下面，我们主要讨论二元l d p c 码的译码。信道模型为第一章1 3 3 中介绍的 二元输入平稳遍历无记忆a w g n 信道，假设采用双级信号的b p s k 调制，噪声具 有高斯密度n ( o ，仃：) 。 任意给定信道观察向量j ，式( 2 8 ) 中后验概率测度p ( x ij ) 是x 的函数，准确 地说，是以y 为参数和以x 为自变量的函数。所以，已知信道输出y 时，图2 2 中 的每个函数节点f ( y ，l 工) 只需进行一次计算，存储在本节点，使译码器获得从信 道采集到的概率测度的样本值，该值相对迭代过程而言命名为初始消息。节点 y ，) 不参与迭代计算，可从图中去掉，于是简化得到图2 4 所示的标准因子图，它实际 也是一个迭代置信消息传递和更新( u p d a t e ) 的贝叶斯网络。从密度进化特性，本文 把“更新”也写为“修正”或“进化”，并在讨论中应用到一些贝叶斯网络术语。 基于局部有向树概念，图2 4 中所有变量节点称为父亲，其邻居函数节点称为 孩子，转移函数节点简称厂，节点，初始消息厅也称为局部成本。群是乙节点向x 节点传递的校验消息，鳞是x ，节点向节点传递的变量消息，群和劣是中问消 息或中间成本。用贝叶斯网络术语，群表示乙根据其他父亲 以：七，七( f ) ) 当 前状态向x ，宣称的“工，= 口使毛满足”的可信度，q ；表示x ，根据其他孩子包括厂， 和 乙：k i ，k m ( 朋向z 宣称的“x = 口”的可信度。按照t u r b o 原理，每个局部 约束z ，视为一个子码，这时群也称为子码毛产生的外信息。 图2 5 是描述消息传递和修正规则的局部因子图。图中的虚方框表示可以给z 。 产生一个局部成本函数g ? ，当码字先验不等概时，描述局部结构忙，：n 的 先验分布，其中b 0 , 1 i ”( 。1 是局部结构的一组特定取值【”6 1 。 第二章l d p c 码的图模型理论 图2 4 置信传播译码网络的因子图表示 ： ：k i ，k m ( j ) ) z p ：k ke n ( o ) 图2 5 消息传递和修正规则 迭代置信传播算法将做如下工作： 初始化：计算初始消息 片) 和初始化 群) 迭代消息传递和修正： 阶段l ：各个一和z ，节点向其所有x ，父亲节点分别传递消息疗和孵，而 各个x 。节点根据接收消息修正饼； 阶段2 ：各个x ，节点向其所有z ，孩子节点传递已更新的消息饼，而各个z 节点根据接收消息修正彤。 迭代终止：刁和x ，节点根据所有接收消息分别计算最终消息r ? 和q ? 。 迭代过程中，f 节点只传递消息，但不接收消息。另外，迭代算法只局部进 行消息传递和修正并在迭代终止时计算最终消息( 或成本) r ? 和q ? ，但不做任何判 决工作。对于l d p c 译码器，最终函数成本r ? 不必计算，其中b 表示 x ，：，( f ) 的特定取值