资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,2024/11/15,1,Your time is limited,so dont waste it living someone elses life.,Dont let the noise of others opinions drown out your own inner voice,。,-,Steve Jobs,2024/11/15,2,离散无失真,信源编码定理,2024/11/15,3,4.1,离散无失真信源编码定理,4.1.1,问题的提出,4.1.2,定长,/,等长,编码定理,4.1.3,变长编码定理,2024/11/15,4,4.1.1,问题的提出,(1),为什么要进行信源编码,(2),信源编码的概念,(3),一些码的定义,(4),信源编码的方法,2024/11/15,5,(1),为什么要进行信源编码,信源的两个重要问题,信源输出的,信息量计算,问题；,如何更有效地表示,信源输出,的问题。,为什么要进行信源编码,人们都希望,无失真传送,，首先要对信源无差错编码；,数字技术应用越来越多，模拟信源通过数字化变成,数字信号传送,。,2024/11/15,6,(2),信源编码的概念,信源编码定义：,指定能够满足信道特性,/,适合于信道传输,的符号序列,/,码序列,，来代表信源输出的消息。,完成编码功能的器件称为编码器。,离散信源输出的码序列,离散信源输出的消息是由一个个离散符号组成的随机序列,X,=(,X,1,X,2,X,l,X,L,),X,l,x,1,x,2,x,i,x,n,信源编码就是把信源输出的随机符号序列变成码序列,Y,=(,Y,1,Y,2,Y,k,Y,K,),Y,k,y,1,y,2,y,j,y,m,2024/11/15,7,研究信源编码时，将信道编码和译码看成是信道的一部分，而突出信源编码；,研究信道编码时，将信源编码和译码看成是信源和信宿的一部分，而突出信道编码。,2024/11/15,8,讨论无失真信源编码可以先不考虑抗干扰问题，所以它的数学模型比较简单，如下图。,2024/11/15,9,码符号,/,码元：,编码器的输入是信源符号,x,1,x,2,x,i,x,n,，同时存在另一符号，,y,1,y,2,y,j,y,m,，,一般元素,y,j,是适合信道传输的,称为码符号,/,码元。,编码器功能：,将信源符号集中的符号（或者长为,L,的信源符号序列）变换成由,y,j,(,j,=1,2,m,),组成的长度,k,i,为的序列。,码字：,码符号序列,Y,=(,Y,1,Y,2,Y,k,Y,ki,),称为码字。,码长,/,码字长度：,k,i,称为码字长度或简称码长。,编码就是从信源符号到码符号的一种映射。若要实现无失真编码，这种映射必须是一一对应的，可逆的。,2024/11/15,10,(3),一些码的定义,二元码：,码符号集为,X,=0,1,，所得码字都是一些二元序列。,定长码,/,等长码,：,一组码中所有码字的码长都相同，即,k,i,=,K,(,i,=1,2,n,),。,变长码：,一组码字中所有码字的码长各不相同，即任意码字由不同长度的码符号序列组成。,非奇异码：,一组码字中所有码字都不相同，即所有信源符号影射到不同的码符号序列。,奇异码：,一组码中有相同的码字。,惟一可译码,/,单义可译码：,码的任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号。,2024/11/15,11,码字与信息率的关系,有时消息太多，不可能或者没必要给每个消息都分配一个码字；,给多少消息分配码字可以做到几乎无失真译码？,传送码字需要一定的信息率，码字越多，所需的信息率越大。编多少码字的问题可以转化为对信息率大小的问题；,信息率越小越好，最小能小到多少才能做到无失真译码呢？,这些问题就是信源编码定理要研究的问题。,2024/11/15,12,(4),信源编码的方法,信源编码有定长和变长两种方法。,定长编码,：,码字长度,K,是固定的，相应的编码定理称为定长信源编码定理，是寻求最小,K,值的编码方法。,变长编码,：,K,是变值，相应的编码定理称为变长编码定理。这里的,K,值最小意味着数学期望最小。,2024/11/15,13,4.1.2,定长编码定理,(1),定长编码定理,(2),举例,2024/11/15,14,(1),定长编码定理,定长编码定理,：,一个熵为,H,(,X,),的,离散无记忆信源,X,1,X,2,X,l,X,L,，若对信源长为,L,的符号序列进行定长编码，设码字是从,m,个字母的码符号集中，选取,K,个码元组成,Y,1,Y,2,Y,k,Y,K,。对于任意,0,，,0,只要满足,(,K,/,L,)log,2,m,H,(,X,)+,则当,L,足够大时，必可使译码差错小于,，即译码错误概率能为任意小。反之，若,(,K,/,L,)log,2,m,H,(,X,)-2,则不可能实现无失真编码,(,译码失真一定大于,),，而当,L,足够大时，译码错误概率近似等于,1,（译码必定出错）。,2024/11/15,15,定理中的公式改写成,K,log,2,m,LH,(,X,),不等式左边表示长为,K,的码符号序列能载荷的最大信息量，右边代表长为,L,的信源序列平均携带的信息量。所以定长编码定理告诉我们：,只要码字传输的信息量大于信源携带的信息量，总可实现几乎无失真编码,。,2024/11/15,16,可以证明：,信源熵,H,(,X,),就是一个界限,/,临界值。当编码器输出的信息率超过这个临界值时，就能无失真译码，否则就不行。,信源编码定理从理论上说明了编码效率接近于,1,，即,的理想编码器的存在性，代价是在实际编码时,取无限长的信源符号,(,L,),进行统一编码。,2024/11/15,17,给定,和,用上式规定的,L,计算所有可能信源消息的概率，按由小到大的次序排列，选用概率较大的消息进行编码，有编码的消息构成一个集合,A,，直到该集合的概率,p,(,A,)1-,，意味着译码差错概率必小于,，即完成了编码过程；,只要,足够小，就可实现几乎无失真译码，若,足够小，编码效率就接近于,1,。,说明：,定长编码定理是在平稳无记忆离散信源的条件下论证的，但它同样适用于平稳有记忆信源，只是要求有记忆信源的极限熵和极限方差存在即可。对于平稳有记忆信源，定理中的熵应改为极限熵。,2024/11/15,18,(2),举 例,例,3.1,设单符号信源模型为,其信息熵为,H,(,X,)=2.55,(,比特,/,符号,),2,I(,x,i,)=1.323,若要求编码效率为,90%,，,即,译码差错率为,=10,-6,，则,由此可见，在差错率和效率要求都不苛刻的情况下，就必须有,1600,多万个,信源符号一起编码技术实现非常困难。,2024/11/15,19,4.1.3,变长编码定理,(1),基本概念,(2),码数图,(3),克拉夫特不等式,(4),变长编码定理,2024/11/15,20,(1),基本概念,变长编码：,不等长编码允许把等长的消息变换成不等长的码序列。通常把经常出现的消息编成短码，不常出现的消息编成长码。这样可使平均码长最短，从而提高通信效率，代价是增加了编译码设备的复杂度。,例如，在不等长码字组成的序列中要正确识别每个长度不同的码字的,起点,就比等长码复杂得多。,译码延时,/,译码同步,：,接收到一个不等长码序列后，有时不能马上断定码字是否真正结束，因而不能立即译出该码，要等到后面的符号收到后才能正确译出。,不等长编码的优越性,总体上减少码字的长度。,不等长编码的特殊问题,唯一可译性，或者叫做可识别性。对于一个码，如果存在一种译码方法，使任意若干个码字所组成的字母串只能唯一地被翻译成这几个码字所对应的事件序列。这个码就被称为是唯一可译的。,解决方案：适当地编码，使得每个码字都具有识别标记。,(1),基本概念,不等长编码的特殊问题,平均码字长度。设信源随机变量,U,的概率分布为,a,k,p,(,a,k,),k,=1,K,，事件,a,k,对应的码字长度为,n,k,，则平均码字长度为,希望 小。,解决方案：概率大的事件用短码字。,实时译码和容量限制。,(1),基本概念,唯一可译性的两种解决方法,Def.,逗点码,事件与码字一一对应；,每个码字的开头部分都是一个相同的字母串；,这个字母串仅仅出现在码字的开头，不出现在码字的其它部位，也不出现在两个码字的结合部。,则称这个字母串为逗号，称此码为,逗点码,。,逗点码显然是唯一可译的，见到逗号就识别为一个码字的开始。,(1),基本概念,唯一可译性的两种解决方法,Def.,逗点码,Def.,异字头码,事件与码字一一对应；,每个码字都不是另一个码字的开头部分（字头）。,则称此码为,异字头码,/,异前置码,。,异字头码也是唯一可译的，见到一个码字就识别为一个码字。（即时性）,(1),基本概念,2024/11/15,25,例,3.2,码,1,：,显然不是惟一可译码。,x,2,和,x,4,对应于同一码字,“,11”,，码,1,本身是一个奇异码。,码,2,：,是非奇异码，不是惟一可译码。当收到一串码符号,“,01000”,时，可将它译成“,x,4,x,3,x,1,”,，也可译为“,x,4,x,1,x,3,”,，“,x,1,x,2,x,3,”,或“,x,1,x,2,x,1,x,1,”,等，这种码从单个码字来看虽然不是奇异的，单从有限长的码序列来看，它仍然是一个奇异码。,码,3,：,虽然是惟一可译码，但它要等到下一个,“,1”,收到后才能确定码字的结束，译码有延时。,码,4,：,既是惟一可译码，又没有译码延时。码字中的符号,“,0”,起了逗点的作用，故称为,逗点码,。,前缀条件码,/,异前置码,/,异字头码,/,即时码,/,非延长码,：如果一个码的任何一个码字都不是其它码字的前缀。,码,5,是即时码。,2024/11/15,26,(2),码树图,m,元,/,m,进制树图,树根：,最顶部画一个起始点。,树枝：,从根部引出,m,条线段，每条线段都称为树枝。,一级节点：,自根部起，通过一条树枝到达的节点。一级节点最多有,m,个。,n,级节点：,通过,n,条树枝达到的节点。最多有,m,n,。,终节点,/,终端节点,：,下面不再有树枝的节点。,中间节点：,除了树根和终节点以外的节点。,联枝：,串联的树枝。,满树：,在码数图中，,当每一个码字的串联枝数都相同时，就是定长码。此时的码树称为满树。,例如：码长为,N,的满树的终节点个数为,m,N,，即可表示,m,N,个码字。,2024/11/15,27,非满树：,有些树枝未用时的码树。,非满树构造的就是变长码。,如果每一个码字都被安排在终节点上，这种码就是异前置码。,2024/11/15,28,(3),克拉夫特不等式,克拉夫特不等式：,m,元长度为,k,i,，,i,=1,2,n,的异前置码存在的充要条件是,证明：,必要条件：,设异前置码第,i,个码字的长度为,k,i,，,i,=1,2,n,，,构造一个码树图，在第,k,i,级总共有 个节点。第,i,个码字占据了第,k,i,级的 ，根据异前置码的定义，其后的树枝不能再用。,对于,N,级满树，其后不能用的枝数为 ，那么总共不用的枝数为 。,N,级满树第,N,级上的总枝数已知为,m,N,，所以必有 ，两边除以,m,N,，就得,2024/11/15,29,充分条件,如果式 成立，总可以把第,N,级上的树枝分成,n,组，,各组中从第,N,级开始删除,(,i,=1,2,n,),个枝，,相对于,N,级满树，等于删除了所有可能的,k,i,级节点的,，,在该组中以第,k,i,级节点作为终节点，就构造好了第,i,个码字。,对所有码字如法炮制，则总共删除了所有,m,N,个节点中的,。,由于 ，于是构造了一个异前置码。,2024/11/15,30,(4),变长编码定理,变长编码定理,举例,2024/11/15,31,变长编码定理,平均码长：,变长编码定
展开阅读全文