信息熵与编码定理

惊奇度与信息量
定性描述

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

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

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

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

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

$S(p) = -log p$S(p)=−logp

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

信息熵
信息熵的定义

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

$H(x)=-\sum_{i=1}^{n}p_{i}logp_{i}$H(x)=−i=1∑n​pi​logpi​

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

信息熵的理解

熵、不确定度、惊奇度、信息量是从不同角度来看待X的同一特性：
随机变量$X$X的熵$H(X)$H(X)=随机变量$X$X的不确定度=观测到随机变量$X$X的值后的平均惊奇度=观测到随机变量$X$X的值后的平均信息量

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

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

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

$H(X,Y)=-\sum_{i}\sum_{j}p(x_{i},y_{j})logp(x_{i},y_{j})$H(X,Y)=−i∑​j∑​p(xi​,yj​)logp(xi​,yj​)

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

$H_{Y=y_{j}}(X)=-\sum_{i}p(x_{i}|y_{j})logp(x_{i}|y_{j})$HY=yj​​(X)=−i∑​p(xi​∣yj​)logp(xi​∣yj​)

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

$H_{Y}(X)=\sum_{j}H_{Y=y_{j}}(X)\cdot p(y_{j})$HY​(X)=j∑​HY=yj​​(X)⋅p(yj​)

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

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

证明：

$\begin{aligned} H(X,Y)&amp;=-\sum_{i}\sum_{j}p(x_{i},y_{j})logp(x_{i},y_{j}) \\ &amp; =-\sum_{i}\sum_{j}p(y_{i})p(x_{i}|y_{j})[logp(y_{i})+logp(x_{i}|y_{j})] \\ &amp; = -\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})\\ &amp; =H(Y)+H_{Y}(X) \end{aligned}$H(X,Y)​=−i∑​j∑​p(xi​,yj​)logp(xi​,yj​)=−i∑​j∑​p(yi​)p(xi​∣yj​)[logp(yi​)+logp(xi​∣yj​)]=−j∑​p(yj​)logp(yj​)i∑​p(xi​∣yi​)−j∑​p(yj​)i∑​p(xi​∣yi​)logp(xi​∣yi​)=H(Y)+HY​(X)​

引理:

当$x&gt;0$x>0时，下式恒成立，当且仅当$x=1$x=1时等号成立
$\ln x\leqslant x-1$lnx⩽x−1

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

$H_{Y}(X) \leqslant H(X)$HY​(X)⩽H(X)

编码定理

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

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

$\sum_{i=1}^{N}\left ( \frac{1}{2} \right )^{n_{i}}\leqslant 1$i=1∑N​(21​)ni​⩽1

证明:
记$w_{j}$wj​为$x_{i}$xi​中编码长度为j的个数，$j=1,2,3...$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}$w1​2n−1+w2​2n−2+⋅⋅⋅+wn−1​2+wn​⩽2n

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

$\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$j=1∑n​wj​(21​)j=i=1∑N​(21​)ni​⩽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 )$i=1∑N​ni​p(xi​)⩾H(X)=−i=1∑N​p(xi​)logp(xi​)

证明：
记$p_{i}=p(x_{i})$pi​=p(xi​)，$q_{i}=2^{-n_{i}}/\sum_{j=1}^{N}2^{-n_{j}}$qi​=2−ni​/∑j=1N​2−nj​，则有$\sum_{i=1}^{N}p_{i}=\sum_{i=1}^{N}q_{i}=1$∑i=1N​pi​=∑i=1N​qi​=1

$\begin{aligned} -\sum_{i=1}^{N}p_{i}\log(\frac{p_{i}}{q_{i}})&amp;=-\log e \sum_{i=1}^{N}p_{i}\ln (\frac{p_{i}}{q_{i}})\\ &amp;=\log e \sum_{i=1}^{N}p_{i}\ln (\frac{q_{i}}{p_{i}})\\ &amp;\leqslant \log e \sum_{i=1}^{N}p_{i}(\frac{q_{i}}{p_{i}}-1)\\ &amp;=\log e (\sum_{i=1}^{N}p_{i}-\sum_{i=1}^{N}q_{i})=0 \end{aligned}$−i=1∑N​pi​log(qi​pi​​)​=−logei=1∑N​pi​ln(qi​pi​​)=logei=1∑N​pi​ln(pi​qi​​)⩽logei=1∑N​pi​(pi​qi​​−1)=loge(i=1∑N​pi​−i=1∑N​qi​)=0​

由此可得：

$\begin{aligned} -\sum_{i=1}^{N}p\left ( x_{i} \right )\log p\left ( x_{i} \right )&amp;\leqslant - \sum_{i=1}^{N}p_{i}\log q_{i}\\ &amp;= \sum_{i=1}^{N}n_{i}p_{i}+\log(\sum_{j=1}^{N}2^{-n_{j}})\\ &amp;\leqslant\sum_{i=1}^{N}n_{i}p_{i} \end{aligned}$−i=1∑N​p(xi​)logp(xi​)​⩽−i=1∑N​pi​logqi​=i=1∑N​ni​pi​+log(j=1∑N​2−nj​)⩽i=1∑N​ni​pi​​

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

$-\log p(x_{i}) \leqslant n_{i}\leqslant -\log p(x_{i}) +1$−logp(xi​)⩽ni​⩽−logp(xi​)+1

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

$-\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$−i=1∑N​p(xi​)logp(xi​)⩽L⩽−i=1∑N​p(xi​)logp(xi​)+1

$H(X)\leqslant L&lt; H(X)+1$H(X)⩽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.23+3×0.22×0.8=0.104

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

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

转载自：
作者：Like_eb56
链接：https://www.jianshu.com/p/0123c6ee18c3
来源：简书