《第四章 无失真信源编码优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第四章 无失真信源编码优秀PPT.ppt（106页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章 无失真信源编码第一页，本课件共有106页 本章主要讨论对离散信源进行无失真信源编码本章主要讨论对离散信源进行无失真信源编码的要求、方法及理论极限的要求、方法及理论极限,并得出香农第一极限定并得出香农第一极限定理，同时学习几种常见的无失真信源编码方法。理，同时学习几种常见的无失真信源编码方法。主主 要要 内内 容容4.1 4.1 信源编码概述信源编码概述4.2 4.2 等长码及等长信源编码定理等长码及等长信源编码定理4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理4.4 4.4 常见无失真信源编码方法常见无失真信源编码方法第二页，本课件共有106页4.1 4.1 信源编码
2、概述信源编码概述 实际信源的信源符号之间总存在相关性和分布的不均匀性，使得信源存在冗余度。信源编码的目的是要减少冗余，提高编码效率。信源编码的基本途径有两个：一是编码后使序列中的各个符号之间尽可能地互相独立，即解除相关性，方法包括预测编码和变换编码。二是使编码后各个符号出现的概率尽可能相等，即均匀化分布，方法主要是统计编码。4.1 4.1 信源编码概述信源编码概述第三页，本课件共有106页4.1 4.1 信源编码概述信源编码概述信源编码：信源编码：将信源符号序列按一定的数学规律映射成由码符号组成的码序列的过程。信源编码就要压缩信源输出符号的比特率。信源译码：信源译码：根据码序列恢复信源序列的过
3、程。两类信源编码：两类信源编码：无失真和限失真信源编码。无失真信源编码：无失真信源编码：即信源符号可以通过编码序列无差错地恢复，主要用于文字、数据信源的压缩(适用于离散信源的编码)。限失真信源编码：限失真信源编码：信源符号不能通过编码序列无差错地恢复(可以把差错限制在某一个限度内)，主要用于图像、语音信源的压缩。第四页，本课件共有106页4.1 4.1 信源编码概述信源编码概述4.1.1 4.1.1 编码器编码器 编码编码可以看作是对信源原始符号按照一定的数学规则进行的一种变换，信源编码器模型如下：S为信源符号集合，X为码符号集合。编码器的作用是将信源符号集合中的符号si(或信源符号序列)变换
4、成由码符号集合中的码符号序列输出。第五页，本课件共有106页4.1 4.1 信源编码概述信源编码概述 编码器的输出符号序列称为码字码字，码符号也可以叫作码元，码元，码字的集合称为码组码组(或者叫码或者叫码)，用C表示。码字的长度称为码长码长。码组Wi码字li码长 可见，编码就是从信源符号(信源符号序列)到码符号序列的一种映射。若要实现无失真编码，这种编码的映射必须是一一对应的而且是可逆的。第六页，本课件共有106页4.1 4.1 信源编码概述信源编码概述4.1.2 4.1.2 码的分类码的分类 根据编码器中码符号集合X中码元的个数不同以及码字长度是否一致，编码有以下分类：1 1 二元码和二元码
5、和r元码元码 若码符号集X=0,1，编码所得码字为二元码二元码，数字通信与计算机系统常用。若码符号集共有r个元素，则所得之码称为r元码。元码。2 2 等长码等长码 若一组码中所有码字长度都相同称为等长码等长码。3 3 变长码变长码 若一组码中码字的码长各不相同,称为变长码变长码。第七页，本课件共有106页4 4 非奇异码和奇异码非奇异码和奇异码 若一组码中所有码字都不相同，则称为非奇异码非奇异码，反之，则为奇异码奇异码。如表中的“编码2”是奇异码，其他码是非奇异码。符号概率P(ai)编码1编码2 编码3 编码4编码5a11/4000001a21/401011001a31/81010011000
6、1a41/401111011100001a51/81110111111000014.1 4.1 信源编码概述信源编码概述所有码都是2元码，码1是等长码，也是奇异码；码2是变长码，也是奇异码，码3,4,5是变长码，但是非奇异码。第八页，本课件共有106页4.1 4.1 信源编码概述信源编码概述5 5 同价码同价码 若码符号集X=x1,x2,xr中每个码符号所占的传输时间都相同，则所得的码为同价码同价码。同价码中等长码每个码字的传输时间相同，而变长码每个码字的传输时间不一定相同。6 6 码的码的N次扩展码次扩展码 假定某一种编码，它把信源S=s1,s2,sq中的符号si一一变换成码C中的码字Wi，
7、则码C的N次扩展码是所有N个码字组成的码字序列的集合。例如：若码 满足:第九页，本课件共有106页4.1 4.1 信源编码概述信源编码概述 则码C的N次扩展码集合：其中:即码C的N次扩展码中,每个码字Bi与信源的N次扩展信源SN中的每个信源符号:是一一对应的。即：7 7 惟一可译码惟一可译码 若任意一串有限长的码符号序列只能被唯一地译成所对应的信源符号序列，则此码称为唯一可译码唯一可译码(或称单或称单义可译码义可译码)。否则称为非唯一可译码或非单义可译码。第十页，本课件共有106页4.1 4.1 信源编码概述信源编码概述 若要使某一码为惟一可译码，则对于任意给定的有限长的码符号序列，只能被惟一
8、地分割成一个个的码字。例如：对于二元码C1=1,01,00，当任意给定一串码字序列，例如“10001101”,只可唯一地划分为1,00,01,1,01，因此是唯一可译码；而对另一个二元码C2=0,10,01,当码字序列为“0100101”时，可划分为0,10,01,01或01,0,01,01，所以是非惟一可译的。惟一可译码又分为即时码和非即时码。即时码和非即时码。如果在接收端收到一个完整的码字后，就能立即进行译码，这样的码叫做即时码即时码；第十一页，本课件共有106页4.1 4.1 信源编码概述信源编码概述 当在接收端收到一个完整的码字后，还需等下一个码字接收后才能判断是否可以译码，这样的码叫
9、做非非即时码即时码。即时码又称为非延长码即时码又称为非延长码，对即时码而言，在码组中任意一个码字都不是其它码字的前缀部分。对非即时码来说，有的码是惟一可译的，有的码是非惟一可译的，主要取决于码的总体结构。例如：码组C=a1,a2,a3,a4=1,01,001,0001，对于码符号序列“10100100011001”，可译码为a1a2a3a4a1a3，因每见一个码字，不根据其后或其前的码符号即可进行译码，因此该码为即时码。第十二页，本课件共有106页4.1 4.1 信源编码概述信源编码概述4.1.3 4.1.3 简单信源编码器举例简单信源编码器举例1 1 二进制信源编码器二进制信源编码器ASCI
10、I ASCII(美国信息交换标准代码)，是由美国国家标准协会(ANSI)开发的代码，是一个由7位二进数组成的字母、符号和命令代码。它存在多个变种。例如，可以增加1位校验位，变成8位。ASCII是PC机上使用的标准代码。第十三页，本课件共有106页4.1 4.1 信源编码概述信源编码概述2 2 摩尔斯信源编码器摩尔斯信源编码器 1836年，Samuel F.Morse(美国)发明了摩尔斯电码。曾在过去的通信中发挥过重要作用，至今仍被业余无线电爱好者和海上船只所使用。信源符号是英文字母，码符号集由“点”、“划”、“字母间隔”和“单词间隔”组成。编码器先将英文字母变成摩尔斯电码(信源编码I)，再将摩
11、尔斯电码变成二进码(信源编码器II)。第十四页，本课件共有106页4.1 4.1 信源编码概述信源编码概述3 3 中文电报信源编码器中文电报信源编码器 中文电报信源编码器的信源符号是一万个常用汉字，一个汉字首先用一个四位十进来代表，而每个十进制数字再用5位二进制3:2的等重码来代表。该等重码含3个“1”和”2”个“0”，因此重量为3。所以存在45=20个5位二进3:2的等重码。例如，汉字“中”，在编码时，先编成一个四位十进数“0022”，再用4个5位二进3:2的等重码“01101 01101 11001 11001”来表示。第十五页，本课件共有106页4.2 4.2 等长信源编码定理等长信源编
12、码定理4.2 4.2 等长码及等长信源编码定理等长码及等长信源编码定理4.2.1 4.2.1 无失真编码条件无失真编码条件 对于定长码，只要非奇异就唯一可译。这就要求码字的数目不少于被编码的信源序列的个数。1 1 单信源符号编码单信源符号编码 设信源S包含信源q个符号，码符号集包含的符号数为r，对单信源符号进行定长编码，则信源S存在唯一可译码的条件为：qrl 其中l为码长.第十六页，本课件共有106页2 2 N长信源符号序列编码（长信源符号序列编码（N次扩展码）次扩展码）将q个信源符号的信源进行N次扩展，扩展信源的消息序列数为qN，则对扩展信源编成长度为l的码字，则编码唯一可译的条件是:qNr
13、l例如，英文字母26个加1个空格可看成共27个符号的信源。如对其单符号进行2元编码，设编码长度为l，则需满足：272l，则每个信源符号所需二进码(r=2)符号数为：取4.2 4.2 等长信源编码定理等长信源编码定理第十七页，本课件共有106页4.2.2 4.2.2 渐近等分割性及渐近等分割性及 典型序列典型序列设离散无记忆信源如下：其N次扩展信源如下：4.2 4.2 等长信源编码定理等长信源编码定理第十八页，本课件共有106页 当q为有限值时，DI(ai)方差为有限值。定理定理4.2.14.2.1渐进等分割性 若随机序列S1S2SN中Si(i=1,2,N)相互统计独立并且服从同一概率分布P(s
14、),又ai=(si1si2siN)S1S2SN，则4.2 4.2 等长信源编码定理等长信源编码定理第十九页，本课件共有106页证明：证明：因为相互独立的随机变量的函数也是相互独立的随机变量。因此Si(i=1,2,N)是彼此统计独立并服从同一概率分布p(s)的，所以-logP(Si)也是统计独立的随机变量，且有E-logp(s)=H(S)。4.2 4.2 等长信源编码定理等长信源编码定理第二十页，本课件共有106页可见，信源序列ai的自信息均值I(ai)/N以概率收敛于H(S)。当N为有限长，在所有的qN个长为N的序列中必有一些ai，其自信息量的均值与信源熵H(S)之差小于；而另一些信源序列ai
15、来说，I(ai)/N与信源熵H(S)之差大于。可以分为两类序列：4.2 4.2 等长信源编码定理等长信源编码定理第二十一页，本课件共有106页定理定理4.2.24.2.2 对于任意小的正数0，0，当N足够大时，则4.2 4.2 等长信源编码定理等长信源编码定理第二十二页，本课件共有106页证明：证明：(1)由定理4-1知由性质(2)可知，所有典型序列出现的概率近似相等，近似为 ，为渐近等概序列。4.2 4.2 等长信源编码定理等长信源编码定理第二十三页，本课件共有106页N次扩展信源中信源序列分为两大类：一类典型序列经常出现，当N时概率趋近于1。反之非典型序列则不经常出现。N时概率接近于0。4
16、.2 4.2 等长信源编码定理等长信源编码定理第二十四页，本课件共有106页4.2.3 4.2.3 等长信源编码定理等长信源编码定理 定理定理4.2.34.2.3(等长信源编码定理)离散无记忆信源其熵为H(S)，对其N次扩展信源的N长信源序列进行长度为l的编码，若 只要满足则当N足够大时可实现几乎无失真编码，反之若不能实现无失真编码，N足够大时错误概率接近1。4.2 4.2 等长信源编码定理等长信源编码定理第二十五页，本课件共有106页证明思路：证明思路：只考虑对N次扩展信源中的典型序列进行编码，非典型序列则放弃，不编码。证明：证明：由前面定理可知典型序列个数为4.2 4.2 等长信源编码定理
17、等长信源编码定理如果只对典型序列进行编码，则只需要满足：第二十六页，本课件共有106页4.2 4.2 等长信源编码定理等长信源编码定理编码序列的个数r l少于典型序列的个数 ，则l长的编码序列只能对部分典型序列进行编码，即则其余的信源序列则没有对应的编码，若一旦出现，则会出错，即错误概率为第二十七页，本课件共有106页4.2 4.2 等长信源编码定理等长信源编码定理定理说明：定理说明：(1)定理是在平稳离散无记忆信源的条件下得到的，但是同样适用于平稳离散有记忆信源。此时信源熵用极限熵替换即可，即(2)若进行2元编码，则(3)将上式改写成 ,令R是编码后平均每个信源符号能载荷的最大信息量，称为编
18、码后的信息传输率。编码后的信息传输率。(4)编码效率编码效率第二十八页，本课件共有106页4.2 4.2 等长信源编码定理等长信源编码定理(5)当H(S)一定，信源序列长度N与最佳编码效率和允许错误概率有关。当DI(si)和均为定值，允许错误概率小于时，N满足通常通常,要想达到最佳编码效率且很小的错误概率要想达到最佳编码效率且很小的错误概率,往往需要很大往往需要很大的的N值值.即即要大要大和和P Pe e要小都需要要小都需要N N越大。越大。第二十九页，本课件共有106页4.2 4.2 等长信源编码定理等长信源编码定理 例例4-1 4-1 一离散无记忆信源的模型如下：要求采用二元编码，编码效率
19、为 ，差错率 试估计信源序列的最小长度N。解解:第三十页，本课件共有106页4.2 4.2 等长信源编码定理等长信源编码定理 例例4-24-2 设离散无记忆信源如下:若要对信源采用定长二元编码,要求编码效率90%,允许错误概率小于10-6,请问N最少需要多长。解解:要达到一定误码要求,信源序列长度需很长,编码器难于实现.第三十一页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理 由前面等长码信源编码定理可知，等长编码很难提高编码效率，除非增加N到很大，大到编码器很难实现。变长编码可以很好的解决这
20、个问题，变长编码往往在码符号序列长度不大时就可以编出效率很高且不失真的码。要实现无失真编码，则变长码必须是惟一可以惟一可以码码，即必须是非奇异码是非奇异码(且其任意有限长N次扩展码也应该是非奇异码)，如果要能即时译码还必须是即时码。即时码。第三十二页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理4.3.1 4.3.1 唯一可译变长码与即时码唯一可译变长码与即时码 与等长编码一样，变长码也必须是唯一可译码才能实现无失真编码。变长码是非奇异的，其任意有限长N次扩展码也是非奇异的，则是唯一可译码唯一可译码。定义定义4.3.14.3.1 在唯一可译码中，若在译码时
21、不需要参考后续的码符号就能立即做出判断，译码成对应的信源符号，这类码称为即时码。即时码。定义定义4.3.2 4.3.2 设某码字称码符号序列 为码字 的前缀前缀(又称为词头词头)；或称码字 是码符号序列的延长延长。第三十三页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理定义定义4.3.34.3.3 若码C中，没有任何完整的码字是其他码字的前缀，即设 是码C中的任一码字，而它不是其他码字 ，的前缀，则此码为非延长码非延长码或前缀条件码前缀条件码。可见，码为即时码的充要条件充要条件是没有任何完整的码字是其他码字的前缀。因此即时码就是前缀条件码，前缀条件码(非延
22、长码)也就是即时码。各种码的关系如图所有码非奇异码唯一可译码即时码第三十四页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理4.3.2 4.3.2 即时码的树图构造法即时码的树图构造法1 1 码树码树 对于给定的码字的集合，可以用树图来描述,称此树图为码树码树。第三十五页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理(1)树根树根为码树起点(根节点根节点)，根节点根节点经n个树支的节点为n阶节点阶节点，最末树支对应的为终端节点。终端节点。(2)给每个节点的树支分配不同的r个码符号，从根节点到某终端节点所经过的树支所对应的
23、码符号序列就形成一个码字码字。(3)如果一个码树的各叶(终端节点)的阶数相同，则称为全树或整树全树或整树，否则为非全树非全树。(4)全树对应等长码等长码，非全树对应着变长码变长码。(5)每个节点对应的树支数为码树的元数元数。(5)r元码树中，n阶节点个数最多为rn，2进码树中，n阶节点数目最多为2n。第三十六页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理根节点根节点一阶节点一阶节点二阶节点二阶节点三阶节点三阶节点四阶节点四阶节点r=2二元码树二元码树r=3三元码树三元码树第三十七页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信
24、源编码定理2 2 即时码的树图构造法即时码的树图构造法 即时码的一种简单构造方法是树图法。树图法。对于给定码字的全体集合 ，可以用码树码树来描述它。利用码树构造码字，将码树的某个节点取为码字，取码字以后的节点为终端节点终端节点，不再继续伸出树支。从根节点到终端节点之间的节点称为中间节点，中间节点不安排为码字，因此，由码树构成的码一定是即时码即时码(非非延长码延长码)。另外，当第i阶节点作为终端节点，且分配以码字，则这个码字的码长为i。第三十八页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理 例例4-34-3 分别用树图法构造码C1=0,10,110,111
25、0，C2=1,10,100,1000。01 01 0 011 00001011011101101001000码C2在构造时，取为码字的节点继续伸展树支，因此，前面码字为后面码字的前缀码，不满足前缀条件码，不是即时码。但仍为唯一可译码。由树图可知，码C1在构造时，取为码字以后即为终端节点，再不继续伸展树支，因此为即时码。第三十九页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理4.3.3 4.3.3 克拉夫特不等式克拉夫特不等式定理定理4.3.14.3.1 对于码符号数集为X=x1,x2,xr的任意r元即时码，其码字为W1,W2,Wq，相应码长度为l1,l2,
26、lq，则必定满足克拉夫特不等式反之，若码长满足克拉夫特不等式，则一定存在具有这样码长的r元即时码。（充要条件）证明：证明：按照定义，如果在译码时无须参考后续码字即可译出对应信源符号，或码C中没有任何完整的码字是其他码字的前缀，则为即时码。第四十页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理必要性必要性：若按照码长分布 的码为即时码，必须满足克拉夫特不等式。每个码字作为树的终端节点后每个码字作为树的终端节点后都会影响第都会影响第N阶所伸出的树枝数，阶所伸出的树枝数，则则q q个码字使第个码字使第N N阶节点减少的树阶节点减少的树枝总数为枝总数为:将即时码将
27、即时码C用用r元树图来表示，元树图来表示，第第N阶所有可阶所有可能的树枝为能的树枝为rN枝。枝。当第当第i(iN)阶节点为码阶节点为码字，即码长为字，即码长为li=i，它将，它将影响到第影响到第N阶所伸出的阶所伸出的树枝数，第树枝数，第N N阶减少的阶减少的树枝数为树枝数为第四十一页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理即：如果码C为即时码，则克拉夫特不等式成立。减少的树枝总数减少的树枝总数应该少于应该少于N阶节阶节点的总数点的总数充分性：充分性：当每个码字的长度分布满足克拉夫特不等式，则一定存在具有这样码长分布的即时码。设即时码的码长可以按顺序排
28、列如下：若码长分布满足克拉夫特不等式:第四十二页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理俩边同乘以俩边同乘以式中 是最大码长,表示 阶节点数的最大值。设设 阶节点阶节点分配一个码分配一个码字字,则则 阶阶将减少节点将减少节点设设 阶分配阶分配一个码字一个码字,则则 阶再减阶再减少节点数少节点数假设假设 阶分阶分配一个码字配一个码字,则则 阶再减阶再减少节点数少节点数现在我们来构造上述码长的一组即时码：第四十三页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理直到直到 阶分配一阶分配一个节点为码字以后个节点为码字以后
29、,阶总共减少的节阶总共减少的节点数为点数为因因因此因此 阶至少还有阶至少还有一个终端节点可以一个终端节点可以分配一个码字。分配一个码字。则则 阶剩下的可以用阶剩下的可以用来分配作为码字的节来分配作为码字的节点数为点数为因此，当码长分布满因此，当码长分布满足克拉夫特不等式时，足克拉夫特不等式时，可以通过树图法构造可以通过树图法构造出即时码。出即时码。定理得证定理得证第四十四页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理定理说明定理说明1 即时码的码长分布一定满足克拉夫特不等式。2 码长分布满足克拉夫特不等式的即时码存在。3 码长分布满足克拉夫特不等式的码不
30、一定是即时码。4 定理只给出了即时码存在的充分必要条件，但码长分布满足克拉夫特不等式的码不一定是即时码，即克拉夫特并不是判断一个编码是否是即时码的充分必要条件。第四十五页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理 例例4-44-4 下表列出了3组码，并给出了每个码对应的码长和具有同一码长的码字的个数，其中码符号集为0,1,2,3。每个码是否存在相应的即时码？4 5 4 5 7 3 3 4 3 3 3 3 7 7 3 2 1 2 3 1码3码2 码1码字 码 个数码长第四十六页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编
31、码定理解解:利用Kraft不等式来验证码1：存在相应的即时码(异前置码)。同样可以验证：对于码2不存在相应的即时码(异前置码)，对于码3存在相应的即时码(异前置码)。同样，也可以用树图法构造即时码的方法来验证是否存在即时码，方法更简单。第四十七页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理其中，分别为信源符号数和码符号数。反之，若码长满足克拉夫特不等式，则一定存在这样码长的惟一可译码。定理定理4.3.24.3.2 若一个码是唯一可译码且码长分布为 则必满足Kraft不等式，即证明：证明：充分性：充分性：如果码长分布满足克拉夫特不等式，则一定存在这样码长分
32、布的唯一可译码。由定理4.3.1知，满足克拉夫特不等式的码长分布的即时码一定存在，而即时码就是惟一可译码。第四十八页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理必要性：必要性：如果码是惟一可译码，则其码长分布一定满足克拉夫特不等式。惟一可译码的定义：惟一可译码的定义：如果一个码是非奇异码，且其任意N(有限)次扩展码也是非奇异的，则此码为惟一可译码。反之如果码C为惟一可译码，则码C和其N次扩展码都是非奇异码。设q个码字长度分布为 ，则码C为其N次扩展码为第四十九页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理扩展码字一
33、共为 个，我们设为n=个。每一个码字 的码长为 。若设：则有：一般取 则其中：其中：为码 中码长都为 的码字的个数。第五十页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理由于码B是非奇异码，所以码长为 的码字数 应满足如下关系。即当码C为惟一可译码时，其码长分布满足克拉夫特不等式。从而证明了必要性。第五十一页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理定理说明定理说明:1 如果码C是唯一可译码，则其码长分布一定满足克拉夫特不等式；2 码长分布满足克拉夫特不等式的唯一可译码一定存在；3 码长分布满足克拉夫特不等式的码不
34、一定是唯一可译码，奇异码也可能满足kraft不等式；4 定理只是给出了唯一可译码存在的充分必要条件，而不是说满足克拉夫特不等式的码长分布的码就是唯一可译码。或者说克拉夫特并不是判断一个编码是否是唯一可译码的充分必要条件。第五十二页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理定理定理4.3.34.3.3 任意唯一可译码都可用即时码代替，而不改变码的码长分布，即如果存在一种码长分布的惟一可译码，则一定存在相同码长分布的即时码。证明：证明：由定理4.3.2可知，如果码C是唯一可译码，则其码长分布一定满足kraft不等式。再由定理4.3.1可知，满足克拉夫特不等
35、式的码长分布的即时码一定存在。即码C是唯一可译码，其码长分布一定满足克拉夫特不等式，满足坷拉夫特不等式的码长分布的即时码一定存在。因此如果存在某一码长分布的唯一可译码，就一定具有相同码长分布的即时码。第五十三页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理4.3.4 4.3.4 惟一可译码判断准则惟一可译码判断准则若已知某码 ，对应的码长分布为 如何判断它是否为惟一可译码？如图，若码C不是唯一可译码，则一定有至少俩种以上的译码结果，其中 和 表示俩种不同译码，且 。特点特点：是 的前缀，而 的尾随后缀一定是另一码字 的前缀；又 的尾随后缀又是其他码字的前缀
36、。最后，码符号序列的尾部一定为一个码字。最后，码符号序列的尾部一定为一个码字。第五十四页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理惟一可译码的判断方法如下惟一可译码的判断方法如下 将码中所有可能的尾随后缀组成一个集合，当且仅当中没有包含任何一个码字，则码为唯一可译码。其具体步骤如下：(1)首先观察码C中的最短码字是否是其它码字的前缀，若是则写出其所有的尾随后缀。(2)这些尾随后缀又可能是其它码字的前缀，按(1)的方法写出所有的尾随后缀。(3)以此类推，直到再找不到尾随后缀为止。(4)观察次短码字，依次按(1)(2)(3)列出所有尾随后缀。(5)将所有的
37、尾随后缀列写成集合F，判断集合中是否有骂字，若有则不是惟一可译码，反之这是惟一可译码。第五十五页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理 例例4-54-5 设码C=0,10,1100,1110,1011,1101，试判断是否为惟一可译码?解：解：最短码字为“0”，不是其它码字的前缀，没有尾随后缀，次短码字“10”，它是另外好几个码字的前缀，因此有尾随后缀：10110010011110100110011101011 F集合为F=10,11,00,01,1,0,100,110,011,101其中“0”和“10”为码字，因此码C不是惟一可译码。第五十六页，
38、本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理 例例4-64-6 C=110,11,100,00,10 是唯一可译码吗?11解解:00可见，“0”不是码字，因此码C是惟一可译码。104.3.4 4.3.4 变长编码定理变长编码定理1 1 平均码长平均码长(码平均长度码平均长度)设信源编码码字码长分布平均码长每个信源符号平均需要的码元数。第五十七页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理因平均每个信源符号包含的信息量为H(S)，则编码后平均每个码元符号携带的信息量(信息传输率或码信息传输率或码率率)为若每传输一个码元
39、符号平均需要t秒，则得信息传输信息传输速率速率(每秒传输的信息量)为信息传输信息传输(速速)率率与平均码长成反比，定义平均码长最短的唯一可译码为紧致码紧致码(最佳码最佳码)。第五十八页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理定理定理4.3.44.3.4 对于熵为H(S)的离散无记忆信源用r元码符号集对信源符号进行编码，则存在唯一可译码，其平均码长满足：说明说明:(1)平均码长小于下界的唯一可译码不存在；(2)并不是说平均码长大于上界的惟一可译码不存在，而是我们希望平均码长越短越好；(3)平均码长等于下界时唯一可译码为最佳码。第五十九页，本课件共有10
40、6页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理证明证明:(1)证明不等式前半部由詹森不等式等号成立的充要条件此时，平均码长达到最短，编码为最佳码。第六十页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理(2)证明上界(不等式后半部分)只需证明可以构造一种唯一可译码满足定理上界首先，令式中符号 代表不小于x的最小正整数。若 为整数，选择 ，若 不是整数，则选取 满足 的整数，即选择码长满足对i求和得第六十一页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理若熵以r进制为单位再对不等式求的变量i的加权和加
41、权和(统计平均统计平均)，得 唯一可译码存在第六十二页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理定理定理4.3.5(4.3.5(无失真信源编码定理无失真信源编码定理-香农第一定理香农第一定理)设离散无记忆信源其信源熵为H(S)，该信源的N次扩展信源为：对扩展信源进行编码，总可构造唯一可译码，使信源S中的每个符号所需要的平均码长满足：第六十三页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理证明：证明：将扩展信源视为一个新的离散无记忆信源，按照定理定理4.3.44.3.4可以得出或者当或者当N充分大时，每个信源符号所对
42、应的平均码长等于r进制的信源熵 或者2进制信源熵 ,若达不到这个码长，则唯一可译码不存在。第六十四页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理推论：推论：对于一般离散信源或者马尔可夫信源则有表示编码后平均每个信源符号能载荷的信息量。则若是对N次扩展信源编码，平均码长编码后信道的信息传输率第六十五页，本课件共有106页编码后的极限信息传输率为R=logr，对于无噪无扰信道，其信道容量C=logr，即RC。无失真信源编码定理无失真信源编码定理也称无噪信道编码定理无噪信道编码定理，可表述为：若信道的信息传输率R不大于信道容量C，总能对信源的输出进行适当的编码
43、，使得在无噪无损信道上能无差错地以最大信息传输率C传输信息；反之则不可能无差错传输。4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理若对有记忆普通信源第六十六页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理为了衡量各种编码距极限压缩(码长越短越好)值的情况，定义变长编码的编码效率一般有记忆信源对于无记忆信源无记忆信源二元编码为了衡量各种编码与最佳码的差距，定义编码的剩余度第六十七页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理 例例4-7 4-7 已知信源模型1)对单信源符号进行二元编码，即s10，s2
44、0，求平均码长和编码效率；2)编码成2次扩展码，信源序列与码序列的映射关系为s1s10,s1s210,s2s1110,s2s2111，求平均码长和编码效率。解解：第六十八页，本课件共有106页4.3 4.3 变长码及变长信源编码定理变长码及变长信源编码定理 与例4-1、4-2相比，可以看出，为得到同样编码效率所用的N比定长码小得多，因此容易达到高的编码效率，是变长码的显著优点。信息传输率用同样可得对3、4次扩展信源编码。其编码效率。第六十九页，本课件共有106页4.4 4.4 常见无失真信源编码方法常见无失真信源编码方法4.4 4.4 常见无失真信源编码方法常见无失真信源编码方法 信源编码主要
45、分为无失真和限失真信源编码无失真和限失真信源编码，其目的都是为了用较少的码率来传送同样多的信息，增加单位时间传送的信息量，提高有效性。无失真信源编码主要适用于离散信源或数字信号，例如文本、表格及工程图纸等信源；限失真信源编码主要适用于波形信源或波形信号(模拟信号)，如语音、电视图象、彩色静止图象等信号。无失真信源编码常被称熵编码熵编码(entropy coding)，常见的无失真信源编码方法有：香农编码、霍夫曼编码、费诺编码、游程编码及算术编码等。第七十页，本课件共有106页4.4 4.4 常见无失真信源编码方法常见无失真信源编码方法4.4.1 4.4.1 香农编码香农编码(不是最佳编码方法)
46、最佳编码：最佳编码：凡能载荷一定信息量，平均码长最短，可分离的(接收端能分开)变长码的码集。关键：关键：码长最短 大概率短码 小概率长码香农编码编码步骤为香农编码编码步骤为:1 信源符号按概率排序：p(s1)p(s2)p(sn)2 确定码长lj(整数)：-log2p(sj)lj1-log2p(sj)3 计算第j个码字(之前)的累加概率pa(sj)4 将pa(sj)变为二进制数，并取其小数点后lj位作为si的编码。第七十一页，本课件共有106页4.4 4.4 常见无失真信源编码方法常见无失真信源编码方法 例例4-84-8 对下表信源符号s1,s2,s7进行编码，并计算平均码长及编码效率。消息符号
47、si消息概率p(si)累加概率pa(sj)累加概率对应的二进制-logp(si)代码长度li二进制代码S1S2S3S4S5S6S70.200.190.180.170.150.100.0100.200.390.570.740.890.990.0000.00110.01100.10010.10110.11100.11111102.342.412.482.562.743.346.66333334700000101110010111101111110第七十二页，本课件共有106页4.4 4.4 常见无失真信源编码方法常见无失真信源编码方法4.4.2 4.4.2 费诺编码费诺编码 费诺编码属于概率匹配编
48、码，但也不是最佳编码，只有当信源的概率分布呈现 分布形式的条件下，才能达到最佳码的性能。步骤：1）将信源符号以概率递减的次序排列；2）将信源符号按概率划分成两大组，使每组的概率和接近相等,并赋值“0”和“1”；3）将每一大组信源符号再分成两组，使划分后每组的概率和接近相等,分别赋值“0”和“1”；4）依次下去，直至各小组只剩一个信源符号；;5）按分组次序由前向后将赋值排序，即得码字。第七十三页，本课件共有106页4.4 4.4 常见无失真信源编码方法常见无失真信源编码方法 例例4-9 4-9 将下列消息按二元费诺码进行编码。因信源符号概率分布满足 ，能达到最佳码，否则，通常不能达到编码效率为“
49、1”。第七十四页，本课件共有106页信源符号 概率 编码 s1 0.32 s2 0.22 s3 0.18 s4 0.16 s5 0.08 s6 0.044.4 4.4 常见无失真信源编码方法常见无失真信源编码方法 例例4-10 4-10 将下列消息按二元费诺码进行编码。码字 码长 00 2 01 2 10 2 110 3 1110 4 1111 40 01 10 01 10 01 10 01 10 01 1第七十五页，本课件共有106页4.4 4.4 常见无失真信源编码方法常见无失真信源编码方法4.4.3 4.4.3 霍夫曼编码霍夫曼编码(最佳码编码方法)1952年霍夫曼提出的,命名为藿夫曼编
50、码。适用于多元独立信源。分为二元和多(r)元藿夫曼编码。1 1 二元霍夫曼编码二元霍夫曼编码(1)信源符号按出现概率递减递减的顺序排列；(2)取概率最小概率最小的两个信源符号分别赋值“0”、“1”，然后把这两个符号合并为一个新信源符号，并将其概率值相加作为新符号的概率值与剩余信源符号按概率递减重新排序；(3)按新排列顺序重复(2)，直到概率和达到1；(4)由后向前由后向前按路径将赋值排列成码序。第七十六页，本课件共有106页4.4 4.4 常见无失真信源编码方法常见无失真信源编码方法 例例4-11 4-11 对离散无记忆信源做二元霍夫曼编码。解法解法1 1：合并后概率上放00101101001