（基础数学专业论文）ra码在bsc信道下的有限长分析.pdf

摘要 重复积累码( r e p e a t a c c u m u l a t ec o d e s ，简称r a 码) 具有性能接近香农 限、收敛速度快、编译码复杂度低的特点，适合应用于各种实际通信系统，是近 年来信道纠错编码领域的研究热点。新近出现的有限长度量准则是一种能够较准 确地估计码型在有限帧长情况下性能的一种数学分析工具。本文利用有限长度量 准则，对r a 码在b s c 信道下的有限长性能进行了分析，主要工作如下： 1 、计算r a 码在b s c 信道下的有限长度量准则形式及其度量参数； 2 、利用该度量准则对( 3 ，3 ) r a 码进行有限长分析，估计其误帧率； 3 、通过仿真曲线验证该估计算法的精确性。 关键词：重复积累码；二进制对称信道；门限值；有限长度量准则 a b s t r a c t a sac l a s so fc a p a c i t y - a d l i 嘶n ge n s e i ：【l _ b l e s ，r e p e a t a c c i m m l a t ec o d e s ( r ac o d 铭) a r ew i d e l yu s e di l l 肌m e r o u sp r a c t i c a la p p l i c a t i o i l sd u et 0n l e i rf 奴c o n v e r g e l l c ea i l d l o wc 0 m p l e x 时i l le i l c o d i n ga i l dd e c o d i n g t h e yn l _ 璐b e c o m em ef o c a lp o i n to f e 盯o r - c o r r e c t i n gc o d e f i l l i t e - l e n g t l ls c a l i n gl a wi sap o w e r f u 1t o o lt 0a 砌y s em ep 耐o 册a n c eo fm o d e r a t e s i z ec 印a c i 妒a c h i e v i n ge l l s e n l b l e sw i mi t e r a t i v ed e c o d i l l g h l l i st l l e s i s ，w eu s es u c h s c a l i n gla _ wt o 锄a l y s em ep e r f i o m l a i l c eo f 缸i l i t e 1 e 1 1 9 t 1 1r ac o d e s ，a s 舳g 也a tm e n 硼s m i s s i o nt a l ( e sp l a c e0 v e rt 1 1 eb s c ( b i l l a 巧s y 玎咖e t r i cc h a l l i l e l ) a n db e l i e f p r o p a g a t i o nd e c o d i n gi su s e dw i la6 n i t e 瑚m l b e r o fi t e r a t i o n s t h em a i l lc o n t e n t sa r ea sf o l l o w s f i r s t l y ，w es h o wh o wt 0r e - d e r i v em es c a l i n gl a wa 1 1 ds c a l i i l gp a r 锄酏e rf o rr a c o d e s 仃a 1 1 s m i 钍e do v e rt 1 1 eb s c s e c o n d l y ，w ed e m o n s t r a t eh o wt ou s et 1 1 es c a l i n gl a wa sa i le s t i m a t et 0 0 1f 0 r ( 3 ，3 ) r ac o d e s f i n a l l y ，w ec o m p a r e 廿1 ep r e d i c t i v er e s u l t so nt l l e 丘锄ee r r o rp r o b a b i l i t ) rw i m s i m u l a t i o nr e s u l t st os h o wt l l a tb o mo ft 1 1 锄m a tc _ hv e 巧w e l l k e y w o r d s ：r 印e a t - a c c l l m l l l a t ec o d e s ；b i n a 巧s y n l i i l e t r i cc h a l l n e l ； 缸e s h o l d ； f i n i t e - l e n g t l ls c a l i n gl a w 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研究成 果。本人在论文写作中参考其他个人或集体已经发表的研究成果，均 在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学 术活动规范( 试行) 。 另外，该学位论文为() 课题( 组) 的研究成果，获得() 课题( 组) 经费或实验室的 资助，在() 实验室完成。( 请在以上括号内填写课 题或课题组负责人或实验室名称，未有此项声明内容的，可以不作特 别声明。) 声明人( 签名) ：做客事 年月日 厦门大学学位论文著作权使用声明 本人同意厦门大学根据中华人民共和国学位条例暂行实施办 法等规定保留和使用此学位论文，并向主管部门或其指定机构送交 学位论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书 馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国 博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和 摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于： () 1 经厦门大学保密委员会审查核定的保密学位论文， 于年 月日解密，解密后适用上述授权。 () 2 不保密，适用上述授权。 ( 请在以上相应括号内打“”或填上相应内容。保密学位论文 应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密 委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认 为公开学位论文，均适用上述授权。) r a 码在b s c 信道下的有限长分析 1 1 论文的研究背景 第一章绪论 1 9 9 3 年，瑞士日内瓦召开的国际通信会议上，法国不列颠通信大学的 c b e r r o u ，a g l a v i e u x 和p t h i t i 腿j s h i w a 首次提出一种称之为t u r b o 码的 编、译码方案。方案中，t u r b o 码是由两个递归循环卷积码( r s c ) 通过交织器 以并行级联的方式结合生成的。这种方案采用反馈迭代译码方式，真正发掘了级 联码的潜力，并以其类似于随机的编译码方式，突破了最小距离的短码设计思想， 使t u r b o 码更加逼近了理想的随机码的性能。 1 9 9 8 年，d d i v s a l a r ，h j i n 和r m c e l i e c e 等人发现了一类特殊的t u r b o 码重复积累码2 3 ( r e p e a t a c c u 舢l a t ec o d e s ，简称r a 码) 。从编码角度看， r a 码与t u r b o 码相同，都是采用迭代译码技术的级联( 并联或串联) 码；就构造 与译码而言，r a 码与l d p c 码口1 类似，能够用t a n n e r 图表示，通过节点度分布 函数定义码的结构，可采用基于t a n n e r 图的和积迭代译码算法。从这两个方面 来讲，r a 码实际上就是t u r b o 码与l d p c 码的共同子集，因而它承袭了t u r b o 码 与l d p c 码的所有优点具有线性时间编码和线性时间译码的特点，并且性能 接近香农限，因此r a 码成了近年来的研究热点。 目前，r a 码的研究主要集中在编译码技术和分析设计两个方面。而分析设 计中的性能分析方法又可以分为两大类，一类是通过蒙特卡罗仿真对r a 码的误 帧率( f r 锄ee r r o rr a t e ) 或误比特率( b i te r r o rr a t e ) 直接进行评测，另一类 是从理论上对其性能进行估计( 如估计误帧率或误比特率，或者计算码型最小汉 明距离等) 。第一类的精确度要比第二类高，但随着帧长的增加其复杂度也逐渐 增大，特别是在中长帧长情况下，一条误帧率( 或误比特率) 曲线的仿真耗时就要 以天来计算。较之而言，第二类方法则用精确度的一点点牺牲换来复杂度的大大 降低。近年，学者们发现a m o n t a n a r i 提出的一个有限长分析方法1 ( f i n i t e l e n g t ha n a l y s i s ) 对有限长( 即帧长有限) 的r a 码来说是一个极有价 值的理论分析方法凹3 。下面我们来看一下有限长分析的发展。 i 认码在b s c 信道下的有限长分析 1 2 有限长分析的发展 2 0 0 1 年，r u r b a n k e 等人发明了密度进化( d e n s i t ye v 0 1 u t i o n ) 方法n 1 ， 并用它估计l d p c 码的性能。随着对密度进化的进一步研究，人们发现它不仅对 基于t a n n e r 图迭代译码的各种码型适用，还可以用来计算门限值n 】。但同时密 度进化也存在两个大的缺点：一是，它在衡量码的有限长性能时，存在极大的误 差；另一个是，它只能分析误比特率的情况，而不能分析误帧率的情况。 同年，r u r b a n k e 等人又提出了一个有限长分析的方案阻1 。这个方案精确 地估计了l d p c 码在b e c ( b i n a r ye r a s u r ec h a n n e l ) 信道下的误帧率，但也存 在了很大的局限性：1 计算复杂度( o ( n 5 ) ，n 是帧长) 太高，并且度分布若为不 规则时，复杂度更大；2 这个方法并不一定能推广到其它的信道、码型。 同样是在这一年，r u r b a n k e 团队中的a m o n t a n a r i 将统计物理中的度量 准则( s c a l i n g1 a w ) 9 3 引进了编码理论来分析码型性能，这一思想引起了编 码界的极大震动。a m o n t a n a r i 指出，稀疏图码n 叼( s p a r s eg r a p hc o d e s ，l d p c 码与r a 码都属于这一类码) 的有限长误帧率曲线可以用一个函数衡量h 1 。也就 是说，要实现稀疏图码的有限长性能估计，我们只需寻找它的度量函数即可! 与 r u r b a n k e 的有限长分析方案叩1 相比，a m o n t a n a r i 提出的有限长度量准则 ( f i n i t e l e n g t hs c a l i n gl a w ) 4 1 分析方法不仅适用的对象、信道广泛，还大 大降低了计算复杂度。但是，对于不同的码型、不同的信道，这个度量函数的形 式也会有所变化，所以要实现有限长度量准则的应用，还必须具体对象具体分析。 a a m r a o u i 是第一个寻找到度量函数的学者，他用了五年的时间计算出了 b e c 信道下可以精确估计l d p c 码性能的度量函数，并用它实现优化设计n 1 1 2 “3 1 。2 0 0 7 年，j e z r i 在将a i n r a o u i 的成果推广到更一般的信道n 钉中，发现有 限长度量准则依然可以实现精确的性能估计。这两人的工作，同时展现了有限长 度量准则的发展潜力，各国学者开始纷纷投入到寻找各类码型度量函数的行动 中，从而掀起了一股有限长分析的研究新风。 目前，除了l d p c 码之外，有限长度量准则也已被用来分析有限长r a 码在b e c 信道下的性能凹3 ，但b e c 信道是一个理想化的信道模型，与实际信道存在较大差 距，因此在其它更接近实际的信道下利用有限长度量准则分析r a 码的性能具有 一定的研究意义。 2 r a 码在b s c 信道下的有限长分析 1 3 本文的主要工作与结构安排 由前两节的论述可知，对r a 码的有限长性能进行分析有重要的意义虽然 i r y n aa n d r i y a n o v a 已在b e c 信道做了一定的工作引，但如何在更贴近实际的信 道下对r a 码进行有限长分析尚未解决。鉴于此，本文选择在更贴近实际情况的 b s c ( b i n a r ys y 姗e t r i cc h a n n e l ) 信道下对r a 码进行有限长分析，以期从理 论上较为准确地估计其误帧率。 本文的工作主要从以下几个方面展开： ( 1 ) 借鉴j e z r i 的方法，计算r a 码在b s c 信道下的有限长度量准则形式及 其度量参数。 ( 2 ) 利用该度量准则对( 3 ，3 ) r a 码进行有限长分析，估计不同帧长情况下的 误帧率。 ( 3 ) 将估计的结果与仿真曲线作比较，验证该方法的精确性。 本文结构安排如下： 第一章，介绍论文的背景，以及有限长分析的发展。 第二章，阐述r a 码的一些基本知识、编译码方法，并用密度进化方法分析 其在b s c 信道下的门限值的计算方法。 第三章，讨论r a 码在b s c 信道下的有限长度量准则形式，以及度量参数的 计算；应用结论，对不同帧长( 3 ，3 ) r a 码的误帧率进行估计，并与仿真曲线 进行比较。 。 第四章，总结全文，给出下一步工作方向。 3 r a 码在b s c 信道下的有限长分析 第二章r a 码 2 1 队码的编码原理及表示 2 1 1 触码的构造方式 r a 码是r e p e a t a c c u m u l a t ec o d e s 的简写，称为重复积累码，其编码结构图 如图2 1 所示。将一个长为以的信息分组瞳l 一，吩，“厅】重复c 次得到信息 串j 【五，玉，】，然后将信息串j 送入一个长度为铡的随机交织器打乱， 最后通过一个累加编码器输出一串长为厂的信息只累加器可以看作是一个递归 编码器，其输入j 【葺，薯， 和输出j ，【y l ，咒，只】之间的约束关系 是域最上的模2 和运算。对此，我们称这个r a 码为( c 疗，1 ) r a 码，并且称 吩( 1 f 刀) 为信息节点，只( 1 f ，) 为奇偶节点，模2 和运算关联点为校验节 点。 “r r ， r 。，| 、 、， 随 ， j 广 严 ! 广1 l； 机 。 ；， 、一，o 一一 交 t 广1 ， 虿：! 广1 l 织 n - i i 、， ， 器、ii， _ y l p y ： j i l i i - - 斗 l r 手 ， ，y ， ， ， 重复c 次册册的置换矩阵 累加编码器 图2 1r a 码编码结构图，o 表示信息节点，口表示校验节点，表示奇偶节点 4 r a 码在b s c 信道下的有限长分析 2 1 2 队码的表示方法 由r a 码的构造方式可知，其输入点与输出点之间有一定的约束关系，因此 我们可以利用t a n n e r 图来刻画、分析它。下面介绍r a 码的t a n n e r 图表示方 法。 t a n n e r 图，又称因子图，是一种用于描述多变量函数的二部图( b i p a r t i t e g r a p h ) 。一般来说，在t a n n e r 图中存在两类节点，其中一种是变量节点，另一 种是函数节点，变量节点所代表的变量是函数节点的自变量。根据二部图的定义， 同一类节点之间无直接边连接。 用t a n n e r 图表示，r a 码的顶点分为变量节点矿( 包括信息节点和奇偶节 点d 和校验节点f ，两类节点之间通过边相连接。校验节点，即函数节点，用来 表示变量节点与校验节点之间的约束关系。 图2 2 是一个( 6 ，2 ) r a 码的t a n n e r 图表示，其信息分组长度为2 ，重复次 数c = 3 ，交织图样p ：( 1 ，2 ，5 ，3 ，4 ，6 ) ，校验节点的约束关系为：与校验节 点相连接的所有变量节点的模2 和为0 。 u c y 图2 2 ( 6 ，2 ) r a 码的t a n n e r 图表示。其中。表示信息节点，表示奇偶 节点，口表示校验节点。 5 r a 码在b s c 信道下的有限长分析 在实际应用中还有一种表示方法也很常用，即度分布的表示方法。它是基于 t a n n e r 图进行的。定义每个节点发出的边数为这个点的度。由r a 码的t a n n e r 图 可知，每个奇偶节点与两个校验节点相连，即奇偶节点的度为2 。同理，每个校 验节点与奇偶节点相连的边数亦为2 ，因此对于校验节点的度，我们只需考查它 与信息节点相连的边数即可。于是，我们不妨定义校验节点的度为它与信息节点 相关联的边数。 如果r a 码的信息节点的度都为c ，校验节点的度都为d ，则称r a 码是 ( c ，j ) r a 码( t a n n e r 图如图2 3 所示) ，否则称为不规则的r a 码n6 1 。这里，称 a ( c ，d ) 为r a 码的度分布对。对于给定的( c ，d ) r a 码，其码率为：r = 。 c 十口 本文分析的对象是( c ，d ) r a 码，因此对不规则的r a 码不再作详细介绍。 图2 3 ( c ，d ) r a 码的t a n n e r 图。其中。表示信息节点，表示奇偶节点，口表 示校验节点。 2 2r a 码的译码算法 作为l d p c 码的一个子集，r a 码的译码算法采用与l d p c 码译码算法类似的 信息传播( m e s s a g e p r o p a g a t i o n ) 算法7 1 。本文r a 码的译码算法采用的是类 6 r a 码在b s c 信道下的有限长分析 似l d p c 码的l o g b p ( l o g b e l i e f - p r o p a g a t i o n ) 译码算法7 1 。首先，我们先介 绍l d p c 码的l o g _ b p 算法。 2 2 1l o g b p ( b e ii e fp r o p a g a t i o n ) 算法 在介绍译码算法前我们首先介绍一些符号： 枷札g 端 汜。 表示x 的对数似然比值( 简记为，l l r ) 。 壳，表示从变量点传给校验点的关于吃= 6 的外信息，即除了校验点外 其他校验点传来的关于本变量点取值为6 的概率信息。( 6 o ，1 ) ) 。 吃，表示从校验点传给变量点屹的信息量，即给定屹= 6 和其他比特满足第 m 个校验方程满足的概率。 钟，表示变量节点的初始信道信息。 ( 朋) ，表示与校验点聊相连的变量点集合。 m ) ，表示与变量点，z 相连的校验点集合。 ( 历) 刀，表示除了第，1 个变量点外与校验点m 相连的变量点集合。 m 0 ) 朋，表示除了第m 个校验点外与变量点刀相连的校验点集合。 下面我们开始介绍l o g b p 译码算法。 由b p 译码算法可知： 如= 吉+ 寺兀( 卜2 9 二) = 卜兹 ( 2 2 ) 厶 厶一e ( 朋) 、，l g ：= 兀兹g 二= 吒疗p ：兀呓_ ( 2 3 ) 式中k 为归一化系数，使得也+ 如打= l 。 在译码之前，对变量点做如下处理： 儿尺( g m 玎) = 删( 以) + 枷( 以) ( 2 4 ) r a 码在b s c 信道下的有限长分析 式中，第一项表示来自信道的初始似然比，第二项则是变量点的处理。 对于校验节点，做处理： 1 + 兀( 1 2 1 ) 删= 1 0 9 等一1 0 9 f 背尚 ! 兰：竺迎 札二墨型竺竺 l n ( t a n h ( 去砌( g 肭) ) = 2 t a n h 。( n ( t a n h ( 去瑚( 玎) ) ) ) 。 l o g - b p 算法的译码步骤如下： l 、初始化 对每个变量点赋予由信道得到的l l r ，作为变量点的内信息( i n t r i n s i c m e s s a g e ) ： 皿r ( 以) = 儿尺曲( 屹) = l o g ；端。 ( 2 6 ) 对于校验节点，我们假定每个校验点的初始信息是等概率( 名，以o = ，一1 = o 5 ) 的，则 砌。( ) = l 。g 譬= o 。 ( 2 7 ) 一 2 、计算从变量点传给校验点的信息量 由式( 2 4 ) 得： 砌7 ( 吼刀) = 砌( 岛) + 儿( 。 ) ( 2 8 ) 式中j 表示当前的迭代次数。 3 、计算校验点到变量点的信息量。 由式( 2 5 ) 得： 8 r a 码在b s c 信道下的有限长分析 砌“( ) = 2 蛐。1 ( 兀( t a l l h ( 去础m d ( ) ) ) ) 。 一( 朋) j l 厶 4 、计算变量点的后验信息 由上面的计算，每个变量节点输出的外信息( e x t r i n s i cm e s s a g e ) 为 础州( ) = 脚( 名一) 。 因此，后验信息为： 儿r 删( 屹) = 三从1 m ( ) + 儿r 删( ) = 蚴( 以) + 础( 拧) 5 、判决 根据如下规则对每个变量点进行判决： 弘 尝搿嚣。 2 2 2 队码的l o g 一印译码算澍川 ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) 在r a 码b p 译码过程中有四类信息需要处理，如图2 2 所示： m 陬，c 】，表示信息节点“传给校验节点c 的对数似然比信息； m y ，c 】，表示奇偶节点y 传给校验节点c 的对数似然比信息； 朋k ，“】，表示校验节点c 传给信息节点“的对数似然比信息； 朋 c ，少】，表示校验节点c 传给奇偶节点y 的对数似然比信息。 因此，r a 码的迭代译码过程就是这四类信息的更新过程，根据l o g b p 算法r a 码 译码过程如下： l 、初始化 r a 码的变量点含两类节点，因此由信道得到的对数似然比信息有： 信息节点“的初始信道信息： 叫炉砌) _ l 。g 端。 ( 2 1 3 ) r a 码在b s c 信道下的有限长分析 奇偶节点少的初始信道信息： 叫加伽) - l 。g 端。 ( 2 1 4 ) 对于校验节点，我们假定每个校验点的初始信息等概率，即 p r ( 掣= o ) = p r ( 掣= 1 ) = o 5 则： 酬c ) = 蚴) _ l 。g 嚣苦= 。 ( 2 1 5 ) 2 、计算变量节点传给校验节点的信息量 ( 1 ) 奇偶节点到校验节点 朋( ，c y ，c ，= 主篓 ；：i 。丢；：y ，少 ( 2 1 6 ) 式中，e 表示t a n n e r 图的所有边的集合：z 表示当前的迭代次数；c 满足： c c ，( c ，y ) e 。 m 1 “，c 】_ 三幽( “) + 聊7 c ，甜】。 ( 2 1 7 ) 3 、计算校验节点传给变量节点的信息量 ( 1 ) 校验节点到奇偶节点 m 7 c ，y 】 翊划“。见t 础c 号屿t a 血半字， 组 其中，少满足：y 少，( 少：c ) e 。 ( 2 ) 校验节点到信息节点 聊7 c ，“】 _ 2 t a n h l ( 兀t a n h ( 丛掣) 兀t a n h 型掣) ( 2 1 9 ) 球“，( “- c ) 层 厶 ( y ，c ) e 。 4 、计算信息节点的后验信息 l o r a 码在b s c 信道下的有限长分析 由上面的计算，每个信息节点输出的外信息为 枷谢( “) = m ，) c ：“】 c c ，( c ) e e 从而信息节点的后验信息为： 儿尺删( “) = 三幽( “) + m 7 【c ：“】 。( 2 2 0 ) c c ( c ) e 5 、判决 “( ，) = j o ，砌删( “) o l l ，儿尺删 ) o 2 3b s c 信道下r a 码的门限值 ( 2 2 1 ) 由于有限长分析的度量准则方法，是计算一个信道参数接近门限值时的度量 函数，即关于门限的母函数，所以要计算度量函数必须先知道门限值。而密度进 化是一个计算门限值的有效方法，因此这一节我们将介绍b s c 信道下( c ，d ) r a 码的密度进化以及门限值的计算。 2 3 1b s c 信道3 3 定义2 1如果一个离散时间信道满足以下条件： 输入字母表x 为 0 ，1 ) ； 输出字母表y 为 0 ，1 ) ； 离散时间内，输出值y 只与当前的输入x 有关； 所有的输出少，均满足对称条件： 昂( o ) = 舅( 1 ) 其中，只( 少) 表示输入x 接收到j ，的概率； 则我们称这个信道为二进制对称信道( b i n a r ys y 唧e t r i cc h a n n e l ， 它的信道模型如图2 4 所示。 ( 2 2 2 ) 简称b s c ) 。 r a 码在b s c 信道下的有限长分析 0 1 1 一p 0 1 l p 图2 4b s c 信道模型 2 3 2b s c 信道下队码的密度进化博1 密度进化的过程，就是随着译码的迭代次数增加，变量点与校验点概率密度 函数相应变化的过程。因为r a 码的变量点分为信息节点与奇偶节点，所以r a 码 的密度进化过程需要观察四个概率密度函数的进化，即： 足2 ( x ) ，表示第，次迭代从校验节点到信息节点的l l r 信息x 的概率密度函数； 础，( x ) ，表示第，次迭代从校验节点到奇偶节点的l l r 信息x 的概率密度函数； 掣c ( x ) ，表示第，次迭代从信息节点到校验节点的l l r 信息x 的概率密度函数； e 竺( x ) ，表示第次迭代从奇偶节点到校验节点的l l r 信息x 的概率密度函数。 将信息节点与奇偶节点的初始概率密度函数分别记为：兄( x ) 与名( x ) ， 假设b s c 信道的交错概率为占，则可知： 弓( x ) = 0 ( x ) = ( 1 一s ) 万( x f ) + 筇( x + f ) ( 2 2 3 ) 式中，f = 1 。g ( 生) ， 占 c ，、f o ，x o d 【x ) = t l ，x = o 。 首先，观察础。( 功的进化： 根据概率理论，多个独立的随机变相加，其和的概率密度等于原随机变量概 率密度的卷积。又因为，1 f d ，是独立同分布，所以由式( 2 1 7 ) ，可知信 l ( 功 ，= o 职 卜1 兰( 礁h p o q 2 4 ) 1 2 r a 码在b s c 信道下的有限长分析 式中，d 表示( c ，d ) r a 码的校验点( 与信息点相连) 的度，幸表示卷积运算 与信息节点类似，奇偶节点的概率分布弓竺( 砷的变化由式( 2 1 6 ) 可知： 舢，= 蒜哪舞 弦2 5 ) 再看足劣( x ) 的密度进化，相对更为复杂。 定义运算符号7 ：7 ( 五力= 2 t a i l l l - 1 ( t a 血主t a m l 考) ，则式( 2 1 8 ) 演变为： 聊7 c ，y 】= 7 ( 所7 1 ，c 】，( m 7 1 【甜2 ，c 】，7 ( 聊7 1 【“d ，c 】，m 7 1 y ：c 】) ) ) 。 设z = 厂 ，y ) ，则=足( x ) 0 ( y ) ，简记为：= r ( 足，0 ) 。 ( x ，y ) ：z = ，( j ，) 由于“，1 f d 是独立同分布的，因此聊，) c ，少】的概率密度可计算如下： 艘v ( x ) = 尺( 毪( x ) ，r ( 联( 力，r ( 毪( 功，9 2 ( x ) ) ) ) 简记为： 鹳( 功= 删( x ) o 弓2 ( x ) ( 2 2 6 ) 同理，由式( 2 1 9 ) 础。( x ) 的进化如下： 4 一i 二 础“( x ) = o 职( x ) o 盟( x ) ( 2 2 7 ) 引入运算符的意义在于：由于随机变量掰( c ，材】( 珑 c ，少】) 是由式( 2 1 9 ) ( 式( 2 1 8 ) ) 得来的，没有办法直接观察它的概率密度函数础”( x ) ( 础， ) ) 的进化规律，只有建立输入输出表，通过查询该表来计算新一轮迭代中础”( x ) ( 础，( x ) ) 的值。 在仿真中，发送方采用b p s k ，o 调制为+ 1 ，1 调制为一1 ，在接收方用b p 算 法迭代足够多的次数之后，由于信息m m ，c 】都是l l r ，所以当m 陋，c 】取正值的 时候，判决该比特为o ；川阻，c 取负值的时候，判决该比特为1 。假设传输全。 r a 码在b s c 信道下的有限长分析 码字，如果硝掰，c 】取负值将判决为l ，则出现了译码错误因此，m 曲，c 】取负 值的概率对应了误码概率，从而， 乞= ：( 暇( x ) ) 牛( x ) 出 ( 2 2 8 ) 2 3 3 门限值 门限值口1 是一个用来刻画误码率发生相位转移的信道参数，定义如下： 定义2 2 信道参数g 是关于b p 译码下度分布对( 允，p ) 的函数占卯( 允，p ) ， 如果g 即( 名，p ) = s u p g o ，l 】： 蛩e 荔纠( g ) = o ，其中，互( 见，p ) 是指度分布 对( 名，p ) 的计算树图，则称此时的s 卯为( 名，户) 的门限值，记为，。 由上面的定义可看出，门限值是基于计算树图的，但上面的形式不便于用来 分析，为此我们引入固定点的概念，并用它来重新定义门限值。 定义2 3 口1对于给定的分布对( 名，p ) 和信道参数g o ，l 】，如果厂( 占，x ) = x ， 则称此时的x 是固定点，其中厂是密度进化函数。特别地，当占取门限值时，此 时的固定点，称为临界点。 注：厂( 占，x ) = x 表示迭代输入的信息x 等于输出的信息厂( 占，x ) ，即信息不更 新，此时迭代中止。以( c ，d ) r a 码为例，它的固定点是满足密度进化方程： j l d l2 嘲( x ) 2 ；兰( o 寸。( x ) o e 斗c ( x ) ) 宰( x ) ( 2 2 9 ) 的只一。( x ) 。 从而，我们可以从固定点出发，简单而形象地给出门限值的等价定义： 定义2 4 7 1 门限值g + 有以下两种表现形式： ( 1 ) 占卯( 五，p ) = s u p s o ，1 】：( g ，x ) = x 在( o ，l 】中无解) ( 2 ) 占卯( 旯，p ) = i n f g o ，l 】：厂( g ，x ) = x 在( o ，1 】中有解) 。 1 4 r a 码在b s c 信道下的有限长分析 第三章r a 码在b s c 信道下的有限长分析 本章讨论的是( c ，d ) r a 码在b s c 信道下的有限长分析，应用的分析方法是 有限长度量准则。首先，我们先介绍度量准则( s c a l i n gl a w ) 伽在编码理论中 的形式。 3 1 有限长度量准则 2 0 0 1 年，a m o n t a n a r i 第一次将统计物理中的度量准则引入编码领域，并 证明了它应用的合理性n 1 。他指出，误帧率函数弓( 行，g ) 可用一个母函数厂( z ) 逼近，具体描述如定理3 1 。 定理3 1 “3 误帧率r 是关于码长以及信道参数s 的函数，s 是信道的门限 值，如果s ，时，1 i m b ( ，z ，占) = 1 ，则存在一 n n 悃 个非负常数及非负函数厂( z ) ，使得： 进一步有： l i m 尼( 刀，s ) = 厂( z ) ( 3 1 ) 以 一 b ( 玎，占) = 厂( z ) + 以一国g ( z ) + d ( n 一国) ( 3 2 ) 这里，国是正实数，g ( z ) 是b ( 聆，g ) 关于z 的二阶展式。 由此可见，我们可以通过确定厂( z ) ，进而估计误帧率乞0 ，g ) 。那么，如 何寻找厂( z ) 呢? 编码学者们发现，当帧长趋于无穷时，迭代译码过程中r a 码 的误帧率弱收敛于一个高斯随机变量，也就是说我们可以用期望和协方差来表征 译码过程。再者，基于集中性定理，如同j - e z r i 的作法，我们可以得到r a 码 在b s c 信道下的有限长度量准则形式： 定理3 2 如果b s c 信道参数为办，则信息长度为以的( c ，d ) r a 码的误帧率 为： 1 5 r a 码在b s c 信道下的有限长分析 b ( ，l ，办) = q ( 石( 7 l 一7 l ) ) ( 3 3 ) 式中， ) ：= 击f 8 一乇 慨4 ) 便是度量的母函数，五是( c ，j ) r a 码的门限值，口是与度分布对 ，d ) 有关的 函数，称为度量参数( s c a l i n gp a r 锄e t e r ) 。 综上可知，要得到一个具体的度量函数，最主要的任务就是其参数臼的计 算。 3 2 度量参数 在计算口前，我们先定义一个二元组( | l ，x ) ，这里信道参数办指的是信道 交叉概率g 的熵：五= 一g l o g g 一( 1 一占) l o g ( 1 一s ) ；x 指t a n n e r 图中第一类边 传送的导致译码错误的信息。根据大数定律以及密度进化原理，办可理解为信 息节点的出错概率，x 理解为第一类边的出错概率。因为信息节点的信息是由 边传送而来的，所以五是关于x 的函数。下面介绍一些符号： ，l ：信息节点的个数( 即信息比特长度) ； 局：信息节点与校验节点相关联的边的集合，称为第一类边； e ：奇偶节点与校验节点相关联的边的集合，称为第二类边； e ：t 时刻，信息节点出错个数； 五：t 时刻，第一类边出错( 即含有使得信息节点译错的信息) 的数量； a = 竺： t 时刻，信息节点出错概率； 幺= 高：t 时刻，第一类边出错概率； 盘= 等： 五= xi 巨i 时，怠的取值，即信息节点出错概率； 1 6 r a 码在b s c 信道下的有限长分析 幺= 高：耳= 砌时，2 的取值，即巨的出错概率 由上节的讨论以及密度进化可知， 当五 虬时，b p 将以极大的概率译码出错( 译码停止于非零点) 。 因此，若致服从期望为j i i ，方差为巳的高斯分布，则误帧率可估计为n 5 玉 b ( 办) = p r 办 屯) = q ( 业) ( 3 5 ) u 矿 再根据i a n d r i y a n o v a 的结论嘲可知，方差吒具有如下形式： 巳2 = 高( 等1 ) 2 黔叫y 陬6 ， y = 墨区互二里互垡!( 3 7 ) i 巨l 对于信息长度为刀的( c ，d ) r a 码，l 巨| _ 册，lcl - 等，这里的c 表示校验点 集合。因此，r a 码的度量参数形式如下： 州警i ) 粤( 一妒店 慨8 ) ( 一) 信息方差矿 从式( 3 8 ) 司知，为了计算口，首要解决的是信恳方差的计算l 司趑。为 计算矿，先定义： 嘭= 坐坠坳 ( 3 9 ) 则y = l i m l i m 彰，刀是信息长度，是迭代次数。 f n 瑚 对信息进行量化口1 后，不妨设信息字母表为 一所，o ，所) ，聊n 。并且 1 7 r 码在b s c 信道下的有限长分析 译码过程中，当边传递的信息为m 时译码出错，故而叫= ：。l l 。研) ，这里的 “表示第f 次迭代，信息节点沿第f ( 1 蔓f 兰删) 条边传给校验节点的信息- 再设兰为固定点处信息节点输出的概率密度函数：h 为固定点处信息节点输 出为m 时的概率密度函数。因此， ，_ 里l 型二里型垡】 “ 积 皿( 三1 一。 ) 2 卜可三1 。，。 】2 删蚓皿1 f h r = 用) 1 m 】一胙吲研1 一训 研l 硼一 ( 3 1 0 ) = 啪l 皿l h ，刊l “，圳卜皿l 抽，硼】吲矧研1 f 圳】 = 皿l l n ) 1 耐卜( 妄) 2 = 。( p r “= m ，h 。= m 一( 妄) 2 ) 。 定义33 如果连接两个信息节点的最短路径含有f 一1 个信息节点，则称这两个 信息节点的距离为，。 由定义来看，对任意一个信息节点，与它距离为，的信息节点有y 个，其中 ( ，= ( c 一1 ) ( d 一1 ) ) 。考虑由信息节点与控验节点构成的长为，的一条链，并 对各个点标识，如图3 1 所示。 ”l 一1”i ” p t 一1 一钳”：卜- j 三| i 三 p - 一1 一i p ；i + i 图3 1 信息节点与校验节点构成的链 链中边传递的信息用表示，下标表示信息传递的方向，上标表示迭代 j + f 的次数；用一( 一) 表示第f 次迭代时其它c 一2 ( d ) 个点传给信息节点f ( 校 兰i p ， 跨虫 r a 码在b s c 信道下的有限长分析 验节点f ) 的信息。由此，边的信息方差可演变为： y = l i m l i m ，一 ( ) ( 善7 7 ( p r 唯。毗吃：。= m 一z 2 ) ) ( 二) 联合概率p r = 珑，7 = 职) 的计算 o + - 0，+ ，+ l 1 、当，为偶数时 ( 3 1 1 ) 长为j 的链的中心位置必是信息节点妻，所以由馏与臀 无关有： z t f2 l i f 2 l | 2 七- l | 2 p r = 所，。= 耽) o - o， ，+ 1 ，j p r 删= 所，馅= s f 终= ，) o 旬，2 i ，2，2 一，2 p r 7 = 朋，2 = r i 幺2= j ) f “l，2 卜，2，2 寸，2 对于p r 7 = o o 朋， = s l _ = ，) 有递归关系： f + _ f p r 尘= 朋，从= sl 一= 厂 o - 加 f 蚵f 卜l ，酽r 吒= sl 味? 啾哼1 = + 铭) ，七一，v 州卜l 寸f j p r 卜件l f l 一f = 后i 矿= ，p = 1 ，) p r 吱1 p r = ，竹，卜1 = i 卜“l = 后 。 ( 一oj l jj l - f = “，订= 1 ，) j 定义两个长为( 2 所+ 1 ) 2 的向量星盖，兰：其分量分别如下： 堡z = p r = 朋，= l = 财 一 o + - ol 寸li 卜f ， 轨廿r 卜。一，。0 - of f + l 根据对称性，有 = j fi 卜= 砧 “一f + 1 篡= p r 7 = 历，= 后i h= 歹)。 ，+ l ，一l + 一卜i + l 。 ，一f “一i + l 1 9 ( 3 1 2 ) ( 3 1 3 ) ( 3 1 4 ) ( 3 1 5 ) ( 3 1 6 ) r a 码在b s c 信道下的有限长分析 再定义( 曼肚= p r 吒南= 肌，吃舀= 后i 吃一，= ) 。 2 m + 1 ) 2 ( 2 加+ 1 ) 2 的矩阵c “，c 其元素如下 ，1 x = 善n 吃a = 歹l 叫= s ，e = “玑v l 斗l + l l 州 八i j c ( ，x _ ，乒) = h y p r 矿= ，i h = 七，一一= 1 ， f + 0i f + i p r t = “，一= v ) p r 从 i 村 = s l卜1 = ，谚= “) j l “j p r m l = 尼l = ，= 嵋 l - l + - f j + ii p r t = “，矿 lf 由上述的符号定义，可知： = y = p r = m ，= 歹i = 尼 o 十一oi hf 卜f 材y p r = 歹l 卜1 = 歹，订1 = 甜 i “f l ij p r 卜+ _ = 后l 卢 o 卜- o，+ l 堡蟛2 邕2 ，j ( 3 1 7 ) ( 3 1 8 ) ( 3 1 9 ) ( 3 2 0 ) r a 码在b s c 信道下的有限长分析 影2 c 圳2 2 ，j ，2 ( 兀 扛l l jl f 2 l 乒 a ，一1 ( 埔) r ) r ，c