数据压缩与信源编码培训资料.pptxVIP

第3章数据压缩和信源编码;数据压缩;数据压缩-作用;数据压缩-目的;数据压缩-目的;数据压缩-类型;数据压缩-类型;数据压缩-类型;数据压缩-类型;数据压缩-概要;数据压缩-概要;数据压缩-概要;数据压缩-概要;数据压缩-概要;数据压缩-应用;数据压缩-应用;数据压缩-应用;数据压缩-理论;数据压缩-理论;数据压缩-理论;数据压缩-理论;数据压缩和信源编码;数据压缩和信源编码;数据压缩和信源编码;数据压缩和信源编码;数据压缩和信源编码;等长码;等长码;等长码;等长码;数据压缩和信源编码;变长编码;变长编码;变长编码;变长编码;变长编码;变长编码;变长编码;变长编码;作业;

;

;用树的概念可导出即时码存在的条件，即各码字的

长度li应符合克莱夫特不等式：

定理3.2.1克莱夫特（Kraft，1949）不等式

含m个码字，码长为{l1,l2,…,lm}的D进码是一个

即时码，则它满足Kraft不等式

反之，存在给定码长的即时码；

;变长编码的平均码长：

若信源，编码后的码子为，

码长分别为，则平均码长为：

;变长信源编码问题就是

求使得给定信源平均码长最小的唯一可译的变长码.

注意：Kraft不等式是一个存在定理，不是唯一可译码的判定定理.

存在长度满足Kraft不等式的码不是即时码：

;例1：考虑二元码C={0,11,100,110}，|D|=2.

可以验证其码字长度1，2，3，3满足Kraft

不等式；

但不是即时码，因为它不是唯一可译码.;如何用Kraft不等式的证明过程构造即时码.

例2.令U={0,1,2},且

l1=l2=1，l3=2，l4=l5=4，l6=5.

①可以证明他们满足Kraft不等式；

②能够构造U上具有对应码字长度的即时

码：;由li的取值得到：

(a1,a2,a3,a4,a5)=(2,1,0,2,1);

写出码长为i的个数ai序列

任取a1个长度为1的码元：{0，1}；

任取a2个长度为2，并且不以已经出现的码字为

前缀的码元：{20}；

任取a4个长度为4，……的码元：{2100，2101}；

任取a5个长度为5，……的码元：{21020}.;在有些编码选择中，我们会面临一些最优选择的问题。比如下面这样的问题：

我们要编码字符串“7F-05051234567AB”，使得编码结果序列最短。可使用的编码方案已给定，有两种???择：

每个数字或字符对应一个定长码，比如1-〉1001100，F-1010100

每两个连续数字可以对应一个定长码。比如12-〉1001100，23-〉1101100

注意，给定的编码方案里，上面两种情况下定长码均等长(例子中为长度为7)。这里，我们看到，如果要编码结果序列最短。就需要尽量多的使用第二个方案。;这里有两种极限情况：

比如ABECDDDEFG.....FHE这样的字串只能按第一种方案进行,因为它没有连续数字出现.

比如1234235345.....32这样的字串,如果有偶数个数字的话,我们完全可以按第二种方案进行.

那么既有字符,又有数字的情况,就有一个选择的问题,所以这里的问题就是我们如何识别可以使用第二个方案的字串。;.blog.21ic./user1/1946/archives/2006/31023.html

作者fineamy;变长信源编码问题就是

求使得给定信源平均码长最小的唯一可译的变长码.

但是满足Kraft不等式的码长集未必是最优的，即其平均码长未必是最小的！;定理3.2.2（最优码码长的下界估计）：

随机变量X的任何D进即时码的平均码长L

应满足，

;证明：记

如果C是即时码，则根据Kraft不等式，有;定义3.2.3相对冗余度

作业：P751)

;定理3.2.2（最优码码长的下界估计）：

随机变量X的任何D进即时码的平均码长L

应满足，

;某地的A同学要给另外一方B同学传递信息,信息必须以二进制编码(即01编码)的方式传递.假设A传递给B的所有字符只有a,b,c,d四个,且不包含空格.

一种显而易见的编码方法是:a-----00;b-----01;c-----10;d-----11;

这样保证不会产生翻译错误的情况发生,而平均每个字符需要2个Bit的带宽.

然而这种方法不是最优的;借助统计规律,就可以构造出保证不会产生错误,然而却能更省带宽的编码方式:;给出一个例子:假设