信息论与编码-算术编码.ppt

信息论与编码——算术编码

主要内容一、信息论概念二、算术编码

一、信息论概念 信息论或称为通信的数学理论，应用概率论和数理统计的方法研究有效地、可靠地、安全地传递信息的科学。 2.分类◆信息论基础（香农信息论、狭义信息论）◆一般信息论◆广义信息论

一、信息论◆信息论基础（香农信息论、狭义信息论）在信息可以量度的基础上，研究有效地、可靠地传递信息。（信息的量度、信道容量、信息率失真函数，与这三个概念相对应的香农三大定理，信源编码、信道编码）◆一般信息论研究信息传输和处理。 包括通信的全部统计问题：●Shannon：依附在信号上的信息●Wiener：携带信息的信号◆广义信息论 不仅包括一般信息论的所有研究内容，还包括如医学、生物学、心理学、遗传学、语言学，甚至社会学和经济管理中有关信息的问题。香农信息论的基本任务：为设计有效而可靠的通信系统提供理论依据

通信系统的模型

二、算术编码1、算术编码的定义2、自适应算术编码3、静态算术编码4、程序设计

1、算术编码的定义算术编码是一种无损数据压缩方法，也是一种熵编码的方法。和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码，而算术编码是直接把整个输入的消息编码为一个数，一个满足(0.0≤n1.0)的小数n。算术编码在图像数据压缩标准(如JPEG，JBIG)中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。

分类算术编码是用符号的概率和它的编码间隔两俩个基本参数来描述的。算术编码可以是静态的或是自适应的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改。在静态算术编码中，信源符号的概率是固定的。在编码期间估算信源符号概率的过程叫建模。需要开发动态算术编码的原因，是因为事先知道精确的信源符号概率是很难的，而且是不切实际的。动态建模是确定编码器压缩效率的关键。

2、自适应算术编码例1：算术编码对某条信息的输出为1010001111，那么它表示小数0.1010001111，也即十进制数0.64。考虑某条信息中可能出现的字符仅有abc三种，要压缩保存的信息为bccb。采用的是自适应模型，开始时暂时认为三者的出现概率相等，也就是都为1/3，将0-1区间按照概率的比例分配给三个字符，即a从0.0000到0.3333，b从0.3333到0.6667，c从0.6667到1.0000。用图形表示就是：

+0.0000_Pa=1/3+0.3333Pb=1/3+0.6667Pc=1/3+1.0000现在拿到第一个字符b，把目光投向b对应的区间0.3333-0.6667。这时由于多了字符b，三个字符的概率分布变成：Pa=1/4，Pb=2/4，Pc=1/4。好，按照新的概率分布比例划分0.3333-0.6667这一区间，划分的结果可以用图形表示为：+0.3333Pa=1/4+0.4167Pb=2/4+0.5834Pc=1/4+0.6667接着拿到字符c，现在要关注上一步中得到的c的区间0.5834-0.6667。新添了c以后，三个字符的概率分布变成Pa=1/5，Pb=2/5，Pc=2/5。用这个概率分布划分区间0.5834-0.6667：+0.5834Pa=1/5+0.6001Pb=2/5+0.6334Pc=2/5+0.6667

现在输入下一个字符c，三个字符的概率分布为：Pa=1/6，Pb=2/6，Pc=3/6。来划分c的区间0.6334-0.6667：+0.6334Pa=1/6+0.6390Pb=2/6+0.6501Pc=3/6+0.6667输入最后一个字符b，因为是最后一个字符，不用再做进一步的划分了，上一步中得到的b的区间为0.6390-0.6501，好，在这个区间内随便选择一个容易变成二进制的数，例如0.64，将它变成二进制0.1010001111，去掉前面没有太多意义的0和小数点，我们可以输出1010001111，这就是信息被压缩后的结果，就完成了一次最简单的算术压缩过程。其译码的过程跟编码过程相似，具体如下表。

自适