第0章 多媒体发展简史

1、第第0章章 多媒体发展简史多媒体发展简史2022-7-3第第2页页/共共80页页第第0章章 多媒体发展简史多媒体发展简史1. 数据压缩技术半个世纪发展小述2. 互联网的诞生 3. 多媒体发展简史第一章 作业题2022-7-3第第3页页/共共80页页2022-7-3第第4页页/共共80页页 电脑里的数据压缩其实类似于美眉们的瘦身运动，电脑里的数据压缩其实类似于美眉们的瘦身运动，不外有两大功用。不外有两大功用。 第一，可以节省空间。拿瘦身美眉来说，要是八第一，可以节省空间。拿瘦身美眉来说，要是八个美眉可以挤进一辆出租车里，那该有多省钱啊！个美眉可以挤进一辆出租车里，那该有多省钱啊！ 第二，可以减少

2、对带宽的占用。例如，我们都想第二，可以减少对带宽的占用。例如，我们都想在手机在手机 上观看上观看 DVD DVD 大片，前者则取决于美眉们的恒大片，前者则取决于美眉们的恒心和毅力，后者有待于数据压缩技术的突破性进展。心和毅力，后者有待于数据压缩技术的突破性进展。2022-7-3第第5页页/共共80页页 简单地说，如果没有数据压缩技术，我们就没简单地说，如果没有数据压缩技术，我们就没法用法用 WinRARWinRAR 为为 Email Email 中的附件瘦身；如果没有数据中的附件瘦身；如果没有数据压缩技术，市场上的数码录音笔就只能记录不到压缩技术，市场上的数码录音笔就只能记录不到 20 20

3、分分钟的语音；如果没有数据压缩技术，从钟的语音；如果没有数据压缩技术，从 Internet Internet 上下上下载一部电影也许要花半年的时间载一部电影也许要花半年的时间可是这一切究竟可是这一切究竟是如何实现的呢？数据压缩技术又是怎样从无到有发是如何实现的呢？数据压缩技术又是怎样从无到有发展起来的呢？展起来的呢？ 2022-7-3第第6页页/共共80页页数据压缩简史 音画时尚音画时尚 回到未来回到未来 概率奇缘概率奇缘 数学游戏数学游戏异族传说异族传说2022-7-3第第7页页/共共80页页 4一千多年前的中国学者就知道用一千多年前的中国学者就知道用“班马班马”这样这样的缩略语来指代班固和

4、司马迁，这种崇尚简约的缩略语来指代班固和司马迁，这种崇尚简约的风俗一直延续到了今天的的风俗一直延续到了今天的 Internet Internet 时代：时代：当我们在当我们在 BBS BBS 上用上用“ 7456 7456 ”代表代表“气死我气死我了了”，或是用，或是用“ B4 B4 ”代表代表“ Before Before ”的时候，的时候，我们至少应该知道，这其实就是一种最简单的我们至少应该知道，这其实就是一种最简单的数据压缩呀。数据压缩呀。2022-7-3第第8页页/共共80页页 4严格意义上的数据压缩起源于人们对概严格意义上的数据压缩起源于人们对概率的认识。率的认识。4当我们对文字信息

5、进行编码时，如果为当我们对文字信息进行编码时，如果为出现概率较高的字母赋予较短的编码，出现概率较高的字母赋予较短的编码，为出现概率较低的字母赋予较长的编码，为出现概率较低的字母赋予较长的编码，总的编码长度就能缩短不少。总的编码长度就能缩短不少。 2022-7-3第第9页页/共共80页页 4著名的著名的 Morse 电码电码(由美国的摩尔斯在由美国的摩尔斯在 1844年发明的，所以电码符号也被叫做年发明的，所以电码符号也被叫做摩尔斯电码摩尔斯电码Morse code），电码），电码 符号符号由两种基本信号和不同的间隔时间组成：由两种基本信号和不同的间隔时间组成：短促的点信号短促的点信号“ ”，读

6、，读“ 的的 ”（Di）；）；保持一定时间的长信号保持一定时间的长信号“”，读，读“答答 ”（Da）。）。 2022-7-3第第10页页/共共80页页 A: . - B: - . . . C: - . - . D: - . . E: . F: . . - . G: - - . H: . . . . I: . . J: . - - - L: . - . . M: - - N: - . P: . - - . Q: - - . - R: . - . S: . . . T: - U: . . - V: . . . -W: . - - X: - . . - Y: - . - - Z: - - . . 0

7、: - - - - - 1: . - - - - 2: . . - - - 3: . . . - - 4: . . . . - 5: . . . . . 6: - . . . . 7: - - . . . 8: - - - . . 9: - - - - . 2022-7-3第第11页页/共共80页页4信息论之父信息论之父 C. E. Shannon 第一次用数学第一次用数学语言阐明了概率与信息冗余度的关系。语言阐明了概率与信息冗余度的关系。在在 1948 年发表的论文中，年发表的论文中， Shannon 指指出，任何信息都存在冗余，冗余大小与出，任何信息都存在冗余，冗余大小与信息中每个符号（数

8、字、字母或单词）信息中每个符号（数字、字母或单词）的出现概率或者说不确定性有关。的出现概率或者说不确定性有关。 Shannon 借鉴了热力学的概念，把信息借鉴了热力学的概念，把信息中排除了冗余后的平均信息量称为中排除了冗余后的平均信息量称为“信息熵信息熵”，并给出了计算并给出了计算信息熵的数学表达式信息熵的数学表达式。2022-7-3第第12页页/共共80页页4这篇伟大的论文后来被誉为信息论的开山之作，这篇伟大的论文后来被誉为信息论的开山之作，信息熵也奠定了所有数据压缩算法的理论基础。信息熵也奠定了所有数据压缩算法的理论基础。从本质上讲，数据压缩的目的就是找出并消除从本质上讲，数据压缩的目的就

9、是找出并消除信息中的冗余，而信息熵及相关的定理恰恰用信息中的冗余，而信息熵及相关的定理恰恰用数学手段精确地描述了信息冗余的程度。利用数学手段精确地描述了信息冗余的程度。利用信息熵公式，人们可以计算出信息编码的极限，信息熵公式，人们可以计算出信息编码的极限，即在一定的概率模型下，无损压缩的编码长度即在一定的概率模型下，无损压缩的编码长度不可能小于信息熵公式给出的结果。不可能小于信息熵公式给出的结果。 2022-7-3第第13页页/共共80页页En = - log2( Pn )I=D-du2022-7-3第第14页页/共共80页页4有了完备的理论，接下来的事就是要想办法实有了完备的理论，接下来的事

10、就是要想办法实现具体的算法，并尽量使算法的输出接近信息现具体的算法，并尽量使算法的输出接近信息熵的极限了。当然，大多数工程技术人员都知熵的极限了。当然，大多数工程技术人员都知道，要将一种理论从数学公式发展成实用技术，道，要将一种理论从数学公式发展成实用技术，就像仅凭一个就像仅凭一个 E=mc2 的公式就要去制造原子弹的公式就要去制造原子弹一样，并不是一件很容易的事。一样，并不是一件很容易的事。 2022-7-3第第15页页/共共80页页 4设计具体的压缩算法的过程通常更像是一场数设计具体的压缩算法的过程通常更像是一场数学游戏。开发者首先要寻找一种能尽量精确地学游戏。开发者首先要寻找一种能尽量精

11、确地统计或估计信息中符号出现概率的方法，然后统计或估计信息中符号出现概率的方法，然后还要设计一套用最短的代码描述每个符号的编还要设计一套用最短的代码描述每个符号的编码规则。码规则。41948 年，年， Shannon 在提出信息熵理论的同时，在提出信息熵理论的同时，也给出了一种简单的编码方法也给出了一种简单的编码方法 Shannon 编编码。码。 1952 年，年， R. M. Fano 又进一步提出了又进一步提出了 Fano 编码。这些早期的编码方法揭示了变长编码。这些早期的编码方法揭示了变长编码的基本规律，也确实可以取得一定的压缩编码的基本规律，也确实可以取得一定的压缩效果，但离真正实用的

12、压缩算法还相去甚远。效果，但离真正实用的压缩算法还相去甚远。2022-7-3第第16页页/共共80页页4第一个实用的编码方法是由第一个实用的编码方法是由 D. A. Huffman提提出出的。的。4Huffman 编码效率高，运算速度快，实现方式编码效率高，运算速度快，实现方式灵活。今天，在许多知名的压缩工具和压缩算灵活。今天，在许多知名的压缩工具和压缩算法（如法（如 WinRAR 、 gzip 和和 JPEG ）里，都有）里，都有 Huffman 编码的身影。编码的身影。4如果不是后文将要提到的那两个犹太人，我们如果不是后文将要提到的那两个犹太人，我们还不知要到什么时候才能用上还不知要到什么

13、时候才能用上 WinZIP 这样方这样方便实用的压缩工具呢。便实用的压缩工具呢。2022-7-3第第17页页/共共80页页异族传说异族传说4逆向思维永远是科学和技术领域里出奇制胜的法逆向思维永远是科学和技术领域里出奇制胜的法宝。就在大多数人绞尽脑汁想改进宝。就在大多数人绞尽脑汁想改进 Huffman 或或算算术编码术编码，以获得一种兼顾了运行速度和压缩效果，以获得一种兼顾了运行速度和压缩效果的的“完美完美”编码的时候，两个聪明的犹太人编码的时候，两个聪明的犹太人 J. Ziv 和和 A. Lempel 独辟蹊径，完全脱离独辟蹊径，完全脱离 Huffman 及算及算术编码的设计思路，创造出了一系

14、列比术编码的设计思路，创造出了一系列比 Huffman 编码更有效，比算术编码更快捷的压缩算法。我编码更有效，比算术编码更快捷的压缩算法。我们通常用这两个犹太人姓氏的缩写，将这些算法们通常用这两个犹太人姓氏的缩写，将这些算法统称为统称为 LZ 系列算法。系列算法。 2022-7-3第第18页页/共共80页页异族传说异族传说4说实话，说实话， LZ 系列算法的思路并不新鲜，其中既没系列算法的思路并不新鲜，其中既没有高深的理论背景，也没有复杂的数学公式，它们有高深的理论背景，也没有复杂的数学公式，它们只是简单地延续了千百年来人们对字典的追崇和喜只是简单地延续了千百年来人们对字典的追崇和喜好，并用一

15、种极为巧妙的方式将字典技术应用于通好，并用一种极为巧妙的方式将字典技术应用于通用数据压缩领域。通俗地说，当你用字典中的页码用数据压缩领域。通俗地说，当你用字典中的页码和行号代替文章中每个单词的时候，你实际上已经和行号代替文章中每个单词的时候，你实际上已经掌握了掌握了 LZ 系列算法的真谛。这种基于字典模型的系列算法的真谛。这种基于字典模型的思路在表面上虽然和思路在表面上虽然和 Shannon 、 Huffman 等人开等人开创的统计学方法大相径庭，但在效果上一样可以逼创的统计学方法大相径庭，但在效果上一样可以逼近信息熵的极限。而且，可以从理论上证明，近信息熵的极限。而且，可以从理论上证明， L

16、Z 系列算法在本质上仍然符合信息熵的基本规律。系列算法在本质上仍然符合信息熵的基本规律。 2022-7-3第第19页页/共共80页页异族传说异族传说4今天，今天， LZ77 、 LZ78 、 LZW 算法以及它们的算法以及它们的各种变体几乎垄断了整个通用数据压缩领域，我各种变体几乎垄断了整个通用数据压缩领域，我们熟悉的们熟悉的 PKZIP 、 WinZIP 、 WinRAR 、 gzip 等压缩工具以及等压缩工具以及 ZIP 、 GIF 、 PNG 等文件格式等文件格式都是都是 LZ 系列算法的受益者。系列算法的受益者。 4没有谁能否认两位犹太人对数据压缩技术的贡献。没有谁能否认两位犹太人对数

17、据压缩技术的贡献。我想强调的只是，在工程技术领域，片面追求理我想强调的只是，在工程技术领域，片面追求理论上的完美往往只会事倍功半，如果大家能像论上的完美往往只会事倍功半，如果大家能像 Ziv 和和 Lempel 那样，经常换个角度来思考问题，那样，经常换个角度来思考问题，没准儿你就能发明一种新的算法，就能在技术方没准儿你就能发明一种新的算法，就能在技术方展史上扬名立万呢。展史上扬名立万呢。 2022-7-3第第20页页/共共80页页音画时尚音画时尚4LZ 系列算法基本解决了通用数据压系列算法基本解决了通用数据压缩中兼顾速度与压缩效果的难题。但缩中兼顾速度与压缩效果的难题。但是，数据压缩领域里还

18、有另一片更为是，数据压缩领域里还有另一片更为广阔的天地等待着我们去探索。广阔的天地等待着我们去探索。2022-7-3第第21页页/共共80页页音画时尚音画时尚4例如，对于生活中更加常见的，图片、图像例如，对于生活中更加常见的，图片、图像等，通用压缩算法的优势就不那么明显了。等，通用压缩算法的优势就不那么明显了。幸运的是，科学家们发现，如果在压缩这一幸运的是，科学家们发现，如果在压缩这一类图像数据时允许改变一些不太重要的像素类图像数据时允许改变一些不太重要的像素值，或者说允许损失一些精度（在压缩通用值，或者说允许损失一些精度（在压缩通用数据时，我们绝不会容忍任何精度上的损失，数据时，我们绝不会容

19、忍任何精度上的损失，但在压缩和显示一幅数码照片时，如果一片但在压缩和显示一幅数码照片时，如果一片树林里某些树叶的颜色稍微变深了一些，看树林里某些树叶的颜色稍微变深了一些，看照片的人通常是察觉不到的），我们就有可照片的人通常是察觉不到的），我们就有可能在压缩效果上获得突破性的进展。也许，能在压缩效果上获得突破性的进展。也许，这和生活中常说的这和生活中常说的“退一步海阔天空退一步海阔天空”的道的道理有异曲同工之妙吧。理有异曲同工之妙吧。 2022-7-3第第22页页/共共80页页音画时尚音画时尚2022-7-3第第23页页/共共80页页音画时尚音画时尚4Internet 的发展对视频压缩提出了更高

20、的的发展对视频压缩提出了更高的要求。在要求。在内容交互、对象编辑、随机存内容交互、对象编辑、随机存取取等新需求的刺激下，等新需求的刺激下， ISO 于于 1999 年通年通过了过了 MPEG-4 标准。标准。 MPEG-4 标准拥有标准拥有更高的压缩比率，支持基于内容的交互更高的压缩比率，支持基于内容的交互操作等先进特性。操作等先进特性。2022-7-3第第24页页/共共80页页音画时尚音画时尚 Internet 上新兴的上新兴的 DivX 和和 XviD 文件格式文件格式就是采用就是采用 MPEG-4 标准来压缩视频数据的，标准来压缩视频数据的，它们可以用更小的存储空间或通信带宽提供与它们可

21、以用更小的存储空间或通信带宽提供与 DVD 不相上下的高清晰视频，这使我们在不相上下的高清晰视频，这使我们在 Internet 上发布或下载数字电影的梦想成为了上发布或下载数字电影的梦想成为了现实。现实。 2022-7-3第第25页页/共共80页页回到未来回到未来 4从信息熵到算术编码，从犹太人到从信息熵到算术编码，从犹太人到 WinRAR ，从从 JPEG 到到 MP3 ，数据压缩技术的发展史就，数据压缩技术的发展史就像是一个写满了像是一个写满了“创新创新”、“挑战挑战”、“突破突破”和和“变革变革”的羊皮卷轴。也许，我们在这里不的羊皮卷轴。也许，我们在这里不厌其烦地罗列年代、人物、标准和文

22、献，其目厌其烦地罗列年代、人物、标准和文献，其目的只是要告诉大家，前人的成果只不过是后人的只是要告诉大家，前人的成果只不过是后人有望超越的目标而已，谁知道在未来的几年里，有望超越的目标而已，谁知道在未来的几年里，还会出现几个还会出现几个 Shannon ，几个，几个 Huffman 呢？呢？ 4谈到未来，我们还可以补充一些与数据压缩技谈到未来，我们还可以补充一些与数据压缩技术的发展趋势有关的话题。术的发展趋势有关的话题。2022-7-3第第26页页/共共80页页回到未来回到未来4分形压缩技术是图像压缩领域近几年来的一个热点。这分形压缩技术是图像压缩领域近几年来的一个热点。这一技术起源于一技术起

23、源于 B. Mandelbrot 于于 1977 年创建的分形几年创建的分形几何学。何学。 M. Barnsley 在在 20 世纪世纪 80 年代后期为分形压缩年代后期为分形压缩奠定了理论基础。从奠定了理论基础。从 20 世纪世纪 90 年代开始，年代开始， A. Jacquin 等人陆续提出了许多实验性的分形压缩算法。今天，很等人陆续提出了许多实验性的分形压缩算法。今天，很多人相信，分形压缩是图像压缩领域里最有潜力的一种多人相信，分形压缩是图像压缩领域里最有潜力的一种技术体系，但也有很多人对此不屑一顾。无论其前景如技术体系，但也有很多人对此不屑一顾。无论其前景如何，分形压缩技术的研究与发展

24、都提示我们，在经过了何，分形压缩技术的研究与发展都提示我们，在经过了几十年的高速发展之后，也许，我们需要一种新的理论，几十年的高速发展之后，也许，我们需要一种新的理论，或是几种更有效的数学模型，以支撑和推动数据压缩技或是几种更有效的数学模型，以支撑和推动数据压缩技术继续向前跃进。术继续向前跃进。 2022-7-3第第27页页/共共80页页回到未来回到未来4人工智能是另一个可能对数据压缩的人工智能是另一个可能对数据压缩的未来产生重大影响的关键词。既然未来产生重大影响的关键词。既然 Shannon 认为，信息能否被压缩以及认为，信息能否被压缩以及能在多大程度上被压缩与信息的不确能在多大程度上被压缩

25、与信息的不确定性有直接关系，假设人工智能技术定性有直接关系，假设人工智能技术在某一天成熟起来，假设计算机可以在某一天成熟起来，假设计算机可以像人一样根据已知的少量上下文猜测像人一样根据已知的少量上下文猜测后续的信息，那么，将信息压缩到原后续的信息，那么，将信息压缩到原大小的万分之一乃至十万分之一，恐大小的万分之一乃至十万分之一，恐怕就不再是天方夜谭了。怕就不再是天方夜谭了。 2022-7-3第第28页页/共共80页页回到未来回到未来4回顾历史之后，人们总喜欢畅想一下回顾历史之后，人们总喜欢畅想一下未来。但未来终究是未来，如果仅凭未来。但未来终究是未来，如果仅凭你我几句话就可以理清未来的技术发你

26、我几句话就可以理清未来的技术发展趋势，那技术创新的工作岂不就索展趋势，那技术创新的工作岂不就索然无味了吗？依我说，未来并不重要，然无味了吗？依我说，未来并不重要，重要的是，赶快到重要的是，赶快到 Internet 上下载几上下载几个个MP3或或DVD大片，好好享受一下数大片，好好享受一下数据压缩为我们带来的无限快乐吧。据压缩为我们带来的无限快乐吧。 返回2022-7-3第第29页页/共共80页页多媒体多媒体ISDN2022-7-3第第30页页/共共80页页 多媒体是通信、计算机和电视等各种技多媒体是通信、计算机和电视等各种技术联合发展的必然结果。术联合发展的必然结果。 通信通信A A电视电视B

27、 B计算机计算机C CB BA AC CA AB CB C返回2022-7-3第第31页页/共共80页页作业题作业题4 参照课上所讲到的参照课上所讲到的“数据压缩数据压缩”与与“互联网互联网”的发展简史，通过查找相关的发展简史，通过查找相关资料，写一篇资料，写一篇“多媒体通信技术多媒体通信技术”的小的小论文。论文。返回2022-7-3第第32页页/共共80页页2022-7-3第第33页页/共共80页页4 亚历山大亚历山大格拉汉姆格拉汉姆贝尔（贝尔（Alexander Alexander Graham BellGraham Bell，1847-19421847-1942）美国发明家和）美国发明家

28、和企业家。他发明了世界上第一台可用的电企业家。他发明了世界上第一台可用的电话机，创建了贝尔电话公司。被誉为话机，创建了贝尔电话公司。被誉为“电电话之父话之父”。 2022-7-3第第34页页/共共80页页 1847 1847年生于英国苏格兰，他的祖父亲毕生年生于英国苏格兰，他的祖父亲毕生都从事聋哑人的教育事业，由于家庭的影都从事聋哑人的教育事业，由于家庭的影响，他从小就对声学和语言学有浓厚的兴响，他从小就对声学和语言学有浓厚的兴趣。开始，他的兴趣是在研究电报上。有趣。开始，他的兴趣是在研究电报上。有一次，当他在做电报实验时，偶然发现了一次，当他在做电报实验时，偶然发现了一块铁片在磁铁前振动会发

29、出微弱声音的一块铁片在磁铁前振动会发出微弱声音的现象，而且他还发现这种声音能通过导线现象，而且他还发现这种声音能通过导线传向远方。这给贝尔以很大的启发。他想，传向远方。这给贝尔以很大的启发。他想，如果对着铁片讲话，不也可以引起铁片的如果对着铁片讲话，不也可以引起铁片的振动吗振动吗? ?就是贝尔关于电话的最初构想。就是贝尔关于电话的最初构想。2022-7-3第第35页页/共共80页页 是梅布尔鼓舞他进行了所有那些使人精是梅布尔鼓舞他进行了所有那些使人精疲力竭的实验，也是梅布尔使他克服了不疲力竭的实验，也是梅布尔使他克服了不时产生的沮丧情绪时产生的沮丧情绪那种常常困扰着紧那种常常困扰着紧张工作去夺

30、取成功的人们的沮丧情绪张工作去夺取成功的人们的沮丧情绪使他得以研制出当时很了不起的一种工具。使他得以研制出当时很了不起的一种工具。它能把人说的话转变为电脉冲，之后又在它能把人说的话转变为电脉冲，之后又在金属丝的末端使之还原成人说的话。金属丝的末端使之还原成人说的话。 2022-7-3第第36页页/共共80页页 为了纪念贝尔的功绩，将电学和声学中为了纪念贝尔的功绩，将电学和声学中计量功率或功率密度比值的一种单位命名计量功率或功率密度比值的一种单位命名为为“贝尔贝尔”。 2022-7-3第第37页页/共共80页页声音编码示意图声音编码示意图 2022-7-3第第38页页/共共80页页 声音编码的范

31、围声音编码的范围2022-7-3第第39页页/共共80页页声音编码示意图声音编码示意图2022-7-3第第40页页/共共80页页声音编码示意图声音编码示意图 2022-7-3第第41页页/共共80页页声音编码示意图声音编码示意图2022-7-3第第42页页/共共80页页声音编码示意图声音编码示意图 2022-7-3第第43页页/共共80页页声音编码示意图声音编码示意图音频编码示意图音频编码示意图 输入信号2022-7-3第第44页页/共共80页页 视频压缩基本原理视频压缩基本原理1.1.时域冗余信息时域冗余信息 使用帧间编码技术可去除时域冗余信息，它包括以下二使用帧间编码技术可去除时域冗余信息

32、，它包括以下二部分：部分： 帧间预测帧间预测 只传两帧之间变化的部分；只传两帧之间变化的部分； 运动补偿运动补偿 运动补偿是通过先前的局部图像来预测、补偿当前运动补偿是通过先前的局部图像来预测、补偿当前的局部图像，它是减少帧序列冗余信息的有效方法。的局部图像，它是减少帧序列冗余信息的有效方法。 2022-7-3第第45页页/共共80页页视频压缩基本原理视频压缩基本原理2.2.空域冗余信息空域冗余信息 变换编码变换编码 变换编码将空域信号变换到另一正交矢量空间，使其变换编码将空域信号变换到另一正交矢量空间，使其相关性下降，数据冗余度减小。相关性下降，数据冗余度减小。 量化编码量化编码 经过变换编

33、码后，产生一批变换系数，对这些系数进经过变换编码后，产生一批变换系数，对这些系数进行量化，使编码器的输出达到一定的位率。行量化，使编码器的输出达到一定的位率。 熵编码熵编码 熵编码是无损编码。它对变换、量化后得到的系数和运动熵编码是无损编码。它对变换、量化后得到的系数和运动信息，进行进一步的压缩。信息，进行进一步的压缩。2022-7-3第第46页页/共共80页页2022-7-3第第47页页/共共80页页4背景全景图+视频对象(VO)=合成图像MPEG-4应用实例2022-7-3第第48页页/共共80页页2022-7-3第第49页页/共共80页页叛逆斗士的胜利-ZIP格式诞生 2022-7-3第

34、第50页页/共共80页页叛逆斗士的胜利-ZIP格式诞生 于是数据压缩软件就成为了一项必须的工具。于是数据压缩软件就成为了一项必须的工具。1985年年SEA 公司开发了公司开发了MS-DOS环境下第一个应用环境下第一个应用LZW算法算法的的ARC压缩软件，它是当时压缩软件，它是当时MS-DOS下统治性的压缩软下统治性的压缩软件。从技术角度来说件。从技术角度来说ARC确实不错，但使用了专利确实不错，但使用了专利LZW算法的算法的ARC当然是标准的商业软件，使用这种软件工作当然是标准的商业软件，使用这种软件工作就必须付费。不过当时许多玩家根本买不起就必须付费。不过当时许多玩家根本买不起ARC软件，软

35、件，顺便说一句题外话，那时大多顺便说一句题外话，那时大多PC玩家基本都没什么富裕玩家基本都没什么富裕的钱，事实上个人计算机本身的发展就是被穷玩家精打的钱，事实上个人计算机本身的发展就是被穷玩家精打细算所推动。不过个人计算机从诞生之日起就充满了叛细算所推动。不过个人计算机从诞生之日起就充满了叛逆、自由的精神，这也是推动整个个人计算机世界前行逆、自由的精神，这也是推动整个个人计算机世界前行的主要动力。此时一个年轻的程序员出现并试图改变压的主要动力。此时一个年轻的程序员出现并试图改变压缩世界，这个人叫缩世界，这个人叫Phillip W.Katz（菲利普（菲利普卡兹）。卡兹）。 2022-7-3第第5

36、1页页/共共80页页 2022-7-3第第52页页/共共80页页 SEA其实不是什么大企业，它只是个其实不是什么大企业，它只是个3人起家的小公司，人起家的小公司，当然无法接受这种毁灭性打击。以现在的眼光看来，最初当然无法接受这种毁灭性打击。以现在的眼光看来，最初SEA的方式是温和的，它接洽菲利普的方式是温和的，它接洽菲利普卡兹并希望通过授权卡兹并希望通过授权的方式将的方式将PKARC纳入旗下，然而并不认为自己有什么过错纳入旗下，然而并不认为自己有什么过错的菲利普的菲利普 卡兹一口拒绝，他不想让卡兹一口拒绝，他不想让PKARC成为商业软件，成为商业软件，他制作这个工具的初衷并不是为了赚钱。最终菲

37、利普他制作这个工具的初衷并不是为了赚钱。最终菲利普卡兹卡兹被被SEA以侵犯以侵犯ARC压缩格式编码算法的罪名告上了法庭，压缩格式编码算法的罪名告上了法庭，并输掉了官司。叛逆倔强的卡兹在败诉后依然拒绝将并输掉了官司。叛逆倔强的卡兹在败诉后依然拒绝将PKARC授权给授权给SEA公司，而选择了支付法律费用和停止发公司，而选择了支付法律费用和停止发放放PKARC。2022-7-3第第53页页/共共80页页 2022-7-3第第54页页/共共80页页 也许是被激怒后带来了惊人的动力，只用了几周的时也许是被激怒后带来了惊人的动力，只用了几周的时间菲利普间菲利普卡兹就创造出一个全新的压缩编码算法，该算卡兹就

38、创造出一个全新的压缩编码算法，该算法完美地结合法完美地结合LZ77和和Huffman编码，也就是后来大名鼎鼎编码，也就是后来大名鼎鼎的的PKZIP，而其文件格式扩展名叫作，而其文件格式扩展名叫作“.zip”。PKZIP可将可将多个文件压缩到一个文件中，无论压缩比、压缩速度都全多个文件压缩到一个文件中，无论压缩比、压缩速度都全面超过了商业软件面超过了商业软件ARC。菲利普。菲利普卡兹将卡兹将PKZIP作为自由作为自由软件免费发放，使其如野火般在全美各大软件免费发放，使其如野火般在全美各大BBS上蔓延开来，上蔓延开来，用户以几何级数增长，遭受毁灭性打击的用户以几何级数增长，遭受毁灭性打击的SEA公

39、司半年内公司半年内就无声无息。这段故事最后演变为用自由软件打败商业软就无声无息。这段故事最后演变为用自由软件打败商业软件的传奇，菲利普件的传奇，菲利普卡兹更是成为充满幻想的年轻程序员卡兹更是成为充满幻想的年轻程序员心中十步杀一人的偶像。心中十步杀一人的偶像。 2022-7-3第第55页页/共共80页页 2022-7-3第第56页页/共共80页页 2022-7-3第第57页页/共共80页页4考虑用 0 和 1 组成的二进制数码为含有 n 个符号的某条信息编码，假设符号 Fn 在整条信息中重复出现的概率为 Pn，则该符号的熵也即表示该符号所需的位数为：熵的计算公式2022-7-3第第58页页/共共

40、80页页算术编码2022-7-3第第59页页/共共80页页 2022-7-3第第60页页/共共80页页 2022-7-3第第61页页/共共80页页2022-7-3第第62页页/共共80页页2022-7-3第第63页页/共共80页页2022-7-3第第64页页/共共80页页2022-7-3第第65页页/共共80页页DCTDCT变换变换4物理意义：将信号从一种表达形式（空物理意义：将信号从一种表达形式（空间域，即图像的像素值）变成另一种等间域，即图像的像素值）变成另一种等同的表达形式（频率域，即频率系数），同的表达形式（频率域，即频率系数），并且这种变换过程是不可逆的。并且这种变换过程是不可逆的。2022-7-3第第66页页/共共80页页DCT DCT 变换变换2022-7-3第第67页页/共共80页页DCTDCT变换变换4DCTDCT变换：