信息与通信信源编码课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,Efficiency vs.Reliability,Efficiency,Average code length as small as possible,Reliability,The ability to recover from errors in the transmission,Coding,Decoding,Information,source,Source,coding,Channel,coding,Information,channel,Channel,decoding,Source,decoding,Destination,Efficiency vs.ReliabilityEffi,提要,1,基本概念,2,基本定理：变长编码定理,3,即时码（非续长码）,4,仙农,-,费诺（,Shannon-Fano,）法,5,霍夫曼（,Huffman,）法,*,6,数据压缩的分类与国际标准简介,1,基本概念,编码：,利用编码符号集对消息符号集进行的某种变换。,例,汉字电报,汉字符号,标准电码五单元电码，即,汉字,0,，,1,，,2,，,，,9 0,，,1,（,5,位,0,、,1,表示一个数字）,0 01101,，,1 01011,，,2 11001,，,，,4 11010,，,，,8 01110,，,9 10011,中（,0022,）国（,0948,）,01101 01101 1101 1101 01101 10011 11010 01110,2,信源编码：,又称,数据（语音、图象、文本）压缩,，目的在于减少数字信息中的冗余度，提高通信或存储的有效性,连续信源编码,：,（,A,）,A/D,转换（不讨论）；（,B,）去冗余度。,离散信源的统计特性：,离散消息,-,在有限符号集中选取若干个符号组成的随机序列；,形成消息时，各符号出现的概率不同；,组成消息的符号之间有一定的相关性。,信源的最佳编码：,在保证信息量不变（或在允许一定的失真度）条件下，使各码字的平均长度最短，即每个码元所含的平均信息量最大。,2 信源编码：又称数据（语音、图象、文本）压缩，目的在于,2,无干扰离散信道的信源编码定理,（仙农第一定理，仙农无失真信源编码定理）,传输效率：,实际传信率（,R,）与信道容量之比，即信道容量 的利用率。,=R/C,对于无干扰（无噪声）信道，,=,实际信源熵,/,最大信源熵,=,H,0,(X)/max H(X),问：,能达到多大？,2 无干扰离散信道的信源编码定理,2 ,仙农第一定理,：设离散无记忆,信源熵为,H(X),，经容量为,C,（,bit/,符号）的无干扰信道传输，则总可以找到某种编码方法对信源的输出进行编码，使其在信道中的传信率任意地接近于信道容量,C,（正定理）。,（证明略）,逆定理：不存在任何编码方法，使传信率,R,大于等于,C,。,3,信源编码器的作用：,改造信源，使,H,（,X,）最大化，从而使,1,，,1,的过程就是使信源最佳化的过程。,信源编码又称为使,信源与信道匹配,的最佳编码。,类比：,2 仙农第一定理：设离散无记忆信源熵为H(X)，经容,信源,又分为,有记忆信源,与,无记忆信源,：,有记忆信源,-,信源发出的符号前后有关连，一个符号的出现会影响另一个符号的出现。,无记忆信源,-,符号之间是独立的，一个符号出现的概率与前面出现的符号有关。,H(X),最大化包含两个步骤：,(1),符号独立化，除符号之间的相关性；,(2),各符号概率均匀化。,本章只考虑无记忆离散信源的编码，不考虑步骤（,1,）。,信源又分为有记忆信源与无记忆信源：,3,编码效率及变长编码定理,最小平均码长与编码效率,平均码长,:,可以证明，码字的平均长度,（,1,）最小平均码长,3 编码效率及变长编码定理可以证明,若,D=2,，则,（,2,）编码效率：,（,3,）编码剩余度：,例,一个离散信源输出为,4,个长度均为,1,的符号，每个符号出现的概率分别为,1/2,，,1/4,，,1/8,。,1/8,，求平均码长与编码效率。,若D=2，则（2）编码效率：（3）编码剩余度：例 一个离散,解,:,解:,信源编码的必要性,:,实际信源往往含有大量冗余,比如,英文字母表,(,含空格符,),共,27,个符号,若等概出现,则每个符号的信息量为,4.76bit,而在无记忆情况下实际信源熵只有,4.076bit/,符号,若考虑两个字母之间的相关性，则实际熵只有,3.32bit/,符号,;,若考虑,100,个字母之间的相关性,则实际信源熵只有,1bit/,符号,此时编码剩余度为,79%!,如何编码才能使平均码长最短？,一般离散信源各符号出现的概率并不相等,由,可知,概率大的符号编短码,概率小的编长码,就可以使平均码长最短,.Morse,电报就采用这种方法,.,信源编码的必要性:可知,概率大的符号编短码,概率小,信息与通信信源编码课件,编码方法,例,一个离散信源由,4,个符号,S1,S2,S3,S4,组成,其出现的概率分别为,0.6,0.2,0.2,0.1,和,0.1,试用不同的方法编码,并加以比较,.,编码方法,码（,1,）：,若发,S4S1=,（,110,），接收时既可译成,11,，,0=S4S1,，,也可译成,110=S3,，不唯一可译；,码（,2,）：,等长码，唯一可译，效率较低；,码（,3,）：,每码字均以,0,结尾，称为逗点码，唯一可译，且可随收随译；,码（,4,）：,以,0,开头，须等待下一个,0,到来时才能开始译；,码（,5,）：,立即可译。,码（1）：若发S4S1=（110），接收时既可译成11，0=,编码的一般原则,:,须唯一可译,;,(2),概率大的用短码,概率小的用长码,;,(3),码字之间不用空格符就能区分,;,(4),须立即可译,.,变长编码定理,:,若离散信源的熵为,H(X),每个信源符号用,D,进制符号进行编码,则存在某种编码方法,其码字平均长度满足,编码的一般原则:,对于,二进制编码,(D=2),则有,(2),对于,L,次扩展信源,则有以下关系,对于二进制编码(D=2),则有(2)对于L次扩展信源,注,:(1),该定理只是一个极限定理，必须在,L,为无穷时才能达到理论情况；,(2),某些信源（如语音、图象等）在实际应用中往往允许一定的失真（不研究）。,注:(1)该定理只是一个极限定理，必须在L为无穷时才能,信息与通信信源编码课件,4,即时码（非续长码、非延长码）,1,唯一可译码（单义码）与即时码,编码,-,等长码，变长码,等长码：效率低，简单、方便,变长码：效率高，但码字区分困难,要求：,唯一可译；,即时性,-,可边收边译，不必等待。,（,1,）唯一可译码（单义码）：,只能译出一种结果,例,C,1,=,1,，,01,，,00,接收序列,10001101,（唯一译成）,1,，,00,，,01,，,10,，,1,（唯一可译码，单义码）,4 即时码（非续长码、非延长,C,2,=,0,，,10,，,01,接收序列,01001,（既可译成）,01,，,0,，,01,（也可译成）,0,，,10,，,01,（不唯一可译，非单义码）,（,2,）即时码（非续长码）：,收到一个码字就能译出，不必等待与观察后面接收的是什么符号。,例 （,1,）,C,1,=S,1,，,S,2,，,S,3,，,S,4,=0,，,01,，,011,，,111,接收序列：,0111101101,若边收边译：,0,，,111,，,1,译不下去了,若收完后再译（从后往前）：,01,，,111,，,011,，,01,唯一可译，但需要等待,（,2,）,C,2,=S,1,，,S,2,，,S,3,，,S,4,，,S,5,=00,，,01,，,10,，,110,，,111,接收序列：,110101110100 110,，,10,，,111,，,01,，,00,（唯一可译码）,C2=0，10，01,（,3,）即时码与唯一可译码（单义码）之间的关系：,即时码一定是唯一可译码（单义码），但唯一可译码（单义码）不一定是即时码。,即时码存在的充要条件,（,1,）即时码存在的充要条件（从结构上）：,即时码中,任何一个码字都不能是另一个码字的开头（前缀）,，或者说,任何一个码字都不能是另一个码字的延续（延长）,，因而这种码又称为,非续长码,。,（,2,）即时码存在的充要条件（从码长上）：,存在,N,个码长为,n,i,（,i=1,2,n,）的即时码的充要条件是,(D,是编码符号集中符号的数目，即编码采用的进制）,（3）即时码与唯一可译码（单义码）之间的关系：(D是编码符号,信息与通信信源编码课件,信息与通信信源编码课件,信息与通信信源编码课件,信息与通信信源编码课件,信息与通信信源编码课件,例 已知：信源,X=x,1,x,2,x,7,，采用,2,进编码，编出的码长分,别为，,n,i,=2,2,3,3,3,4,5,试判断是否存在这样的即时码。,解：,例 设,w,i,表示码长为,i,的码字数目,且,w,1,=0,w,2,=3,w,3,=0,w,4,=5,求：能编成即时码的,D,的最小值。,解：,例 已知：信源X=x1,x2,x7，采用2进编码,即时码的编译码,编码器的描述,（,1,）即时码的编码（码树法）,例,设,A=0,，,1,，将,X=x,1,x,2,x,3,x,4,编成码长分别为,1,，,2,，,3,，,3,的即时码。,解：,D=2,原则：任何一个码字不能作为另一个码字的开头,即时码的编译码（1）即时码的编码（码树法）原则：任何一个码字,用码树图编码的步骤：,从顶点（树根）出发，画出两条（,D=2,）分枝，一条代表“,0”,，另一条代表“,1”,。选取其中的一个终点作为码字，如,w,1,=0;,从未被选用的终点再画出两枝，选其中的一个终点作为码字,w,2,;,继续下去，直至,W,中所有的码字都有一个终点来表示为止；,从树根出发到各个终点，依次读出各枝代表的符号（,0,，,1,），便得到相应的码字。,w,1,=0,W,2,=10,W,3,=110,W,4,=111,用码树图编码的步骤：w1=0,(2),即时码的译码,例,在上例中，若收到一串码字,100110010,，试用码树进行译码。,解：,译码方法：,顺着码树走，遇到一个终点便得到一个码字，然后再回到树根，从头开始走，直至全部码序列都译完为止。,译码结果：,W,2,W,1,W,3,W,1,W,2,，即,10,，,0,，,110,，,0,，,10,(2)即时码的译码译码方法：顺着码树走，遇到一个终点便得到一,紧致即时码：,平均码长刚好等于信源熵的即时码，其编码效率为,100%,。,1963,年,Abramson,发现，若符号出现的概率为,，取码字长度为,n,i,便能编出紧致即时码。,例,设信源源不断个符号出现的概率分别为,1/2,，,1/4,，,1/8,，,1/8,，试编成紧致即时码，并将其平均码长与信源熵进行比较。,解：,由,知，,4,个码字的长度分别选为,1,，,2,，,3,，,3,，编码后得到的码字分别为,0,，,10,，,110,，,111,。,紧致即时码：平均码长刚好等于信源熵的即时码，其编码效率为10,5,仙农,-,费诺（,Shannon-Fano,）编码法,最佳编码,-,按概率匹配的原则，概率大的编短码，概率小的编长码，使在给定信息量的条件下，平均码长最短。,两种最佳编码法：,仙农费诺法，霍夫曼（,Huffman,）法,.,仙农,-,费诺编码法,5 仙农-费诺（Shannon-Fano）,信息与通信信源编码课件,信息与通信信源编码课件,仙农,-,费诺法的编码步骤：,（,1,）将信源符号按概率由大到小排列；,（,2,）将全部信源符号分成概率和大致相等的两个（,D=2,）组，分别赋予“,0”,，“,1”,；,（,3,）再按（,2,）的方法对各组进行处理，直至每个符号被分割出来为止；,（,4,）按编码过程顺序读出各符号相应的码元，便得到对应的