第三章 离散信源

3-1 离散信源的分类及其描述

根据时域：

• 单符号信源：信源每次只输出一个符号，可用随机变量描述信源输出的消息
• 符号序列信源：信源每次输出一个时域离散的符号序列，可用随机向量描述信源输出的消息
• 波形信源：信源每次输出时域连续的消息，可用随机过程描述信源输出的消息，采样后即为符号序列信源

根据时间和取值分布：

• 离散信源：在时间和取值上均离散，可用离散随机变量/随机向量/随机过程描述
• 连续信源：在时间或取值上连续，可用连续随机变量/随机向量/随机过程描述，采样后为信号、脉冲信号

根据平稳特性：

• 平稳：信源概率分布/密度不随时间改变
• 非平稳

根据记忆特性：

• 无记忆：信源在不同时刻发出的消息统计独立
• 有记忆（记忆长度有限的信源为马尔可夫信源）

信源编码：尽可能少的码元符号或尽可能低的数据速率来描述信源输出的消息

3-2 离散信源的熵

信息熵

定义 3.5 若信源发出 N 个不同符号 $x_1,x_2,\dots ,x_i,\dots ,x_N$ 分别代表 N 种不同消息，各符号概率为 $P_1,P_2,\dots ,P_i,\dots ,P_N$ 且相互统计独立，则为单符号离散无记忆信源

其信息熵为 $$H(X)=\sum _{i=1}^N{P}_{i}I(x_i)=-\sum _{i=1}^N{P}_i\mathrm{lb}{P}_i$$

定义 3.6 若信源发出的消息是由 K 个离散符号构成的符号序列，且各消息相互统计独立，则为发出符号序列消息的离散无记忆信源

K 重符号序列信源：每次发送都在 N 个符号里随机选 K 个（可重复）

定义 3.7 若单符号离散无记忆信源的信源空间为 $[X\cdot P]$，对其 K 重扩展得到符号序列 $X=X_1{X}_2\dots X_K$，则称扩展后的信源为离散无记忆信源 $[X\cdot P]$ 的 K 重扩展信源，扩展得到的符号序列记为 $X^K$

若 $X^K$ 彼此统计独立，则定义 3.7 与 3.6 等价，也是发出符号序列消息的离散无记忆信源

发出符号序列消息的离散无记忆信源的熵为 $$H(X^K)=KH(X)=-K\sum _{i=1}^N{P}_i\mathrm{lb}{P}_i$$

定义 3.8 若信源发出的消息是由 K 个离散符号构成的符号序列，且各消息相互统计相关，则为发出符号序列消息的离散有记忆信源

有记忆信源的符号序列之间的关联程度可以用转移概率描述

符号间非独立（有关联）会使得信源输出的信息量减少

马尔可夫信源熵：是一般信源熵的特例 $$H(X|Y)=-\sum _{XY}P(xy)\mathrm{lb}P(x|y)$$

时间熵

时间熵 单位时间内发出的平均信息量 $H_t$，单位 b/s 或 bps

定义 3.9 若信源为具有 N 个单个符号消息的离散信源，第 i 个符号消息占用的时间为 $b_i$ 秒，概率为 $P_i$，则称 $b_i$ 的统计平均值为该信源符号消息的平均时间长度 $\overline{b}$ 或 平均长度，单位为秒/符号 $\overline{b}={\sum }_{i=1}^N{P}_i{b}_i$ 秒/符号

若信源平均每秒发送 n 个符号，则 $\overline{b}=1/n$ 秒/符号

对于单符号离散无记忆信源： $$H_t=\frac{H(X)}{\overline{b}}b/s$$

K 重扩展的符号序列的时间熵

K 重扩展的离散无记忆信源的符号消息平均长度 $$\overline{B}=K\overline{b}=K\sum _{i=1}^N{P}_i{b}_i$$

仍有 $H_t=\frac{H(X^K)}{K\overline{b}}=\frac{H(X)}{\overline{b}}b/s$

若信源平均每秒发送 n 个 K 重符号序列消息，则 $\overline{b}=1/nK$ 秒/符号， 有$H_t=nKH(X)b/s$

若为有记忆信源，有 $H_t=\frac{H(X^K)}{K\overline{b}}<\frac{H(X)}{\overline{b}}b/s$， 其时间熵小于无记忆信源的

消息之间的关联性体现在信源熵而非平均长度

3-3 信源的冗余度

3-3-1 最大信源熵

定理3.1 最大熵定理 设信源 X 中包含 M 个不同符号，其信源熵为 $H(X)$，有 $$H(X)\le \mathrm{lb}M$$ 当且仅当 X 中各个符号的概率全相等时取等，此时得到最大熵 $$H(X{)}_{max}=\mathrm{lb}M$$ 即熵的极值性，第二章证过

定理 3.2 两个集合 X、Y 的共熵 $H(XY)$ 与这两个集合的信源熵 $H(X),H(Y)$ 之间有 $$H(XY)\le H(X)+H(Y)$$ 当且仅当两个集合相互独立时取等，此时取得最大熵 $$H(XY{)}_{max}=H(X)+H(Y)$$

定理 3.3 对于初始信源 X 经过 K 重扩展的信源，若初始信源熵为 $H(X)$，扩展后为 $H(X^K)$，有 $$H(X^K)\le KH(X)$$ 当且仅当 K 重符号序列消息的各个符号间相互独立时取等，此时取得最大熵 $$H(X^K{)}_{max}=KH(X)$$

符号不等概或符号间有相关性都会损失信源熵

• 信源编码中要压缩冗余度来提高传输的有效性
• 信道编码中要注入冗余度来提高传输的可靠性

定义 3.10 设信源实际的熵为 H，该种信源可能的最大熵为 $H_{max}$，则信源的冗余度为 $$R=\frac{H_{max}-H}{H_{max}}\times 100\%$$ 即信源在发出消息时无用信息量的百分比

3-4 信源符号序列分组定理

设离散无记忆信源的信源空间为 $$[\mathbf{X}\cdot P]:\{\begin{array}{ccccc}\mathbf{X}:& x_1,& x_2,& \dots ,& x_N\\ P(\mathbf{X}):& P\left(x_1\right),& P\left(x_2\right),& \dots ,& P\left(x_N\right)\end{array}$$

K 重扩展后，各符号序列为 ${\mathbf{x}}_i=(x_{i1},x_{i2},\dots ,x_{iK})$，这样的符号序列有 $N^K$ 个。

当 K 足够大时，一个序列中任一符号 $x_i$ 出现的次数都会趋近于 $K{P}_i$，即扩展后很多序列的概率组成相同，是等概的 $$P(x_1,\dots ,x_N)=\sum _{i=1}^N(P_i{)}^{K{P}_i}$$

具有上述结构的序列称为 典型序列 $G_1$，其余的序列为 非典型序列 $G_2$

典型序列的自信息量也相等，为 $I({\mathbf{x}}_1)=I({\mathbf{x}}_2)=\cdots =I({\mathbf{x}}_i)=-\mathrm{lb}{P}_i$

自信息量的期望，即信息熵，为 $E\{I({\mathbf{x}}_i)\}=KH(X)$

当典型序列的概率之和很大时，就可以用典型序列来代表扩展信源（这正是数据压缩的本质）

信源符号序列分组定理说明上述分组是存在的，且可以估算其典型序列的数目

定理 3.4 信源符号序列分组定理 AEP（渐进均分特性） 设离散无记忆信源的信源符号为 $x_1,x_2,\dots ,x_i,\dots ,x_N$，各符号概率为 $P_1,P_2,\dots ,P_i,\dots ,P_N$，将该信源进行 K 重扩展得到 K 重符号序列 $\mathbf{x}$，则任意给定 $\epsilon >0,\delta >0$，总有对应整数 $K_0$，使得 $K>K_0$ 时，有 $$P\left\{\left|\frac{1}{K}\mathrm{lb}P(\mathbf{x})+H(\mathbf{X})\right|<\delta \right\}>1-\epsilon$$ 即信息熵与自信息量的差趋近于0

所谓渐近等分性：序列的越长，典型序列的总概率越接近于1，它的各个序列的出现概率越趋于相等

• 每个典型序列的概率
  • 对于任意小的正数 $\delta$，当 K 足够大时，$2^{-K(H(X)+\delta )}<P(x)<2^{-K(H(X)-\delta )}$，可近似于 $P(\mathbf{x})=2^{-KH(X)}$
• 典型序列个数
  • 对于任意小的正数 $\epsilon ,\delta$，当 K 足够大时，$(1-\epsilon )2^{K(H(X)-\delta )}\le |G_1|\le 2^{K(H(X)+\delta )}$，可近似于 $G_1=2^{KH(X)}$
• 典型序列占的比例
  • $\xi =\frac{|G_1|}{N^K}\le \frac{2^{K(H(X)+\delta }}{N^K}=2^{-K(\mathrm{lb}N-H(X)-\delta )}$
  • 根据最大熵定理，一般有 $\mathrm{lb}N-H(X)-\delta >0$
  • 随着 K 增大，典型序列占的比例逐渐趋于 0，典型序列出现概率高不等于典型序列种类多

$|G_1|$ 表示 $G_1$ 里的元素个数

信源符号序列分组定理表明，对于 K 重扩展信源，只考虑少量典型符号序列对信源特性带来的损失可以忽略，这给出了信源压缩编码的理论依据

3-5 平稳离散信源及其性质

平稳：概率分布不随时间变化

大部分实际信源在较短的一段时间都可以看作平稳信源

定义 3.10 若一个离散信源发出的符号序列 $(x_1,x_2,\dots ,x_K)$ 其出现概率与另一符号序列 $(x_{j+1},x_{j+2},\dots ,x_{j+K})$ 的出现概率相等，则为平稳离散信源

• 改变其符号序列的起始位置，其概率和条件概率均不变，即平稳离散信源对应的随机过程是严平稳的

平稳离散信源的极限熵

有记忆离散信源每发一个符号所提供的平均信息量为 $$H_{\infty }=\underset{K\to \infty }{\lim }\frac{1}{K}H(X_1{X}_2\dots X_K)\triangleq \underset{K\to \infty }{\lim }{H}_K(X_1{X}_2\dots X_K)$$

称 $H_K(X_1{X}_2\dots X_K)=\frac{1}{K}H(X_1{X}_2\dots X_K)$ 为平均符号熵，$H_{\infty }$ 为平稳离散有记忆信源的极限熵，又称熵率

平稳离散信源熵的性质

定理 3.5 若信源 X 是平稳离散信源，则有 $$H(X)=H(X_1{X}_2\dots X_K)=H(X_1)+H(X_2|X_1)+H(X_3|X_1{X}_2)+\cdots +H(X_K|X_1{X}_2\dots X_{K-1})$$ 即 $H(X)$ 是 X 中起始时刻随机变量 $X_1$ 的熵与各阶条件熵之和。也即熵的链接准则。

定理 3.6 平稳离散信源的条件熵随 K 的增加是非递增的，即 $H(X_K|X_1{X}_2\dots X_{K-1})\le H(X_{K-1}|X_1{X}_2\dots X_{K-2})$

特别的，由于平稳性，$H(X_1)=H(X_2)$，故 $H(X_2|X_1)\le H(X_2)=H(X_1)$

推论 1：给定 K 时，平稳离散信源的条件熵小于等于平均符号熵，即 $H(X_K|X_1{X}_2\dots X_{K-1})\le (1/K)H(X_1{X}_2\dots X_K)$

推论 2：平稳离散信源的平均符号熵随 K 的增加是非递增的，即 $H_K(X_1{X}_2\dots X_K)\le H_{K-1}(X_1{X}_2\dots X_{K-1})$

定理 3.7 极限熵的第二种形式 对于平稳离散信源，令 $H_K(X_1{X}_2\dots X_K)=\frac{1}{K}H(X_1{X}_2\dots X_K)$，若 $H(X_1)<\infty$，则 $H_K(X)$ 的极限值存在且有 $$H_{\infty }=\underset{K\to \infty }{\lim }{H}_K(X)=\underset{K\to \infty }{\lim }H(X_K|X_1{X}_2\dots X_{K-1})$$

• 一般离散平稳有记忆信源每发一个符号所提供的平均信息量等于极限熵 $H_{\infty }$
• $H_{\infty }$ 较难计算，但当 K 不是很大时，其平均符号熵 $H_K(X)$ 或条件熵 $H(X_K|X_1{X}_2\dots X_{K-1})$ 就非常接近于 $H_{\infty }$，可用作极限熵的近似值