信息论第5章 信源编码

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2013/10/9,#,第,五,章 信源编码,问题,对信源有两个重要问题,信源输出的信息量的,度量问题,；,如何更,有效地,表示信源,输出的问题,；,信源输出的符号序列，经过信源编码，变换成适合信道传输的符号序列，同时，在不失真或允许一定失真的条件下，用尽可能少的码符号来传递信源消息，提高信息传输的效率。,5.1,编码的定义,概述,信源编码是以,提高通信的有效性,为目的编码。,通常通过,压缩信源的冗余度,来实现。,信源编码,无失真信源编码,限失真信源编码,统计匹配编码,据信源符号的概率不同，编码的码长不同。概率大的信源符号编的码字短，使平均马场最短 ，达到压缩信源冗余度的目的,5.1,编码的定义,编码的定义,将信源符号序列按一定的数学规律映射成码符号序列的过程是信源编码过程，完成编码功能的器件就是,编码器,。,信源,编码器,信道,码表,X,Y,编码器的作用,是将信源符号集,X,中的符号变换成由码符号组成的一一对应的输出符号序列,编码器的输出,称为,码字,，码字的集合称为,码,，信源符号对应码字需的码符号的个数表示,码字长度，简称码长,。,分组码才有对应的码表,5.1,编码的定义,举例,怎么用编码器实现对信源符号的编码,信源的概率空间为,把信源符号编码为适合二元信道的二元码。二元信道是数字通信中最常用的一种新到，它的码符号集为,0,，,1,。,解：,将信源通过一个二元信道传输，就必须把信源符号,s,i,变换成由,0,，,1,符号组成的码符号序列，即进行编码。可以用不同的二元码符号序列与信源符号 一一对应，就得到不同的码。,信源符号,P(si),码,1,码,2,s1,P(s1),00,0,s2,P(s2),01,01,s3,P(s3),10,001,s4,P(s4),11,111,定长码,变长码,二次扩展信源符号,二次扩展码字,S1=,S1S1,00,s2=,S1S2,001,s4=,S4S4,111111,5.1,编码的定义,码的分类,分组码和非分组码,分组码,(,块码,),:,将信源符号集中的每个信源符号固定映射成一个码字 ，这样的码称为。,非分组码,(,树码,):,树码编码器输出的码符号通常与编码器的所有输入的信源符号都有关,5.1,编码的定义,码的分类,奇异码和非奇异码,若一种分组码中所有码字都不相同，也即信源符号和码字一一对应，则称为,非奇异码,，否则为奇异码。,信源符号,ai,符号出现概率,p(ai),码,1,码,2,a1,1/2,0,0,a2,1/4,11,10,a3,1/8,00,00,a4,1/8,11,01,奇异码,非奇异码,5.1,编码的定义,码的分类,唯一可译码和非唯一可译码,任意有限长的码元序列，只能唯一地分割成一个个码字，便是唯一可译码。,信源符号,ai,符号出现概率,p(ai),码,1,码,2,码,3,a1,1/2,0,0,1,a2,1/4,11,10,10,a3,1/8,00,00,100,a4,1/8,11,01,1000,奇异码,非奇异码,EG:,10000100,由码,2,产生,(10,0,0,01,00),产生的码流，译码时可有多种分割方法，产生歧义。,唯一可译码首先是非奇异码，且任意有限长的码字序列不会雷同。,一个分组码，若对以任意有限的整数,N,，其,N,次扩展码均维非奇异，则为唯一可译码 。,5.1,编码的定义,码的分类,即时码和非即时码,无须考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一可译码 称为 即时码。,信源符号,ai,符号出现概率,p(ai),码,1,码,2,码,3,码,4,a1,1/2,0,0,1,1,a2,1/4,11,10,10,01,a3,1/8,00,00,100,001,a4,1/8,11,01,1000,0001,奇异码,非奇异码,定理,：一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其它码字的前缀。,即时码,非即时码,5.1,编码的定义,码的分类,码,非分组码,分组码,奇异码,非奇异码,非唯一可译码,唯一可译码,即时码,非即时码,5.1,编码的定义,树图,树根,码字的起点,树枝数,码的进制数,节点,码字或码字的一部分,终端节点,码字,节数,码长,非满树,变长码,满树,等长码,根节点,终端节点,中间节点,一阶节点有最多,r,个；,N,阶节点最多有,r,N,个；,若制定某个,N,阶节点为终端节点，表示一个信源符号，则该节点就不再延伸，相应的码字即为从树根到此端点的树枝标号序列，其长度为,N,。为即时码。,0,0,0,1,1,1,1,1,01,001,0001,5.1,编码的定义,克拉夫特,Kraft,不等式,举例,用二进制对符号集,a1,a2,a3,a4,进行编码，对应的码长分别为,K,1,=1,，,K,2,=2,，,K,3,=2,，,K,4,=3,，问是否存在满足这种,K,i,的唯一可译码？,解：据克劳夫特不等式得,因此，不存在满足这种,Ki,的唯一可译码,其中：,m,是进制数；,n,是信源符号数；,各码字的长度,K,i,应符合：,该不等式是唯一可译码,存在,的必要条件，不是唯一可译码的必要条件。,5.1,编码的定义,定长码及定长信源编码定理,若要实现无失真编码，所编的码必须是唯一可译码。,5.2,无失真信源编码,若定长码是非奇异码，则它的任意有限长,N,次扩展码一定也是非奇异码，定长非奇异码一定是唯一可译码。,若对信源,S,的,N,次扩展信源,进行定长编码，信源的符号个数,q,N,满足：,若对一个有,q,个信源符号的信源,S,进行编码，信源,S,存在唯一可译定长码的条件,q r,l,，其中,r,是码符号集中的码元数，,l,是定长码的码长。,取对数,对于定长唯一可译码，平均每个原始信源符号至少需要码符号的个数,英文电报信源有,32,个符号，对每一个符号进行二元编码，,每个英文电报符号至少要用,5bit,二元符号进行编码才能得到唯一可译码。,q=32,r=2,分析,：考虑到符号出现的概率以及符号之间的相关性后，实际平均每个英文电报符号所提供的信息量约,1.4bit,，远小于,5bit,，因此定长编码后，每个码字只载,1.5bit,信息，,5,个二进制符号最大能载,5bit,信息 ，因此，定长编码的信息传输效率低。,解决方案,:,(1),对于不会出现的符号序列不予编码，这样不会造成误差；,(2),对于概率非常小的信源符号序列不予编码，这样可能会造成一定误差，但当信源符号序列,N,足够大，误差概率非常小,定长信源编码所需码长的理论极限值,定长信源编码定理,5.2,无失真信源编码,英文电报信源有,32,个符号，对每一个符号进行二元编码，,每个英文电报符号至少要用,5bit,二元符号进行编码才能得到唯一可译码。,q=32,r=2,分析,：考虑到符号出现的概率以及符号之间的相关性后，实际平均每个英文电报符号所提供的信息量约,1.4bit,，远小于,5bit,，因此定长编码后，每个码字只载,1.5bit,信息，,5,个二进制符号最大能载,5bit,信息 ，因此，定长编码的信息传输效率低。,解决方案,:,(1),对于不会出现的符号序列不予编码，这样不会造成误差；,(2),对于概率非常小的心愿符号序列不予编码，这样可能会造成一定误差，但当信源符号序列,N,足够大，误差概率非常小,定长信源编码所需码长的理论极限值,定长信源编码定理,由于英文信源的极限熵,H 1.4bit/,信源符号，所以码长,l,满足,l/N,1.4,，即平均每个英文符号只需要近似,1.4,个二元码符号来表示，从而提高了信息传输效率,5.2,无失真信源编码,定长编码定理,由,L,个符号组成的，每个符号的熵为,H,L,(X),的无记忆平稳信源符号序列,(X,1,X,2,X,l,X,L,),，可用,K,L,个符号,Y,1,Y,2,Y,k,Y,KL,(,每个符号有,m,中可能值,),进行定长编码。,同样适用于平稳有记忆信源，将式中的,H(S),改称极限熵即可。,5.2,无失真信源编码,5.2,无失真信源编码,编码效率,5.2,无失真信源编码,举例,举例,5.2,无失真信源编码,变长码及变长信源编码定理,？,什么样的码是唯一可译码或即时码？,Kraft,不等式和,McMillan,不等式给出了即时码和唯一可译码的码长条件。,变长码,信源符号,Si,概率分布,码,1,码,2,码,3,码,4,S1,1/2,0,0,1,1,S2,1/4,11,10,10,01,S3,1/8,00,00,100,001,S4,1/8,11,01,1000,0001,非奇异码,唯一可译码,唯一可译码,即时码,克拉夫特,Kraft,不等式,McMillan,不等式,单个符号变长编码定理,离散平稳无记忆序列变长编码定理,M,进制码元作变长编码，,序列长度为,L,个信源符号,编码效率,码的剩余度：,编码效率：,衡量各种编码方法与最佳码的差距,在二元无噪无损信道中：,在二元无噪无损信道中信息传输率：,单位是比特,/,码符号,无单位,举例,将信道中平均每个符号所能传送的信息量定义为信道的信息传输率,R,序列,序列概率,即时码,a1a1,9/16,0,a1a2,3/16,10,a2a1,3/16,110,a2a2,1/16,111,编码效率,：信源的平均符号熵是采用了平均符号码长来编码后得到的效率。,二元码编码后的信息传输率和编码效率在数值上是相等的,比,较,若对这一信源采用定长二元码编码，要求编码效率达到,96%,，允许译码错误概率,定长码需要的信源序列长，使得码表很大，且总存在译码差错；,而变长码编码效率达到,96%,时，只需要,L=2,，而且可实现无失真编码，编码后的信息传输率,R,也越来越接近无噪 无损二元信道的信道容量,C=1bit/,符号,通过对扩展信源进行编码，可以提高编码后的信道的信息传输率,最佳变长编码,香农编码方法,费诺编码方法,哈夫曼编码方法,5.2,无失真信源编码,凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为,最佳变长码,。,下面介绍几种最佳变长编码均为统计匹配编码，都是对出现概率较高的信源符号编短码，而对出现概率较小的信源符号编长码，从而使,平均码长最短,，达到最佳编码的目的。,香农编码,设有离散无记忆信源,香农编码方法的步骤,按信源符号的概率从大到小的顺序排队,设,按下式依次计算每个信源符号的二元码码长,为了变成唯一可译码，计算第,i,个消息的累加概率,将累加概率变成二进制小数，取小数点后 数作为第,i,各信源符号的码字,举例,设,有一单符号离散无记忆信源,试,对该信源编二进制香农码。,解答：,信源消息符号,ai,符号概率,p(ai),累加概率,Pi,-logp(ai),码字长度,Ki,码字,a1,0.20,0,2.34,3,000,a2,0.19,0.2,2.41,3,001,a3,0.18,0.39,2.48,3,011,a4,0.17,0.57,2.56,3,100,a5,0.15,0.74,2.74,3,101,a6,0.10,0.89,3.34,4,1110,a7,0.01,0.99,6.66,7,1111110,费诺编码,按信源符号的概率从大到小的顺序排队,将依次排列的信源符号按概率值分为两大组，使两大组概率之和近似相同，并对各组赋予一个二进制码元,”0”,和,”1”,；依次重复上述操作，直到每个组只剩下一个信源符号为止。,信源符号所对应的码字即为,费诺码,。,编码步骤如下：,举例,与香农编码例子相同,消息符号,ai,符号概率,p(ai),第一次分组,第二次分组,第三次分组,第四次分组,二元码字,码长,Ki,a1,0.20,0,0,00,2,a2,0.19,1,0,010,3,a3,0.18,1,011,3,a4,0.17,1,0,10,2,a5,0.15,1,0,110,3,a6,0.10,1,0,1110,4,a7,0.01,1,1111,4,费诺码比香农码的平均码长小，消息传输速率大，编码效率高！,哈夫曼编码,按信源符号的概率从大到小的顺序排队,编码步骤如下：,取两个概率最小的字母分别配以,”0”,和,”1”,两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进制符号的字母重新排队；对重排后的两个概率最小符号重复上述操作。依次重复上述操作，直到最后两个符号配以,0,和,1,为止。,从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。,举例,与香农编码例子相同,消息符号,ai,符号概率,p(ai),编码过程,二元码字,码长,Ki,a1,0.20,0.20,0.26,0.35,0.39,0.61,10,2,a2,0.19,0.19,0.20,0.26,0.35,0.39,11,2,a3,0.18,0.18,0.19,0.20,0.26,000,3,a4,0.17,0.17,0.18,0.19,001,3,a5,0.15,0.15,0.17,010,3,a6,0.10,0.11,0110,4,a7,0.01,0111,4,0,1,0,1,0,1,0,1,0,1,0,1,每次相 加时都将“,0”,和“,1”,赋与相加的两个概率，,读出时,由该符号开始一直走到最后的“,1”,， 将路线上所遇到的“,0”,和“,1”,按最低位到最高位的顺序排好，就是该符号的霍夫曼编码。,总结,比,较,编码,平均码长,信息传输率,香农码,3.14,0.831,费诺码,2.74,0.953,霍夫曼编码,2.72,0.96,上述几种编码都是针对离散无记忆信源的单个信源符号的编码，因此在编码时没有考虑信源符号之间的相关性。,霍夫曼码是最佳码，但实际使用时霍夫曼编码的设备还是比较复杂的。一般只适用于已知其统计特性的信源。若信源的统计特性不知或发生变化时，则采用所谓的通用编码方法。,霍夫曼编码,游程编码,基本原理,：用一个符号值或串长表示连续出现的信源符号,(,这些连续出现的信源符号构成了一段连续的“游程”,),，使码符号序列长度少于原始信源符号序。,符号码,标识码,游程长度,举例,：二元序列,000101110010001,变换成游程序列,31132131,0,游程和,1,游程是交替出现的,范围,：游程编码只适用于二元序列，对于多元信源，一般不直接利用游程编码。,5.3,常用信源编码方法简介,算术编码,编码基本思路,：,从全序列出发，将各信源序列的概率映射到,0,，,1,区间上，使每个序列对应着区间内的一点，也就是一个二进制的小数。这些点把,0,，,1,区间分成许多小段，每段的长度等于某一序列的概率。再在段内取一个二进制小数，其长度可与该序列的概率匹配，达到高效率编码的目的。,5.3,常用信源编码方法简介,举例,：,5.3,常用信源编码方法简介,第一个符号,a1,的概率区间,前两个符号,a1a3,的概率区间,符号,a1a3a4,的概率区间,设,N,长信源符号序列,s,的概率,p(s),和累积概率,F(s);,递推出,N+1,长信源符号序列,sr,的概率,p(sr),和累积概率,F(sr);r,为新添加的符号,LZW,编码,对于统计特性不可知时，需要用到具有自适应性能的通用编码方法，,LZW,编码就是一种基于字典的编码方法。,5.3,常用信源编码方法简介,LZW编码步骤,如下：,1、初始化字典，读入一个字符放入W中。,2、读入,一,个字符K：,1不存在字符K可读：输出W对应的字码。结束编码。,2WK在字典中：将K加入到W末尾。,3WK不在字典中：将字码W输出，然后将WK加入字典，并令W为K。,LZW,编码,LZW,解码步骤如下：,1,、初始化字典，读入一个字码,W,。,2,、读入一个字码,K,：,1,不存在字码,K,可读：输出,W,对应的字符（串）。结束解码。,2,存在字码,K,可读：在,W,对应的字符（串）末尾加入字码,K,的第一个字符，形成的字符串加入字典。然后输出,W,对应的字符（串），把,K,的值给,W,。,字符串,索引,字符串,索引,a,0H,LZW-CLEAR,2H,b,1H,LZW-EOI,3H,行号,输入数据,S2,S1+S2,输出结果,S1,生成新字符及索引,1,NULL,NULL,3H,NULL,2,a,a,a,3,a,aa,0H,a,aa(4H),4,b,ab,0H,b,ab(5H),5,b,bb,1H,b,bb(6H),6,b,bb,bb,7,a,bba,6H,a,bba(7H),8,a,aa,aa,9,b,aab,4H,b,aab(8H),10,b,bb,bb,11,6H,12,3H,输出,LZW-CLEAR,在字串表中的索引,3H,读取一个字符,a,，将其赋予字符串变量,S2,，判断,S1+S2=a,在字符表中，则,S1=S1+S2,=a,读取下一个字符,a,，将其赋予字符串变量,S2,，判断,S1+S2=aa,不在字符表中，则,S1=a,在字符串表中的索引,0H,，并在字串表末尾为,aa,添加索引,4H,，且,S1=S2=a,读取下一个字符,b,，将其赋予字符串变量,S2,，判断,S1+S2=ab,不在字符表中，则,S1=a,在字符串表中的索引,0H,，并在字串表末尾为,ab,添加索引,5H,，且,S1=S2=b,5.3,常用信源编码方法简介,编码模拟：,ababcbababaaaaaaa,0,1,3,2,4,7,0,9,10,0,编码,字符（串）,0,a,1,b,2,c,3,ab,4,ba,5,abc,6,cb,7,bab,8,baba,9,aa,10,aaa,11,aaaa,预测编码和变换编码,在信息论中，对于相关性很强的信源，条件熵可远远小于无条件熵，因此人们常采用尽量,解除相关性的办法,，使信源输出转化为独立序列，以利于进一步压缩码率。,5.3,常用信源编码方法简介,常用的解除相关性的两种措施是预测和变换。,预测编码,是从已受到的符号来提取关于未收到的符号的信息，从而预测其最可能的值作为预测值；并对它与实际值之差进行编码，达到进一步压缩码率的目的。,变换编码,是经变换后的信号的样值能更有效地编码，通过变换来解除或减弱信源符号间的相关性，再将变换后的样值进行标量量化，或采用对于独立信源符号的编码方法，以达到压缩码率的目的。,估计理论,作业,5-1,，,5-3,，,5-55-7,，,5-10,，,5-11,5-14,，,5-16,5.3,常用信源编码方法简介,