离散序列信源的熵课件

2023/6/71问题：如何描述离散无记忆序列信源的序列熵？如何描述离散有记忆序列信源（平稳序列和齐次遍历马氏链信源）的序列熵？

第四节离散序列信源的熵2023/6/722.4.1离散无记忆信源的序列熵

设信源输出的随机序列为X，X＝（X1X2…Xl…XL），序列中的变量即序列长为L。2023/6/73设：随机序列的概率为：p(X=xi)=p(X1=xi1,X2=xi2,……,XL=xiL)=p(xi1)p(xi2/xi1)p(xi3/xi1xi2)…p(xiL/xi1xi2…xiL-1)=p(xi1)p(xi2/xi1)p(xi3/xi12)…p(xiL/xi1L-1)式中xi1L-1=xi1xi2…xiL-1

2023/6/74分析：（1）当信源无记忆（序列中的符号之间无相关性）时，p(xi)=p(xi1xi2…xiL)=2023/6/75其中（2）若信源的序列满足平稳特性（与序号l无关）时，有p(xi1)=p(xi2)=…=p(xiL)=p，p(xi)＝pL，则信源的序列熵又可表示为H(X)=LH(x).

平均每个符号熵为

HL(X)=H(X)/L=H(x)(单个符号信源的符号熵)2023/6/76第四讲2003年5月6日2023/6/772.4.2离散有记忆信源的序列熵

问题对于由两个符号组成的联合信源，有下列结论：（l）H（X1X2）＝H（X1）＋H（X2／X1）

=H（X2）+H（X1／X2）（2）H（X1）≥H（X1／X2）

H（X2）≥H（X2／X1）

2023/6/78当前后符号无依存关系时，有下列推论：

H（X1X2）＝H（X1）＋H（X2）

H（X1）=H（X1／X2）

H（X2）=H（X2／X1）2023/6/79由有限个有记忆序列信源符号组成的序列

设：信源输出的随机序列为X，X＝(X1X2…XL)，则信源的序列熵定义为

H(X)=H(X1X2…XL)

=H(X1)+H(X2/X1)+…+H(XL/X1X2….XL-1)记作

H（X）=H（XL）=2023/6/710平均每个符号的熵为

HL（X）=H（X）/L若当信源退化为无记忆时，有

H（X）=H（Xl

）若进一步又满足平稳性时，则有

H（X）=LH（X）

2023/6/711例2-4-1

已知:离散有记忆信源中各符号的概率空间为:

现信源发出二重符号序列消息（ai,aj），这两个符号的概率关联性用条件概率p(aj/ai)表示，并由下表给出。求离散信源的序列熵和平均每个符号的熵?2023/6/712ai

aja0a1a2a09/112/90a11/83/41/8a202/97/92023/6/713解：条件熵

H（X2／X1）=比特/符号单符号信源熵

比特/符号发二重符号序列的熵

H（X1X2）=H（X1）+H（X2/X1）

=1.543+0.872=2.415比特/符号平均符号熵

H2（X）=H（X2）/2=1.21比特/符号2023/6/714说明：比较上述结果可得：

H2（X）<H1（X），即二重序列的符号熵值较单符号熵变小了，也就是不确定度减小了，这是由于符号之间存在关联性（相关性）造成的。2023/6/715

离散平稳序列信源(1)

时间不变性:联合概率具有时间推移不变性：

p{Xi1=x1,Xi2=x2,…….,XiL=xL}=p{Xi1+h=x1,Xx2+h=x2,……,XiL+h=xL

}2023/6/716(2)

H(XL/XL-1)是L的单调递减函数证明:H(XL/X1X2…XL-1)≤H(XL/X2X3…XL-1)(条件较多的熵小于或等于减少一些条件的熵)=H(XL-1/X1X2…XL-2)（平稳性）

≤H(XL-1/X2X3…XL-2)(条件较多的熵小于或等于减少一些条件的熵)=H(XL-2/X1X2…XL-3)（平稳性）

…≤H(X2/X1)2023/6/717(3)

HL(X)≥H(XL/XL-1)证明:HL(X)=H(X1X2…XL)/L=[H(X1)+H(X2/X1)+…+H(XL/X1X2…XL-1)]/L

≥[LH(XL/X1X2…XL-1)]/L=H(XL/XL-1)

2023/6/718(4)

HL(X)是L的单调递减函数证明:

LHL(X)=H(X1X2…XL)=H(X1X2…XL-1)+H(XL/X1X2…XL-1)=(L-1)HL-1(X)+H(XL/XL-1)≤(L-1)HL-1(X)+HL(X)

所以

HL(X)≤HL-1(X)同理,有

H∞(X)≤

…

≤HL+1(X)≤HL(X)≤HL-1(X)≤

…

≤H0(X)

2023/6/719(5)

H∞(X)=

HL(X)=H(XL/X1X2…XL-1)H∞(X)叫极限熵或极限信息量。证明：

HL+k(X)=[H(X1X2…XL-1)+H(XL/X1X2…XL-1)+…+H(XL+k/X1X2…XL+k-1)]≤[H(X1X2…XL-1)+H(XL/X1X2…XL-1)+…+H(XL/X1X2…XL-1)]=H(X1X2…XL-1)+H(XL/X1X2…XL-1)2023/6/720当固定L时，有

HL+k(X)≤H(XL/X1X2…XL-1)=H(XL/XL-1)又因为

H(XL/XL-1)≤HL(X)所以，当

时，HL(X)=HL+k(X)得：HL(X)=H(XL/X1X2…XL-1)推广可得结论：H∞(X)≤

…

≤H2(X)≤H1(X)≤H0(X)

式中，H0(X)为等概率无记忆信源单个符号的熵，

H1(X)为一般无记忆（不等概率）信源单个符号的熵H2(X)为两个符号组成的序列平均符号熵，依次类推。2023/6/721说明:(i)

如何计算极限熵是一个十分困难的问题.(ii)

在实际应用中常取有限L下的条件熵H(XL/XL-1)作为H∞(X)的近似值。(iii)

当平稳离散信源输出序列的相关性随着L的增加迅速减小时，其序列熵的增加量H(XL/XL-1)与相关性有关，相关性很弱，则H（XL/X1X2…XL-1）

H（XL／X2…XL-1）=H（XL-1/X1…XL-2），增加量不再变小，所以平均符号熵也几乎不再减小。

2023/6/722(6)

设信源发出的符号只与前面的m个符号有关，而与更前面出现的符号无关时,有

H∞(X)=H(Xm+1/X1X2……Xm)=Hm+1(X)证明:

信源发出的符号只与前面的m个符号有关，而与更前面出现的符号无关。用概率意义表达为

p(xt/xt-1,xt-2,xt-3,……,xt-m,……)=p(xt/xt-1,xt-2,……xt-m)

则根据（5）可得

=H(Xm+1/X1X2……Xm)=Hm+1(X)2023/6/723离散马氏链信源

平稳信源的m阶马尔可夫信源：信源发出的符号只与前面的m个符号有关，而与更前面出现的符号无关。用概率意义表达为:p(xt/xt-1,xt-2,xt-3,…,xt-m,…)=p(xt/xt-1,xt-2,…xt-m)

2023/6/724状态转移描述对于m阶马尔可夫信源

2023/6/725在某一时刻（m＋1），信源符号出现的概率，仅与前面已出现的m个符号有关，而与更前面出现的符号无关。可通过引人状态转移概率，从而转化为马尔可夫链，即令

2023/6/726如果信源符号表中的数目为q，则由前面出现的m个符号所组成的序列si共有Q＝qm种，将这些序列看作是状态集S={s1,s2,…,sQ}，则信源在某一时刻出现符号xj的概率就与信源此时所处的状态si有关，用条件概率表示为p(xj/si)，i=1,2,...,Q；j=l,2,…,q。当信源符号xj出现后，信源所处的状态将发生变化，并转人一个新的状态。用转移概率表示如下:pij(m,n)=p{Sn=sj/Sm=si}=p{sj/si}si,sjS

状态转移概率p(sj/si)由信源符号条件概率p(xj/si)确定。

2023/6/727为什么状态转移概率是一个条件概率?(1)状态转移概率Pij(m,n)表示已知在时刻m系统处于状态si，或Sm取值si的条件下，经(n-m)步后转移到状态sj的概率。(2)把Pij(m,n)理解为已知在时刻m系统处于状态i的条件下，在时刻n系统处于状态j的条件概率，故状态转移概率实际上是一个条件概率。2023/6/728两个基本转移概率性质:

2023/6/729什么叫基本转移概率(一步转移概率)?

当n=m+1时，把pij(m,m+1)记为pij(m)，m≥0，并称为基本转移概率(一步转移概率)。记2023/6/730齐次马尔可夫链转移概率具有时间推移不变性

转移概率性质：

转移概率可表示为：

2023/6/731k步转移概率表示为:

k步转移概率矩阵:

说明:

一步转移概率矩阵为:2023/6/732一步矩阵P中第i行元素对应于从某一个状态Si转移到所有状态Sj的转移概率，显然矩阵中的每一个元素都是非负的，并且每行之和均为1；一步矩阵P中第j列元素对应于从所有状态Si转移到同一个状态Sj的转移概率，列元素之和不一定为1。2023/6/733切普曼一柯尔莫郭洛夫方程

说明:

(1)k步转移概率P(k)ij与l（l＜k)步和（k-l）步转移概率之间关系;

(2)上式右侧是对第l步的所有可能取值求和，因而也就是k步转移概率。2023/6/734

(3)

当l=1时,矩阵表示:(p(k))=(p)(p(k-1))=(p)(p)(p(k-2))=…=(p)k

对于齐次马氏链来说，一步转移概率完全决定了k步转移概率。

2023/6/735如何确定无条件概率?令初始概率为p0i＝p(S0＝si)

2023/6/736如何确定平稳分布的Wj＝p(Sk=sj)?其中,Wi和Wj均为稳态分布概率.2023/6/737分析:

………2023/6/738………2023/6/7392023/6/740所以

有非零解W1,W2,…,WQ。2023/6/741如果再用就可解得各稳态分布概率Wj。若［］的秩是(n-1)，则解是唯一的。

2023/6/742马氏链的可约性马氏链可约性:

若对所有k，都有p(k)ij=0，就意味着一旦出现Si以后不可能到达Sj,也就是不能各态遍历，或者状态中应把Sj取消，这样就成为可约的了。马氏链不可约性:

对任意一对i和j，都存在至少一个k使p(k)ij＞0，这就是说从Si开始，总有可能到达Sj.2023/6/743香农线图

S1S3S21/21/21/21/21S4S51/21/2可约马氏链1/21/22023/6/744注意:

(1)S1,S2,S3是三种状态，箭头是指从一个状态转移到另一个状态，旁边的数字代表转移概率。这就是香农提出的马尔可夫状态图，也叫香农线图。

(2)由状态S3转移到S1的转移概率p(k)31=0，因为一进人状态S3就一直继续下去，而不会再转移到其他状态。P(k)41=0也是明显的，因S4和S1之间没有连接箭头，因此这种链就是可约的。2023/6/745马氏链周期性

非周期性，就是所有p(k)ii＞0的n中没有比1大的公因子。

S1S4S21/21/21/2周期性马氏链S31/21/21/21/21/21/22023/6/746注意:(1)上图周期为2.因为从S1出发再回到S1所需的步数必为2，4，6，…，.(2)p(n)ij矩阵2023/6/747当k为奇数时

当k为偶数时2023/6/748若起始状态为s1，则经奇数步后，Sk=sj的概率为经偶数步后

2023/6/749

达不到稳定状态!

虽然方程组是有解的为，所以，为使马氏链最后稳定，成为遍历的马氏链，还必须有不可约性和非周期性。2023/6/750例2-4-2+TXrYr101qqpp2023/6/751输入的码Xr(r=1,2,…)是相互独立的，取值0或1，且已知p(X=0)=p，p(X=1)=1-p=q，输出的码是Yr，显然有

Y1=X1，Y2＝X2Y1…

其中表示模2加，那么Yr就是一个马氏链，因Yr确定后，Yr+1分布只与Yr有关，与Yr-1、Yr-2…等无关，且知Yr序列的条件概率为2023/6/752p00=p(Y2=0/Y1=0)=p(X=0)=pp01=(Y2=1/Y1=0)=p(X=1)=qp10=p(Y2=0/Y1=1)=p(X=1)=qp11=p(Y2=1/Y1=1)=p(X=0)=p说明:(1)转移矩阵为，它与r无关，因而是齐次的。(2)由图容易验证该马氏链具有不可约性和非周期性2023/6/753看P26,例2-4-32023/6/754计算遍历的m阶马尔可夫信源提供的平均信息量对于齐次、遍历的马尔可夫链，其状态由唯一确定因此有：对上式两边同取对数，并对和取统计平均，然后取负，可以得到：左边2023/6/755右边即2023/6/756

是马尔可夫链的平稳分布，