信息论与编码（三）| 联合熵和条件熵

联合熵和条件熵

联合熵

联合集 X Y 上, 对联合自信息 $I(x y)$ 的平均值称为联合熵:

$\begin{array}{l} H(X Y)=\underset{p(x y)}{E}[I(x \rightleftharpoons y)] \\ =-\sum_{x} \sum_{y} p(x y) \log p(x y) \end{array}$

当有 n 个随机变量 $X=\left(X_{1}, X_{2}, \ldots, X_{n}\right)$ , 有

$H(\mathbf{X})=-\sum_{X_{1}, X_{2}, \ldots, X_{n}} p\left(x_{1}, x_{2}, \ldots, x_{n}\right) \log p\left(x_{1}, x_{2}, \ldots, x_{n}\right)$

信息熵与热熵的关系

信息熵的概念是借助于热熵的概念而产生的。

1.信息熵与热熵含义相似
2.信息熵与热熵的区别:
1)信息熵的不增原理;2)热熵不减原理。

3．热熵的减少等于信息熵的增加。

条件熵

联合集 $\mathbf{X Y}$ 上, 条件自信息 $I(y / x)$的平均值定义为条件 熵：

$\begin{array}{l} H(Y / X)=\underset{p(x y)}{E}[I(y / x)]=-\sum_{x} \sum_{y} p(x y) \log p(y / x) \\ =\sum_{x} p(x)\left[-\sum_{y} p(y / x) \log p(y / x)\right]=\sum_{x} p(x) H(Y / x) \end{array}$

推广：

$\begin{array}{l} H\left(X_{n} \mid X_{1}, \ldots, X_{n-1}\right) \\ =-\sum_{X_{1}, X_{2}, \ldots, X_{n}} p\left(x_{1}, x_{2}, \ldots, x_{n}\right) \log p\left(x_{n} \mid x_{1}, \ldots, x_{n-1}\right) \end{array}$

注意：

$\begin{array}{l} H(X, Y)=H(Y)+H(X \mid Y)=H(X)+H(Y \mid X) \\ H(\mathbf{X}) \\ =H\left(X_{1}\right)+H\left(X_{2} \mid X_{1}\right)+\ldots+H\left(X_{n} \mid X_{1}, X_{2}, \ldots, X_{n-1}\right) \end{array}$

注意： $\mathbf{H}(\mathbf{X} \mid \mathbf{Y})$ 表示已知变量 $\mathbf{Y}$ 后, 对变量 $\mathbf{X}$ 尚存在的平均不确定性（存在疑义）。

定义：一个平稳的时域离散随机过程的熵速率 (entropy rate) 定义为

$H=\lim _{n \rightarrow \infty} H\left(X_{n} \mid X_{1}, X_{2}, \ldots, X_{n-1}\right)$

具有记忆性的信源的熵速率定义为

$H=\lim _{n \rightarrow \infty} \frac{1}{n} H\left(X_{1}, X_{2}, \ldots, X_{n}\right)$

Example 6. 两个二进制随机变量 $\mathbf{X}$ 和 $\mathbf{Y}$ , 其联合分布为 p(X=Y=0)=p(X= 0, Y=1)=p(X=Y=1)=1 / 3 . 计算 H(X), H(Y), $H(X \mid Y)$, $H(Y \mid X)$ , and H(X, Y) .
Solution:

$\begin{array}{l} p(X=0)=p(X=0, Y=0)+p(X=0, Y=1)=\frac{2}{3} \\ p(X=1)=p(X=1, Y=0)+p(X=1, Y=1)=\frac{1}{3} \\ p(Y=0)=p(X=0, Y=0)+p(X=1, Y=0)=\frac{1}{3} \\ p(Y=1)=p(X=0, Y=1)+p(X=1, Y=1)=\frac{2}{3} \\ H(X)=\frac{1}{3} \log 3+\frac{2}{3} \log \frac{3}{2}=0.9183 \quad H(Y)=\frac{1}{3} \log 3+\frac{2}{3} \log \frac{3}{2}=0.9183 \\ H(X, Y)=\sum_{i=1}^{n} p(X, Y) \log (X, Y)=\log 3=1.585 \\ H(X \mid Y)=H(X, Y)-H(Y)=0.6667 \quad H(Y \mid X)=H(X, Y)-H(X)=0.6667 \end{array}$

各类熵的关系

1. 条件熵不大于信息熵

熵的不增原理: $H(Y / X) \leq H(Y)$

2. 联合熵不大于个信息熵的和，即

   $H\left(X_{1} X_{2} \ldots X N\right) \leq \sum_{i=1}^{N} H\left(X_{i}\right)$

   仅当各 $X_{i}$ 相互独立时, 等号成立。

3. $H(X Y)=H(X)+H(Y \mid X)=H(Y)+H(X \mid Y)$

4. $H(X) \geq H(X \mid Y) ; H(Y) \geq H(Y \mid X)$

四、离散无记忆信源的序列熵

马尔可夫信源的特点：无后效性。

发出单个符号的信源

• 指信源每次只发出一个符号代表一个消息;

发出符号序列的信源

• 指信源每次发出一组含二个以上符号的符号序列代表一个消息。

• 当信源无记忆时

$\begin{aligned} p(\bar{X}&\left.=x_{i}\right)=p\left(x_{i_{1}}, x_{i_{2}}, \cdots, x_{i_{L}}\right) \\ &=p\left(x_{i_{1}}\right) p\left(x_{i_{2}}\right) p\left(x_{i_{3}}\right) \cdots p\left(x_{i_{L}}\right)=\prod_{l=1}^{L} p\left(x_{i_{l}}\right) \end{aligned}$

信源的序列熵

$\begin{aligned} H(\bar{X}) &=-\sum_{i=1}^{n^{L}} p\left(x_{i}\right) \log p\left(x_{i}\right) \\ &=-\sum_{i} \prod_{l=1}^{L} p\left(x_{i_{i}}\right) \log p\left(x_{i_{i}}\right)=\sum_{l=1}^{L} H\left(X_{l}\right) \end{aligned}$

• 若又满足平稳特性, 即与序号 l 无关时:

  $p(\overline{\mathrm{X}})=\prod_{l=1}^{L} p\left(x_{i_{\mathrm{i}}}\right)=p^{L}$

• 信源的序列熵

  $H(\overline{\mathrm{X}})=\operatorname{LH}(X)$

• 平均每个符号(消息)熵(符号熵) 为

  $H_{L}(\bar{X})=\frac{1}{L} H(\bar{X})=H(X)$

例: 有一个无记忆信源随机变量 $\mathrm{X} \in(0,1)$ , 等概率分布,若以 单个符号出现为一事件, 则此时的信源熵:

$H(X)=\log _{2} 2=1 \mathrm{bit} / \text { 符号 }$

即用 1 比特就可表示该事件。

• 如果以两个符号出现 ( $\mathrm{L}=2$ 的序列)为一事件, 则随机序 列 $\mathrm{X} \in(00,01,10,11)$ , 信源的序列熵

  $H(\bar{X})=\log _{2} 4=2 b i t / \text { 序列 }$

即用2比特才能表示该事件。

• 信源的符号熵

  $H_{2}(\overline{\mathrm{X}})=\frac{1}{2} H(\overline{\mathrm{X}})=1 b i t / \text { 符号 }$

离散有记忆信源的序列熵

• 对于有记忆信源,就不像无记忆信源那样简单, 它必须 引入条件熵的概念, 而且只能在某些特殊情况下才能 得到一些有价值的结论。
• 对于由两个符号组成的联合信源, 有下列结论:

$H\left(X_{1} X_{2}\right)=H\left(X_{1}\right)+H\left(X_{2} \mid X_{1}\right)=H\left(X_{2}\right)+H\left(X_{1} \mid X_{2}\right)$

$H\left(X_{1}\right) \geq H\left(X_{1} \mid X_{2}\right), H\left(X_{2}\right) \geq H\left(X_{2} \mid X_{1}\right)$

• 当前后符号无依存关系时,有下列推论:

$\begin{array}{l} H\left(X_{1} X_{2}\right)=H\left(X_{1}\right)+H\left(X_{2}\right) \\ H\left(X_{1} \mid X_{2}\right)=H\left(X_{1}\right), H\left(X_{2} \mid X_{1}\right)=H\left(X_{2}\right) \end{array}$

• 若信源输出一个L长序列,则信源的序列熵为

  $\begin{aligned} H(\overline{\mathrm{X}}) &=H\left(X_{1} X_{2} \cdots X_{L}\right) \\ &=H\left(X_{1}\right)+H\left(X_{2} \mid X_{1}\right)+\cdots+H\left(X_{L} \mid X_{L-1} \cdots X_{1}\right) \\ &=\sum_{l}^{L} H\left(X_{l} \mid X^{l-1}\right)=H\left(X^{L}\right) \end{aligned}$

• 平均每个符号的熵为：

  $H_{L}(\bar{X})=\frac{1}{L} H\left(X^{L}\right)$

• 若当信源退化为无记忆时:若进一步又满足平稳性时

  $H(\bar{X})=\sum_{l}^{L} H\left(X_{l}\right) \quad H(\bar{X})=L H(X)$

平稳有记忆N次扩展源的熵

设 $\mathbf{X}$ 为离散平稳有记忆信源, $\mathbf{X}$ 的 $\mathbf{N}$ 次扩展源记为 $X^{N}$ ,

$X^{N}=\left[X_{1} X_{2} \cdots X_{N}\right]$

根据熵的可加性,得
$H\left(X^{N}\right)=H\left(X_{1} X_{2} \cdots X_{N}\right)=H\left(X_{1}\right)+H\left(X_{2} / X_{1}\right)+\cdots H\left(X_{N} / X_{1} \cdots X_{N-1}\right)$
根据平稳性和熵的不增原理,得 $H\left(X^{N}\right) \leq N H\left(X_{1}\right)$,
仅当无记忆信源时等式成立。

对于 $\mathrm{X}$ 的 $\mathrm{N}$ 次扩展源, 定义平均符号熵为:

$H_{N}(X)=\frac{1}{N} H\left(X^{N}\right)=\frac{1}{N} H\left(X_{1} \cdots X_{N}\right)$

信源 $\mathrm{X}$ 的极限符号熵定义为：

$H_{\infty}(X)=\lim _{N \rightarrow \infty} \frac{1}{N} H\left(X^{N}\right)=\lim _{N \rightarrow \infty} \frac{1}{N} H\left(X_{1} \cdots X_{N}\right)$

极限符号熵简称符号熵, 也称熵率。

定理: 对任意离散平稳信源, 若 $H_{1}(X)<\infty$ , 有:

(1) $H\left(X_{N} / X_{1} \cdots X_{N-1}\right)$ 不随 $\mathbf{N}$而增加;
(2) $H_{N}(X) \geq H\left(X_{N} / X_{1} \cdots X_{N-1}\right) ;$
(3) $H_{N}(X)$ 不随 N 而增加;
(4) $H_{\infty}(X)$ 存在,且 $H_{\infty}(X)=\lim _{N \rightarrow \infty} H\left(X_{N} / X_{1} \cdots X_{N-1}\right)$

该式表明, 有记忆信源的符号熵也可通过计算极限条件熵得到。