信息论与编码理论-第三章.ppt
第三章 信源编码（一）离散信源无失真编码,3.1 信源及其分类3.2 离散无记忆信源的等长编码3.3 离散无记忆信源的不等长编码3.4 最佳不等长编码,3.1 信源及其分类,信源及其分类,离散信源 U-2,U-1,U0,U1,U2,，Ul取自字母表A无记忆信源:Ul彼此独立有记忆信源：Ul彼此相关简单信源：Ul独立同分布平稳信源，各态历经源M阶记忆源（有限状态马尔可夫链）连续信源时间离散连续源随机波形源,3.2 离散无记忆源的等长编码,离散无记忆源,字母表A=a1,aK,概率p1,pK,长为L的源输出序列uL=u1,uL，共有KL种序列码符号字母表B=b1,bD,以码符号表示源输出序列，D元码等长D元码，不等长D元码单义可译码，每个消息都至少有一个码字与之对应。单义可译码存在充要条件DNKL NLlogK/logD,DMS的等长编码,NlogDLH(U)H(U)是统计平均值，L达到无限时，一个具体的源输出序列的平均每符号的信息量才等于H(U)选L足够长，使 NlogDLH(U)+eL,DMS序列的自信息量,弱、强e典型序列集,信源划分定理,典型序列集,非典型序列集,序列集合,典型序列的比例,编码速率和等长编码定理,R=(1/L)logM=(N/L)logD,M为码字总数定义：对于给定信源和编码速率R以及任意e0，若有L0,以及编译码方法，使得LL0,错误概率小于e，R是可达的等长编码定理 RH(U),R是可达的，RH(U)是不可达的编码效率=H(U)/R,3.3 DMS的不等长编码,平均码长,几个定义,唯一可译码逗点码，无逗点码字头或前缀异字头码或异前缀码树码，满树，非满树，全树树码构造异字头码,例子,ShannonFano编码,D元码每次信源符号化为概率近似相等的D个子集这样可以保证D个码元近似等概，每个码字承载的信息量近似最大，码就近似最短。理想情况I(ak)=nklogD,p(ak)=D-nk,Kraft不等式,长度为n1，n2，nK的D-元异字头码存在的充分必要条件是,二元异字头码Kraft不等式等号成立,定理:任意唯一可译码必满足Kraft不等式,不等长编码定理,编码速率,3.4最佳不等长编码,Huffman编码的最佳性,所谓最佳：是指在所有可能的编码方法中，其编码得到的平均码长最短。定理：对于给定信源，存在有最佳惟一可译二元码，其最小概率的两个码字CK-1和CK的长度最长且相等，它们之间仅最后一位码元取值不同(一个为0，另一个为1)。,Huffman编码的最佳性,对信源可对aK-1和aK的码字的最后一位分别指定为1和0，然后作一辅助集,Huffman编码的最佳性,定理3.4.2 对辅助集U 为最佳的码，对原始消息集U也是最佳的。若C1，C2，CK-1是对辅助集U 的最佳码，相应码长为n1，n2，nK-1，则对U的码字C1，C2,CK的码长为nk=nk kK2nk=nK-1+1 k=K,K1,Huffman编码的最佳性,例：Huffman编码过程,例：Huffman编码过程,Shannon-Fano编码例子,cabcedeacacdeddaaabaababaaabbacdebaceada 共40个字母频度a-16，b-7，c-6，d-6，e-5 1)将给定符号按照其频率从大到小排序。a-16 b-7 c-6 d-6 e 52)将序列分成左右两部分，使得左部频率总和尽可能接近右部频率总和。有：(a,b),(c,d,e),Shannon-Fano编码例子,3)我们把第二步中划分出的上部作为二叉树的左子树，记 0，下部作为二叉树的右子树，记 1。4)分别对左右子树重复 2 3 两步，直到所有的符号都成为二叉树的树叶为止。,b,a,c,d,e,0,0,1,0,1,0,1,1,a 00b 01c 10d 110e 111,Shannon-Fano编码例子,编码结果Cabcedeacacdeddaaabaababaaabbacdebaceada10 00 01 10 111 110 111 00 10 00 10.长91bit采用3bit等长编码需120bit采用ASCII码需要320bit,采用Huffman编码,a 16,b 7,c 6,d 6,e 5,11,13,24,0,1,0,1,0,1,0,1,a 0,b 100,c 101,d 110,e 111,总比特数88，信源熵为86.601bit,Huffman编码,Shannon-Fano编码构造二叉树是自树根到树叶，很难保证最佳性。Huffman编码则是从树叶到树根，是最佳的,总结,Huffman需要知道信源的概率分布，这在实际中有时是比较困难的。采用半静态模型、自适应模型、markov模型，部分匹配预测模型等等解决这一问题。,D元Huffman编码,共有K个符号，概率最小的R个符号码长最长K+B=D+m(D-1)注意BD-1 K-2=m(D-1)+D-2-B,B个,R个,B=D-2-(K-2)mod(D-1)R=2+(K-2)mod(D-1),Shannon-Fano-Elias编码,累计分布函数,修正累计分布函数,Shannon-Fano-Elias编码,采用 的数值作为ak的码字码长,Shannon-Fano-Elias编码,Shannon-Fano-Elias编码,算术码,应用于JPEG2000,H.263等图像压缩标准,算术码,信源序列(u1u2un)的累计分布算术编码是计算序列的累计分布，用累计分布值表示序列，所以称为算术编码以二元信源输出序列的编码为例01110,算术码,P(010),P(011),F(011),P(0110),P(0111),F(0111),P(01110),P(01111),F(01111),算术码,信源符号序列u对应区间的宽度等于符号序列的概率,算术编码,F(u)将0,1)分割成许多小区间，取小区间内的一个点代表该序列，以该点数值的二进制小数表示该序列，码字长度为,算术编码,例：,P(0)=0.25,P(1)=0.75,u=11111100 P(u=11111100)=0.7560.252L=7F(sC=1101010编码效率92.7%,LZ编码,利用字典编码方法信源符号A=(a1aK)将序列分为不同的段取最短长度的连续符号构成段，保证互不相同。先取一个符号分段，若与前面段相同，就再取一个符号，直至序列结束得到字典表，码字由段号加后一个符号组成。单符号的码字，段号为0,LZ编码,LZ编码,00000 00110 00011 00001 10000 00100 01110,1 2 3 4 5 6 7,LZ编码,设长为L的信源序列u分为M(u)个码段，每段短语的二元码符号长度为总码长平均,+,LZ编码,设长度为l段有Kl种。若把长为L的信源序列u分为M(u)个码段后，设最长的段长为lmax，而且所有小于等于lmax 的段型全部都有，则,LZ编码,典型段，ak出现的次数为lmaxp(ak),LZ编码,设较短的段型忽略不计,
