离散无记忆与有记忆信源的序列熵

本专栏包含信息论与编码的核心知识，按知识点组织，可作为教学或学习的参考。markdown版本已归档至【Github仓库：information-theory】，需要的朋友们自取。或者公众号【AIShareLab】回复 信息论 也可获取。

离散无记忆信源的序列熵

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

发出单个符号的信源

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

发出符号序列的信源

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

当信源无记忆时：
$$\begin{array}{rl}p(\bar{X}& =x_i)=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{array}$$

信源的序列熵

$$\begin{array}{rl}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{array}$$

• 若又满足平稳特性（平稳信号包含的信息量小，其统计特性随时间不变化）,即与序号l无关时:

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

• 信源的序列熵

  $$H(\overline{\mathrm{X}})=\mathrm{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$ bit/符号

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

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

  $H(\bar{X})={\log }_{2}4=2$ bit/序列

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

• 信源的符号熵

  $H_2(\overline{\mathrm{X}})=\frac{1}{2}H(\overline{\mathrm{X}})=1$ bit/符号

• 信源的序列熵

$H(\overline{\mathrm{X}})=H\left(X^L\right)=-{\sum }_{i=1}^{9}p\left(a_i\right)\log p\left(a_i\right)=3bit/\text{ 序列 }$

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

$\begin{array}{c}H(X)=-{\sum }_{i=1}^{3}p\left(x_i\right)\log p\left(x_i\right)=1.5\text{ bit/符号 }\\ H(\bar{X})=2H(X)=2\times 1.5=3\mathrm{bit}/\text{ 序列 }\end{array}$

离散有记忆信源的序列熵

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

• 对于由两个符号组成的联合信源, 有下列结论:
  $$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)\ge H\left(X_1\mid X_2\right),H\left(X_2\right)\ge 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{array}{rl}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{array}$$

• 平均每个符号的熵为：

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

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

  $$H(\bar{X})=\sum _l^{L}H\left(X_l\right)H(\bar{X})=LH(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)\le NH\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)=\underset{N\to \infty }{\lim }\frac{1}{N}H(X^N)=\underset{N\to \infty }{\lim }\frac{1}{N}H(X_1\cdots X_N)$$
极限符号熵简称符号熵, 也称熵率。

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

(1) $H\left(X_N/X_1\cdots X_{N-1}\right)$ 不随 $\mathbf{N}$而增加;
(2) $H_N(X)\ge 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\to \infty }H(X_N/X_1\cdots X_{N-1})$

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

参考文献：

1. Proakis, John G., et al. Communication systems engineering. Vol. 2. New Jersey: Prentice Hall, 1994.
2. Proakis, John G., et al. SOLUTIONS MANUAL Communication Systems Engineering. Vol. 2. New Jersey: Prentice Hall, 1994.
3. 周炯槃. 通信原理（第3版）[M]. 北京：北京邮电大学出版社, 2008.
4. 樊昌信, 曹丽娜. 通信原理（第7版） [M]. 北京：国防工业出版社, 2012.