企业官网建设流程全解析

第三章 离散信源及信源熵

3.4 离散多符号信源

3.5 马尔科夫信源

3.6 信源的相关性和剩余度

3.4 离散多符号信源

3.4.1 离散平稳信源的定义

定义3.3：离散平稳信源：消息为离散随机序列 X=X₁X₂X₃…，满足两条
1. 离散性：每个 Xᵢ 取值在有限符号集 {a₁,a₂,…,a_Q}
2. 平稳性：联合概率分布和时间起点无关，只和符号间隔长度有关
P[X_{i₁}=x₁,X_{i₂}=x₂,…,X_{i_N}=x_N] = P[X_{i₁+h}=x₁,X_{i₂+h}=x₂,…,X_{i_N+h}=x_N]

离散平稳信源性质：1. 一维分布：任意时刻单符号分布相同P[Xᵢ]=P[Xⱼ]

2. 二维联合分布：P[XᵢX_{i+1}]=P[XⱼX_{j+1}]

拓展：推广到N维，N维联合分布只和符号之间的间隔有关，和从哪个时刻开始无关

3.4.2 常见的离散平稳信源

1.一维离散平稳信源

当N=1时，平稳性退化为：

P[Xᵢ] = P[Xⱼ]

此时就是单符号离散信源，符号一维先验概率和时间无关，称为一维离散平稳信源。

2. 二维离散平稳信源

当N=2时，平稳性退化为：

P[Xᵢ] = P[Xⱼ]

P[XᵢX_{i+1}] = P[XⱼX_{j+1}]

等价表征公式：

P[Xᵢ] = P[Xⱼ]

P[X_{i+1}|Xᵢ] = P[X_{j+1}|Xⱼ]

说明二维离散平稳信源的条件概率与时间起点无关。

3. 有限维离散平稳信源

一般地，N为有限正整数m时，平稳性退化为：

P[Xᵢ] = P[Xⱼ]

P[X_{i+1}|Xᵢ] = P[X_{j+1}|Xⱼ]

P[X_{i+2}|X_{i+1}Xᵢ] = P[X_{j+2}|X_{j+1}Xⱼ]

……

P[X_{i+m-1}|X_{i+m-2}…Xᵢ] = P[X_{j+m-1}|X_{j+m-2}…Xⱼ]

3.4.3 离散多符号信源的信源熵
定义3.4 平均符号熵（有限序列）：N长随机变量序列 X = X₁X₂…X_N 中，平均符号熵定义为：H_N(X) = (1/N) H(X₁X₂…X_N)

定义3.5 极限熵（无限序列）：当平均符号熵中符号序列长度 N 趋于无穷时，可以得到极限熵 H_∞。N长随机变量序列 X = X₁X₂…X_N 中，当 N→∞ 时，平均符号熵 H_N(X) 定义为极限熵

H_∞ = lim(N→∞) H_N(X) = lim(N→∞) (1/N) H(Xᴺ)

极限熵又称为熵率。
3.4.4 离散平稳无记忆信源

简单起见，先讨论无记忆信源；同时假设信源具有平稳性，即首先讨论离散平稳无记忆信源。

假定信源每次输出的是 N 长符号序列，这可以看作一个新的信源 Y。

1. 扩展信源的含义

①扩展信源是从单符号信源扩展而成的新信源。

②二次扩展信源是一个二维随机矢量，二维矢量中的两个元素取自同一个信源符号集。

③三次扩展信源是一个三维随机矢量，三维矢量中的三个元素取自同一个信源符号集。

④N次扩展信源是一个N维随机矢量，此N维随机矢量中的N个元素取自同一个信源符号集A。

同一个信源符号集：扩展信源里面所有的符号来自同一个样本空间。

定义3.6 N次扩展信源：设信源X的符号符号集为A，x为N维随机矢量 x=(X₁X₂…X_N)，并且随机矢量中的元素取自同一个符号集，即 X₁=x₁∈A，X₂=x₂∈A，…，X_N=x_N∈A，则此类信源称为N次扩展信源。

2. 离散无记忆二进制信源的二次扩展信源

二次扩展信源符号：a₁=00，a₂=01，a₃=10，a₄=11

离散无记忆性：

p(a₁)=p(00)=p(0)p(0)

p(a₂)=p(01)=p(0)p(1)

p(a₃)=p(10)=p(1)p(0)

p(a₄)=p(11)=p(1)p(1)

二次扩展信源示意：

原始单符号信源发出0、1序列，两个一组打包，变成二次扩展信源符号。

二次扩展信源记为 X²=(X₁,X₂)。

3. 离散无记忆二进制信源的三次扩展信源

三次扩展信源里，一个信源符号包含3个基础符号，取自符号集A={0,1}。

三次扩展信源一共8个符号：

a₁=000，a₂=001，a₃=010，a₄=011

a₅=100，a₆=101，a₇=110，a₈=111

每个符号的概率等于对应三位二进制各位概率相乘。

4. 离散无记忆信源的N次扩展信源

定义3.7 离散无记忆信源的N次扩展信源：

5. 扩展信源的信源熵

等概：①平均符号熵（熵率）②信源熵

例3.8 红绿灯例题

已知：红灯、绿灯概率都是0.5，符号之间无关联。

(1) N=1，单符号信源：符号{红，绿}，p=0.5

单个符号自信息量 I = -log₂0.5 = 1 bit

（2) N=2，二次扩展，一个扩展符号含2个基础符号

序列概率 p=0.5²，自信息量 I=2bit，平均每个基础符号信息量：2/2=1 bit

(3) N=4，四次扩展，一个扩展符号包含4个基础符号

p=0.5⁴，自信息量 I=4bit，平均基础符号信息量=1bit

(4) N=8，八次扩展，一个扩展符号包含8个基础符号

p=0.5⁸，自信息量 I=8bit，平均基础符号信息量=1bit

小结：离散无记忆扩展，不管扩展多少次，每一个基础符号携带的平均信息量不变，始终等于原单符号的自信息。

3.4.5 离散平稳有记忆信源

1. 离散平稳有记忆信源的信源熵

平稳有记忆信源，符号依赖不只是相邻符号，多个符号之间也会存在依赖。
N长序列的联合熵：
H(X)=H(X1X2…XN)

熵链规则展开：
H(X1X2…XN)
= H(X1)+H(X2X3…XN | X1)
= H(X1)+H(X2|X1)+H(X3|X1X2)+…+H(XN | XN-1 XN-2 … X1）

2. 离散平稳有记忆信源的信源熵性质

定理3.2信源熵性质
1. 条件熵 H(XN | XN-1 XN-2 … X2 X1) 随着N增加而递减
2. N固定时，平均符号熵大于等于条件熵
HN(X) ≥ H(XN | XN-1 XN-2 … X1)
3. 平均符号熵 HN(X) 随着N增加而递减
4. 如果H(X1)<无穷，极限熵 H∞ 存在
H∞ = lim（N→∞）HN(X)
H∞ = lim（N→∞）H(XN | XN-1 XN-2 … X2 X1)
3.4.6 一维离散平稳信源的信源熵

1. 一维离散平稳信源的本质

我们先思考：一维离散平稳信源是不是单符号离散无记忆信源？下面看例题3.9红绿灯。
例3.9 红绿灯
红绿灯序列满足N=1时平稳条件：不同时刻红灯概率相同、绿灯概率相同。
但是相邻时刻的红绿灯不是独立的，转移关系：
P(绿|绿)=0.8
P(红|绿)=0.2
P(绿|红)=0.2
P(红|红)=0.8
含义：P(绿|红)=0.2，代表当前是红灯，下一时刻变成绿灯的概率是0.2，其余同理。
求t=2、3、4时刻遇到红灯的概率。
公式：P(Xt=红) = 求和【P(Xt-1) · P(Xt=红 | Xt-1)】
初始条件：
P(X1=红)=0.6，P(X1=绿)=0.4
t=2：
P(X2=红)
= P(X1=绿)·P(X2=红|X1=绿) + P(X1=红)·P(X2=红|X1=红)
= 0.4×0.2 + 0.6×0.8 = 0.56
P(X2=绿)=0.44
t=3：
P(X3=红)
= P(X2=绿)·P(X3=红|X2=绿) + P(X2=红)·P(X3=红|X2=红)
= 0.44×0.2 + 0.56×0.8 = 0.536
P(X3=绿)=0.464
t=4：
P(X4=红)
= P(X3=绿)·P(X4=红|X3=绿) + P(X3=红)·P(X4=红|X3=红)
= 0.464×0.2 + 0.536×0.8 = 0.5216
总结结果：
P(X1=红)=0.6
P(X2=红)=0.56
P(X3=红)=0.536
P(X4=红)=0.5216
结论：
不同时刻红灯概率不一样，和“无记忆信源”互相矛盾。
所以：一维离散平稳信源不是无记忆信源。
2. 一维离散平稳信源的信息熵
由平稳性，任意时刻的信息熵相等：
H(Xt) = H(X)
3. 一维离散平稳信源的条件熵
任意两个时刻的条件熵：
H(Xi | Xj) = H(X)
4. 一维离散平稳信源的联合熵
两个符号Xi、Xj的联合熵：
H(Xi Xj) = H(Xi)+H(Xj|Xi) = H(Xi)+H(Xj) = 2H(X)

3.5马尔可夫夫信源

在实际问题中往往采取限制记忆长度的做法来简化符号之间的相关性，3.5.1 有限状态马尔可夫链

在引入有限状态马尔可夫链之前，先分析下面的例题。

例题3.10 青蛙跳

已知小学生春风抓住了一只青蛙，放到画了棋盘格的操场上，观察发现青蛙跳跃时期四个方向（前、后、左、右）等概率跳跃。假设初始时刻青蛙在方格一；时刻1在方格二；时刻2在方格三；时刻3在方格四，见图3.4。求时刻4青蛙所处位置的概率。

解：时刻4青蛙所处位置的概率

可以发现：青蛙在时刻4所处位置的概率分布，只与时刻3所处位置有关，而与更早的历史时刻（时刻2、1和0）无关：青蛙跳具有马尔可夫性。

更进一步，春风还发现下面的条件概率成立：

定义3.9 马尔可夫链

1.马尔可夫链的物理解释

马尔可夫链性质：不可约i←→j；非周期(d=1)

不可约+非周期 ⇒ 收敛平稳（唯一）

P：稳态分布→极限分布（唯一性）

简而言之，当前时刻系统所处状态，只与前一时刻有关，即具有马尔可夫性

2.转移概率与转移矩阵

① 在状态空间 S 相同的情况下，不同的条件概率对应的不同的马尔可夫链，因此条件概率是描述马尔可夫链性质的重要参数，此处条件概率，定义为转移概率。

②对于马尔可夫链{Xn,n∈Z+}，转移概率定义为

③条件概率称为一步转移概率，也称为基本转移概率，即

显然，一步转移概率满足下面的性质：

，

④当时，k 步转移概率即为一步转移概率：

⑤当时，可得 k 步转移概率：

⑥组成 k 转移矩阵：

k 步转移矩阵中每行元素之和为1。

3.5.2 齐次马尔可夫链及其平稳分布

定义3.10齐次马尔可夫链

在马尔可夫链中，如果满足

则从状态 i 一步转移到状态 j 的概率与起始时刻 m 无关，这类马尔可夫链称为齐次马尔可夫链或时齐马尔可夫链。

1.齐次马尔可夫链的性质

（1）根据齐次马尔可夫链的定义可以得到如下性质：①齐次马尔可夫链是具有平稳转移概率的马尔可夫链；

②；

③。

2.齐次马尔可夫链的转移矩阵

由齐次马尔可夫链的一步转移概率可以写出一步转移矩阵：

3.切普曼-柯尔莫哥洛夫方程（C-K方程）

对于齐次马尔可夫链，有切普曼-柯尔莫哥洛夫方程。

定理3.3切普曼-柯尔莫哥洛夫方程

对于具有步转移概率的齐次马尔可夫链，存在下述的切普曼-柯尔莫哥洛夫方程：

证明：

写成矩阵形式：

推论：

（1）；

（2）；

（3）齐次马尔可夫链的 m 步转移矩阵可以利用一步转移矩阵求取。

4.齐次马尔可夫链的平稳分布

（1）转移矩阵的渐近性质。

则 n 步转移矩阵P(n)存在下列极限（式(D.1)）：

（2）平稳分布性质。

①假设有一有限状态马尔可夫链，其转移矩阵为 P。若存在一个正整数 m，使得对状态空间 S 中的任意状态 i 和 j，有

②平稳分布满足如下性质：

（3）平稳分布的意义如下：

①可以建模为齐次马尔可夫链的系统，若满足平稳分布所要求的条件，则初始时刻系统所处的状态并不影响系统平稳后的状态分布。

②系统最后所处状态的概率与初始时刻（或者历史时刻）所处状态无关，也说明系统（指满足平稳分布条件的齐次马尔可夫链）的状态仅与前一时刻有关（取决于一步转移矩阵）。

（4）平稳分布具有唯一性。

例3.12求取平稳分布。

已知一齐次马尔可夫链的状态转移矩阵为

是否存在平稳分布？若存在，求此平稳分布。

解：

（1）平稳分布存在性：

式中，星号“*”表示非零元素。根据平稳分布存在的条件知 m=3 时转移矩阵中各元素均大于0，故存在平稳分布。

（2）求取平稳分布。设平稳分布为。根据平稳分布的性质可得

解得：

3.5.3 齐次马尔可夫信源

定义3.11马尔可夫信源

若信源输出的符号序列和状态序列满足下面的条件：

（1）某一时刻信源输出的符号xn只与当前信源状态zn有关，而与历史状态无关，即

（2）信源状态只由当前输出符号和前一时刻信源状态唯一决定，即

式中，为信源符号集，；为信源状态集，.

1.一阶马尔可夫信源及数学模型

2.一阶齐次马尔可夫信源

齐次马尔可夫链性质，若状态转移概率与时间无关，即

P[Xt|Xt-1…X1]=P[Xt|Xt-1]=P[X2|X1]

则称此信源为一阶齐次马尔可夫信源。

例3.14一阶齐次马尔可夫信源

假设例3.9中相邻时刻红绿灯的关联关系为

P[绿|绿]=0.8,P[红|绿]=0.2,P[绿|红]=0.2,P[红|红]=0.8

3.一阶齐次马尔可夫信源的信息熵

已求得 t 在1、2、3、4时刻红绿灯的概率分布如下（例3.9）：

P[X1=红]=0.6,P[X2=红]=0.56,P[X3=红]=0.536,P[X4=红]=0.5216

P[X1=绿]=0.4,P[X2=绿]=0.44,P[X3=绿]=0.464,P[X4=绿]=0.4784

H(X1)=0.809比特/符号,H(X2)=0.830比特/符号

4.一阶齐次马尔可夫信源相邻符号间的条件熵

相邻两符号的联合分布：

条件熵：

条件熵：

条件熵：

总结：对于一阶齐次马尔可夫信源，任意相邻两个符号间的条件熵相同。

5.一阶齐次马尔可夫信源多符号间的条件熵

对于一阶齐次马尔可夫信源，多符号间的条件熵为相邻符号间的条件熵：。

6.二阶齐次马尔可夫信源

则此类信源称为二阶马尔可夫信源，即有

P[Xn|Xn-1Xn-2Xn-3…X2X1]=P[Xn|Xn-1Xn-2]

例3.15二阶马尔可夫信源。

假设例3.9中红绿灯间的关联关系（为表示方便：0=绿灯；1=红灯）：

P[0|00]=0.8：已遇到灯00的情况下，再遇到灯0的概率

：已遇到灯00的情况下，再遇到灯1的概率

：已遇到灯01的情况下，再遇到灯0的概率

P[1|01]=0.5：已遇到灯01的情况下，再遇到灯1的概率

：已遇到灯10的情况下，再遇到灯0的概率

P[1|10]=0.5：已遇到灯10的情况下，再遇到灯1的概率

：已遇到灯11的情况下，再遇到灯0的概率

：已遇到灯11的情况下，再遇到灯1的概率

3.5.4 m 阶齐次马尔可夫信源

1. m阶马尔可夫信源

P[xn = ain | xn-1 = ain-1, xn-2 = ain-2, ··· , xn-m = ain-m , ··· , x2 = ai2, x1 = ai1]

= P[xn = ain | xn-1 = ain-1, xn-2 = ain-2, ··· , xn-m = ain-m]

则此类信源称为 m 阶马尔可夫信源。

2. m阶马尔可夫信源的状态转移概率

时刻 n 处的一步状态转移概率为

pij(n) = P[ain+1 | aim aim-1 ··· ai2 ai1] i,j ∈ {1,2,···,Q^m} (3.58)

Si = aim aim-1 ··· ai2 ai1

Sj = ain+1 aim ··· ai3 ai2

ain+1, aim, aim-1, ··· , ai2, ai1 ∈ A

3.m阶齐次马尔可夫信源的极限熵

定理3.4 m阶齐次马尔可夫信源极限熵

m阶齐次马尔可夫信源的极限熵为

H∞ = H(Xm+1 | Xm Xm-1 ··· X2 X1) = H_{m+1} (3.60)

H_{m+1} = ∑_{S∈S} P[Si] H(X|Si) (3.61)

例3.16 极限熵计算举例。

例3.15所示的交通灯间的关联关系与时间无关，因此可以建模为二阶齐次马尔可夫信源，【手写标注：m=2】

其状态转移矩阵为

[0.8 0.2 0.0 0.0]

P=[0.0 0.0 0.5 0.5]

[0.5 0.5 0.0 0.0]

[0.0 0.0 0.2 0.8]

求此信源的极限熵。

解：（1）判断是否存在平稳分布。经计算可知：P·P=P² =

[0.64 0.16 0.10 0.10]

[0.25 0.25 0.25 0.25]

[0.40 0.10 0.10 0.25]

[0.10 0.10 0.16 0.64]

使得 P^m 中各个元素均大于 0

（2）求取平稳分布。设所述马尔可夫信源的平稳分布为 π = [π1 π2 π3 π4]，据式 (3.49) 中平稳分布性质，有

π = πP

π1+π2+π3+π4 = 1 限制条件

解得：

π1 = 5/14

π2 = 1/7

π3 = 1/7

π4 = 5/14 (3.62)

【π1=π4；π2=π3】

（3）求取极限熵。根据式 (3.61) 中极限熵计算公式可得

H∞ = H_{m+1} = H_3

= P[S1]H(X|S1) + P[S2]H(X|S2) + P[S3]H(X|S3) + P[S4]H(X|S4)

H(X|S1) = -P[0|S1]logP[0|S1] - P[1|S1]logP[1|S1] = H(0.8,0.2)

H(X|S2) = -P[0|S2]logP[0|S2] - P[1|S2]logP[1|S2] = H(0.5,0.5)

H(X|S3) = -P[0|S3]logP[0|S3] - P[1|S3]logP[1|S3] = H(0.5,0.5)

H(X|S4) = -P[0|S4]logP[0|S4] - P[1|S4]logP[1|S4] = H(0.2,0.8)

= P[S1]H(0.8,0.2) + P[S2]H(0.5,0.5) + P[S3]H(0.5,0.5) + P[S4]H(0.2,0.8)

P[S1]=π1 π4=P[S4] P[S2]=π2 π3=P[S3]

P[S1]=P[S4]=5/14 P[S2]=P[S3]=1/7

= 0.8(比特/符号)

3.6 信源的相关性和剩余度[冗余度和剩余度，小题部分】

3.6.1 信源的相关性
因此，对于有 Q 个信源符号【等概发生的时候】的离散平稳有记忆信源，可以分别用不同阶的马尔可夫信源来近似。
根据定理3.2可得
log Q = H_max = H0 ≥ H1 ≥ H2 ≥ … ≥ Hm ≥ … ≥ H_{m+1} ≥ … ≥ H∞ (3.63)
【最大熵；符号携带最大的信息量】
表3.2 马尔可夫信源近似

例3.17 已知英文信源包括26个英文字母和1个空格符号。英文信源所发送符号有相关性，对相关程度做不同近似，会得到不同的信源模型：
（1）英文符号等概率分布且相互独立；
（2）统计英文符号实际出现的概率；
（3）英文信源建模为一阶马尔可夫信源；
（4）英文信源建模为二阶马尔可夫信源；
（5）英文信源建模为四阶马尔可夫信源；
（6）考虑全部符号具有相关性。

求上述各种模型下的英文信源的熵。

解：H0 = log Q = log 27 = 4.76(比特/符号)
H1 = - Σ P[xi]log P[xi] = 4.03(比特/符号)
H2 = 3.32(比特/符号)
H3 = 3.10(比特/符号)
H5 = 1.65(比特/符号)
H∞ = 1.40(比特/符号)

3.6.2 剩余度的引入

1. 例3.13

如果要传输100bit的信息量，那么不同的信源模型各需要多少符号？

符号等概率分布并且独立：
N = [100 / H0] = [100 / 4.76] = 21 个字符

非等概率分布的无记忆信源：
N = [100 / H1] = [100 / 4.03] = 25 个英文符号

信源建模为一阶马尔可夫信源：
N = [100 / H2] = [100 / 3.32] = 31 个英文符号

信源建模为二阶马尔可夫信源：
N = [100 / H3] = [100 / 3.10] = 33 个英文符号

信源建模为四阶马尔可夫信源：
N = [100 / H5] = [100 / 1.65] = 61 个英文符号

考虑全部符号具有相关性：
N = [100 / H∞] = [100 / 1.40] = 72 个英文符号
2. 信源效率
定义3.12 信源效率
信源熵率（极限熵）与具有相同符号集的最大熵之间的比值称为信源效率，其表达式为
η = H∞ / H0 (3.64)
【相对熵】

定义3.13 信源剩余度
信源剩余度定义为
γ = 1 - η = 1 - H∞ / H0 (3.65)
信源剩余度也称冗余度。

3. 信源剩余度的性质
(1) H0 - H∞ 越大，信源剩余度越大；
(2) 如果信源为符号等概率分布的离散无记忆信源，则信源剩余度为0；
(3) 信源符号的记忆长度越长，相关性越强，H∞ 就越小，信源剩余度越大。

4. 信源剩余度的意义
剩余度大的消息抗干扰能力强。
例3.18 根据例3.17的结果，计算英文信源的信源剩余度。
解：
η = H∞ / H0 = 1.40 / 4.76 = 0.29
γ = 1 - η = 0.71