信息熵与编码定理

惊奇度与信息量
定性描述

惊奇度：一个事件的惊奇度是指该事件发生时我们所感到的惊奇程度
信息量：一条信息的信息量是指该信息所含信息的多少。一条信息越是让我们感到惊奇，它所含信息量就越大

对于一个掷骰子的试验，假设E代表掷出点数为偶数（概率为1/2），我们对于事件E发生的惊奇程度并不大，但是当E代表掷出点数为6（概率为1/6），我们的惊奇程度就会很大。同样的我们会认为，“明天太阳会从东边升起”这句话没有任何信息量，而“国足将在世界杯夺冠”，这句话信息量太大了。

定量描述
我们希望能够将这种惊奇度/信息量进行量化，一个合理的假设是：

事件的惊奇度/信息量只取决于事件发生的概率。

用 $S (p)$ 表示由概率为 $p$ 的事件发生以后所产生的惊奇程度，假定 $S (p)$ 对一切 $0 < p < = 1$ 有定义。下面我们从 $S (p)$ 应满足的条件出发确定 $S (p)$ 的形式：
公理1：
$S (1) = 0$ ，当听到一个必然事件发生时，不会感到任何惊奇
公理2：
$S (p)$ 是 $p$ 的严格连续递减函数，事件发生的概率越大，惊奇度越小
公理3：
$S (p q) = S (p) + S (q)$ ，对于独立事件E和F，假设E发生的惊奇度为 $S (p)$ ，F发生的惊奇度为 $S (q)$ ，则二者同时发生的惊奇度等于二者分别发生的惊奇度之和
容易验证，对数函数可同时满足这四个条件：

$S (p) = - l o g p$

当底数取2时，惊奇度/信息量的单位可用比特表示。

信息熵
信息熵的定义

考虑一个取值于 $x_{1},x_{2},...,x_{n}$ 的随机变量X，且相应概率分别为 $p_{1},...,p_{n}$ ,当观察到随机变量X的值，所引起的平均惊奇度为：

$H(x)=-\sum_{i=1}^{n}p_{i}logp_{i}$

规定 $0 l o g 0 = 0$ 。可以证明当 $p_{i}$ 相同时， $H (x)$ 达到最大值，所以 $H (x)$ 也可认为是随机变量 $X$ 的不确定程度。在信息论中， $H (x)$ 称为随机变量的熵，即观测到随机变量 $X$ 的值以后所接收的平均信息量。

信息熵的理解
在这里插入图片描述
熵、不确定度、惊奇度、信息量是从不同角度来看待X的同一特性：
随机变量 $X$ 的熵 $H (X)$ =随机变量 $X$ 的不确定度=观测到随机变量 $X$ 的值后的平均惊奇度=观测到随机变量 $X$ 的值后的平均信息量

我们可以从以下不同角度来理解它们之间的关系：

随机变量X的熵H(X)代表了X取值的“混乱”程度，即我们对X取值的不确定程度，我们越是不确定X的取值，当我们观测到它的值时所产生的平均惊奇度就越大；
信息熵代表了信息内容的“混乱”程度，即我们对信息内容的不确定程度，我们越是不确定信息的内容，当我们获取该信息的内容时，它所带给我们的信息量就越大；
对于获取到的一条信息，我们越是感到惊奇说明它所包含的信息量越大；

随机向量的熵
随机向量 $(X, Y)$ 的联合不确定度为：

$H(X,Y)=-\sum_{i}\sum_{j}p(x_{i},y_{j})logp(x_{i},y_{j})$

当 $Y=y_{j}$ 已观测到， $X$ 在 $Y=y_{j}$ 条件下的剩余不确定度为：

$H_{Y=y_{j}}(X)=-\sum_{i}p(x_{i}|y_{j})logp(x_{i}|y_{j})$

当 $Y$ 被观测到后， $X$ 的平均不确定度为：

$H_{Y}(X)=\sum_{j}H_{Y=y_{j}}(X)\cdot p(y_{j})$

定理1:
随机变量 $X$ 和 $Y$ 的联合不确定度可分解为 $Y$ 的不确定度与 $Y$ 被到测到后 $X$ 的平均不确定度之和:

$H(X,Y)=H(Y)+H_{Y}(X)$

证明：

$\begin{aligned} H(X,Y)&=-\sum_{i}\sum_{j}p(x_{i},y_{j})logp(x_{i},y_{j}) \\ & =-\sum_{i}\sum_{j}p(y_{i})p(x_{i}|y_{j})[logp(y_{i})+logp(x_{i}|y_{j})] \\ & = -\sum_{j}p(y_{j})logp(y_{j})\sum_{i}p(x_{i}|y_{i})-\sum_{j}p(y_{j})\sum_{i}p(x_{i}|y_{i})logp(x_{i}|y_{i})\\ & =H(Y)+H_{Y}(X) \end{aligned}$

引理:

当

x > 0

时，下式恒成立，当且仅当

x = 1

时等号成立

\ln x\leqslant x-1

定理2： 当另一个随机变量 $Y$ 被观测到后， $X$ 的不确定度在平均意义下减少，当二者独立时等号成立：

$H_{Y}(X) \leqslant H(X)$

编码定理

通信中的编码问题（最小期望码长）：假设一个离散型随机变量X取值于 $\left \{x_{1}, \cdot \cdot \cdot ,x_{N}\right \}$ ，其相应概率为 $\left \{p(x_{1}), \cdot \cdot \cdot ,p(x_{N})\right \}$ ，设计一个编码系统，将 $x_{i}$ 编成 $n_{i}$ 位的二进制序列，通过一个通信网络将从A处传送到B处，为避免混乱，要求编码后的序列不能出现一个序列是另一个序列的延伸。如何设计编码系统使得最终的期望码长最小。

引理1:
为了将 $X$ 的可能取值编码成0-1序列，且任何一个序列都不能是另一序列的延伸，其充要条件为：

$\sum_{i=1}^{N}\left ( \frac{1}{2} \right )^{n_{i}}\leqslant 1$

证明:
记 $w_{j}$ 为 $x_{i}$ 中编码长度为j的个数， $j = 1, 2, 3 . . .$ ，显然有：

$w_{1}2^{n-1}+w_{2}2^{n-2}+\cdot \cdot \cdot +w_{n-1}2+w_{n}\leqslant 2^{n}$

两边同除以 $2^{n}$ 得：

$\sum_{j=1}^{n}w_{j}\left ( \frac{1}{2}\right )^{j}=\sum_{i=1}^{N}\left ( \frac{1}{2} \right )^{n_{i}}\leqslant 1$

无噪声编码定理
无噪声编码定理:
假设每个信号单位从位置A到位置B的过程没有发生错误，则编码的期望码长不小于随机变量的信息熵:

$\sum_{i=1}^{N}n_{i}p\left ( x_{i} \right )\geqslant H(X)=-\sum_{i=1}^{N}p\left ( x_{i} \right )\log p\left ( x_{i} \right )$

证明：
记 $p_{i}=p(x_{i})$ ， $q_{i}=2^{-n_{i}}/\sum_{j=1}^{N}2^{-n_{j}}$ ，则有 $\sum_{i=1}^{N}p_{i}=\sum_{i=1}^{N}q_{i}=1$

$\begin{aligned} -\sum_{i=1}^{N}p_{i}\log(\frac{p_{i}}{q_{i}})&=-\log e \sum_{i=1}^{N}p_{i}\ln (\frac{p_{i}}{q_{i}})\\ &=\log e \sum_{i=1}^{N}p_{i}\ln (\frac{q_{i}}{p_{i}})\\ &\leqslant \log e \sum_{i=1}^{N}p_{i}(\frac{q_{i}}{p_{i}}-1)\\ &=\log e (\sum_{i=1}^{N}p_{i}-\sum_{i=1}^{N}q_{i})=0 \end{aligned}$

由此可得：

$\begin{aligned} -\sum_{i=1}^{N}p\left ( x_{i} \right )\log p\left ( x_{i} \right )&\leqslant - \sum_{i=1}^{N}p_{i}\log q_{i}\\ &= \sum_{i=1}^{N}n_{i}p_{i}+\log(\sum_{j=1}^{N}2^{-n_{j}})\\ &\leqslant\sum_{i=1}^{N}n_{i}p_{i} \end{aligned}$

定理:
对于大部分随机变量 $X$ ，不存在一组编码系统使得期望码长达到下界 $H (X)$ ，但是总存在一个编码系统，使得期望码长与 $H (X)$ 之间的误差小于1
证明:
取 $n_{i}=\left \lceil -\log p(x_{i}) \right \rceil$ ，即：

$-\log p(x_{i}) \leqslant n_{i}\leqslant -\log p(x_{i}) +1$

代入期望码长公式 $L=\sum_{i=1}^{N}n_{i}p(x_{i})$ 得：

$-\sum_{i=1}^{N}p\left ( x_{i} \right )\log p\left ( x_{i} \right )\leqslant L\leqslant -\sum_{i=1}^{N}p\left ( x_{i} \right )\log p\left ( x_{i} \right )+1$

$H(X)\leqslant L< H(X)+1$

有噪声编码定理
假设每个信号单位的传送是独立的，且以概率p正确地从A处传送到B处，这样的通信系统称为二进制对称通道。若不经过处理直接传送便会发生误传，一种减少误传信号的方法是将信号重复多次，在译码时按多数原则进行翻译。
假设p=0.8，通过将信号重复3次进行编码译码。如000、001、010、100都代表0，111，110，101，011代表1。此时，传输一位错误的概率为：

$0.2^{3}+3\times 0.2^{2}\times 0.8=0.104$

错误率由0.2减小到0.104，事实上，只要重复足够多次可以将误传概率变得任意小，但是这种方法是以牺牲传输效率为代价的。但值得庆幸的是将传输错误概率减小到0的同时，传输效率并不会减小到0，这正是香农在信息论中提出的含噪声编码定理。
有噪声编码定理:
对于二进制对称系统，为使传送一比特的误差概率变得任意小，传输平均速率存在一个上限 $C^{*}$ ，称为通道容量。

$C^{*}=1+p\log p+(1-p)\log(1-p)$