3.2 数据压缩的理论依据
在讨论数据压缩的时候，需要涉及现代科学领域中的一个重要分支——信息论。香农所创立的信息论对数据压缩有着极其重要的指导意义。它一方面给出了数据压缩的理论极限，另一方面又指明了数据压缩的技术途径。本节将对无信息损失条件下数据压缩的理论极限作一简要的介绍；而下一节将讨论限定失真条件下数据压缩的理论极限。
3.2.1 离散信源的信息熵
在日常生活中，当我们收到书信、电话或看到图像时，则说得到了消息，在这些消息中包含着对我们有用的信息。通常，消息由一个有次序的符号（如状态、字母、数字、电平等）序列构成。例如，一封英文信是利用由26个英文字母加上标点符号所构成的序列来传递消息的。一个符号所携带的信息量I用它所出现的概率p按如下关系定义：
I＝log（1/p）＝－logp （3-1）
上述定义符合我们日常生活中的概念。例如，如果符号出现的概率为1，这说明传递给我们的是一条几乎肯定要发生的事件的消息，对我们来说是“不出所料”，没有什么信息量；因此，I＝0。反之，概率较小的符号（事件），出现的不肯定性大，那么收到这个事件发生的消息时，带给我们较大的信息量。
当（3-1）式中的对数以2为底时，它的单位是比特。从后面的讨论中将会看到，表示信息量的比特其含义与二进制符号中的比特并不完全相同。
若信息源所产生的符号取自某一离散集合，则该信源称为离散信源。离散信源X可以用下式来描述：
式中，p（si）为符号集中的符号si发生（或出现）的概率。由于信源产生的符号si是一个随机变量（在符号产生之前，我们不知道信源X将发出符号集中的哪一个符号），而信息量I是si[或p（si）]的函数，因此I也是一个随机变量。对于一个随机变量，研究它的统计特性更有意义。考虑I的统计平均值
式中，〈 〉表示数学期望。
借用热力学的名词，我们把H叫做熵。在符号出现之前，熵表示符号集中符号出现的平均不肯定性；在符号出现之后，熵代表接收一个符号所获得的平均信息量。因此，熵是在平均意义上表征信源总体特性的一个物理量。
3.2.2 信源的概率分布与熵的关系
由（3-3）式可以看出，熵的大小与信源的概率模型有着密切的关系。如果符号集中任一符号出现的概率为1，则其他符号出现的概率必然为零，信源的平均信息量（熵）则为零。如果所有符号出现的概率都小于1，熵则为某一正值。这说明，各符号出现的概率分布不同，信源的熵也不同。下面我们来求证，当信源中各事件服从什么样的分布时，熵具有极大值，即求解
图3-1 二进制信源的熵与概率p之间的关系
根据求条件极值的拉格朗日乘数法，我们有
式中，λ为拉格朗日常数。解方程组（3-5）前，得到
此时，信源具有最大熵
Hmax（X）＝log2n （3-7）
这是一个重要结论，有时称为最大离散熵定理。
以n＝2为例，熵随符号“1”的概率p的变化曲线如图3-1所示。p＝0或1时，H（X）＝0。当p＝1/2时，H（X）＝1bit/符号。p为其他值时，0＜H（X）＜1。从物理意义上讲，通常存储或传输1位的二进制数码（1或0），其所含的信息量总低于1bit；只有当字符0和1出现的概率均为1/2时，不肯定性最大，1位二进数码才含有习惯上所说的1比特的信息量。
3.2.3 信源的相关性与序列熵的关系
上面讨论的离散信源所能输出的信息量，是针对一个信源符号而言的。实际上，离散信源输出的不只是一个符号，而是一个随机符号序列（离散型随机过程）。若序列中各符号具有相同的概率分布，该序列（过程）是平稳的。若序列中各符号间是统计独立的，即前一个符号的出现不影响以后任何一个符号出现的概率，则该序列是无记忆的。
假设离散无记忆信源产生的随机序列包括两个符号X和Y（即序列长度等于2），且X取值于（3-2）式所表示的集合，而Y取值于
那么接收到该序列后所获得的平均信息量称为联合熵，定义为
式中，rij为符号si和tj同时发生时的联合概率。由于X和Y相互独立，rij＝p（si）q（tj），（3-9）式变为
H（X·Y）＝H（X）＋H（Y）（3-10）
将上面的结果推广到多个符号的情况，可以得到如下结论：离散无记忆信源所产生的符号序列的熵等于各符号熵之和。要知道收到其中一个符号所得到的平均信息量（即序列的平均符号熵）可以用序列熵除以序列的长度求得。显然，当序列是平稳的，任一符号的熵就是序列的平均符号熵。
假设离散信源是有记忆的，而且为了简单起见，只考虑相邻两个符号（X和Y）相关的情况。由于其相关性，联合概率rij＝p（si）Pji＝q（tj）Pij，其中Pji＝P（tj/si）和Pij＝P（si/tj）为条件概率。
在给定X的条件下，Y所具有的熵称为条件熵，即
上式中在对-log2Pji进行统计平均时，由于要对si和tj进行两次平均，所以用的是联合概率rij。利用（3-9）式和（3-11）式以及联合概率与条件概率之间的关系，不难证明联合熵与条件熵之间存在下述关系：
H（X·Y）＝H（X）＋H（Y/X）＝H（Y）＋H（X/Y）（3-12）
上式表明，如果X和Y之间存在着一定的关联，那么当X发生，在解除X的不肯定性的同时，也解除了一部分Y的不肯定性。但此时Y还残剩有部分的不肯定性，这就是（3-12）式中H（Y/X）的含义。我们把无条件熵和条件熵之差定义为互信息，即
I（X；Y）＝H（Y）－H（Y/X）（3-13）
I（Y；X）＝H（X）－H（X/Y）（3-14）
显然，I（X；Y）＝I（Y；X）≥0。
图3-2 无条件熵、条件熵和互信息之间的关系
两个事件的相关性越小，互信息越小，残剩的不肯定性便越大。当两事件相互独立时，X的出现，丝毫不能解除Y的不肯定性。在这种情况下，联合熵变为两个独立熵之和（见（3-10）式），从而达到它的最大值。图3-2给出了无条件熵、条件熵和互信息之间关系的示意。
由（3-12）式和（3-10）式，可以得到
H（X·Y）＝H（X）＋H（Y/X）≤H（X）＋H（Y）（3-15）
对于信源输出序列中有多个符号相关的情况，也可以得到类似的结果。序列熵与其可能达到的最大值之间的差值反映了该信源所含有的冗余度。信源的冗余度越小，即每个符号所独立携带的信息量越大，那么传送相同的信息量所需要的序列长度越短，或符号数越少。因此数据压缩的一个基本途径是去除信源产生的符号之间的相关性，尽可能地使序列成为无记忆的。而对于无记忆信源而言，如3.2.2节所述，在等概率情况下，离散平稳无记忆信源单个符号的熵（平均信息量）具有极大值。因此，在无信息损失的情况下，数据压缩的另一基本途径是改变离散无记忆信源的概率分布，使其尽可能地达到等概率分布的目的。