3.1 信息熵理论在线视频

同学们好

今天我们开始学习第三章

数据压缩的基本技术

在这一章里头

我们首先要学习

信息论中相关的基本理论

在此基础上

我们学习数据压缩的基本技术

包括预测编码

序列图像中运动矢量的估计

具有运动补偿的帧间预测

正交变换编码

子带编码

量化编码和熵编码技术

我们现在学习信息熵理论这一节

研究数据压缩就一定会涉及到信息论

仙农创立的信息论

为数据压缩奠定了重要的基础

在信息论中

除了给出了信息压缩的基本的思想

同时也给出了信息压缩的理论极限

我们先来看一下信息论中两个重要的量

信息熵和信息量

对于离散信源X

它包含有n个符号

这n个符号的概率是已知的

所有符号概率的和是等于1的

那么对于这样一个离散的信源

当符号发生的时候

他所携带的信息量

我们可以用

它发生概率的负对数来计算

那么从这个信息量的计算表达式中

我们看到符号发生的概率越小

它所携带的信息量就越大

对一个信源来说

符号发生的平均信息量叫信源的熵

也就是对符号

所携带信息量进行一个统计平均

信源的平均信息量

我们用H(X)来表示

信息熵反映了一个信源

它所携带信息量的平均值

熵表示出符号出现的平均不确定性

或者是说符号所蕴含的平均信息量

对一个信源来说

它的信源熵越大

说明这个信源所涵盖的信息量就越大

那么我们就有一个问题

在什么样的概率分布下

这个信源具有最大的熵

从熵的计算公式中

我们看到

一个信源的信息量的大小

跟信源符号的发生概率密切相关

所以说概率分布不同

信源所包含的信息量也不一样

那么在什么样的概率分布下

信源能够达到最大的信息熵

我们来做一个分析

我们讨论离散信源的熵

和概率分布的关系

离散信源的概率分布不同

信源所具有的熵也是不一样的

那么概率分布和熵之间对应的关系

我们分析在什么样的概率下

信源具有最大熵

这其实是一个优化问题

也就是说

在什么样的概率分布下

信源具有最大的伤

所以我们可以把它归为一个带约束的优化问题

那么用数学的形式来表示

我们可以表示成这样子的一个

条件极值优化问题

对于这样一个优化问题

我们引入拉格朗日系数

用拉格朗日乘数法来求它最优的解

那么我们建立起一个代价函数

我们求它关于概率的最优的解

那么我们能够建立起一组

有关概率的分布的一组方程

在这i取值从1到n

对应的是我们离散信源

一共n个符号

那么每一个符号发生的概率

在最大熵的情况下

它的概率分布应该是什么样子的

那么求这个最优解

我们得到的最优解是

所有符号概率发生是等概的情况下

那么这个信源的熵是最大的

它的最大熵等于log 2 n

那也就是说

我们分析概率

分布和熵的关系

我们得到能够使信源的熵

为最大的信源符号概率分布

应该是均匀的

那么这个结论我们又把它叫做是

最大离散熵的定律

对一个信源来说

它生的大小

表示这个信源所涵盖信息量的多少

或者叫携带信息量的多少

那么对于一个信源来说

我们希望它能够携带尽量多的信息量

对于一个离散信源

如果信源中某一个符号出现的概率为一的话

那么这个信源的熵是等于0的

当信源的符号是等概出现的时候

这个信源的熵最大

我们刚才得出了这样子的结论

信源的熵等于符号数的对数

那么我们让离散无记忆信源

尽可能达到等概分布的话

就可以使这个信源的平均信息量最大

那么对于有限的数据

数据集我们就可以

用更少的符号数来进行描述

我们以两符号的

离散数据集来进行一个分析

假设X是一个

0 1 符号所构成的这样子的一个离散的信源

每一个符号概率分布跟

对应信源的熵之间的关系

我们可以画出一个

熵和概率的一个函数图

在这个函数图中

我们可以看到

随着概率的变化

信源的熵在发生变化

这个函数是一个凸函数

当概率分布式

均等的时候

也就是说0和1的概率

都是二分之一的时候

那么达到熵的一个极大值等于1

也就是说

当0 1分布概率是二分之一的时候

每一个符号

也就是一个0或者是一个1

它携带的信息量是1个比特

这样在等概率分布的情况下

每个符号所携带的信息量是最大的

那么同样的信息量下

我们需要使用的符号数就是最少的

所以说对信源进行编码的时候

我们希望信源的

概率分布是均匀的是等概的

那么这样这个惜缘

他所携带的信息量就是最大的

下面我们来看一下信源的相关性

和序列商的关系

刚才我们讨论了对一个信源来说

我们希望他它携带的信息量最大

那么就希望信源符号的概率分布是均匀的

那么对于信源的

符号之间的相关性和熵具有什么样的关系呢

我们来讨论一下

首先我们来看一下离散无记忆的信源

离散无记忆信源指的是

信源的符号之间是没有相关性的

这类的信源

我们把它叫做离散无记忆信源

假设这样一个离散无记忆的信源

它是有两个符号所构成的

也就是说这个信源产生的每一个系列

是由来自于两个符号集的

两个符号组成的

假设是X Y这两个符号

构成气源所生成的符号序列

XY分别来自于两个符号集

一个是由n个符号组成的符号集

一个是由M个符号组成的符号集

那么当我们接收到这样子的

有两符号构成的符号系列的时候

所获得的平均信息量用联合熵来给出

那么联合熵是由

这两个符号的联合概率来进行求解

在联合商的表达式中

rij代表的是X和Y

这两个符号同时发生的联合概率

那么联合熵我们用

H(X·Y)来表示

因为我们现在讨论的是

离散无记忆的信源

所以说两个符号之间是相互独立的

那么两个符号之间的联合概率呢

就等于各自边缘概率的乘积

联合熵就等于两个符号各自熵的和

那这样子的一个两符号形成的

序列对应的信源

我们得到的结论可以

很容易地推广到多个符号的情况

那么对于一个离散无记忆的信源

所产生的符号系列的熵

等于各个符号熵的和

那么我们再来看一下

离散有记忆的信源

对于离散有记忆的信源来说

信源符号之间是具有相关性的

那么在给定X的条件下

Y所具有的熵叫条件熵

那么条件熵是要基于

条件概率来进行求解

我们用H(Y/X)来表示条件熵

那么在条件熵的求解中

rij这个联合概率是由

条件概率来计算得到的

对于联合熵和条件熵的关系

我们可以经过证明得出这样一个结论

也就是说联合熵

等于其中一个符号的独立熵

加上以这个符号为条件的

另外一个符号的条件上

在信源具有相关性的情况下

联合熵一定是小于等于

两个符号的独立熵

那么从联合熵和条件熵的关系中

我们看到

如果信源符号之间有相关性的话

一个符号的发生其实就解出了

另一个符号的一部分不确定性

那么在这种情况下

它的联合熵一定是小于

信源符号之间没有相关的情况下的

信源的联合熵

那么在这样子的一个基础上

我们就看到对于信源进行压缩的时候

如果我们能够通过有效的手段

去除符号之间的相关性的话

那么就可以使信源得到压缩

所以说去除符号之间的相关性可以使

符号序列的平均信息量达到最大

这个其实也是我们在对

信源数据进行压缩的时候常用的一种手段

就是去除信源符号之间的相关性

是信源变成无记忆的信源

实现对信源的压缩

我们来看一下信源的相关性

和序列熵关系中的

另外一个重要的概念概念就是互信息

无条件熵与条件熵的差

我们把它叫做互信息

其实互信息给出了

两个符号之间的关联关系

或者叫两个事件之间的相关性

对于X和Y之间的信息

可以用I (X;Y)来表示

也可以用I(Y;X)来表示

它们两者是相等的

而且都是大于零的

那么互信息表示出了两个

事件之间的相关性的大小

那么两个事件之间的相关性越小

互信息就越小

我们可以把刚才所讨论的互信息

无条件熵和条件熵之间的关系

做一个进一步的理解

那么我们通过这样一个图示

把这三个量之间的关系做了一个展示

那么我们看到

中间交叠的部分给出的就是

两个事件之间的相关性的大小

当一个事件发生的时候

就会解除另外一个实践的

一部分不确定性

那么另外一个事件的不确定性

就减小了

那么它所携带的信息量也就减小

这个从互信息可无条件熵

条件熵之间的关系

我们有这样子的一个结论

那么基于前面信息了相关的理论

我们可以对数据压缩

做一个基本的总结

那么数据压缩的基本途径

我们来看一下有哪些

序列的熵与

它能够达到的最大值之间的差值

反映了这个信源所包含的冗余度的大小

信源冗余越小

那么每一个符号所携带的信息量就越大

这样我们传送相同信息量

所需要的符号数就越小

对于一个离散有记忆的信源

数据压缩的基本途径

就是去除信源符号中的相关性

尽可能是信源序列成为无记忆的

那么对于已经去除信源相关性的

一个无记忆的信源

我们可以考察它的概率分布是不是均匀

那么如果信源的概率分布是不均匀的

这样的信源就存在着冗余

那么这种冗余通常我们也称为

叫统计冗余或者叫熵冗余

那么我们可以通过

改变这个离散信源的概率分布

使它变成一个等概分布的信源

来达到对这类信源的压缩

刚才我们总结了对于离散无记忆信源

和离散有记忆信源进行

数据压缩的基本的途径

在实际应用中

我们对一个信源进行压缩

有的时候希望是无失真的

有的时候是允许引入失真的

所以说对于信源进行压缩

可以分成有失真压缩和无失真压缩

我们来看一下无失真压缩编码的基本原理

对信源进行无失真压缩

主要是通过改变信源的概率分布不均匀性

使编码后的数据率接近于信源信息熵

同时不引入失真

这类的压缩都是属于无失真的压缩编码

在无失真压缩编码中有一个重要的定律

叫Shannon无失真编码定律

这个定律是这么说的

再无任何干扰的情况下

存在着一种无失真的编码方法

这种编码方法可以使编码的平均码长

L与信源的熵任意的接近

但是是以信源的熵为下限的

那也就是说

Shannon的无失真编码定律

告诉我们能够找到一个编码的方法

这样子的一种熵编码的方法

最终实现的码长是以信源的熵为极限

但是只要是无失真的压缩编码

那么所实现的编码的平均码长

就一定不会突破熵所给出来的限制

也就是说

平均码长是以信源的熵作为下限

那么在这样子的一个定理的指导下

无失真编码的主要方法有

Huffman编码

算术编码

还有游程编码

那么这一类的编码算法

都是属于无失真压缩编码的方法

同时我们也可以把无失真压缩编码

称为熵编码或者叫统计编码

这一列压缩编码方法主要是

基于信源概率分布特征实现的信源压缩

所以说这类方法实现的性能的好坏

与对信源概率分布了解的准确与否

密切相关

对一项Huffman编码和

算术编码这例的编码

实现的编码结果是每个符号的

编码码长是不一样的

属于变长编码的类型

那么对于变长编码有一个重要的定律

叫变长编码的最佳编码定理

这个定理告诉我们

在变长编码中

对于出现概率大的符号

我们给它编以短的码字

对于概率出现小的码字符号

我们给它编以长的码字

那么如果我们码字的长短是

严格按照符号概率出现的大小

逆顺序排序的话

那么我们得到的这个编码的平均码长

一定会小于其它按任何顺序排序的结果

那么对于Huffman编码和算术编码

都是属于在这个定律下的

最优的变长编码