第5章无失真信源编码定理课件

Click to edit Master title style,Click to edit Master text styles,Second Level,Third Level,Fourth Level,Fifth Level,信息论课件,通信与信息基础教学部,*,信息论课件,通信与信息基础教学部,Click to edit Master title style,Click to edit Master text styles,Second Level,Third Level,Fourth Level,Fifth Level,*,1,第5章 无失真信源编码,5.1 编码器,5.2 等长码,5.3 渐进等分割性和e典型序列*,5.4 等长信源编码定理,5.5 变长码,5.6 变长信源编码定理,1第5章 无失真信源编码5.1 编码器,2,5.1 编码器,对整个通信系统来说，要解决两个问题：信源编码和信道编码。,对信源来说有两个重要问题：一个是信源输出信息量的定量度量问题。这在前面信源及其信息熵章中已讨论。本章将要讨论第二个问题：如何有效地表示信源输出问题。即将重点讨论对信源进行无失真信源编码的要求、方法及理论极限，从而得出香农第一定理。,25.1 编码器对整个通信系统来说，要解决两个问题：信源编码,3,编码器的描述,码元,码字,码,码长,l,码符号集,3编码器的描述码元码字码码长 l码符号集,4,信源编码器的,主要任务,：完成输入消息集合与输出代码集合之间的,映射,。若要实现无失真编码，则这种,映射必须是一一对应的、可逆的。,4信源编码器的主要任务：完成输入消息集合与输出代码集合之间的,5,常用码型,1、,二元码,：,若信道码符号集,A=,0,，,1,，编码输出的码字都是二元码，称为二元码。,2,、,等长码：,若一组码中所有码字的码长都相同，称为等长码。,3,、,变长码：,若一组码中所有码字的码长,Ki,各不相同，即任意码字由不同长度的码符号序列组成，则称为变长码。,5常用码型1、二元码：若信道码符号集A=0，1，编码输,6,常用码型,4、,非奇异码和奇异码：,若一组分组码中的所有码字都不相同，即所有信源符号映射到不同的码字。称此分组码为非奇异码。否则为奇异码,5,、,同价码和非同价码,：,若每个码符号的传输时间都相同则称为同价码。否则为非同价码,6常用码型4、非奇异码和奇异码：若一组分组码中的所有码字都不,7,常用码型,6、码的,N,次扩展码：,假使某分组码,W，,把信源,X,中的符号,xi,一一变换成码,W,中的码字,Wi,字，则码,W,的,N,次扩展码是,N,个码字组成的码字序列的集合。,7常用码型6、码的N次扩展码：假使某分组码W，把信源X中的符,8,例：,设信源,X,的概率空间为,若把该信源通过一个二元信道进行传输，为适合信道传输，就必须把信源符号,xi,变换成0、1符号组成的码序列（二元序列）。可采用不同的二元序列使其与信源符号,si,一一对应，所以可有多种方法得到二元码。如表4.1所示,8例：设信源X的概率空间为若把该信源通过一个二元信道进行传输,9,表,5.1,信源,X,的两种不同编码码字,现求码,S2,的二次扩展码。,9表5.1 信源X的两种不同编码码字 现求码S2的二次扩展,10,常用码型,7、,唯一可译码：,若码的任意一串有限长的码符号序列只能被唯一地译成所对应的信源符号序列，则此码为唯一可译码。否则，称为非唯一可译码。,唯一可译码的物理含义：,不仅要求不同的码字表示不同的信源符号，而且还进一步要求对由信源符号构成的信息序列进行编码时，在接收端仍能正确译码，而不发生混淆。,本章主要研究的是同价唯一可译码。,10常用码型7、唯一可译码：若码的任意一串有限长的码符号序列,11,5.2,定长码,一般来说，若要实现无失真的编码，所编的码必须是唯一可译码，否则，就会因译码带来的错误与失真。,非奇异定长码的,N,次扩展码一定也是非奇异定长码。,非奇异定长码一定是唯一可译码。,115.2 定长码 一般来说，若要实现无失真的编码，所编的码,12,信源存在唯一可译定长码的条件：,对信源,X,进行等长编码，必须满足,其中,l,是等长码的码长,有,例：英文电报有,32,个符号，即,n,=32,。若对它进行二元编码，则,r,=2,，可得,l,=5,。也就是说，每个英文电报符号至少要用,5,位二元符号编码才行。,12信源存在唯一可译定长码的条件：,13,实际英文电报符号信源，在考虑了符号出现的概率以及符号之间的依赖性后，其信息熵约为,1.4,比特,/,符号，即平均每个英文符号所提供的信息量为,1.4,比特。,因此等长编码后,5,个二元符号只携带约,1.4,比特信息量。,对于无噪无损二元信道，每,5,个二元符号最大能载荷,5,比特的信息量。,因此，如此,等长编码的信息传输效率极低。,13实际英文电报符号信源，在考虑了符号出现的概率以及符号之间,14,5.4,等长信源编码定理,定理4.3一个熵为,H,(,X,),的离散无记忆信源，若对信源长为,N,的符号序列进行等长编码，设码字是从,r,个字母的码符号集中选取,l,个码元组成。对于任意,0,，只要满足,则当,N,足够大时，可实现几乎无失真编码，即译码错误概率能为任意小。,145.4等长信源编码定理定理4.3一个熵为H(X)的离散,15,编码信息率,编码效率,举例：书145页例4.1,15编码信息率编码效率举例：书145页例4.1,16,5.5 变长码,变长码也必须是唯一可译码，才能实现无失真编码。,定义：在唯一可译变长码中，有一类码，它在译码时，无须参考后续的码符号就能立即作出判断，译成对应的信源符号，则这类码称为,即时码,165.5 变长码变长码也必须是唯一可译码，才能实现无失真编,17,一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。故即时码一定是唯一可译码，反之，唯一可译码不一定是即时码。,即时码可用,树图法来进行编码和译码,。,17即时码可用树图法来进行编码和译码。,18,树码：,通过树图法构成的码叫树码,对,r,进制树图，,有树根、树枝和节点,。树图最顶部的节点称为,树根,。,树枝,的尽头称为,节点,，每个节点生出的树枝树目等于码符号树,r,。,即时码的构造,18树码：通过树图法构成的码叫树码即时码的构造,19,19,20,即时码可用,树图法来进行编码和译码,。,构造步骤：,1,、最上端为树根，从根出发向下伸出树枝，树枝总数等于,m,（,码符号数）,，树枝的尽头为节点。,2,、从每个节点再伸出,m,枝树枝，当某节点被安排为码字后，就不再伸枝，这节点为终端节点。能再伸枝的节点称为中间节点。一直继续进行，直到都不能伸枝为止。,3,、每个节点所伸出的树枝标上码符号，从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字。,20即时码可用树图法来进行编码和译码。,21,树码一定是即时码，任一即时码都可用上述树图法来表示。即时码一定是唯一可译码。唯一可译码，不一定是即时码。,21树码一定是即时码，任一即时码都可用上述树图法来表示。即时,22,例：,一信源,X(,x,1,x,2,x,3,x,4),经编码后得码字集合,S,(1,01,001,0001),且一一对应。现接收码元序列为,101110001001101011,，试写出译码结果。,解,：,该编码规则为：,x,1,1,x,2,01,x,3,001,x,4,001,，,每一码字均以,1,结尾，见,1,即可译码。对所接收序列的译码结果为,x,1,x,2,x,1,x,1,x,4,x,3,这种编码，译码时不需要考察后续码元，故又称之为,即时码,。,22例：一信源X(x1,x2,x3,x4)经编码后得,23,编码的树图表示,即时码一定是单义可译码,。,23编码的树图表示 即时码一定是单义可译码。,24,单义可译定理（即时码,存在,的充要条件）,对含有,n,个信源符号的信源用含,r,个符号的码符号集进行编码，各码字的码长为,的唯一可译码存在的充要条件是，满足,Kraft,不等式,含义：,24单义可译定理（即时码存在的充要条件）对含有n个信源符号的,25,例：,信源空间为,X,：,x,1,x,2,x,3,x,4,P,(X),：,1/2,，,1/4,，,1/8,，,1/8,对其进行信源编码，信道基本符号集合为：,m=0,1；,若编码后对应的码长分别为,k,1=1,k,2=2,k,3=3,k,4=3，,问能否构造出一种即时码？,解：,将,m,=2,n,=4,和,ki,的4个值带入,Kraft,不等式,得,满足,Kraft,不等式，所以一定能构成至少一种即时码,25例：信源空间为 X：x1,x2,26,26,27,唯一可译码的判断法,应该注意的是克拉夫特（,Kraft,）,不等式只是给出来即时码或唯一可译码存在的充分必要条件，,但该定理并不能作为判别一种码是否为即时码或唯一可译码的依据。,即唯一可译码（或即时码）一定满足不等式，反之，满足不等式的码不一定是唯一可译码。,例：,码字（,0,，,10,，,010,，,111,），满足克拉夫特不等式，但它不是唯一可译码。,27唯一可译码的判断法应该注意的是克拉夫特（Kraft）不等,28,唯一可译码的判断步骤：,1,、观察是否是非奇异码。若是奇异码则一定不是唯一可译码。,2,、计算是否满足,Kraft,不等式，若不满足一定不是唯一可译码。,3,、将码画成一棵树图，观察是否满足即时码的树图构造，若满足则是唯一可译码。,4,、直接用判别测试算法：,28唯一可译码的判断步骤：1、观察是否是非奇异码。若是奇异,29,5.6变长信源编码定理,设信源 有,n,个离散符号，编码后的码字为,其码长分别为,对于唯一可译码来说，信源符号与码字一一对应，所以有,则这个码的,平均长度,为,295.6变长信源编码定理设信源,30,码的平均长度是每个信源符号平均需用的码元数。平均每个码元携带的信息量即编码后信道的信息传输率为,若要信息传输效率高，需寻求使平均码长最短的码，即,紧致码,，或称,最佳码,。,30码的平均长度是每个信源符号平均需用的码元数。平均每个码元,31,平均码长可能达到的理论极限,定理：若一离散无记忆信源,X,具的熵为,H,(,X,),，并有,r,个码元的码符号，则总可以找到一种无失真编码方法，构成唯一可译码，使其平均码长满足,无失真变长信源编码定理,香农第一定理,31平均码长可能达到的理论极限定理：若一离散无记忆信源 X,32,编码效率：,码的剩余度：,二元无噪无损信道中信息传输率,32编码效率：,33,例：有一离散无记忆信源,其熵为,H,(,X,)=0.811,比特/信源符号。,用二元码构造一个非续长码：,x,1,0，,x,2,1,这时平均码长 ，,编码效率,信道信息传输率为,33例：有一离散无记忆信源,34,对该信源的二次扩展信源进行编码如下,这个码的平均长度,得信源中每一个单个符号的平均码长,编码效率,信道信息传输率为,同样可得,34对该信源的二次扩展信源进行编码如下,35,香农第一定理仅是一个存在性定理，指出了平均码长与信源熵之间的关系，但没有给出如何构造的信息。,用前述例子的编码方法虽然可以得到即时码，但通常不是最佳编码，故有必要寻求更高效率的编码方法。,35香农第一定理仅是一个存在性定理，指出了平均码长与信源熵之,