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

《第5章无失真信源编码定理课件.ppt》由会员分享，可在线阅读，更多相关《第5章无失真信源编码定理课件.ppt（35页珍藏版）》请在三一办公上搜索。

1、1,第5章 无失真信源编码,5.1 编码器5.2 等长码5.3 渐进等分割性和e典型序列*5.4 等长信源编码定理5.5 变长码5.6 变长信源编码定理,2,5.1 编码器,对整个通信系统来说，要解决两个问题：信源编码和信道编码。对信源来说有两个重要问题：一个是信源输出信息量的定量度量问题。这在前面信源及其信息熵章中已讨论。本章将要讨论第二个问题：如何有效地表示信源输出问题。即将重点讨论对信源进行无失真信源编码的要求、方法及理论极限，从而得出香农第一定理。,3,编码器的描述,码元,码字,码,码长 l,码符号集,4,信源编码器的主要任务：完成输入消息集合与输出代码集合之间的映射。若要实现无失真编

2、码，则这种映射必须是一一对应的、可逆的。,5,常用码型,1、二元码：若信道码符号集A=0，1，编码输出的码字都是二元码，称为二元码。2、等长码：若一组码中所有码字的码长都相同，称为等长码。3、变长码：若一组码中所有码字的码长Ki各不相同，即任意码字由不同长度的码符号序列组成，则称为变长码。,6,常用码型,4、非奇异码和奇异码：若一组分组码中的所有码字都不相同，即所有信源符号映射到不同的码字。称此分组码为非奇异码。否则为奇异码5、同价码和非同价码：若每个码符号的传输时间都相同则称为同价码。否则为非同价码,7,常用码型,6、码的N次扩展码：假使某分组码W，把信源X中的符号xi一一变换成码W中的码字

3、Wi 字，则码W的N次扩展码是N个码字组成的码字序列的集合。,8,例：设信源X的概率空间为,若把该信源通过一个二元信道进行传输，为适合信道传输，就必须把信源符号xi变换成0、1符号组成的码序列（二元序列）。可采用不同的二元序列使其与信源符号si一一对应，所以可有多种方法得到二元码。如表4.1所示,9,表5.1 信源X的两种不同编码码字,现求码S2的二次扩展码。,10,常用码型,7、唯一可译码：若码的任意一串有限长的码符号序列只能被唯一地译成所对应的信源符号序列，则此码为唯一可译码。否则，称为非唯一可译码。唯一可译码的物理含义：不仅要求不同的码字表示不同的信源符号，而且还进一步要求对由信源符号构

4、成的信息序列进行编码时，在接收端仍能正确译码，而不发生混淆。本章主要研究的是同价唯一可译码。,11,5.2 定长码,一般来说，若要实现无失真的编码，所编的码必须是唯一可译码，否则，就会因译码带来的错误与失真。非奇异定长码的N次扩展码一定也是非奇异定长码。非奇异定长码一定是唯一可译码。,12,信源存在唯一可译定长码的条件：,对信源X 进行等长编码，必须满足 其中l 是等长码的码长,有 例：英文电报有32个符号，即n=32。若对它进行二元编码，则r=2，可得l=5。也就是说，每个英文电报符号至少要用5位二元符号编码才行。,13,实际英文电报符号信源，在考虑了符号出现的概率以及符号之间的依赖性后，其

5、信息熵约为1.4比特/符号，即平均每个英文符号所提供的信息量为1.4比特。因此等长编码后5个二元符号只携带约1.4比特信息量。对于无噪无损二元信道，每5个二元符号最大能载荷5比特的信息量。因此，如此等长编码的信息传输效率极低。,14,5.4等长信源编码定理,定理4.3一个熵为H(X)的离散无记忆信源，若对信源长为 N 的符号序列进行等长编码，设码字是从 r 个字母的码符号集中选取 l 个码元组成。对于任意 0，只要满足则当N足够大时，可实现几乎无失真编码，即译码错误概率能为任意小。,15,编码信息率,编码效率,举例：书145页例4.1,16,5.5 变长码,变长码也必须是唯一可译码，才能实现无

6、失真编码。定义：在唯一可译变长码中，有一类码，它在译码时，无须参考后续的码符号就能立即作出判断，译成对应的信源符号，则这类码称为即时码,17,一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。故即时码一定是唯一可译码，反之，唯一可译码不一定是即时码。,即时码可用树图法来进行编码和译码。,18,树码：通过树图法构成的码叫树码对r进制树图，有树根、树枝和节点。树图最顶部的节点称为树根。树枝的尽头称为节点，每个节点生出的树枝树目等于码符号树r。,即时码的构造,19,20,即时码可用树图法来进行编码和译码。构造步骤：1、最上端为树根，从根出发向下伸出树枝，树枝总数等于m（码符号

7、数），树枝的尽头为节点。2、从每个节点再伸出m枝树枝，当某节点被安排为码字后，就不再伸枝，这节点为终端节点。能再伸枝的节点称为中间节点。一直继续进行，直到都不能伸枝为止。3、每个节点所伸出的树枝标上码符号，从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字。,21,树码一定是即时码，任一即时码都可用上述树图法来表示。即时码一定是唯一可译码。唯一可译码，不一定是即时码。,22,例：一信源X(x1,x2,x3,x4)经编码后得码字集合S(1,01,001,0001)且一一对应。现接收码元序列为101110001001101011，试写出译码结果。解：该编码规则为：x11,x201,x30

8、01,x4001，每一码字均以1结尾，见1即可译码。对所接收序列的译码结果为 x1,x2,x1,x1,x4,x3,这种编码，译码时不需要考察后续码元，故又称之为即时码。,23,编码的树图表示,即时码一定是单义可译码。,24,单义可译定理（即时码存在的充要条件）,对含有n个信源符号的信源用含r 个符号的码符号集进行编码，各码字的码长为 的唯一可译码存在的充要条件是，满足Kraft不等式含义：,25,例：信源空间为 X：x1,x2,x3,x4 P(X)：1/2，1/4，1/8，1/8 对其进行信源编码，信道基本符号集合为：m=0,1；若编码后对应的码长分别为k1=1,k2=2,k3=3,k4=3，

9、问能否构造出一种即时码？解：将m=2,n=4 和ki的4个值带入Kraft不等式得,满足Kraft不等式，所以一定能构成至少一种即时码,26,27,唯一可译码的判断法,应该注意的是克拉夫特（Kraft）不等式只是给出来即时码或唯一可译码存在的充分必要条件，但该定理并不能作为判别一种码是否为即时码或唯一可译码的依据。即唯一可译码（或即时码）一定满足不等式，反之，满足不等式的码不一定是唯一可译码。例：码字（0，10，010，111），满足克拉夫特不等式，但它不是唯一可译码。,28,唯一可译码的判断步骤：,1、观察是否是非奇异码。若是奇异码则一定不是唯一可译码。2、计算是否满足Kraft不等式，若不

10、满足一定不是唯一可译码。3、将码画成一棵树图，观察是否满足即时码的树图构造，若满足则是唯一可译码。4、直接用判别测试算法：,29,5.6变长信源编码定理,设信源 有n个离散符号，编码后的码字为其码长分别为对于唯一可译码来说，信源符号与码字一一对应，所以有则这个码的平均长度为,30,码的平均长度是每个信源符号平均需用的码元数。平均每个码元携带的信息量即编码后信道的信息传输率为若要信息传输效率高，需寻求使平均码长最短的码，即紧致码，或称最佳码。,31,平均码长可能达到的理论极限,定理：若一离散无记忆信源 X 具的熵为H(X)，并有 r 个码元的码符号，则总可以找到一种无失真编码方法，构成唯一可译码，使其平均码长满足无失真变长信源编码定理,香农第一定理,32,编码效率：码的剩余度：二元无噪无损信道中信息传输率,33,例：有一离散无记忆信源其熵为H(X)=0.811比特/信源符号。用二元码构造一个非续长码：x10，x21这时平均码长，编码效率信道信息传输率为,34,对该信源的二次扩展信源进行编码如下这个码的平均长度得信源中每一个单个符号的平均码长编码效率信道信息传输率为同样可得,35,香农第一定理仅是一个存在性定理，指出了平均码长与信源熵之间的关系，但没有给出如何构造的信息。用前述例子的编码方法虽然可以得到即时码，但通常不是最佳编码，故有必要寻求更高效率的编码方法。,