第4章 无失真信源编码-第14讲.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,4,章 无失真信源编码,第一节 编码的定义,第二节 定长编码定理,第三节 变长编码定理,第四节 最佳编码,引言,引言,编码分为,信源编码,和,信道编码,，其中信源编码又分为,无失真信源编码,和,限失真信源编码,。,无失真信源编码,：适用于离散信源或数字 信号。,限失真信源编码,：主要用于连续信源或模拟信号，如语音、图像等信号的数字处理。,香农信息论三大定理,:,1.,第一极限定理,:,无失真信源编码定理,.,第二极限定理,:,信道编码定理（包括离,散和连续信道）,.,3.,第三极限定理,:,限失真信源编码定理,.,信源编码的主要任务是什么,?,由于信源符号之间存在分布,不均匀,和,相关性,，使得信源存在冗余度，信源编码的,主要任务,就是减少冗余，提高编码效率。,具体说，就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短的码字序列。,信源编码的基本途径 是什么,?,信源编码的,基本途径,有两个,:,一是,使序列中的各个符号尽可能地互相独立，即解除相关性；,二是,使编码中各个符号出现的概率尽可能地相等，即概率均匀化。,信源编码的基础是什么,?,信源编码的,基础,是：两个编码定理。,即无失真编码定理和限失真编码定理。,编码定理证明,：,（,1,）,必存在一种编码方法，使代码的平均长度可任意接近但不能低于符号熵,（,2,）,达到这目标的途径，就是使概率与码长匹配。,说明,：,（,1,）,无失真编码或可逆编码只适用于离散信源。,（,2,）对于连续信源，编成代码后就无法无失真地恢复原来的连续值，因为后者的取值可有无限多个。此时只能根据限失真编码定理进行限失真编码。,什么是分组码？,设,:,源消息为符号序列,X,i,，,序列中的每个符号取自于符号集,A,，,。,而每个符号序列,X,i,依照固定的码表映射成一个码字,Y,i,，这样的码称为分组码，有时也叫块码。只有分组码才有对应的码表，而非分组码中则不存在码表。,第一节 编码的定义,信源编码器,L,长序列,K,长码字,图,4-1-1,信源编码器,设,:,信源输出的序列长度为,1,，即信源符号集,信源概率空间为：,二元信道的信道基本符号集为,0,，,1,。,若将信源,X,通过一个二元信道传输，就必须把信源符号,x,i,变换成由,0,，,1,符号组成的码符号序列，即编码。可用不同的码符号序列，如所示。,分组码的一些直观属性,分组码的一些直观属性,码,非分组码,分组码,奇异码,非奇异码,非唯一可译码,唯一可译码,非即时码,即时码（非延长码）,码树图,A,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,1,1,1,1,1,二进制码树,2,0,0,0,0,0,1,1,1,11,2,2,2,2,2,三进制码树,唯一可译码存在的充分和必要条件,用树的概念可导出唯一可译码存在的充分和必要条件，即各码字的长度,K,i,应符合克劳夫特不等式：,(4-1-1),式中，,m,是进制数，,n,是信源符号数。,无失真信源编码定理要研究的内容,若信源输出符号序列的长度 ，即,变换成由,K,L,个符号组成的码序列（码字,),变换的要求,:,(1),能够无失真或无差错地从,Y,恢复,X,，也就是能正确地进行反变换或译码,(2),传送,Y,时所需要的信息率最小,由于,Y,k,可取,m,种可能值，即平均每个符号输出的最大信息量为,logm,，,K,L,长码字的最大信息量为,K,L,logm,。用该码字表示,L,长的信源序列,则送出一个信源符号所需要的信息率平均为,:,其中 是,Y,所能编成的码字的个数。,信息率最小,，就是找到一种编码方式使 最小。,无失真信源编码定理要研究的内容,:,(1),最小信息率为多少时，才能得到无失真的译码？,(2),若小于这个信息率是否还能无失真地译码？,定长编码定理,由,L,个符号组成的、每个符号的熵为,H,L,（,X,）的无记忆平稳信源符号序列 ，可用,K,L,个符号,（每个符号有,m,种可能值）进行定长编码。对任意 ，只要,则当,L,足够大时，必可使译码差错小于 ；反之，当,时，译码差错一定是有限值，而当,L,足够大时，译码几乎必定出错。,第二节 定长编码定理,说明,（,1,）当编码器容许的输出信息率，也就是当每个信源符号所必须输出的码长是,时，只要 ，这种编码器一定可以做到几,乎无失真，也就是收端的译码差错概率接近零，条件是所取的符号数,L,足够大。,（,2,）将定理的条件改写成,其中：,左边：,K,L,长码字所能携带的最大信息量，,右边：,L,长信源序列携带的信息量。,上述定理表明,，只要码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，当然条件是,L,足够大。,反之，当 时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。,时，则为临界状态，可能无失真，也可能有失真。,2026/4/8 周三,17,单个符号变长编码定理,：,若一离散无记忆信源的符号熵为,H,（,X,），每个信源符号用,m,进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式,第三节 变长编码定理,2026/4/8 周三,18,离散平稳无记忆序列变长编码定理,对于平均符号熵为,H,L,（,X,）的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率 满足不等式,其中 为任意小正数,。,2026/4/8 周三,19,证明,:,设用,m,进制码元作变长编码，序列长度为,L,个信源符号，则由（,4,3,1,）式可以得到平均码字长度 满足下列不等式,当,L,足够大时，可使,这就得到了 所需结论,2026/4/8 周三,20,说明,:,(1),用变长编码来达到相当高的编码效率，一般所要求的符号长度,L,可以比定长编码小得多。可得编码效率的下界：,2026/4/8 周三,21,(2),例,用二进制，,m,2,，,log,2,m=l,，,H,（,X,）,2.55,比特符号，若要求 ，则,2026/4/8 周三,22,(3),码的剩余度 为,码的剩余度 用来衡量各种编码方法与最佳码的差距,.,2026/4/8 周三,23,例,4,3,1,设离散无记忆信源的概率空间为,解,:,其信源熵为,比特,/,符号,求,:,编码效率,?,2026/4/8 周三,24,(1),定长编码,若用二元定长编码（,0,，,1,）来构造一个,即时码：,这时平均码长为,=1,二元码符号,/,信源符号,编码效率为,(,对于无记忆信源而言,有,H,L,(X)=H(X),输出的信息率为,R,0,811,比特二元码符号,2026/4/8 周三,25,(2),变长编码,假定信源序列的长度为,L=2,其即时码如表,4-3,所示。,序列,序列概率,即时码,x,1,x,1,9/16,0,x,1,x,2,x,2,x,1,x,2,x,2,1/16,3/16,3/16,111,110,10,2026/4/8 周三,26,这个码的码字平均长度,单个符号的平均码长,编码效率,输出的信息率为,R,2,0,961,比特二元码符号,比较（,1,）、（,2,）可见，经过二重扩展后，,效率由,81.1%,上升到,96.1%,。,2026/4/8 周三,27,(1),最佳码定义是什么,?,凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合都可称为最佳码。,(2),最佳编码思想是什么,?,将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。,(3),最佳码的编码主要方法有哪些,?,香农（,Shannon,）、费诺（,Fano,）、哈夫曼（,Huffman,）编码等。,第四节 最佳编码,2026/4/8 周三,28,4.4.1,香农编码方法,编码方法如下：,(1)将信源消息符号按其出现的概率大小依次排列,(2),确定满足下列不等式的整数码长,K,i,：,2026/4/8 周三,29,(3),为了编成唯一可译码，计算第,i,个消息,的累加概率,(4),将累加概率,P,i,变换成二进制数。,(5),取,P,i,二进数的小数点后,K,i,位即为该消,息符号的二进制码字。,2026/4/8 周三,30,例,4-4-1,设信源共有,7,个消息符号，按照概率大小排列后的概率分布和累加概率如表,4-4-1,所示。根据自信息量定义计算每个信源符号的信息量,I,(x,i,)=-logp(x,i,),，然后根据信息量确定码长,K,i,，如表,4-4-1,中第,4,、,5两列以,i=4,为例，,2026/4/8 周三,31,累加概率,P,4,=0.57,，变换成二进制为,0.1001,，由于,3,，所以第,4,个消息的编码码字为,100,。其他消息的码字可用同样方法求得，如表,4-4-1,所示。,2026/4/8 周三,32,x,i,P(x,i,),P,i,-logp(x,i,),K,i,码字,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0.20,0.19,0.18,0.17,0.15,0.10,0.01,0,0.2,0.39,0.57,0.74,0.89,0.99,2.34,2.41,2.48,2.56,2.74,3.34,6.66,3,3,33,3,4,7,000,001,011,100,101,1110,1111110,2026/4/8 周三,33,说明,:,(1),该信源共有,5,个三位的码字，各码字之间至少有一位数字不相同，故是唯一可译码。同时可以看出，这,7,个码字都不是延长码，它们都属于即时码。这里,L=1,，,m=2.,(2),信源符号的平均码长,码元,/,符号,2026/4/8 周三,34,(3),平均信息传输率,4.4.2,费诺编码方法,费诺从概率匹配角度出发，构造了一种编码算法，称为费诺码。,其基本思想是：按照累加概率尽可能相等的原则对信源符号进行分组，对于二元码，每次分为两组，对于,d,元码，则每次分为,d,个组，并且给不同的组分配一个不同的码元符号；对其中的每组按照累计概率尽可能相等的原则再次进行分组，并指定码元符号，直到不能再分类为止,;,然后将每个符号指定的码元符号排列起来即可得到相应的码字。,如果采用二元码，,编码步骤：,2026/4/8 周三,36,编码步骤：,（,1,）,将信源消息符号按其出现的概率大小依次排列：,p(x,1,)p(x,2,)p(x,n,),。,（,2,）,将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“,0”,和“,1”,。,2026/4/8 周三,37,（,3,）,将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“,0,和“,1”,。,（,4,）,如此重复，直至每个组只剩下一个信源符号为止。,（,5,）,信源符号所对应的码字即为费诺码。,2026/4/8 周三,38,对例,4-4-1,的信源进行费诺编码，具体编码过程参见下表。,2026/4/8 周三,39,费诺码的平均码长,信息传输速率,4.4.3,哈夫曼编码方法,哈夫曼提出了一种编码效率较高的构造最佳码的方法，其基本思想是：概率大的符号分配短码字，而概率小的信源符号分配长码字，为此首先给小概率符号分配码元，分配码元后的符号进行概率合并，然后按照大小顺序重排概率，并对概率小的符号或者符号集合分配码元，直到概率合并结束为止，最后逆向搜索参与概率合并时分配的码元符号，形成对应的码字。对于二元码，其编码步骤如下：,2026/4/8 周三,41,哈夫曼编码 步骤：,（,1,）,将,n,个信源消息符号按其出现的概率大小依 次排列，,p,（,x,1,）,p,（,x,2,）,p,（,x,n,）,（,2,）,取两个概率最小的字母分别配以,0,和,1,两码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。,2026/4/8 周三,42,（,3,）,对重排后的两个概率最小符号重复步骤（,2,）的过程。,（,4,）,不断继续上述过程，直到最后两个符号配以,0,和,1,为止。,（,5,）从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。,2026/4/8 周三,44,问题,:,为何哈夫曼编码方法得到的码并非是唯一的,?,(1),每次对信源缩减时，赋予信源最后两个概率最小的符号，用,0,和,1,是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。,2026/4/8 周三,45,(2),对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。码方差小的编码方法要比码方差大的编码方法好。,例,设有离散无记忆信源的概率空间为,采用二元码进行编码，由于符号合并后的概率与信源其他符号的概率相等，合并概率放置的位置不同，因此可以得到不同的编码结果，即有两种哈夫曼编码方法。如果将合并概率放在下面，编码过程、产生码字和编码长度如表,5.4,所示；如果将合并概率放在上面，则编码过程及结果如表,5.5,所示。,根据两种方法的编码结果，计算两种哈夫曼码的平均码长，结果是两种编码方法的平均码长相等，即,比特,/,符号,编码效率也相等，都为,将两种编码方法得到的码长分别代入上式，得到各自码方差为,0,l1,=1.36,2,l2,=0.16,码方差小的编码方法要比码方差大的编码方法好。由于方法,2,的码方差比方法,1,的码方差小许多，因此方法,2,的编码质量好。,