（通信与信息系统专业论文）低密度奇偶校验码的译码算法及性能分析的研究.pdf

摘要摘要低密度奇偶校验( l d p c ) 码，在码长不受限的理想情况下，其校验矩阵对应的t a n n e r 图中无环( c y c l e ) 。又若假设信源满足等概率分布，则采用的置信传播( b p ) 算法迭代译码是一种最大似然译码( m l d ) ，此时它拥有近s h a n n o n 限的译码性能。而在实际应用中，在有限码长中总是有环的存在，此时应用的b p 算法只是次最优( s u b o p t i m a l ) 的算法，但它仍然展示了突出的软译码性能和线性增长的计算复杂度等优点，因此l d p c 码在未来通信系统设计信道编码时是一类重要的候选方案。l d p c 码的编码方法多种多样，其对应的b p 译码算法或其它低复杂度的译码算法要取决于l d p c 码的编码特点和性能要求。本文对中短长度的低列权重的传统l d p c 码和高列权重的有限几何( f g ) l d p c 码的译码算法进行了深入的研究。主要工作包括：对现有各种b p 算法从多种角度进行了归类总结。具体地说，从b p 算法消息传递的方式来讲，串行译码比并行译码能有效降低迭代次数。另一方面，最小和算法在牺牲一定性能的前提下，能大幅降低计算复杂度。由它派生的各种改进算法又使得在增加少量计算复杂度的代价下，很大程度上弥补了最小和译码带来的性能上的损失。各种译码算法均是围绕着寻求更好的译码性能和计算复杂度的均衡而展开的。现有的b p o s d 联合迭代算法可以取得近m l d 的译码性能，但对每个接收序列，o s d 算法要多次调用，而它的计算复杂度甚至会显著超过b p 算法的迭代一次所需的计算复杂度。本文提出了一种可以适用于b p 及最小和派生译码算法的级联框架，即b p o s d 后处理译码。其特点是o s d 算法仅在b p 算法译码失败时调用一次。类似地，b f o s d 后处理译码是通过累积b f 算法迭代过程中的比特翻转函数值来实现的。仿真表明它们能取得译码性能和计算复杂度的较好均衡。低列权重的l d p c 码在码长有限时，为弥补b p 算法性能和m l d 性能上较大的差距，提出了种基于b p 算法译码伴随式的后处理思想。它采用启发式的波束搜索( b s ) 来不断构造校验矩阵的列组合，并定义了衡量列组合与伴随式之间相似度的目标函数，在有限宽度波束的约束下，相似度高的列组合在竞争中胜出，若搜索最后阶段的列组合和伴随式完全一致的南京邮电大学博士学位论文话，则此列组合对应的码位集就是b p 算法译码错误位发生的位置，模二加就可以恢复成发送的码字。仿真表明这种方法配置灵活，可有效的改善短l d p c 码的译码性能。与传统l d p c 码相比，f g l d p c 码的校验矩阵尽管也具有稀疏的特点，但它含有较高的非零元素密度，采用传统的b p 算法译码伴随着很高的计算复杂度。为降低复杂度，减少译码时延，提出了两种改进的并行比特翻转( b f ) 译码方法。在比特翻转译码过程中，提出了一种有效降低每次迭代中误翻概率的策略。由于在算法中存在着多个参数需要优化的问题，引入的差分演化算法能有效的解决多参数优化问题。仿真结果验证了所提出的两种译码方法的有效性。进一步，比特翻转算法和最小和派生算法的组合译码结构同时突出了两个优点：最小和派生算法的译码性能；比特翻转算法的计算复杂度。系统阐述了用e x i t 图进行l d p c 码的渐近性能分析的原理。在已知变量节点和校验节点的e x i t 近似解析表达函数后，提出了用一组方程来确定译码门限的解析解。关键词：低密度奇偶校验码，置信传播译码。误比特率，比特翻转译码，外信息转移图a b s t r a c ta b s t r a c tl 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 sa r er e g a r d e da so n ec l a s so fc a p a c i t y a c h i e v i n gc o d e s ，w h e nd e c o d e du n d e rb e l i e fp r o p a g a t i o n ( b p ) a l g o r i t h m s t h eb pd e c o d i n gi se q u i v a l e n tt om a x i m u ml i k e l i h o o dd e c o d i n g ( m l d ) w h e nt h eb l o c kl e n g t ho ft h ec o d ei si n f i n i t e h o w e v e lt h eb pd e c o d i n gd e g r a d e st os u b o p t i m a ld e c o d i n gg i v e nf i n i t eb l o c kl e n g t h ，d u et ot h eu n a v o i d a b l ec y c l e si nt h et a n n e rg r a p h d e s p i t et h i s ，t h eb pd e c o d i n gs h o w si t ss u p e r i o rp e r f o r m a n c eo v e ro t h e rc o u n t e r p a r t si nt h ew a yo fs o f td e c o d i n ga n dl i n e a rc o m p l e x i t y , h e n c el d p cc o d e sh a sb e c o m eas e r i o u sc a n d i d a t ew h e nc h o o s i n gs c h e m ef o rt h ec h a n n e lc o d i n go fm o d e r nc o m m u n i c a t i o ns y s t e m s t h e r ea r em a n ym e t h o d st oc o n s t r u c tt h ep a r i t yc h e c km a t r i xo fl d p cc o d e s a c -c o r d i n g l y , t h e r ee x i s t sf r u i t f u lm e t h o d so fd e c o d i n gl d p cc o d e s ，i nt h ef o r mo fb po ri t sl o w c o m p l e x i t yv e r s i o n s o u rr e s e a r c hf o c u so ni m p r o v i n gt h ep e r f o r m a n c eo fv a r i o u sd e c o d i n ga l g o r i t h m sf o rt h el d p cc o d e so fs h o r tt om o d e r a t el e n g t h s p e c i f i c a l l y ，c o n v e n t i o n a ll o w - c o l u m n - w e i g h tl d p cc o d e sa n df i n i t eg e o m e t r y ( f g ) l d p cc o d e sa r ea m o n gt h o s eo fi n t e r e s t t h em a i nr e s e a r c hr e s u l t si n c l u d e ：s u m m a r i z et h ee x i s t i n gb pd e c o d i n ga l g o r i t h m sa n dc a t e g o r i z et h e mi n t of o u rc l a s s e s f r o mt h ep e r s p e c t i v eo fm e s s a g e p a s s i n gt i m i n g ，s e q u e n t i a ld e c o d i n gi sm o r ee f f i c i e n tt h a np a r a l l e ld e c o d i n gi nt e r m so ft h ea v e r a g ed e c o d i n gi t e r a t i o n s o nt h eo t h e rh a n d ，m i n s u md e c o d i n gc a ns i g n i f i c a n t l yr e d u c et h ec o m p l e x i t y ，a tt h ec o s to fs o m ep e r f o r m a n c ed e g r a d a t i o n h o w e v e r , m a n ym i n s u mv a r i a n t sw e r ep r o p o s e dt oe f f e c t i v e l yb r i d g es u c hp e r f o r m a n c eg a p i nan u t s h e l l ，a l ld e c o d i n gs c h e m e sa r ca i m i n gt oa c h i e v eag o o dt r a d e o f fb e t w e e np e r f o r m a n c ea n dc o m p l e x i t y t h ee x i s t i n gb p - o s di t e r a t i v ed e c o d i n gc a l la c h i e v en e a r - m l dp e r f o r m a n c e h o w e v e r , f o re a c hr e c e i v e ds e q u e n c e ，m a n yt i m e so fo s di n v o k i n g ，i m p l y i n gh i g hc o m p l e x i t y ，m a yh i n d e rt h eb p - o s dd e p l o y m e n ti np r a c t i c a la p p l i c a t i o n s t os e e kan e wt r a d e o f f , af r a m e w o r ko fo s ds c h e m ep r e c e d e dw i t ht h eb po rm i n s u mv a r i a n td e c o d i n ga l g o r i t h mi sp r o p o s e d s u c hac o n f i g u r a t i o nc a ng u a r -a n t e et h a tt h eo s di si n v o k e da tm o s to n et i m eo n l yw h e nt h eb po rm i n s u mi i i南京邮电大学博士学位论文v a r i a n tf a i l e d ，t h e r e b yf a v o r a b l yr e s u l t i n gi ns u b s t a n t i a lc o m p l e x i t yr e d u c t i o n i nt h ei m p l e m e n t a t i o no fb f o s dc a s c a d ec o n n e c t i o n ，t h eo s dp o s t p r o c e s s e st h eb ff a i l u r e s ，t h eb i tf l i p p i n gf u n c t i o nv a l u e ，o r i g i n a l l ye m p l o y e di nt h ec a s eo fb i t - f l i p p i n ga l g o r i t h m sf o rf g l d p cc o d e s ，i sa c c u m u l a t e dt om e a s u r et h ec o d e w o r db i tr e l i a b i l i t y t h i sm e a s u r e m e n te x c e l st h em a g n i t u d eo ft h er e c e i v e dv a l u e s ，i nt h es e n s et h a tm o r ed e c o d i n gs u c c e s s e sc a nb ea c h i e v e dg i v e nas m a l lo r d e r p o f t h eo s d f o rl o w - r o w w e i g h tl d p cc o d e s ，t h e i rb pd e c o d i n gp e r f o r m a n c el a g sb e h in dt h em l dd u el a r g e l yt ot h ee x i s t e n c eo fs h o r tc y c l e si nt h e i rt a n n e rg r a p h t oo v e r c o m ei t ，an e wp o s t p r o c e s s i n gs c h e m eb a s e do nt h es y n d r o m eo fb pd e c o d i n gi sp r o p o s e d t h a ti s ，i n v o k i n gah e u r i s t i cb e a ms e a r c h ( b s ) t of i n dt h eb e s tb i t ss e tw h i c h s h o w st h es a m es y n d r o m e g i v e nal i m i t e db e a mw i d t h ，t h eb i t sw h i c ha r ef i g h ti nt h ee r r o n e o u sb i tp o s i t i o n so ft h eb pd e c o d i n gf a i l u r ea r ee x p e c t e dt os u r v i v et h ee v o l u t i o ns t r a t e g yo ft h eb s l a s t l y , m o d u l o2o ft h e s eb i t sw i t ht h eb pd e c o d i n gf a i l u r er e c o v e r st h es e n tc o d e w o r d a b o v ei d e ai sj u s t i f i e di nt h es i m u l a t i o n sf o rs h o r tl d p cc o d e s c o m p a r e dw i t hc o n v e n t i o n a ll d p cc o d e s ，f g l d p cc o d e sh a v em u c hm o r en o n z e r oe l e m e n t si nt h e i rp a r i t yc h e c km a t r i x ，a l t h o u g hs p a r s es t i l l s u c hac o d es t r u c t u r ew i l li n c u rm u c hm o r ec o m p l e x i t yc o n s e q u e n t l y , w h e na d o p t i n gs t a r t d a r db pd e c o d i n g t ot h ee n do fl o w e r i n gt h ec o m p l e x i t ya n dp r o c e s s i n gd e l a y ，t w oi m p r o v e dp a r a l l e lb i t f l i p p i n gs c h e m e sa r ep r o p o s e ds e q u e n t i a l l y b o t ht a k ea d v a n t a g eo ft h ei n t u i t i o nt h a tt h eh i g h e rr e l i a b i l i t yb i t sh a v et h el o w e rp r o b a b i l i t yt ob ee r r o n e o u s ，w h i c hl e a d st ot h ep r o p o s e dd e l a y h a n d l i n gs t e p f o rt h ep r o b l e mo fm u l t i - p a r a m e t e ro p t i m i z a t i o n ，t h ed i f f e r e n t i a le v o l u t i o ns t r a t e g yi se m p l o y e dt oa c q u i r ei t sb e s ta p p r o x i m a t i o n t h ei m p r o v e dd e c o d i n gs c h e m e sa r ev e r i f i e di ne x t e n s i v es i m u l a t i o n s f u r t h e r m o r e ，a l la p p r o p r i a t ec o m b i n a t i o no fb fv a r i a n ta n dm i n s u mv a r i a n ts h o w st w oa d v a n t a g e ss i m u l t a n e o u s l y , t h a ti s ，t h es u p e r i o rd e c o d i n gp e r f o r m a n c eo ft h em i n s u mv a r i a n tp l u st h el o wc o m 。p l e x i t yo ft h eb fv a r i a n t t h es t a t eo ft h ea r ta b o u te x t r i n s i ci n f o r m a t i o nt r a n s f e r ( e x i t ) c h a r ta n a l y s i sf o rl d p cc o d e si ss u m m a r i z e d t oo b t a i nt h ea s y m p t o t i cd e c o d i n gt h r e s h o l d ，ag r o u po fe q u a t i o n sa r ed e r i v e d ，u n d e rt h ec o n d i t i o nt h a tt h ea n a l y t i c a le x p r e s s i o n so fe x i tf u n c t i o n sf o rt h ev a r i a b l ea n dc h e c kn o d e sa r ea v a i l a b l e i va b s t r a c tk e yw o r d s ：l d p cc o d e s ；b e l i e fp r o p a g a t i o nd e c o d i n g ；b i te r r o rr a t e ；b i tf l i p p i n gd e c o d i n g ；e x t r i n s i ci n f o r m a t i o nt r a n s f e rc h a r tv符号变量对照表符号变量对照表码字长度，或者对应的t a n n e r 图中的变量节点数目码字对应的校验矩阵行数，或者t a n n e r 图中的校验节点数目码字中消息位的长度编码效率，简称码率，即码字中消息位所占比例。码字的校验矩阵码字的生成矩阵高斯白噪声的单边谱密度高斯白噪声的方差t a n n e r 图中变量节点的最大次数，即列权重。t a n n e r 图中校验节点的最大次数，即行权重。t a n n e r 图中变量节点的次数分布多项式t a n n e r 图中校验节点的次数分布多项式随机变量x 的s h a n n o n 熵随机变量x 和】，之间的互信息随机变量y 关于随机变量x 的条件概率密度函数波束搜索宽度变量节点f 的邻接校验节点集合 _ i h j , 产1l变量节点f 的邻接校验节点中不含 的集合 j lh j , i = l ，_ j 1 )校验节点_ 的邻接变量节点集合 i j h f - l 校验节点歹的邻接变量节点中不含i l 集合 ih i = 1 ，i i l 由校验节点_ 发往变量节点i 的l l r 消息。由变量节点f 发往校验节点j 的u 皿消息。对于给定的校验节点_ 和变量节点f ，以及从变量节点i t ( 力f 输入的消息张。，在一f 方向输出消息为t o 0 ，1 ) 的概率对于给定的变量节点i 和校验节点已知码位f 的信道输出值y f ，以及从校验节点j l 朋( f ) 输入的消息f ，在i 一方向输出消息为u f 0 ，1 1 的概率对于变量节点f ，已知码位i 的信道输出值y f ，以及从校验节点j a 4 ( i ) 输入的消息屹，得到的用于在每次迭代后做出硬判决x i：竺象埘嚣w圳嗍砌坝如巯瞄南京邮电大学博士学位论文的后验概率s z w b f 算法中比特翻转函数中定义的常数w z w b f , l f i - w b f , l f 2 - w b f 算法中用于触发比特翻转的门限l f l w b f , l f 2 w b f 算法中延迟比特翻转的门限s z w b f 算法中比特翻转函数中定义的码位可靠性门限w z p w b f 算法中比特翻转函数定义的权重因子l f l w b f , l f 2 w b f 中得到延迟翻转变量节点集合的比例因子b w b f 算法中用于码位更新时判断可靠性的门限第，次迭代后变量节点的硬判决结果第，次迭代时的伴随式向量伴随式向量s ( f ) 的第k 个分量第i 个变量节点对应的比特翻转信号累加器当第i 个变量节点是延迟比特翻转的码位时，其对应的延迟比特翻转累加器延迟比特翻转的变量节点集合第；次迭代时，满足ik i 0 的校验节点集合满足 i ia f 口2 ) 的变量节点集合迭代译码算法的平均迭代次数迭代译码算法中，每次迭代时伴随式中的平均非零元素个数。n t - w b f 比特翻转算法中，每次迭代平均选中的翻转比特个数。并行比特翻转算法中，每次迭代中，每个比特更新平均要调用的实数加法数量。x i i叽眈凹及尾岛风砷妒够研阢t 渊f “锄k英文缩略词表a p pa g nb e rb fb pb p b a s e db p s kb sb w b fc n dd ee x i tf e rf gl d p cu rm a pm i m 0m i n s u mm l dn m so m so s dp d fs n rs o v r au m pv n dj z w b fl f l w b f英文缩略词表后验概率( ap o s t e f i o f ip r o b a b i l i t y )加性高斯白噪声( a d d i t i v ew h i t eg a u s s i a nn o i s e )误比特率( b i te r r o rr a r e )比特翻转( b i tf l i p p i n g )置信传播( 算法) ( b e l i e fp r o p a g a t i o n )基于b p 的简化算法，又称最小和算法二进制相移键控( b i n a r yp h a s es h i f tk e y i n g )波束搜索( 算法) ( b e a ms e a r c h )自举加权比特翻转( 算法) 【1 1 ( b o o t s t r a p p i n gw e i g h t e db i tf l i p p i n g )校验节点译码器( c h e c kn o d ed e c o d e r )密度演化( d e n s i t ye v o l u t i o n ) 差分演化( d i f f e r e n t i a le v o l u t i o n )外信息转移( 图) ( e x t r i n s i ci n f o r m a t i o nt r a n s f e r )误帧率( f r a m ee r r o rr a t e )有限几何( f i n i t eg e o m e t r y )低密度奇偶校验码( l o w d e n s i t yp a r i t y - c h e c kc o d e s )对数似然比( l o g l i k e l i h o o dr a t i o )最大后验概率( m a x i m u map o s t e f i o r ip r o b a b i l i t y )多输入多输出( m u l t i p l e i n p u tm u l t i p l e o u t p u t )最小和( 算法)最大似然译码( m a x i m u ml i k e l i h o o dd e c o d i n g )规范化最小和( 算法) ( n o r m a l i z e dm i n s u m )偏移最小和( 算法) ( o f f s e tm i n - s u m )排序统计译码( o r d e r e ds t a t i s t i c sd e c o d i n g )概率密度函数( p r o b a b i l i t yd e n s i t yf u n c t i o n )信噪比( s i g n a l - t o n o i s er a t i o )软输出维特比算法( s o f to u t p u tv i t e r b ia l g o r i t h m )统一有效( u n i f o r m l ym o s tp o w e r f u l )变量节点译码器( v a r i a b l en o d ed e c o d e r )j i a n g 和z h a o 等【2 】提出的加权比特翻转( 算法)论文作者和f e n g 提出的一种改进的加权比特翻转( 算法)南京邮电大学博士学位论文l f 2 w b fl z w b fl p w b fn t w b fs z w b fw z w b f论文作者和f e n g 提出的另一种改进的加权比特翻转( 算法)l i 和z h a n g t 3 1 提出的快速加权比特翻转( 算法)l i u 和p a d o s 4 1 提出的加权比特翻转( 算法)n g a t c h e d 和t a k a w i r a 等【5 】提出的加权比特翻转( 算法)s h a n 和z h a o 等 6 】提出的加权比特翻转( 算法)w u 和z h a o 等【7 1 提出的加权比特翻转( 算法)x i v关于学位论文独创性及使用授权的说明本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人享有著作权的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均己在文中以明确方式标明。本人完全了解南京邮电大学有关保留、使用学位论文的规定，即：南京邮电大学拥有在著作权法规定范围内学位论文的使用权，其中包括：( 1 ) 已获学位的研究生必须按学校规定提交学位论文，学校可以采用影印、缩印或其他复制手段保存研究生上交的学位论文；( 2 )为教学和科研目的，学校可以将公开的学位论文作为资料在图书馆、资料室等场所供校内师生阅读，或在校园网上供校内师生浏览部分内容；( 3 ) 根据中华人民共和国学位条例暂行实施办法，向国家图书馆报送可以公开的学位论文。本人保证遵守上述规定。( 保密的论文在解密后应遵守此规定)鼻、i作者签名：茎j 乏导师签名：作者签名：二r 丑2墨导师签名：日期：五兰耋1z ：3o日期：o多怃弓二一& 。l 乏第1 章绪论第1 章绪论本章首先介绍了通信系统常见的信道模型和信道编码理论的发展历程，然后在分析了l d p c 码的研究现状后，对后续章节的安排给出了必要的说明。最后给出了作者在攻读博士学位期间的研究成果。1 1通信系统数字通信系统旨在将信息或数据由信源端有效、可靠、安全地传送到信宿端。信息的传输或数据存储都可以均可作为通信系统的实例，信源有多种表现形式，如语音、数据、图像和视频等，这些信源通常含有大量的冗余信息。为了提高通信的有效性，就要对信源进行编码以最大可能去除其冗余信息，称作信源编码1 8 9 | 。信源编码能够实现数据压缩，任意给定的离散信源x 都可以用一个称熵( e n t r o p y ) 的量h ( x ) 来表征信源的平均不确定性，日( x ) = 一 ：p ( 工) l 0 9 2p ( 工) ( 比特每信源符号)j其中p ( x ) 是信源的概率。h ( x ) 是无失真数据压缩的下限。信源编码定理1 9 i 指出，在给定的保真度准则下，存在着最小数量的比特来表示独立同分布的信源输出。传输信息的信道根据传输方式或应用不同可分为固定通信信道、移动通信信道、卫星通信信道和数据存储信道等。由于通信信道中总是存在不可避免的噪声，它就会对传输信息产生干扰，降低通信的可靠性。例如，在电话通信中，干扰可能是热噪声、交换脉冲噪声或者相邻线路的串话等；而在磁盘读写过程中，其表面的暇疵以及灰尘颗粒均可看作噪声源。所以，通信系统设计的一个重要方面是在随机噪声干扰下如何有效而可靠地传输信息。在尽量避免或减少上述噪声的基础上，提高通信系统可靠性的一个主要方法就是应用信道编码，信道编码又称纠错编码( e r r o rc o r r e c t i o nc o d i n g ) 或者差错控制编码( e r r o rc o n t r o lc o d i n g ) 。同时，在无线通信等应用场合下，纠错码也是对付多径衰落对通信影响的有力手段。信道编码以特定的控制方式引入适量冗余比特来克服信息传输中受到的噪声和干扰影响。如今，在大多数现代数字通信系统和数据存储系统，为实现高度可靠数据传输和储存，信道编码已成为其一个不可或缺的一部分。南京邮电大学博士学位论文一个典型的通信系统方框图如图1 1 所示，依照惯例当我们的研究只是涉，r、，一一一一、i n f o r m a t i o n- 卜s o u r c e_ i-c h a n n e is o t i r c ee n c o d e re n c o d e ri b -m o d u l a t o ri n p u ts e q u e n c e、c h a n n e lw i t hn o i s e一一一一、tll n f o r m a t i o n一s o u r c eqc h a n n e l 一d e m o d u l a t o rs i n kd e c o d e rd e c o d e r- 、 一puts e q u e n c e一，j、n o i s 。a n ne l 。图1 1 一个典型的通信系统中信息传输和处理的框图及信道编译码时对一个通信系统的其它组成部分可以如图i i 虚线框所示加以简化，仅关心信道编译器的输入输出部分及内部实现，而对其它环节的实现不予关注。1 2 常见信道模型设计信道编、译码方案之前，必须了解传输信息的信道特性。由于噪声和干扰的存在，输入信息总是以一定的概率对应于输出信息。根据信道的特性随时间的变化关系，可将信道分为恒参信道和随参信道：按输出对输入的时间依赖关系可将信道分为无记忆信道和有记忆信道；按信道的转移概率对输入端是否有对称性可将信道分为对称信道和非对称信道。按输入输出量的性质可以分为离散信道，混合信道和连续信道。真实的信道情况往往很复杂，实际应用中要考虑其主要特点做适当简化来建立相应的信道模型。下面介绍编译码设计中经常使用的几种信道模型以及对应的信道容量i 。o _ 眩i 。1 二进制对称信道( b i n a r ys y m m e t r yc h a n n e l 。b s c )如图1 2 所示，b s c 信道有以下转移概率p ( y 1 x ) 。p ( o i o ) = l p ，p ( 11 0 ) = pp ( 1 j 1 ) = l p ，e ( 0 1 1 ) = p 2第1 章绪论可见转移概率p 是刻画b s c 信道的唯一参数。b s c 信道容量c 日s c ( j f ) ) 为9c b s c ( p ) = 1 一h 2 ( p )其中h 2 ( p ) = 一pl 0 9 2p ( 1 一p ) l 0 9 2 ( 1 一p ) 为二进制熵函数。2 二进制删除信道( b i n a r ye r a s u r ec h a n n e l ，b e c )如图1 3 所示，b e c 信道有以下条件概率p ( y i x ) 。p ( o i o ) = l p ，p ( e 1 0 ) = pp ( 1 1 1 ) = l p ，p ( e 1 1 ) = p 000图1 2 转移概率为p 的b s c 信道示图1 3意图意图0e与b s c 信道相比，p 也是刻画b e c 信道的唯一参数。不同的是，b e c 信道的输出是三元的值i o ，e ，1 ，而b s c 信道输出是二元的值i o ，l 。b e c 信道的容量c b e c ( p ) 为1 9 1c b e c ( p ) = 1 一pc 船c 和c b e c 随p 的变化关系分别如图1 4 和i 5 所示。n - - 3 见，b s c 信道t r a n sj tp o np r o b a b i l i t yt r a n s i t i o np r o d a d f lj t y图1 4c 8 s c ( p ) 的曲线图图1 5c 8 e c ( p ) 的曲线图在p = 0 5 时不能传输任何信息，而b e c 信道则随着p 单调递减。3南京邮电大学博士学位论文3 在信道编码文献中，更为常见的是二进制输* a n 性高斯白噪声信道( b i n a r yi n p u ta d d i t i v ew h i t eg a u s s i a nn o i s e ，b i a w g n ) 。它的特点是输入是码字映射后的离散符号，受到a w g n 分布的噪声干扰后，输出是满足条件高斯分布的取值于实数集r 的连续随机变量。其模型如图1 6 。b i a w g n 信道容图1 6b i a w g n 信道示意图量巳w g _ 在文献i1 3 i 有详细论述，此处不再赘述。其它重要的信道模型还包括无线通信中广泛应用的二进制瑞利衰落信道( r a y l e i g hf a d i n gc h a n n e l ) 和其它多径衰落信道以及m i m o ( m u l t i p l e i n p u tm u l t i p l e o u t p u t ) 信道等。理论上，在研究信道编码时，常假定信道是a w g n 信道，原因是：即便在复杂的多径衰落信道中，如构成码字的码元各自独立。有完善的信道估计，多径信道的影响是可以等效为a w g n 信道的。而信道估计不是本文议题。感兴趣的读者可参阅有关文献1 4 i 。1 3 信道编码的简单回顾1 9 4 8 年，s h a n n o n 在他开创性的论文中论述了著名的信道编码定理：假设一个有噪信道信道的容量为c ，信息传送率为r ，如果r c ，则不可能实现无差错通信。信道编码定理指出了信道容量是信息传输速率的最大值，但并没有说明具体的信道编译码方法。虽然随机编码能够用在证明s h a n n o n 的定理，证明了存在性，它在实践中却是行不通的，因为编码和解码的复杂性在那种情况下会随着码长的增加而迅速呈现指数增长。尽管如此，信道编码定理的提出奠定了纠错码的基石。此后人们根据香农的思想，一直致力于构造纠错能力接近理论极限，编译码复杂度在可接受范围内的信道编码。提出了一系列设计好码和有效译码的方法，使纠错码技术有了飞速的发展。纠错码主要有分组码( b l o c kc o d e s ) 和卷积码( c o n v o l u t i o n a lc o d e s ) 两大类。线性分组码是发展最早的一类纠错码。线性分组码是以代数中的群论、域论等4第1 章绪论理论为数学基础1 1 6 1 ，利用各种代数方法设计好的纠错码，比较著名的线性分组码有h a m m i n g 码1 1 7 1 ，g o l a y 码ij 8 1 ，r e e d m u l l e r 码| | 9 ，2 0 1 ，r s 码1 2 1 1 以及b c h码【2 2 l 等。其中一类重要的b c h 码又进一步演化出了扩展b c h 码、缩短b c h码等。8 0 年代以后，g o p p a 等人从几何观点讨论分析相关码字构造，利用代数曲线构造了一类代数几何码1 2 3 , 2 4 1 。使得原来线性码中的重要参数如码长、距离、维数等，具有全新的几何意义。代数几何码是一类范围非常广的码，在理论上己经证明它具有优越的性能。卷积码在编码过程中引入了寄存器来存储当前状态，从而增加了码元之间的相关性，在增加了少量复杂度的条件下可以获得比分组码更高的编码增益。随着各种卷积码的译码方法，尤其是维特比( v i t e r b i ) 译码算法1 2 5 i 的出现，卷积码逐渐得以广泛应用，而后出现的格栅编码调制( t r e l l i s ，c o d e dm o d u l a t i o n ) 技术1 2 6 l ，更加促进了卷积码的发展和应用。期间提出的许多译码思想如门限译码( t h r e s h o l dd e c o d i n g ) 、迭代译码( i t e r a t i v ed e c o d i n g ) 、软判决译码( s o f t d e c i s i o nd e c o d i n g ) 至今仍有广泛的使用。构造码长长的好码的一个自然而又有效的方法，是1 9 6 6 年由f o r n e y 提出的。利用两个短码构造长的串行级联码( c o n c a t e n a t e dc o d e s ) 的思想1 2 7 1 。它将分组码和卷积码结合起来，有关研究表明级联码的性能比单独的分组码和卷积码得到较大改善，而其译码复杂度并没有明显的增加。b e r r o u 等人在19 9 3 年提出了t u r b o 码1 2 8 1 ，它采用随机交织器( i n t e r l e a v e r ) 巧妙地将两个递归系统卷积码( r e c u r s i v es y s t e m a t i cc o n v o l u t i o n a lc o d e s ) 并行级联，实现了随机编码的思想。在译码端，它通过两个软输入软输出( s o f t i ns o f t o u t ) 软输出译码器之间的外部信息( e x t r i n s i ci n f o r m a t i o n ) 的传递来实现迭代译码，从而使得系统在低复杂度的代价下渐进性能逼近最大似然译码( m a x i m u ml i k e l i h o o dd e c o d i n g ，m l d ) 1 2 9 3 0 1 。其译码算法主要有m a p ( m a x i m u map o s t e r i o r ip r o b a b i l i t y )算法1 3 ，3 引、l o g m a p 算法1 3 3 1 、s o v a 算法( s o f t o u t p u tv i t e r b ia l g o r i t h m ) 1 3 4 , 3 5 1 等。无论是串行还是并行t u r b o 码，它的迭代译码的基本思想是将一个复杂的长的译码过程分解为多个相对简单的子迭代译码过程，在子迭代译码过程之间信息的往复传递可以确保几乎没有信息损失。由于t u r b o 码优秀的性能，使其成为当今编码界研究的热点之一。但是t u r b o 码也有一些缺点比如它的译码复杂度仍然较大，且在码长较长时，由于交织器的存在具有较大的时延。t u r b o 码的出现促进了人们对伪随机编码和迭代译码算法的研究热潮，使信道编码理论和实践进入了一个崭新的阶段1 3 6 l 。低密度奇偶校验码( 1 0 w d e n s i t yp a r i t y c h e c kc o d e s ，l d p c ) 在g a l l a g e r l 3 7 1 提5南京邮电大学博士学位论文出并沉寂三十多年后，在上世纪九十年代经过m a c k a y l 3 蝴l 等人的重新研究并加以改进，迅速成为编码界研究的热点。同时。人们在基于图模型1 4 i , 4 2 1 研究l d p c 码时。发现t u r