3无失真信源编码.ppt

《3无失真信源编码.ppt》由会员分享，可在线阅读，更多相关《3无失真信源编码.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 无失真信源编码无失真信源编码3.1 3.1 编码的相关概念编码的相关概念3.2 3.2 定长定长编码定理编码定理3.3 3.3 变长变长编码定理编码定理3.4 3.4 最佳编码最佳编码无失真信源编码无失真信源编码为什么要对进行编码？为什么要对进行编码？1.信源发出的消息符号可能信源发出的消息符号可能不适合不适合信道的传输，将信道的传输，将信源发出的消息符号信源发出的消息符号转换转换为适合信道传输的符号。为适合信道传输的符号。2.信源消息确定后，提高通信的信源消息确定后，提高通信的有效性有效性-信源编码信源编码。3.提高通信的提高通信的可靠性可靠性,编码具有发现错误或纠正错编码具有

2、发现错误或纠正错误的抗干扰能力误的抗干扰能力-信道编码信道编码。4.提高通信的提高通信的安全性安全性-加密编码加密编码。3.1 3.1 编码的相关概念编码的相关概念3.1.1 3.1.1 信源编码的定义信源编码的定义3.1.2 3.1.2 信源编码信源编码的研究方法的研究方法3.1.3 3.1.3 编码相关概念编码相关概念3.1.4 3.1.4 唯一可译码的存在条件唯一可译码的存在条件编码的相关概念编码的相关概念信源编码信源编码的定义的定义信源编码信源编码定义定义：指定能够满足信道特性：指定能够满足信道特性/适合于信适合于信道传输的符号序列道传输的符号序列/码序列，来代表信源输出的消码序列，来

3、代表信源输出的消息。息。完成编码功能的器件称为完成编码功能的器件称为编码器编码器。离散信源输出的码序列离散信源输出的码序列离散信源输出的消息是由离散信源输出的消息是由一个个离散符号一个个离散符号组成组成的随机序列的随机序列信源信源符号序列符号序列；X=(X1X2XlXL)Xlx1,x2,xi,xn信源编码就是把信源输出的随机符号序列变成信源编码就是把信源输出的随机符号序列变成码序列码序列。Y=(Y1Y2YkYK)Yky1,y2,yj,ym信源编码的研究方法信源编码的研究方法研究方法研究方法研究研究信源编码信源编码时，将信道编码和译码看成是时，将信道编码和译码看成是信道信道的一部分，而突出信源编

4、码；的一部分，而突出信源编码；信道信源编码的研究方法信源编码的研究方法研究研究信道编码信道编码时，将时，将信源编码信源编码和和译码译码看成是看成是信源信源和和信信宿宿的一部分，而突出信道编码。的一部分，而突出信道编码。信源信源信宿信宿信源编码的研究方法信源编码的研究方法讨论无失真信源编码可以先不考虑抗干扰问题，所以讨论无失真信源编码可以先不考虑抗干扰问题，所以它的数学模型比较简单，如图所示。它的数学模型比较简单，如图所示。P(yj/xi)无失真信源编码器无失真信源编码器XX1,X2,XLYY1,Y2,Ykiy1,y2,ym(Yk是由是由ki个个yj组成的序列组成的序列)编码相关概念编码相关概念

5、码元和码字码元和码字码元码元(符符)集集：信道可传输的基本符号的集合：信道可传输的基本符号的集合,记为记为Y;设设 Y 有有m个符号：个符号：Y=y1,y2,ym，其中，其中yi称称为为码元码元或或码符码符。m 元信道元信道:可传输可传输m个基本符号的信道；个基本符号的信道；二元信道二元信道:可传输可传输 2个基本符号的信道。这是个基本符号的信道。这是一种最常用的信道一种最常用的信道,基本符号常用基本符号常用 0,1 表示。表示。码字码字:由码元组成的序列称为码字，记为由码元组成的序列称为码字，记为Yi。码字码字Yi的码元个数的码元个数 Ki 称为称为Yi的的码长码长。所有码字所有码字Yi的码

6、长的码长 Ki 均相等称为均相等称为定长码定长码。码字码字Yi的码长的码长 Ki不全相等称为不全相等称为变长码变长码。编码相关概念编码相关概念编码与译码编码与译码信源编码信源编码：将信源符号：将信源符号xi或符号序列或符号序列X按一种规则按一种规则映射映射成码字成码字Yj的过程。的过程。无失真编码无失真编码：信源符号到码字的：信源符号到码字的映射映射必须一一对应。必须一一对应。译码译码：从码符号到信源符号的映射。：从码符号到信源符号的映射。码表码表：所有映射规则的集合。：所有映射规则的集合。编码相关概念编码相关概念许用码和禁用码许用码和禁用码许用码字许用码字：信源的符号：信源的符号xi或符号序

7、列或符号序列X与码字与码字Yj定定义了义了对应关系的码字。对应关系的码字。禁用码字禁用码字：信源的符号：信源的符号xi或符号序列或符号序列X与码字与码字Yj未未定义定义对应关系的码字。对应关系的码字。许用码字的全体称为许用码字的全体称为码集码集。编码相关概念编码相关概念分组码（块码）分类分组码（块码）分类按码字的按码字的码长码长分类分类定长码定长码：码集中所有码字的码长相等。：码集中所有码字的码长相等。变长码变长码：码集中所有码字的码长不全相等。：码集中所有码字的码长不全相等。按信源符号与码字按信源符号与码字对应关系对应关系分类分类非奇异码非奇异码：信源符号与码字：信源符号与码字是是一一对应的

8、。一一对应的。奇异码奇异码：信源符号与码字：信源符号与码字不是不是一一对应的。一一对应的。编码相关概念编码相关概念/分类分类按译码唯一性分类按译码唯一性分类唯一可译码唯一可译码：对于多个码字组成的有限长码流，只：对于多个码字组成的有限长码流，只能唯一地分割一个个的码字。唯一可译码又称为能唯一地分割一个个的码字。唯一可译码又称为单单义码义码。唯一可译码在传输过程中不需要同步码。唯一可译码在传输过程中不需要同步码。非唯一可译码非唯一可译码：对有限长码流，不能唯一地分割一：对有限长码流，不能唯一地分割一个个的码字。个个的码字。例例：码流：码流 100111000 码码1：x10 x210 x311

9、可分割可分割10,0,11,10,0,0码码2：x11 x210 x311 则无法唯一分割则无法唯一分割编码相关概念编码相关概念/分类分类按译码的即时性分类按译码的即时性分类非即时码非即时码：接收端收到一个：接收端收到一个完整完整的码字后，的码字后，不能不能立立即译码；还需要等到下一个码字开始接收后才能判即译码；还需要等到下一个码字开始接收后才能判断是否可以译码。断是否可以译码。即时码即时码：接收端收到一个完整的码字后，就：接收端收到一个完整的码字后，就能能立即立即译码；即时码又称为译码；即时码又称为非延长码非延长码或或异前缀码异前缀码。例例：非即时码：非即时码，码流，码流 01001100

10、x10 x201 x311 译码为译码为 x2,x1,x1,x3,x1,?即时码，码流即时码，码流 01001100 x10 x210 x311 译码为译码为 x1,x2,x1,x3,x1,x1结论结论：即时码指的是码集任何一个码：即时码指的是码集任何一个码不能是其他码不能是其他码的前缀的前缀，即时码，即时码必定必定是唯一可译码是唯一可译码,唯一可译码唯一可译码不不一定一定是即时码。是即时码。编码相关概念编码相关概念/分类分类/举例举例例：例：码码1 1：显然不是惟一可译码。：显然不是惟一可译码。x2和和x4对应于同一码字对应于同一码字“11”，码码1本身是一个奇异码。本身是一个奇异码。码码2

11、 2：是非奇异码，不是惟一可译码。当收到一串码符号：是非奇异码，不是惟一可译码。当收到一串码符号“01000”时，可将它译成时，可将它译成“x4 x3 x1”，也可译为，也可译为“x4x1x3”，“x1x2x3”或或“x1x2x1x1”等，这种码从单个码字来看虽等，这种码从单个码字来看虽然不是奇异的，单从有限长的码序列来看，它仍然是一个奇然不是奇异的，单从有限长的码序列来看，它仍然是一个奇异码。异码。码码3 3：虽然是惟一可译码，但它要等到下一个：虽然是惟一可译码，但它要等到下一个“1”收到后才能收到后才能确定码字的结束，译码有延时。确定码字的结束，译码有延时。码码4 4：既是惟一可译码，又没

12、有译码延时。码字中的符号：既是惟一可译码，又没有译码延时。码字中的符号“1”起了逗点的作用，故称为逗点码。起了逗点的作用，故称为逗点码。xip(xi)码码1码码2码码3码码4x11/20011x21/411101001x31/80000100001x41/8110110000001前缀条件码前缀条件码/异前置码异前置码/异字头码异字头码/逗点码逗点码/即时码即时码/非延长码非延长码：如果一个码的任何一个码字都不是：如果一个码的任何一个码字都不是其它码字的前缀。其它码字的前缀。唯一可译码的存在条件唯一可译码的存在条件码树图码树图码树图码树图:用码树来描述给定码集各码字的方法。用码树来描述给定码集

13、各码字的方法。码树图有码树图有树根树根、树枝树枝、节点节点：一般：一般中间节点中间节点（一级（一级节点、二级节点节点、二级节点）用）用表示表示,终端节点终端节点用用表示。表示。传输传输m个基本符号信道的码可用。个基本符号信道的码可用。例例：二元（进制）码树：二元（进制）码树x1x2x301011x11 x201 x3001唯一可译码的存在条件唯一可译码的存在条件/码树图码树图如果节点过多，也可以用如下方法表示码树图。如果节点过多，也可以用如下方法表示码树图。唯一可译码的存在条件唯一可译码的存在条件/码树图码树图用码树图构造码的方法用码树图构造码的方法在树的生长过程中，中间节点生出树枝，各树枝标

14、在树的生长过程中，中间节点生出树枝，各树枝标出相应的码元；出相应的码元；为了清晰起见相同码元的树枝为了清晰起见相同码元的树枝方向相同方向相同，终端节点，终端节点表示信源符号；表示信源符号；从树根到终端节点所经过的树枝旁的码元按经过从树根到终端节点所经过的树枝旁的码元按经过的顺序组成的序列构成码字。的顺序组成的序列构成码字。用码树图构造用码树图构造即时码即时码的条件的条件如果表示信源符号的终端节点不再延伸，即如果表示信源符号的终端节点不再延伸，即信源符信源符号都在终端节点上号都在终端节点上，这样构造的码满足即时码条件。，这样构造的码满足即时码条件。唯一可译码的存在条件唯一可译码的存在条件前提条件

15、前提条件：非奇异码：非奇异码唯一可译码唯一可译码存在定理：存在定理：设设n为信源符号或信源符号序为信源符号或信源符号序列个数，列个数，m 为码元个数或进制数，为码元个数或进制数，Ki 为信源各符号为信源各符号或信源符号序列对应的码长或信源符号序列对应的码长;则唯一可译码存在的充则唯一可译码存在的充分和必要条件是满足分和必要条件是满足Kraft不等式：不等式：注意注意：Kraft不等式是一个不等式是一个存在定理存在定理，不是不是唯一可译码的唯一可译码的判定定理判定定理。如果如果n、m、Ki 满足该不等式满足该不等式,则存在唯一可译码则存在唯一可译码如果是唯一可译码如果是唯一可译码,则则n、m、K

16、i 必定满足该不等必定满足该不等式。式。唯一可译码的存在条件唯一可译码的存在条件例：设二进制码树中例：设二进制码树中Xx1,x2,x3,x4，K1=1，K2=2，K3=2，K4=3，应用上述判断定理，可得，应用上述判断定理，可得因此，不存在满足这种因此，不存在满足这种K Ki i的唯一可译码的唯一可译码,用树码进用树码进行检查如图所示。行检查如图所示。唯一可译码的存在条件唯一可译码的存在条件信息率信息率若信源输出符号序列长度若信源输出符号序列长度L1变换成由变换成由KL个符号组成的码序列个符号组成的码序列/码字码字变换要求变换要求：能够：能够无失真无失真或无差错地从或无差错地从Y恢复恢复X，同

17、时传送同时传送Y时所需要的时所需要的信息率最小信息率最小。唯一可译码的存在条件唯一可译码的存在条件/信息率信息率Yk有有m种可能值，能编成的码字个数种可能值，能编成的码字个数所以平均每个符号输出的最大信息量为所以平均每个符号输出的最大信息量为logm，KL长长码字最大信息量为码字最大信息量为KLlogm。用该码字表示长度为用该码字表示长度为L的信源序列，则送出一个信的信源序列，则送出一个信源符号所需要的源符号所需要的信息率信息率平均为平均为所谓所谓信息率最小信息率最小，就是找到一种编码方式使，就是找到一种编码方式使K KL Llogmlogm/L/L最小。最小。几个问题几个问题：信息率最小为多

18、少时，才能无失真译码？信息率最小为多少时，才能无失真译码？若小于这个信息率是否还能无失真译码？若小于这个信息率是否还能无失真译码？3.2 3.2 定长编码定理定长编码定理3.2.1 3.2.1 平均码长和编码有效性平均码长和编码有效性3.2.2 3.2.2 定长编码定理定长编码定理平均码长和编码有效性平均码长和编码有效性平均码长平均码长单符号信源空间，其中单符号信源空间，其中信源符号信源符号 xi 对应的码字为对应的码字为Yi（i=1,2,n）,码码字字Yi 对应的码长为对应的码长为 Ki（i=1,2,n）。所有的所有的Ki相等为相等为定长码定长码，记为，记为K,不相等时为不相等时为变长变长码

19、码。单符号对应变长码的单符号对应变长码的平均码长平均码长码符码符/信源符号信源符号平均码长和编码有效性平均码长和编码有效性/平均码长平均码长符号序列信源空间符号序列信源空间XL其中其中XL是是X的的L次扩展。次扩展。信源符号序列信源符号序列 对应的码字为对应的码字为Yi（i=1,2,nL）,码字码字Yi 对应的码长为对应的码长为 Ki（i=1,2,nL）。符号序列对应变长码的符号序列对应变长码的平均码长平均码长码符码符/信源符号序列信源符号序列码符码符/信源符号信源符号平均码长和编码有效性平均码长和编码有效性/编码效率编码效率编码效率（码率）编码效率（码率）定义：平均一个码符所携带的平均信息量

20、称为定义：平均一个码符所携带的平均信息量称为编编码效率码效率，记作，记作；平均码长和编码有效性平均码长和编码有效性例例：信源空间：信源空间 H(X)=-(1/2 log1/2+1/4 log1/4+1/8 log1/8+1/8 log1/8)=1.75 bit/消息消息信源符号个数为信源符号个数为n=4，二元码符，二元码符0,1,码符个数为码符个数为m=2，Ki为信源各符号对应的码字长为信源各符号对应的码字长,且满足且满足Kraft不等式。不等式。定长码定长码:K1=K2=K3=K4=2 2-2+2-2+2-2+2-2=1 码字码字:Y1=00,Y2=01,Y3=10,Y4=11编码效率编码效

21、率=H(X)/K=1.75 2 =0.825平均码长和编码有效性平均码长和编码有效性/举例举例变长码变长码:K1=1,K2=2,K3=3,K4=3 满足不等式：满足不等式：2-1+2-2+2-3+2-3=1 码字码字:Y1=0,Y2=10,Y3=110,Y4=111方案方案1:x10，x210，x3110，x4111 =11/2+21/4+31/8+31/8=1.75 码符码符/信源符号信源符号=1.75 1.75 =1方案方案2:x1111，x2110，x310，x40 =31/2+31/4+21/8+11/8=2.625 码符码符/信源符号信源符号=1.75 2.625 =0.667平均码

22、长和编码有效性平均码长和编码有效性讨论讨论1 1：为什么：为什么定长码定长码的编码效率的编码效率小于小于1 1，而，而变长码变长码的的编码效率编码效率能达到能达到1 1？原因：原因：因为因为H(X)=1.75，是个小数，而定长码的码长不可，是个小数，而定长码的码长不可能为小数，所以编码效率小于能为小数，所以编码效率小于1。除非。除非H(X)为整数。为整数。但变长码的平均码长可以为小数，可能等于但变长码的平均码长可以为小数，可能等于H(X)。平均码长和编码有效性平均码长和编码有效性讨论讨论2 2：编码后码字集合确定，符号对应的码字长度：编码后码字集合确定，符号对应的码字长度不同，为什么编码效率不

23、同？不同，为什么编码效率不同？原因：原因：不同符号的先验概率不同，对应的码字长度不同，不同符号的先验概率不同，对应的码字长度不同，计算出的平均码长也不同，编码效率也就不同。计算出的平均码长也不同，编码效率也就不同。总结总结：一般情况下，一般情况下，变长编码变长编码的编码效率的编码效率可能达到可能达到1 1；对于变长编码，若对于变长编码，若概率大的符号对应短码概率大的符号对应短码,概率小概率小的符号对应长码的符号对应长码，编码效率越高；反之越低。这也，编码效率越高；反之越低。这也是后面最佳编码的思路。是后面最佳编码的思路。定长编码定理定长编码定理定理：由定理：由L个符号组成的、每个符号的熵为个符

24、号组成的、每个符号的熵为HL(X)的的无记忆平稳信源符号序列无记忆平稳信源符号序列X1X2XlXL，可用，可用KL个符个符号（每个符号有号（每个符号有m种可能值）进行定长编码。对任意种可能值）进行定长编码。对任意0，0，只要，只要 则当则当L足够大时，必可使译码差错小于足够大时，必可使译码差错小于；反之，当；反之，当 时，译码差错一定是有限值，而当时，译码差错一定是有限值，而当L足够大时，译码足够大时，译码几乎必定出错。几乎必定出错。定长编码定理定长编码定理定理中的公式改写成定理中的公式改写成表明：不等式左边表示长为表明：不等式左边表示长为KL的码字能载荷的最大的码字能载荷的最大信息量，右边代

25、表长为信息量，右边代表长为L的信源序列平均携带的信息的信源序列平均携带的信息量。量。所以定长编码定理告诉我们：所以定长编码定理告诉我们：只要码字传输的信息量只要码字传输的信息量大于信源携带的信息量，总可实现几乎无失真编码大于信源携带的信息量，总可实现几乎无失真编码。定长编码定理定长编码定理信源熵信源熵HL(X)就是一个界限就是一个界限/临界值。当编码器输出临界值。当编码器输出的信息率超过这个临界值时，就能无失真译码，否的信息率超过这个临界值时，就能无失真译码，否则就不行。则就不行。信源编码定理从理论上说明了信源编码定理从理论上说明了编码效率接近于编码效率接近于1 1，即，即 的理想编码器的的理

26、想编码器的存在性存在性，代价是在实际编码时取无，代价是在实际编码时取无限长的信源符号限长的信源符号(L)进行统一编码。进行统一编码。只要只要足够小，就可实现几乎无失真译码；若足够小，就可实现几乎无失真译码；若足够足够小，编码效率就接近于小，编码效率就接近于1。说明说明：定长编码定理是在：定长编码定理是在平稳无记忆离散信源平稳无记忆离散信源的条的条件下论证的，但它同样适用于平稳件下论证的，但它同样适用于平稳有记忆有记忆信源，只信源，只是要求有记忆信源的是要求有记忆信源的极限熵极限熵和和极限方差极限方差存在即可。存在即可。对于平稳有记忆信源，定理中的对于平稳有记忆信源，定理中的熵应改为极限熵熵应改

27、为极限熵。定长编码定理定长编码定理定长编码定长编码 L 计算计算随机变量随机变量I(xi)；I(xi)的数学期望的数学期望M I(xi)，即，即H(X)；I(xi)的方差的方差 2(X)；符号序列长度符号序列长度L；已知编码效率已知编码效率和译码错误概率和译码错误概率。定长编码定理定长编码定理例例：设单符号信源模型为：设单符号信源模型为信源熵为：信源熵为：H(X)=2.55(比特比特/符号符号)自信息方差为：自信息方差为：2(x)=1.323若要求编码效率为若要求编码效率为90%，即，即译码差错率为译码差错率为=10-6，则，则由此可见由此可见：在差错率和效率要求都不苛刻的情况下，：在差错率和

28、效率要求都不苛刻的情况下，就必须有就必须有1600多万个信源符号一起编码，技术实现非多万个信源符号一起编码，技术实现非常困难。常困难。3.3 3.3 变长编码定理变长编码定理变长编码定理变长编码定理单个符号变长编码定理：单个符号变长编码定理：若一离散无记忆信源的符号熵为若一离散无记忆信源的符号熵为H(X)，每个信源，每个信源符号用符号用m进制码元进行变长编码，一定存在一种无进制码元进行变长编码，一定存在一种无失真编码方法，其码字失真编码方法，其码字平均长度平均长度K满足下列不等式满足下列不等式变长编码定理变长编码定理/单符号单符号证明证明：若：若 xi 按如下不等式取所对应码字的码长为按如下不

29、等式取所对应码字的码长为Ki ,若若 为整数为整数,则上述不等式左边取则上述不等式左边取等号等号。故可得：故可得：变长编码定理变长编码定理/单符号单符号所有码字长度所有码字长度满足满足KraftKraft不等式不等式。如何如何降低降低平均码长：平均码长：1 1、减少减少信源熵信源熵H(X)H(X)2 2、增加增加信道码元数信道码元数m m变长编码定理变长编码定理离散平稳无记忆序列变长编码定理：离散平稳无记忆序列变长编码定理：对于平均符号熵为对于平均符号熵为HL(X)的离散平稳无记忆信源，的离散平稳无记忆信源，必存在一种无失真编码方法，使必存在一种无失真编码方法，使平均信息率平均信息率K满足满足

30、不等式：不等式：证明证明：信源：信源 X 的的 L 次扩展信源次扩展信源XLXL 的信源熵为的信源熵为H(XL)bit/L个信源符号个信源符号XL 所对应码字的码长所对应码字的码长 码符码符/L个信源符号个信源符号变长编码定理变长编码定理/证明证明编码效率的下界：编码效率的下界：码的剩余度：码的剩余度：变长编码定理变长编码定理/举例举例例：设单符号信源模型为例：设单符号信源模型为其信息熵为：其信息熵为：H(X)=2.55(比特比特/符号符号)这里这里m=2，log2m=1要求要求90%，则，则结论：结论：与定长编码相比，对同一信源，要求编码与定长编码相比，对同一信源，要求编码效率都达到效率都达

31、到90%90%时，变长编码只需时，变长编码只需L L=4=4进行编码，进行编码，而等长码则要求而等长码则要求L L大于大于1.6875101.6875107 7。用变长编码。用变长编码时，时，L L不需要很大就可以达到相当高的编码效率不需要很大就可以达到相当高的编码效率而且可实现无失真编码。而且可实现无失真编码。变长编码定理变长编码定理/举例举例例例：设离散无记忆信源的概率空间为：设离散无记忆信源的概率空间为其信源熵为其信源熵为L=1定长码：定长码：x10，x21，则，则K=1 编码效率：编码效率：=H(X)/K=0.811L=2XL x1x1 x1x2 x2x1 x2x2 p(XL)9/16

32、 3/16 3/16 1/16H(XL)=1.622 bit/2个符号个符号变长编码定理变长编码定理/举例举例定长码定长码 XL 00 01 10 11KL=2码符码符/2个信源符号个信源符号编码效率：编码效率：=H(XL)/KL=H(X)/K=0.811变长码变长码 Y 0 10 110 111 Ki 1 2 3 3 =1 9/16+2 3/16+3 3/16 +3 1/16=27/16 =1.6875 码符码符/2个信源符号个信源符号编码效率：编码效率：=H(X)/K=0.81132/27=0.961 当当 L=3 =0.985 L=4 =0.991采用采用扩展信源扩展信源提高编码效提高编

33、码效率带来的率带来的问题问题：1.1.码表迅速扩大；码表迅速扩大；2.2.需求内存大；需求内存大；3.3.译码延时。译码延时。变长编码定理变长编码定理信息传输效率信息传输效率平均信息率平均信息率R R：平均每个码元所含有的信息量。：平均每个码元所含有的信息量。单位单位:bit/码元码元码元传输率码元传输率/码元速率码元速率(R(RB B):每秒钟传输码元的数每秒钟传输码元的数目。单位目。单位:波特波特(B)码元时间长度码元时间长度(TB):TB=1/RB单位单位:秒秒(s)平均信息传输率平均信息传输率(R Rt t):平均每秒钟传输的信息量。平均每秒钟传输的信息量。单位单位:bit/sRt=R

34、/TB3.4 3.4 最佳编码最佳编码3.4.1 3.4.1 香农编码香农编码3.4.2 3.4.2 费诺编码费诺编码3.4.3 3.4.3 哈夫曼编码哈夫曼编码最佳编码最佳编码最佳码最佳码：能载荷一定信息量：能载荷一定信息量,且码字的平均码长最短且码字的平均码长最短,可分离的码字集合。可分离的码字集合。编码思路：编码思路：对概率对概率大大的信息符号编以的信息符号编以短短码；码；对概率对概率小小的信息符号编以的信息符号编以长长码。码。目的：使平均码字长度目的：使平均码字长度最短最短。这种编码方法称为这种编码方法称为统计编码统计编码/熵编码熵编码/概率匹配编码概率匹配编码。最佳编码最佳编码香农编

35、码香农编码若单个字符若单个字符xi按如下不等式取所对应码字的码长为按如下不等式取所对应码字的码长为Ki当当m=2时时,log2m=1，则，则香农编码香农编码编码方法：编码方法：(1)将信源符号消息按其出现概率的大小依次排序。将信源符号消息按其出现概率的大小依次排序。p(x1)p(x2)p(xn)(2)按如下不等式取所对应码字的按如下不等式取所对应码字的码长码长为为Ki。(3)计算第个计算第个 i 消息的累加概率消息的累加概率,以便获得唯一可以便获得唯一可译码；译码；(4)将累加概率变换为二进制数；将累加概率变换为二进制数；(5)取二进制数的小数点后取二进制数的小数点后 Ki 位作为符号消息的二

36、位作为符号消息的二进制进制码字码字。香农编码香农编码/举例举例例例：xi x1 x2 x3 x4 x5 x6 x7 p(xi)0.20 0.19 0.18 0.17 0.15 0.10 0.01编码过程编码过程xip(xi)I(xi)KiPiPi二进制二进制码字码字x10.202.32300.0000000 x20.192.4030.20 0.0011001x30.182.4730.39 0.0110011x40.172.5630.57 0.1001100 x50.152.7430.74 0.1011101x60.103.3240.89 0.111001110 x70.016.6470.99

37、0.111111011111110香农编码香农编码/举例举例信源熵：信源熵：H(X)=2.61 bit/符号符号平均码长平均码长编码效率编码效率费诺编码费诺编码编码方法：编码方法：(1)将信源符号消息按其出现概率的大小依次排列。将信源符号消息按其出现概率的大小依次排列。p(x1)p(x2)p(xn)(2)将依次排列的信源符号按其概率分为两大组将依次排列的信源符号按其概率分为两大组,使两个组的概率之和使两个组的概率之和近似相等近似相等,并对各组赋予一个并对各组赋予一个码元码元0和和1。(3)按按(2)方法将每一大组再分为两组方法将每一大组再分为两组,各组再赋予各组再赋予一个码元一个码元0和和1。

38、(4)如此重复如此重复,直至每个组只剩一个信源符号为止。直至每个组只剩一个信源符号为止。(5)信源符号所对应的码字即为信源符号所对应的码字即为Fano 码码费诺编码费诺编码/举例举例例例：xi x1 x2 x3 x4 x5 x6 x7 p(xi)0.20 0.19 0.18 0.17 0.15 0.10 0.01编码过程编码过程xip(xi)第第1次次 第第2次次 第第3次次 第第4次次 码字码字码长码长x0.2000002x20.19100103x30.1810113x40.1710102x50.15101103x60.101011104x70.01111114费诺编码费诺编码/举例举例信源

39、熵：信源熵：H(X)=2.61 bit/符号符号平均码长平均码长编码效率编码效率哈夫曼编码哈夫曼编码编码方法：编码方法：(1)将信源符号消息按其出现概率的大小依次排序。将信源符号消息按其出现概率的大小依次排序。p(x1)p(x2)p(xn)(2)取两个概率取两个概率最小最小的符号分别配以的符号分别配以0和和1,并将这并将这两个概率相加作为新字母的概率，与未分配的字母两个概率相加作为新字母的概率，与未分配的字母重新排序。重新排序。(3)对重新排序后的两个概率最小的符号重复对重新排序后的两个概率最小的符号重复(2)的的过程。过程。(4)不断重复上述过程不断重复上述过程,直至最后两个符号配以直至最后

40、两个符号配以 0 和和 1为止。为止。(5)从从最后一级最后一级开始开始,向前返回到各个信源符号所向前返回到各个信源符号所对应的码元序列对应的码元序列,即为相应的码字。即为相应的码字。哈夫曼编码哈夫曼编码/举例举例例例：xi x1 x2 x3 x4 x5 x6 x7 p(xi)0.20 0.19 0.18 0.17 0.15 0.10 0.01编码过程编码过程xip(xi)编码过程编码过程WiKix10.200.200.260.350.390.611.0102x20.190.190.200.260.350.39112x30.180.180.190.200.260003x40.170.170.1

41、80.190013x50.150.150.170103x60.100.1101104x70.0101114010101010101哈夫曼编码哈夫曼编码/举例举例信源熵：信源熵：H(X)=2.61 bit/符号符号平均码长平均码长编码效率编码效率哈夫曼编码哈夫曼编码哈夫曼编码方法得到的码哈夫曼编码方法得到的码并非唯一并非唯一的。原因如下：的。原因如下：每次对信源缩减时，赋予信源最后两个概率最小的每次对信源缩减时，赋予信源最后两个概率最小的符号，符号，用用0 0和和1 1是可以任意的是可以任意的，所以可以得到不同的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。哈夫曼码，但不会影响码字的长度。

42、对信源进行缩减时，两个概率最小的符号合并后的对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其信源中进行概率排序，其放置次序是可以任意的放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码一般将合并的概率放在上面，这样可获得较小的码方差方差。哈夫曼编码哈夫曼编码/举例举例例例：设有离散无记忆信源：设有离散无记忆信源方法一：将合并的概率放在下面。方法一：将合并的概率放在下面。哈夫曼编码哈夫

43、曼编码/举例举例方法二：将合并的概率放在上面。方法二：将合并的概率放在上面。结论结论：哈夫曼码的：哈夫曼码的平均码长相等平均码长相等，编码效率也相等编码效率也相等。但是两种码的但是两种码的质量不完全相同质量不完全相同，可用码方差来表示。，可用码方差来表示。码方差越小，越接近平均码长，质量越好码方差越小，越接近平均码长，质量越好。哈夫曼编码哈夫曼编码/举例举例码方差：码方差：哈夫曼编码哈夫曼编码特点：特点：最佳变长码；最佳变长码；编码不是唯一的；编码不是唯一的；码方差小的编码质量好。码方差小的编码质量好。局限性：局限性：只能用只能用近似的整数位近似的整数位来表示单个符号，而不是来表示单个符号，而不是理想理想的小数位的小数位。需要知道需要知道输入符号集的概率分布输入符号集的概率分布。本章小结本章小结1 1、非奇异码、唯一可译码、即时码等、非奇异码、唯一可译码、即时码等相关概念；相关概念；2 2、定长编码定理和变长编码定理；、定长编码定理和变长编码定理；3 3、最佳编码：香农编码、费诺编码和、最佳编码：香农编码、费诺编码和哈夫曼编码的编码方法。（重点）哈夫曼编码的编码方法。（重点）作业作业3-13-13-73-73-113-113-123-12