7z文件格式研究
7z文件格式研究 (1)
摘要 (3)
第一章背景介绍 (4)
1.1 压缩软件 (4)
1.2 7z文件格式 (4)
1.3 7-ZIP软件 (4)
第二章主流压缩算法 (6)
2.1 主流压缩算法简介 (6)
2.2 熵编码算法 (6)
2.3 游程编码算法 (7)
2.4 字典压缩算法 (8)
2.5 当前常用的压缩算法 (9)
第三章 7-ZIP软件工作流程 (10)
3.1工作流程 (10)
3.2 Floder概念 (12)
3.2 7z文件格式解析 (13)
第四章 7-ZIP软件实现 (17)
4.1新算法的加入 (17)
4.2算法加入前后压缩性能的对比 (17)
第五章结论 (19)
参考文献 (20)
随着信息技术产业的高速发展，数据的本身的质和量都在不断地变大，由此，对数据压缩和打包的需求也与日俱增；同时，数据安全性要求不断地提高。压缩软件进入了人们的视野。现如今，压缩软件已经成为每台智能设备上必备的软件之一。而7z是一种可以使用多种压缩算法进行数据压缩的档案格式。因此，本人在学习了压缩编码的基本知识的基础上对压缩软件进行了相关的研究。本人通过解读7-ZIP压缩软件源码、研究了7z文件的结构，了解了7-ZIP软件的工作原理，并在在7-ZIP软件中添加了PAQ压缩算法，进一步提升7-ZIP的工作性能。并对改进后的软件进行了性能分析。
第一章背景介绍
1.1 压缩软件
压缩软件，通常也称为解压缩软件。是实现文件流的压缩、解压缩、加密、解密功能的应用软件。现阶段，压缩软件已经成为每个智能设备的标配软件。现如今的压缩软件都配上了丰富的图形界面。当前常用的压缩软件主要有WinRAR、WinZip、好压、快压、360压缩以及7-ZIP压缩等软件。
由于动辄上百G甚至上T的硬盘普及和宽带网络时代已经到来，压缩软据软件的实质的压缩性能也就显得不那么重要了。压缩软件之所以现在依旧流行，是因为其归档技术，就是将数量众多的小文件可以聚合成为一个较大的文件，这样在互联网中进行传输的时候会更加方便。而且现在的压缩软件都逐步加入云功能，实现云备份。但是，本文的研究重点仍旧放在了压缩文件的压缩和解压特性上。
1.2 7z文件格式
7z文件指的是一种后缀名为.7z的文件。7z 文件格式严格的说是一种"打包(Archive)"的格式, 它规定了打包的方法。同时也采用了无损压缩算法，其中
7z默认的压缩算法是LZMA算法。7z格式是开源且具备模块化的组件结构，这就使得第三方可以使用任何压缩，转换或加密算法，而不需要得到软件开发者的许可。当前许多公司开发的压缩软件都是在7z的源码基础上进行适当的更改而得到的。7z格式还具有最高的压缩比，并且其配置了强大的AES-256加密算法，这使得7z格式无论在性能上还是安全性上都具有非常好的利用价值。而且用户可以随意更改和配置压缩的算法，使得其灵活度大大提升。并且7z支持多线程压缩，使得其具有更高的CPU利用率。
1.3 7-ZIP软件
7-ZIP是一款有极高压缩比的开源压缩软件，大多数源代码都基于 GNU LGPL 许可协议下发布，可任意使用。这就使得很多开发者可以使用7-ZIP的源码进行二次开发，从而使得市场上有着较多的性能高并且免费的压缩软件。7-ZIP软件
不仅仅能对7z格式进行压缩和解压，同时也可以对多种其他的压缩格式进行压缩和解压，比如ARJ，CAB，CHM，CPIO，DEB，DMG，HFS，ISO，LHA，LZH，LZMA，NSIS，RPM，RAR，SPLIT，SWM，TBZ，TBZ2，TGZ，TPZ，VHD，WIM，XAR，Z格式。由于该软件开源，所以开发者可以任意修改其源码，使其支持更多的格式，实现更多的功能。
7-ZIP默认使用了LZMA与LZMA2算法，这就使得其具有极高的压缩比。通过实际的数据可以得到，对于 ZIP 及 GZIP 格式，7-Zip 能提供比使用 PKZip 及 WinZip 高 2-10% 的压缩比。具体测试结果如表1：
软件名称
Mozilla Firefox Google Earth
65 个文件
85 280 391 字节
483 个文件
110 700 519 字节压缩后压缩比压缩后压缩比
7-Zip 9.35
-mx
39 357 375100%15 964 369100%
WinRAR 5.20
-m5 -s -ma5 -md128m
41 789 543 106% 17 035 432 107%
表 1
而且7-ZIP本身就提供了完善的AES-256加密算法，并提供了完整的加密解密框架，可以使得第三方开发者进行二次开发。由于7-ZIP是开源软件，因此，7-ZIP软件不能仅仅能在Windows平台下使用，在Linux和Unix平台下都有较好的兼容性。
本人通过阅读7-ZIP源码，了解7z文件格式，理解了7-ZIP的工作流程，然后向7-ZIP中加入新的压缩算法，进一步提升7-ZIP软件的工作性能。
第二章主流压缩算法
2.1 主流压缩算法简介
对于压缩软件来说，无论其实现多么复杂的功能，其核心仍旧是压缩算法。现阶段主要有两种压缩算法：有损压缩算法和无损压缩算法。有损压缩算法通过移除在保真情形下需要大量的数据去存储的小细节，从而使文件变小。在有损压缩里，因某些必要数据的移除，恢复原文件是不可能的。有损压缩主要用来存储图像和音频文件，同时通过移除数据可以达到一个比较高的压缩率，由于压缩软件要保证数据的完整性，因此本文不讨论有损压缩算法。无损压缩算法，也使文件变小，但对应的解压缩功能可以精确的恢复原文件，不丢失任何数据。无损压缩算法被广泛的应用在计算机领域，从节省电脑的空间，到通过web发送数据，都在使用无损压缩算法。
无损压缩算法可行的基本原理是，任意一个非随机文件都含有重复数据，这些重复数据可以通过用来确定字符或短语出现概率的统计建模技术来压缩。统计模型可以用来为特定的字符或者短语生成代码，基于它们出现的频率，配置最短的代码给最常用的数据。这些技术包括熵编码、游程编码以及字典压缩。下面就分别介绍这几种主流的无损压缩算法。
2.2 熵编码算法
数据压缩中，平均来说为了表示一个字符或短语，熵编码意味着所需要的最少比特数。一个基本的熵编码编码器包括一个分析模型以及一套编码。输入文件被解析，并产生一个由字符出现概率组成的统计模型。然后，编码器可以利用该统计模型去决定该给每一个字符多少个比特，从而使得最常用的字符用最短的编码，反之最不常用的字符用最长的编码[1]。
其中最早的熵编码是Shannon-Fano编码，该压缩编码于1949年由Claude Shannon和Robert Fano发明。这个技术的其中一个步骤是产生一个代表字符出现概率的二叉树。字符以这样一种方式排序，出现得越频繁的字符越靠近树的顶端，越不常见的越靠近树的底部。产生Shannon-Fano编码的步骤如下[1]:
1.解析输入，统计每一个字符出现的频率。
2.根据是上述频率计算字符的概率。
3.依据概率对字符降序排序。
4.为每一个字符生成一个叶节点。
5.把字符列表分为左右两部分，使得左边的概率与右边的概率大致相当。
6.左节点加编码”0”，右节点加编码”1”。
7.对两棵子树重复的步骤5和6，直到所有的字符节点都成为叶子节点。
由于二叉树是自下而上构建的，因此Shannon-Fano编码不总是能够产生最优的编码。由于这个原因，使用的较多的还是对于任意输入都能够得到最优编码的Huffman编码。
Huffman编码也是一种熵编码，其二叉树是自上而下构建的，因此其能产生最优编码。
但是如果单论压缩比，Huffman算法并不是最优的压缩算法，算术编码算法确实是一个最优的熵编码技术，通常压缩比方面算术编码要比Huffman编码表现得更好。然而，它却也比其它技术复杂得多。
算术编码不像熵编码把字符概率构建成一棵树，算术编码把输入转化为一个0到1之间的有理数，输入字符的个数记为基底，里面每一个不同的字符都分配一个零到基底之间的值。然后，最后转化为二进制得到最终的结果。结果也可以通过把基底恢复为原来的基底值，替换为对应字符而得到原输入值。
2.3 游程编码算法
游程编码是一个非常简单的压缩技术，把重复出现的多个字符替换为重复次数外加字符。单个字符次数为1。游程编码非常适合数据重复度比较高的数据，同一行有很多像素颜色相同的渐进图片，也可以结合BWT等其它技术一起使用。
BWT算法是1994年发明的技术，目的是可逆的处理一段输入数据，使得相同字符连续出现的次数最大化。BWT自身并不做任何的压缩操作，仅简单地转化数据，让游程编码压缩算法可以更有效的编码。
BWT算法的步骤:
1.创建一个字符串数组。
2.把输入字符串的所有排列组合塞入上述字符串数组。
3.按照字符顺序为字符串数组排序。
4.返回数组的最后一列。
2.4 字典压缩算法
字典压缩算法中最早的算法是LZ77算法。LZ77算法发表于1977年，是名副其实的字典压缩算法开山之作，相较于当时的几个主要压缩算法，压缩比都有非常明显的提高。但是LZ77还是使用窗口方法生成字典。
LZ78于1978年由Lempel和Ziv发明，缩写正是来源于此。不再使用窗口方法来生成字典，输入数据要么被预处理之后用来生成字典，或者字典在文件解析过程中逐渐形成。LZ78采用了后者。字典的大小通常被限定为几兆的大小，或者所有编码上限为几个比特，比如8个。这是出于减少对内存要求的考量。算法如何处理正是LZ78的各个衍生算法的区别所在。但是LZ78有版权的限制，所开发的软件大都是收费软件因此采用这种方法的软件并没有很流行。
LZ78算法解析文件的时候，把新碰到的字符或者字符串加到字典中。针对每一个符号，形如字典索引以及未出现在字典中的符号的字典记录会对应地生成。如果符号已经存在于字典中，那么将从字典中搜索该符号的子字符串以及其后的其它符号。最长子串的位置即为字典索引。字典索引对应的数据被设置为最后一个未知子串。如果当前字符是未知的，那么字典索引设置为0，表示它是单字符对。这些数据对形成一个链表数据结构。这样就是字典的形成过程以及数据结构。其他算法过程和LZ77算法类似。
字典压缩算法在此之后就迅速流行起来，依据LZ77以及LZ78算法为模板，很多字典压缩算法被开发出来，同时字典压缩算法也成为了当今最主流的压缩算法。在此之后，陆续出现了LZR算法、DEFLATE/ DEFLATE64算法、LZSS算法、LZH算法、LZB算法、ROLZ算法、LZP算法、LZRW1算法、LZJB算法、LZS算法、LZX算法、LZO算法、LZMA/LZMA2算法、LZMW算法、LZW算法以及LZJ算法等算法。
2.5 当前常用的压缩算法
基于DEFLATE算法的gzip格式，同时使用了LZ77算法与Huffman 编码算法的一个无损数据压缩算法。
除了用于PNG和ZIP格式之外， DEFLATE算法也被频繁的用在其它地方。例如gzip(.gz)文件格式也使用DEFLATE，gzip是ZIP的一个开源版本。其它还包括HTTP, SSL, 以及其它的高效压缩网络传输数据的技术[2]。
LZMA以及LZMA2这两种算法基本上和LZ77算法是相同的，只不过它操作的是面向比特级别，而非传统上的面向字节级别，用于解析数据。LZMA2优化了多线程的调度，优化了算法的执行速度，并且在压缩效果上有一定程度的提升[2]。
PAQ于2002年由Matt Mahoney发明，是老版PPM的一个改进版。改进的方法是使用一项叫做context mixing的革命性技术。Context mixing是指智能地结合多个(PPM是单个模型)统计模型，来做出对下一个符号的更好预测，比其中的任何一个模型都要好。这也使得PAQ算法是当前压缩比最高的算法[2]。
bzip2是BWT算法的一个开源实现。它的操作原理很简单，不过却在压缩比和速度之间达到了一个平衡。首先，使用了一个游程编码器，接下来，BWT算法加入进来，然后，使用BWT算法中的转移方法以达到产生大量相同符号的目标，为接下来的另一个游程编码算法做准备。最后结果用Huffman编码，将一个消息头与其打包[3]。
第三章 7-ZIP软件工作流程
3.1工作流程
在7z的压缩过程中，一个非常核心的概念就是coder。一个coder代表一个算法，通常是指一个压缩或解压算法(也包括过滤算法和加密算法等)。例如，在7z中LZMA算法就是一个coder，DEFLATE算法也是一个coder。7z中用于加密的AES256算法也是一个coder。其处理方法如图1：
图 1
这就是单独的一个coder的工作流程，其中文件流的生成是由7-ZIP软件在预先就已经做好了的。通常来讲，一个coder只能处理一个输入流，并且只有一个输出流。比如把一个文件流压缩成一个输出流。但是，7z中有的coder可以把一个输入流处理成多个输出流，反过来也可以把多个流处理成一个流。比如7z的BCJ2 coder，它是一个过滤coder，可以把一个exe文件过滤成四个输出流。这样的话, 7z的coder概念得到了扩展。就是可能同时处理多个输入流，并且可能输出多个流:
图2
下面就介绍7-ZIP软件的具体工作流程了（以LZMA算法为例）：
1.将文件流交给LZMA算法进行压缩，如图3：
图3
2.多个coder进行级联，由熵理论，多个压缩coder级联是没有意义的，这样不会大幅提高压缩率，反而会增加计算成本，通常coder的级联是与加密coder进行的级联，如图4所示：
图4
这样，一次完整的7-ZIP软件按的压缩过程就已经结束了。
对于解压来所，是压缩过程的一个逆过程。
3.2 Floder概念
实际上，7z概念上最小的压缩单位不是文件, 而是FOLDER，它会先把所有的文件都归到一个相应的FOLDER中，然后让这个FOLDER作为文件流，流过若干个Coder。
对于7-ZIP中的FOLDER要特别注意，它不是我们通常指的文件夹。它也不是任何物理上存在的东西。
7z在开始压缩之前，会把文件分类，大体上是按文件类型以及文件是否需要加密来分类的。比如说，把所有的exe文件分成一类(一个FOLDER), 或者把所有需要加密的文件分在一起。这个分类方法并不重要, 用户可以自己定义FOLDER的分类方法，7z的实现用的方法比较简单。用户可以给每个文件划分成一个FOLDER。
假设有五个文件a.exe、b.exe、c.dll、a.txt、b.txt需要压缩，具体的压缩流程如图5所示：
图5
其压缩流程主要分为两步：
1. 首先，通过一定的分组方法，我们分成了两个FOLDER，第一个FOLDER 包括: a.exe, b.exe 和 c.dll 三个文件。第二个FOLDER包括:a.txt和b.txt。
2. 对FOLDER1来说，它包含三个文件，FOLDER1就简单的把三个文件串联起来，当做一个大文件，作为输入流 i1 给Coder1 用。后面的过程就就是上面的图5的内容了。
3.2 7z文件格式解析
7z文件的总体结构，总共分为了三个部分。首先是前文件头；然后是压缩数据；最后是尾文件头。具体格式如图6所示：
图6
首先是前文件头，前文件头是32个字节定长的。前文件头其实记录的信息很少, 它的主要目的是记录尾文件头的位置，压缩信息的主要结构都是存在尾文件头中。
前文件头开头是固定的6个字节的值, 前两个字节的值是字母 '7' 和'z'的ascii值。后面四个字节是固定的: 0xbc， 0xaf, 0x27, 0x1c。
然后是两个字节的版本号,之后是四个字节的UINT32的值, 对于这四个字节来说，由于7z的所有数据都是采用小端在前的存储, 所以这四个字节的实际存储顺序是低位字节在前面, 高位字节在后。后面的所有数据都是这种结构, 所以以后就不再强调了。这4个字节是剩下的20个字节的CRC校验值。
最后这20个字节，先是8个字节的UINT64的值, 它记录的是尾文件头与前文件头的距离, 这个距离是不算前面这32个字节头的, 也就是抛开前面32个字节开始计数的(7-ZIP软件通过读取这个值,然后从第33个字节开始直接跳过这个距离，就可以找到尾文件头了)。然后是8个字节的值, 记录了尾文件头的大小(解压的时候, 通过这个值就能读出尾文件头的长度了)。最后还有4个字节的值, 它也是一个Crc校验值，是整个尾文件头的校验值。
压缩数据就是数据流压缩过后的FOLDER的数据。7-ZIP会把文件压缩成若干个包, 这里就是按顺序存储这些包的。每个包的位置和大小信息都会记录在尾
文件头中，解压的时候就会从这里读出包，然后解压出来。
尾文件头是7z格式中最重要的部分，其存储了压缩文件每个包的信息，包括采用的压缩算法，加密算法，FOLDER的结构等信息。对于尾文件头，采用了两种的生成方法。
第一种方法，就是把尾文件头的内容直接写在后面，不做任何处理。
这种方式最简单，但是却最不常用。因为当用户要压缩大量的文件，尾文件头里面就会有大量的空间用来存储文件名，文件大小，文件时间等等。通常这些信息很多，而且重复信息特别多。对于这些简单的文本信息，其可压缩性非常强。换句话说，这些信息的压缩比比较大。
第二种方法，把原始的尾文件头信息用LZMA算法再压缩一次。这样可以显著的减少尾文件头的大小，尤其是在大量文件的时候。其形成的文件如图7所示：
图7
尾文件头压缩的思路，就是把原始的尾文件头数据当做一个单独的文件流来进行一次前面的压缩过程。就是重复一次前面的7z的压缩过程。不过这一次只有一个文件，因此只划分一个FOLDER。而且压缩方法是指定的LZMA。也就是说只有一个Coder参与。当然，原始尾文件头的内容可能有敏感信息。比如里面的文件名等等信息。因此，7z也提供能力在压缩尾文件头的时候同时加密它。所以压缩尾文件头的时候如果选择加密头信息，则会加入AES加密。其具体工作流程如图8所示：
图8
这种处理的优点是，可以直接通过加密的方式把文件结构隐藏，在第三方不知道密码的情况下，如果选择加密文件头，是无法看到整个压缩文件的文件结构的，这一点ZIP是做不到的。
第四章 7-ZIP软件实现
4.1新算法的加入
本章主要介绍本人通过查阅相关资料阅读相关代码从而将PAQ算法加入到了7-ZIP软件中去了。前面已经介绍过了PAQ算法的实现原理了，根据GPL开源协议，PAQ算法是开放源码的。因此本人将已经开源的PAQ算法的源码加入到了7z-ZIP软件中。在整体的压缩流程上与原7z-ZIP软件是一样的。具体测试数据见4.2。
4.2算法加入前后压缩性能的对比
本章将7z-ZIP自带的LZMA算法，PPM算法，BZIP2算法以及后嵌入的PAQ 算法对同一文档进行压缩，通过比较其压缩后的大小与压缩前的大小进行比较，可以检测改进的算法在文件压缩中是否有性能提升的作用。
这些软件所选取的测试平台均为Windows 7 32bit，处理器为i7 2860qm @ 2.5GHz，内存为2GB。
选取Python27这个包含了很多文件的文档进行压缩，该文档包含4802 个文件，205 个文件夹，其中大部分是小文档，exe程序。经过三种压缩算法进行压缩后，得到结果如图 9所示。
图10 压缩后对比图
具体性能参数如下表 2所示：(压缩率越小表示压缩效果越好)
表 3 采用不同算法压缩Python27文件夹的性能比较
下面测试视频压缩能力，选择三个mp4视频文件分别进行压缩，并对其性能进行比较，测试结果如图11所示：
图12 压缩后对比图
具体性能参数如下所示：(压缩率越小表示压缩效果越好)
由此可以看出，无论是对小文件进行打包，还是对大文件进行压缩，经过加入PAQ算法的7z-ZIP在压缩性能上有了较大的提升。
第五章结论
经过将近两个月的源码阅读与源码适配，通过阅读7z-ZIP软件的源码与官方文档，本人理解了压缩软件的工作流程，压缩文件的格式，以及开发压缩文件类软件的基本方法，通过将开源的PAQ算法加入到7z-ZIP中，提高了7z-ZIP 软件的工作能力，同时也积累的宝贵的开发经验，为后续的科研工作打下了基础。
参考文献
[1] 摘自https://www.doczj.com/doc/e713398141.html,/archives/368.html
[2] 摘自https://www.doczj.com/doc/e713398141.html,/76676/
[3] 摘自https://https://www.doczj.com/doc/e713398141.html,/category/zip-7z/
1、平均自信息为 表示信源的平均不确定度，也表示平均每个信源消息所提供的信息量。 平均互信息 表示从Y获得的关于每个X的平均信息量，也表示发X前后Y的平均不确定性减少的量，还表示通信前后整个系统不确定性减少的量。 2、最大离散熵定理为：离散无记忆信源，等概率分布时熵最大。 3、最大熵值为。 4、通信系统模型如下： 5、香农公式为为保证足够大的信道容量，可采用（1）用频带换信噪比；（2）用信噪比换频带。 6、只要，当N足够长时，一定存在一种无失真编码。 7、当R＜C时，只要码长足够长，一定能找到一种编码方法和译码规则，使译码错误概率无穷小。 8、在认识论层次上研究信息的时候，必须同时考虑到形式、含义和效用三个方面的因素。 9、1948年，美国数学家香农发表了题为“通信的数学理论”的长篇论文，从而创立了信息论。 按照信息的性质，可以把信息分成语法信息、语义信息和语用信息。
按照信息的地位，可以把信息分成 客观信息和主观信息 。 人们研究信息论的目的是为了 高效、可靠、安全 地交换和利用各种各样的信息。 信息的 可度量性 是建立信息论的基础。 统计度量 是信息度量最常用的方法。 熵 是香农信息论最基本最重要的概念。 事物的不确定度是用时间统计发生 概率的对数 来描述的。 10、单符号离散信源一般用随机变量描述，而多符号离散信源一般用 随机矢量 描述。 11、一个随机事件发生某一结果后所带来的信息量称为自信息量，定义为 其发生概率对数的负值 。 12、自信息量的单位一般有 比特、奈特和哈特 。 13、必然事件的自信息是 0 。 14、不可能事件的自信息量是 ∞ 。 15、两个相互独立的随机变量的联合自信息量等于 两个自信息量之和 。 16、数据处理定理：当消息经过多级处理后，随着处理器数目的增多，输入消息与输出消息之间的平均互信息量 趋于变小 。 17、离散平稳无记忆信源X 的N 次扩展信源的熵等于离散信源X 的熵的 N 倍 。 18、离散平稳有记忆信源的极限熵，=∞H )/(lim 121-∞→N N N X X X X H Λ。 19、对于n 元m 阶马尔可夫信源，其状态空间共有 nm 个不同的状态。 20、一维连续随即变量X 在[a ，b]区间内均匀分布时，其信源熵为 log2（b-a ） 。 21、平均功率为P 的高斯分布的连续信源，其信源熵，Hc （X ）=eP π2log 21 2。 22、对于限峰值功率的N 维连续信源，当概率密度 均匀分布 时连续信源熵具
信息论基础发展史 信息论（information theory）是运用概率论与数理统计的方法研究信息、信息熵、通信系统、数据传输、密码学、数据压缩等问题的应用数学学科。是专门研究信息的有效处理和可靠传输的一般规律的科学，是研究通讯和控制系统中普遍存在着信息传递的共同规律以及研究最佳解决信息的获限、度量、变换、储存和传递等问题的基础理论。信息论将信息的传递作为一种统计现象来考虑，给出了估算通信信道容量的方法。信息传输和信息压缩是信息论研究中的两大领域。这两个方面又由信息传输定理、信源－信道隔离定理相互联系。 信息论从诞生到今天，已有五十多年历史，是在20世纪40年代后期从长期通讯实践中总结出来的，现已成为一门独立的理论科学，回顾它的发展历史，我们可以知道理论是如何从实践中经过抽象、概括、提高而逐步形成的。它是在长期的通信工程实践和理论研究的基础上发展起来的。 通信系统是人类社会的神经系统，即使在原始社会也存在着最简单的通信工具和通信系统，这方面的社会实践是悠久漫长的。电的通信系统(电信系统)已有100多年的历史了。在一百余年的发展过程中，一个很有意义的历史事实是：当物理学中的电磁理论以及后来的电子学理论一旦有某些进展，很快就会促进电信系统的创造发明或改进。 当法拉第(M．Faraday)于1820年--1830年期间发现电磁感应的基本规律后，不久莫尔斯(F．B．Morse)就建立起电报系统(1832—1835)。1876年，贝尔(A．G．BELL)又发明了电话系统。1864年麦克斯韦(Maxell)预言了电磁波的存在，1888年赫兹(H．Hertz)用实验证明了这一预言。接着1895年英国的马可尼(G.Marconi)和俄国的波波夫(A．C．ΠoΠoB)就发明了无线电通信。本世纪初(1907年)，根据电子运动的规律，福雷斯特(1，Forest)发明了能把电磁波
信息论实验报告 学生： 班级： 学号：
实验一香农编码一、程序设计的流程图 二、程序清单 #include
#include
aa=tem-1; } else { MM[i]+='0'; aa=tem; } } } string BB[N]; for(int i=0;i 信息论基础结课论文 摘要：信息的产生与应用始终贯穿在人类进化与文明发展的整个过程中，，人类社会的生存和发展都离不开信息的获取、传递、处理、再生、控制和处理。而信息论正是一门把信息作为研究对象，以揭示信息的本质特性和规律为基础，应用概率论、随即过程和数理统计等方法来研究信息的存储、传输、处理、控制、和利用等一般规律的学科。在信息论的指导下，信息技术得到飞速发展，这使得信息论渗透到自然科学和社会科学的所有领域。数学作为基础学科，与信息论的关系十分密切。 关键字：信息论、确立与发展、应用、与数学的联系 信息是一个十分通俗而又广泛的名词，通常是指音信、消息，它的产生与应用始终贯穿在人类进化和文明发展的整个过程中。中国古代有个《烽火戏诸侯》的故事，周幽王为了搏得褒姒的“千金一笑”而点燃了战时传递敌情的烽火来戏耍诸侯，结果失信天下，为后来西周的灭亡埋下了隐患。《三国演义》中蜀国大将关羽“大意失荆州”的原因之一就是东吴将士偷袭了荆州的烽火台，切断了烽火报信的信息源，结果荆州遭到“攻其不备”而失陷。虽然在古代信息传递非常不便，有“烽火连三月，家书抵万金”的难处，但仍然有“鸿雁捎信”、“柳絮传书”等动人的故事。由此可以看出，人类对信息的认识和利用是古已有之。在社会发展的现代生活中，从手机到个人电脑，从书本文件到卫星通信，信息几乎是在各个领域发挥着重要的作用。虽然信息技术在人类历史的进程当中随着生产力的进步而发展，但是信息理论的提出却远远落后于信息的出现，它是在近代才被提出来而形成一套完整的理论体系。 1948年美国杰出科学家香农的著名论文《通信的数学理论》的发表，标志着信息论的诞生。所以，信息论一般是指香农信息论，它是信息科学产生的基础与起点，从20世纪40年代末起，它已经经历了半个多世纪的发展。在这半个多世纪中，人类文明与科学技术经历了一个突飞猛进的发展，信息论与信息科学的发展与变化正是人类文明与科学进步的标志与见证。 自香农理论产生之后，它的发展大体经历了理论的确立与发展、理论的应用与近代史发展几个阶段。1948年到20世纪60年代是理论的确立期，在这一时期中，香农信息论完成了信息度量与通信中的基本问题结合，并对这些问题实现了严格的数学描述论证。从信息的度量到通信模型，从编码问题到主要编码的定理证明，都是在严格的数学定义与证明中完成。20世纪70、80年代，信息论处于理论发展期。由于香农理论的阐明与通信技术的发展，信息论的研究范围日益扩大，这一时期发展的主要体现在“率失真理论”与“多用户信息论”方面。20世纪90年代前后，信息论得到了迅速发展，其主要特点是理论的成功应用与多学科结合，并且在IT领域等多个领域取得显著成就。 信息论是运用概率论与数理统计的方法研究信息、信息熵、通信系统、数据传输、密码学、数据压缩等问题的应用数学学科，是专门研究信息的有效处理和可靠传输的一般规律的科学，是研究通讯和控制系统中普遍存在着信息传递的共同规律以及研究最佳解决信息的获限、度量、变换、储存和传递等问题的基础理论。它主要基本理论包括：信息的定义和度量；各类离散信源和连续信源的信息熵；有记忆、无记忆离散和连续信道的信道容量；无失真信源编码定理。通信的根本目的是将信息有效而可靠的从信源传到信宿。信息论将信息的传递作为一种统计现象来考虑，给出了估算通信信道容量的方法。信息传输和信息压缩是信息论研究中的两大领域。这两个方面又由信息传输定理、信源－信道隔离定理相互联系。 信息科学是以信息为研究对象的独立学科，以信息的运动规律和应用方法为主要研究内容，以计算机等技术为主要研究工具的研究信息运动规律和应用方法，由信息论、控制论、计算机理论、人工智能理论和系统论相互渗透、相互结合而成。由于信息的广泛性与普遍性，它独立于其他自然科学与社会科学中的各门学科。 信息技术是主要用于管理和处理信息所采用的各种技术的总称，它主要应用计算机科学 成绩： 2016-2017学年第1学期 《信息论》课程设计 学院名称： 班级学号： 学生姓名： 教师姓名： 2016年12月 一、判定唯一可译码 1. 任务说明 输入：任意的一个码(即已知码字个数及每个具体的码字) 输出：判决结果（是/不是） 输入文件:in1.txt ，含至少2组码，每组的结尾为”$”符 输出文件:out1.txt ，对每组码的判断结果 说明：为了简化设计，可以假定码字为0，1串 2. 实现原理 判断方法：将码C 中所有码字可能的尾随后缀组成一个集合F ，当且仅当集合F 中没有 包含任一码字，则可判断此码C 为唯一可译变长码。 构成集合F ：首先观察码C 中最短的码字是否是其他码字的前缀。若是，将其所有可能 的尾随后缀排列出。就是将其他码字序列中截去与其最短码字相同的前缀 部分，将余下的序列为尾随后缀。而这些尾随后缀又可能是某些码字的前 缀，或者最短码字又仍是这些尾随后缀的前缀，再将由这些尾随后缀产生 的新的尾随后缀列出。然后再观察这些新的尾随后缀是否是某些码字的前 缀，或观察有否其他码字是这些新的尾随后缀的前缀，再将产生的尾随后 缀列出，依次下去，直至没有一个尾随后缀是码字的前缀或没有新的尾随 后缀产生为止。这样，首先获得的是由最短码字能引起的所有尾随后缀。 接着，按照上述步骤将次短的码字、......所有码字可能产生的尾随后缀前部 列出。由此得到由码C 的所有可能的尾随后缀组成的集合F 。 参考算法伪代码： For all ,i j W W C ∈ do if i W 是j W 的前缀 then 将相应的后缀作为一个尾随后缀放入集合0F 中 End if End for Loop For all i W C ∈ do For all j n W F ∈ do if i W 是j W 的前缀 then 将相应的后缀作为一个尾随后缀放入集合1n F +中 Else if j W 是i W 的前缀 then 将相应的后缀作为一个尾随后缀放入集合1n F +中 End if End for End for i i F F ← If ,i i W F W C ?∈∈ then Return false Else if F 中未出现新的元素 then Return true End if //能走到这里，说明F 中有新的元素出现，需继续 End loop 信息论与编码课程论文 电子邮件安全与密码学的应用 刘畅，200900840179 山东大学威海分校机电与信息工程学院，威海 264209 摘要：本文分析了传统电子邮件系统存在的安全性问题，探讨应用密码技术采弥补这些安全漏洞，并且绍了在安全电子邮件系统中使用的密码技术。 关键词：RSA；PGB；PEM 1、概述 随着计算机技术和网络技术的迅速发展，电子邮件的应用也越来越广泛．成为网络牛活中重要的组成部分，大有取代传统邮件之势。作为一种新的信息传递技术，电子邮件以其简单、快捷、方便的优势被人们所接受和喜爱。但是也存在一些问题妨碍了它的推广。其中关键之一就是电子邮件的信息安全。由于电子邮件技术在设计之初是为了科学家之间的通信方便，所以并来考虑信息安全因素。但是髓着时代的发展。尤其是电子商务的速成长。作为其沟通手段的电子邮件的安全性问题就不得不受到高度重视。人们很自然的想到把已经成熟的密码技术商用于电子邮件系统。密码技术就是对信息进行重新编码。从而达到隐藏信息内容使非法用户无法获取真实信息内容的一种手段。本文就浅述一下密码技术安全电子邮件中的应用。 2、密码学简介 2.1、加密的历史 作为保障数据安全的一种方式，数据加密起源于公元前2000年。埃及人是最先使用特别的象形文字作为信息编码的人。随着时间推移，巴比伦，希腊等都开始使用一些方法来保护他们的书面信息。对信息进行编码曾被Julias Caesar（恺撒大帝）使用，也曾用于历次战争中，包括美国独立战争，美国内战和两次世界大战。最广为人知的编码机器是German Enigma机，在第二次世界大战中德国人利用它创建了加密信息。此后，由于Alan Turing 和Ultra计划及其他人的努力，终于对德国人的密码进行了破解。当初，计算机的研究就是为了破解德国人的密码，当时人们并没有想到计算机给今天带来的信息革命。随着计算机的发展，运算能力的增强，过去的密码都变的十分简单了。于是人们又不断地研究出了新的数据加密方式，如私有密钥算法和公有密钥算法。可以说，是计算机推动了数据加密技术的发展。 2.2、密码学的发展 密码学的发展可以分为两个阶段。第一个阶段是计算机出现之前的四千年（早在四千年前，古埃及就开始使用密码传递消息），这是传统密码学阶段，基本上靠人工对消息加密、传输和防破译。第二阶段是计算机密码学阶段，包括： ①传统方法的计算机密码学阶段。解密是加密的简单逆过程，两者所用的密钥是可以简单地互相推导的，因此无论加密密钥还是解密密钥都必须严格保密。这种方案用于集中式系统是行之有效的。 ②包括两个方向：一个方向是公用密钥密码（RSA），另一个方向是传统方法的计算机密码体制——数据加密标准（DES）。 信息论基础调研报告 一.信息论的起源： 信息论理论基础的建立，一般来说开始于1948年美国数学家香农在《贝尔系统电话杂志》发表题为“通信的数学理论”的长篇论文。这篇论文以概率论为工具，深刻阐释了通信工程的一系列基本理论问题，给出了计算信源信息量和信道容量的方法和一般公式，得出了一组表征信息传递重要关系的编码定理，从而创立了信息论。 信息论自诞生到现在不过60多年，在人类科学史上是相当短暂的。但它的发展对学术界以及人类社会的影响是相当广泛和深刻的。信息作为一种资源，如何开发、利用、共享，是人们普遍关心的问题。 信息论是研究信息的传输、存储和处理的学科，亦称“信息论”为“通信的数学理论”。它主要研究在通信系统设计中如何实现信息传输的有效性和可靠性。 因此，信息论与通信技术、统计数学信号处理等密切相关。 二.信息技术的发展： 现代信息论其实是从上世纪二十年代奈奎斯特和哈特莱的研究开始的，他们最早开始研究了通信系统传输信息的能力，并且试图度量系统的信道容量。 香农于1940年在普林斯顿高级研究所期间开始思考信息论与有效通信系统的问题。经过8年的努力，1948年，来自贝尔研究所的Claude Shannon（克劳德·香农）的《通信的数学理论》论文公诸于世，从此宣告了崭新的一门关于信息发面的学科──信息论的诞生。1949年，香农又在该杂志上发表了另一著名论文《噪声下的通信》。在这两篇论文中，香农阐明了通信的基本问题，给出了通信系统的模型，提出了信息量的数学表达式，并解决了信道容量、信源统计特性、信源编码、信道编码等一系列基本技术问题。两篇论文成为了信息论的奠基性著作。这两篇论文一起阐述了现代信息论的基础。并且香农开始创造性的定义了“信息”。 信息论自从二十世纪四十年代中叶到二十一世纪初期，现已成为一门独立的理论科学，他给出一切传输、存储、处理信息系统的一般理论，并指出，实现有效、可靠地传输和存储信息的途径是走数字化的道路。这是通信技术领域数字化革命的数学或理论基础。1946年的计算机和1947年晶体管的诞生和相应技术的发展，是这一革命的物理或物质基础。信息论是在长期的通信工程实践和理论研究的基础上发展起来的。 20世纪50年代，包括香农在内的一些科学家做了大量的工作，发表了许多重要文章，将香农的科学论断进一步推广，同时信道编码理论有了较大的发展。20世纪60年代，信道编码技术已经成为信息论的又一重要分支。它把代数方法引入到纠错码的研究，使分组码技术达到了高峰，找到了可纠正多个错误的码，并提出了可实现的译码方法。其次是卷积码和概率译码有了重大突破，提出了序列译码和维特比译码方法。 1961年，香农的重要论文“双路通信信道”开拓了多用户信息理论的研究。到70年代，由于数字计算机的广泛应用，通讯系统的能力也有很大提高，如何 从通信联合收发优化剖析香农三大定理 --“信息论与编码”课程论文 课程：信息论与编码 指导老师：王忠 姓名：秦天柱 学号：2012141441420 摘要 本文立足之点为通信系统的收发联合优化，主要根据一种基于广义的率失真函数的信源编码、信道编码和差错隐藏联合优化的方法对此进行讨论。并在此基础上，对香农三大定理进行剖析，分析了香农三大定理的内在联系与通信系统理论构建之间的关系。 1 引言 随着现代通信技术的发展，通信的重要性不言而喻。早在二十世 纪四十年代初，香农提出三大定理，奠定了通信的数字理论基础。用户数量也随之增长，传输错误当然也不可避免。自此，容错恢复编码技术近年来成为无线视频传输研究中的热点。传统的方法[ 3, 4] 往往假设视频信源是统计平稳的，然后对整个视频序列建立经验的或理论的率失真模型来进行码率分配优化；并且只考虑信源编码和信道编码本身的性能，而没有考虑差错隐藏技术的影响。 本文着重分析了一种针对图像局部区域的信源信道编码以及差错隐藏特性的广义的率失真函数. 这种基于局部广义率失真特性的信源 编码,信道编码和差错隐藏的联合优化(以下简称JSCE)有可能取得更好的视频传输效果。并由此将香农的三大定理（无失真信源编码定理、信道编码定理和限失真信源编码定理）进行剖析，深入研究其内在联系和为通信系统的联合优化提供的理论支撑。 2 通信系统的联合优化 2.1 广义的率失真函数 在进行无线视频传输的码率优化分配时,我们将信源编解码,信道 编解码和差错隐藏联合起来进行考虑.失真因素包括信源的量化误差,信道传输错误而引起的失真,以及差错隐藏的增益优化的目的, 是在一定的码流速率和信道条件下,获得最小的端对端失真. 论最大熵原理及其应用 摘要：熵是源于物理学的基本概念，后来Shannon 在信息论中引入了信息熵的概念，它在统计物理中的成功使人们对熵的理论和应用有了广泛和高度的重视。最大熵原理是一种在实际问题中已得到广泛应用的信息论方法。本文从信息熵的概念出发，对最大熵原理做了简要介绍，并论述了最大熵原理的合理性，最后提及它在一些领域的应用，通过在具体例子当中应用最大熵原理，展示该原理的适用场合，以期对最大熵原理及其应用有更深刻的理解。 关键词：熵；信息熵；最大熵原理；不适定性问题 1 引言 科学技术的发展使人类跨入了高度发展的信息化时代。在政治、军事、经济等各个领域，信息的重要性不言而喻，有关信息理论的研究正越来越受到重视，信息论方法也逐渐被广泛应用于各个领域。 信息论一般指的是香农信息论，主要研究在信息可以度量的前提下如何有效地、可靠地、安全地传递信息，涉及消息的信息量、消息的传输以及编码问题。1948年C.E.Shannon 为解决通信工程中不确定信息的编码和传输问题创立信息论，提出信息的统计定义和信息熵、互信息概念，解决了信息的不确定性度量问题，并在此基础上对信息论的一系列理论和方法进行了严格的推导和证明，使以信息论为基础的通信工程获得了巨大的发展。信息论从它诞生的那时起就吸引了众多领域学者的注意，他们竞相应用信息论的概念和方法去理解和解决本领域中的问题。近年来，以不确定性信息为研究对象的信息论理论和方法在众多领域得到了广泛应用，并取得了许多重要的研究成果。迄今为止，较为成熟的研究成果有：E.T.Jaynes 在1957年提出的最大熵原理的理论；S.K.Kullback 在1959年首次提出后又为J.S.Shore 等人在1980年后发展了的鉴别信息及最小鉴别信息原理的理论；A.N.Kolmogorov 在1956年提出的关于信息量度定义的三种方法——概率法，组合法，计算法；A.N.Kolmogorov 在1968年阐明并为J.Chaitin 在1987年系统发展了的关于算法信息的理论。这些成果大大丰富了信息理论的概念、方法和应用范围。 在信息论中，最大熵的含义是最大的不确定性，它解决的一大类问题是在先验知识不充分的条件下进行决策或推断等。熵方法在谱估计、图象滤波、图象重建、天文信号处理、专家系统等中都有广泛的应用。最大熵原理在实际问题中的应用近年来一直在不断地发展。 2 信息熵的概念 信息熵是将熵概念成功地扩展到信息科学领域。熵是描述客观事物无序性的参数，它最早是由R.Clausius 于1865年引入热力学中的一个物理概念，通常称之为热力学熵。后来L.Boltzmann 赋予熵统计意义上的解释，称之为统计热力学熵。1929年，匈牙利科学家Lszilard 首先提出了熵与信息不确定性的关系，使信息科学引用熵的概念成为可能。1948年，贝尔实验室的C ．Shannon 创立了信息论，熵的概念有了新的解释，香农认为信息是人们对事物了解的不确定性的消除或减少 ，他把通讯过程中信源讯号的平均信息量称为信息熵，现在一般称之为香农熵，实现了信息熵的实际应用，从此对信息熵的研究，随着信息科学的发展而得到不断的发展。 香农将随机变量X 的信息熵定义为： =)(X H －n N n n p p log 1∑= 信息论与编码应用报告互信息技术在数字图像配准中的应用 专业班级：电子信息工程 姓名： 学号：201 时间：2014年6月9日 指导老师： 2014年6月9日 目录 摘要： (1) Abstract： (2) 前言 (3) 1 概述 (4) 1.1 互信息与信息论 (4) 1.2 数字图像配准 (5) 1.2.1 数字图像配准的介绍 (5) 1.2.2 数字图像配准的方式 (5) 1.2.3 数字图像配准的发展 (6) 2 配准方法 (7) 2.1 变换和插值模型 (7) 2.2 特征点的提取 (8) 2.3 多元互信息 (11) 2.4 优化算法 (12) 2.4.1 编码方式 (12) 2.4.2适应度表示 (12) 2.4.3轮盘赌法和最优保存策略 (12) 3 互信息技术在图像配置中的应用 (13) 3.1 Harris角点后的CT图和PET图 (14) 3.2 配准过程及结果 (14) 4 总结 (14) 参考文献： (16) 互信息技术在数字图像配准中的应用 信息与计算科学专业 指导教师 【摘要】：医学图像配准技术已经被应用于心脏病诊断和包括脑瘤在内的各种各样的神经混乱诊断研究中。图像配准是使两幅图像上的对应点达到空间上一致的一个过程。本文介绍了一种基于最大互信息原理的图像配准技术。并针对基于最大互信息图像配准的不足，研究了基于Harris角点算子的多模态医学图像配准。在计算互信息的时候，采用部分体积插值法计算联合灰度直方图。在优化互信息函数的时候采用了改进的遗传算法将配准参数收敛到最优值附近。实验结果表明本方法具有较高的配准精度和稳定性。 【关键词】：图像配准互信息 Harris角点算子部分体积插值遗传算法 前言 互信息是信息论的一个基本概念，是两个随机变量统计相关性的测度。Woods用测试图像的条件熵作为配准的测度，用于PET 到MR 图像的配准。Collignon 、Wells[1] 等人用互信息作为多模态医学图像的配准测度。以互信息作为两幅图像的相似性测度进行配准时，如果两幅基于共同解剖结构的图像达到最佳配准时，它们对应的图像特征互信息应为最大。最大互信息法几乎可以用在任何不同模式图像的 联合信源各种熵的计算 一、摘要： 在人类社会中，人与人之间要经常互通情报，交换消息，从一般意义上讲这就是通信。因此传递信息就是通信的根本目的。信源需要传递的事情一般是属于随机事件，也就是其状态是随机的。源熵是信息论中用来衡量信源信息量有序化程度的一个概念。信源熵值与信源有序化程度成反比；有序度越高，信源熵值越低，反之亦成立。信源各个离散消息的自信息量的数学期望（即概率加权的统计平均值）。本文主要研究了联合信源的各种伤的计算。 关键词： 条件熵 非条件熵 共熵 联合信源 二、问题分析： 由这两个信源构成了联合信源的各种概率空间： 联合概率空间——{,()}i j XY p x y 条件概率空间——{/,(/)}j i Y X p y x ，{/,(/)}i j X Y p x y 以下分别对二元联合信源的共熵，条件熵，非条件熵和最大熵进行求解。 1、二元联合信源的共熵： 共熵反映的是每当两个信源同时发送一对消息时，所提供的平均信息量。 二元联合信源的共熵（或联合熵）的定义： ,,1 ()()log ()log ()()i j i j i j i j i j i j H XY p x y p x y p x y p x y ==-∑∑ 2、二元联合信源的条件熵： (1).X 给定的情况下Y 的条件熵： ,,1(/)()log ()log (/)(/) i j i j j i i j i j j i H Y X p x y p x y p y x p y x ==-∑∑ 条件熵H(X/Y)所反映的是信源X 给定的条件下，信源Y 所提供的平均信息量。 (2).Y 给定的情况下X 的条件熵： ,,1 (/)()log ()log (/)(/)i j i j i j i j i j i j H X Y p x y p x y p x y p x y ==-∑∑ 条件熵H(Y/X)所反映的是信源Y 给定的条件下，信源X 所提供的平均信息量。 3、最大熵： 当X,Y 相互独立时，()()()()MAX H XY H X H Y H XY =+-- 三。、程序代码： %---------输入先验概率 转移矩阵 fprintf('\n 请输入先验概率P_x 和状态转移概率P_y_x\n'); eps=1e-8; P_x=input('P_x=')+eps; %+eps 是为了防止概率为0使，对数无意义 P_y_x=input('P_y_x=')+eps; if (min(P_x(:))<0 | max(P_x(:)>1))|(min(P_y_x(:))<0|max(P_x(:)>1)) error('The data shoud be any numbers between 0 and 1.'); end ; eps=1e-10; if min(sum(P_y_x')-1) 信息论发展 现代信息论是从上世纪二十年代奈奎斯特和哈特莱的研究开始的,他们最早开始研究了通信系统传输信息的能力,并且试图度量系统的信道容量。香农于1940年在普林斯顿高级研究所期间开始思考信息论与有效通信系统的问题。经过8年的努力,1948年,来自贝尔研究所的ClaudeShannon（克劳德·香农）的《通信的数学理论》论文公诸于世,从此宣告了崭新的一门关于信息发面的学科──信息论的诞生。1949年,香农又在该杂志上发表了另一著名论文《噪声下的通信》。在这两篇论文中,香农阐明了通信的基本问题,给出了通信系统的模型,提出了信息量的数学表达式,并解决了信道容量、信源统计特性、信源编码、信道编码等一系列基本技术问题。两篇论文成为了信息论的奠基性著作。这两篇论文一起阐述了现代信息论的基础。并且香农开始创造性的定义了“信息”。 信息论自从二十世纪四十年代中叶到二十一世纪初期,现已成为一门独立的理论科学,他给出一切传输、存储、处理信息系统的一般理论,并指出,实现有效、可靠地传输和存储信息的途径是走数字化的道路。这是通信技术领域数字化革命的数学或理论基础。1946年的计算机和1947年晶体管的诞生和相应技术的发展,是这一革命的物理或物质基础。信息论是在长期的通信工程实践和理论研究的基础上发展起来的。当物理学中的电磁理论以及后来的电子学理论一旦有某些进展,很快就会促进电信系统的创造发明或改进。这是因为通信系统对人类社会的发展,其关系实在是太密切了。日常生活、工农业生产、科学研究以及战争等等,一切都离不开消息传递和信息流动。通信系统是人类社会的神经系统,即使在原始社会也存在着最简单的通信工具和通信系统,这方面的社会实践是悠久漫长的。自从香农十九世纪四十年代末两篇论文发表后,前苏联和美国的科学家采取了不同的研究途径经一部发展了信息论。柯尔莫哥洛夫、宾斯基和达布鲁新为首的一批著名数学家致力于信息论的公理化体系和更一般更抽象的数学模型,对信息论的基本定理给出了更为普遍的结果,为信息论发展成数学的一个分支作出了贡献。而在美国测试有一批数学修养很高的工程技术人员致力于信息有效处理和可靠传输的可实现性,维信息论转化为信息技术作出了贡献。 20世纪50年代,信息论向各门学科发起冲击；60年代信息论进入一个消化、 《信息论与编码》期末考察报告 题目JPEG编码 学生姓名蒲亚洁 学号20102334916 院系电子工程 专业通信工程 二Ｏ一三年一月八日 JPEG编码 蒲亚洁 滨江学院电子工程系通信工程专业10级3班 摘要：本文介绍了JPEG。JPEG是一种针对相片影像而广泛使用的一种失真压缩标准方法。JPEG 标准指定了一系列实现静态图像压缩编码的方法,这些方法的选择决定于具体应用的要求及性能价格比的考虑。这些方法基本上可以分为两种：一种是采用以离散余弦变换(DCT)为基础的有损压缩算法，另一种是采用以预测技术为基础的无损压缩算法。使用有损压缩算法时在压缩比为25﹕1 的情况下压缩后还原的图像与原始图像相比较非图像专家难以找到它们的区别因此得到了广泛的应用。 JPEG采取多种编码方式，包含有行程编码(Run Length Coding)和哈夫曼(Huffman)编码，有很高的压缩比。在编码前，先对数据进行分块，离散余弦变换（DCT）及量化，保留能量大的低频信号，丢弃高频信号以达到压缩。解码时，进行熵解码，反量化，反离散余弦变换（IDCT）。 关键词：有损压缩算法；无损压缩算法；失真压缩标准方法；哈夫曼编码;有损压缩；JPEG Abstract：This paper introduced JPEG.JPEG is a widely used for photo image of a standard method for compression distortion. JPEG standard specifies a series of static image compression coding method, these methods of selection determines the specific application requirements and performance 实验一 绘制二进熵函数曲线（2个学时） 一、实验目的： 1. 掌握Excel 的数据填充、公式运算和图表制作 2. 掌握Matlab 绘图函数 3. 掌握、理解熵函数表达式及其性质 二、实验要求： 1. 提前预习实验，认真阅读实验原理以及相应的参考书。 2. 在实验报告中给出二进制熵函数曲线图 三、实验原理： 1. Excel 的图表功能 2. 信源熵的概念及性质 ()()[] ()[]())(1)(1 .log )( .) ( 1log 1log ) (log )()(10 , 110)(21Q H P H Q P H b n X H a p H p p p p x p x p X H p p p x x X P X i i i λλλλ-+≥-+≤=--+-=-=≤≤? ?????-===??????∑ 单位为 比特/符号 或 比特/符号序列。 当某一符号xi 的概率p(xi)为零时，p(xi)log p(xi) 在熵公式中无意义，为此规定这时的 p(xi)log p(xi) 也为零。当信源X 中只含有一个符号x 时，必有p(x)=1，此时信源熵H （X ）为零。 四、实验内容： 用Excel 和Matlab 软件制作二进熵函数曲线。根据曲线说明信源熵的物理意义。 （一） Excel 具体步骤如下： 1、启动Excel 应用程序。 2、准备一组数据p 。在Excel 的一个工作表的A 列（或其它列）输入一组p ，取步长为0.01，从0至100产生101个p （利用Excel 填充功能）。 3、取定对数底c，在B列计算H(x) ,注意对p=0与p=1两处，在B列对应位置直接输入0。Excel中提供了三种对数函数LN(x),LOG10(x)和LOG(x,c)，其中LN(x)是求自然对数，LOG10(x)是求以10为底的对数，LOG(x,c)表示求对数。选用c=2,则应用函数LOG(x,2)。 在单元格B2中输入公式：=-A2*LOG(A2,2)-(1-A2)*LOG(1-A2,2) 双击B2的填充柄，即可完成H(p)的计算。 4、使用Excel的图表向导，图表类型选“XY散点图”，子图表类型选“无数据点平滑散点图”，数据区域用计算出的H(p)数据所在列范围，即$B$1:$B$101。在“系列”中输入X值(即p值)范围，即$A$1:$A$101。在X轴输入标题概率，在Y轴输入标题信源熵。 （二）用matlab软件绘制二源信源熵函数曲线 p = 0.0001:0.0001:0.9999; h = -p.*log2(p)-(1-p).*log2(1-p); plot(p,h) 五、实验结果 信息科学技术概论课程报告 姓名: 葛坤 专业: 11级电子信息工程A班 学号: 1115102016 日期2013年3月1日—2013年4月26日 一、研究内容 信息科学 信息科学是以信息为主要研究对象，以信息的运动规律和应用方法为主要研究内容，以计算机等技术为主要研究工具，以扩展人类的信息功能为主要目标的一门新兴的综合性学科。 信息科学由信息论、控制论、计算机科学、仿生学、系统工程与人工智能等学科互相渗透、互相结合而形成的。 信息科学技术主要研究信息的产生、获取、存储、传输、处理及其应用。其中以微电子、计算机、软件、通信讯技术为主导，微电子是基础，计算机及通信设施是载体，而软件是核心，是计算机的灵魂。 信息，既是信息科学的出发点，也是它的归宿。具体来说，信息科学的出发点是认识信息的本质和它的运动规律；它的归宿则是利用信息来达到某种具体的目的。 信息概念 信息是人类对自然世界的了解的物化形式，信息的概念可以在两个层次上定义： 1、本体论意义的信息是事物运动的状态和状态变化的方式，即事物内部结构和外部联系的状态和方式。 2、认识论意义的信息是认识主体所感知、表达的相应事物的运动状态及其变化方式，包括状态及其变化方式的形式、含义和效用。 信息并非事物本身，而是表征事物之间联系的消息、情报、指令、数据或信号。 信息的主要特征有：可量度、可识别、可转换、可存储、可处理传递、可再生、可压缩、可利用、可共享、主客体二重性等。 信息的产生、存在和流通，依赖于物质和能量，没有物质和能量就没有能动作用。信息可以控制和支配物质与能量的流动。 数据、信息、知识和智慧 数据是未加工过的“信息”； 信息通过将事实和给定的语境关联而导出； 知识将某语境中的信息和在不同语境中得到的信息相关联； 智慧是从完全不同的知识导出的一般性原理。 信息论概念 信息论是研究信息的产生、获取、变换、传输、存贮、处理识别及利用的学科。信息论还研究信道的容量、消息的编码与调制的问题以及噪声与滤波的理论等方面的内容。信息论还研究语义信息、有效信息和模糊信息等方面的问题。 信息论有狭义和广义之分。狭义信息论即申农早期的研究成果，它以编码理论为中心，主要研究信息系统模型、信息的度量、信息容量、编码理论及噪声理论等。广义信息论又称信息科学，主要研究以计算机处理为中心的信息处理的基本理论，包括评议、文字的处理、图像识别、学习理论及其各种应用。广义信息论则把信息定义为物质在相互作用中表征外部情况的一种普遍属性， xx大学 信息论课程设计 姓名： 学号： 学院： 指导老师： 完成日期：2015.01.04 一、判定唯一可译码 1．任务说明： 输入：任意的一个码(即已知码字个数及每个具体的码字) 输出：判决结果（是/不是） 输入文件:in1.txt，含至少2组码，每组的结尾为”$”符 输出文件:out1.txt，对每组码的判断结果 说明：为了简化设计，可以假定码字为0，1串 2．问题分析、实现原理 判定唯一可译码根据唯一可译码的判别方法，利用数据结构所学的知识，定义字符串数据类型并利用指针进行编程来实现算法。 算法： 1、考察C 中所有的码字，若Wi是Wj的前缀，则将对应的后缀作为一个尾随后缀码放入集合Fi+1中； 2、考察C和Fi俩个集合，若Wi ∈C是Wj∈F的前缀或Wi ∈F是Wj∈C的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1中； 3、F=∪Fi即为码C的尾随后缀集合； 4、若F中出现了C中的元素，算法终止，返回假（C不是唯一可译码）；否则若F中没有出现新的元素则返回真。 3.源代码： #include 摘要：信息是自从人类出现以来就存在于这个世界上了，天地万物，飞禽走兽，以及人类的生存方式都离不开信息的产生和传播。人类每时每刻都在不停的接受信息，传播信息，以及利用信息。从原来的西汉时期的造纸，到近代西方的印刷术，以及现在的计算机，信息技术在人类历史的进程当中随着生产力的进步而发展。而信息理论的提出却远远落后于信息的出现，它是在近代才被提出来而形成一套完整的理论体系。信息论的主要基本理论包括：信息的定义和度量；各类离散信源和连续信源的信息熵；有记忆、无记忆离散和连续信道的信道容量；无失真信源编码定理。 关键字：平均自信息信道容量信源编码霍夫曼码 Abstract：Since the human being come out, the information has been existence in the world. The universe, birds and beasts, and the live style of the mankind all can’t live out of the production and transmission of the information. The human being receives the massage, transmits the information and uses the information all the time. From the papermaking in the Western Han Dynasty to the printing of the west, and the computer now, the information technology in human history developed with the productive forces. But Information Theory’s appearance is far behind the emergence of the information. It is raised in modern times and formed a complete theoretical system. The main basic theory of information includes:the definition and measurement of information;the all kinds of discrete and continuous source of information entropy;channel capacity of memorial, memory of discrete and continuous channels;lossless source coding theorem. Key word: The average self-information Channel capacity Source Coding Huffman code信息论基础结课论文
信息论课程设计报告
信息论与编码课程论文
信息论应用调研报告
信息论课程论文汇总
信息论论文
信息论与编码课程论文
信息论报告
信息论发展
信息论与编码期末论文
信息论与编码实验报告
信息论论文
信息论课程设计报告
信息论论文
相关主题
文本预览