信息论第四讲平稳随机序列信源

2.6平稳随机序列信源前面讨论的是单符号离散信源和单符号离散信道的信息特性。这一节开始讨论随机矢量或随机序列信源（多符号信源）的情况。通常这种信源是很复杂的，通常要进行简化分析。1/31/20231首先应当注意以下几点：①实际信源多为相关信源；而前面讨论的为无记忆信源（不相关）；②为了讨论相关信源，考虑一下多符号信源和扩展信源；③在相关信源中只讨论一种特例:马尔科夫信源；④为平稳随机序列，即统计特性不随时间改变；⑤随机序列为有限等长度，每个信源消息由N个符号序列组成。1/31/20232实际的多符号信源为：如果认为平稳序列，则为：其中每个信源状态为：为一个有限长度的多维随机序列，如果不考虑顺序i，可以记为：[X]=X1，X2，X3，…XN

1/31/20233平稳随机序列信源(多符号信源)[X]=X1，X2，X3，…XN离散无记忆信道[X]=X1，X2，X3，…XN[Y]=Y1，Y2，Y3，…YN1/31/202342.7.1离散无记忆信源的扩展信源A.假设条件这里对离散平稳随机序列信源做进一步假设。我们假设多符号离散平稳信源,[X]=X1，X2，…XN

或

中，符号的随机变量Xi都取值于同一个信源空间，

1/31/20235假设多符号离散平稳信源[X]=X1，X2，…Xi…XN中，各变量Xi(i=1,2,…N)之间统计独立，即P(X)=P(X1,X2,…Xi…XN)=P(X1)P(X2)P(X3)…P(XN)我们介绍的离散无记忆信源包括两层意思：①单符号离散无记忆信源，p(x1,x2,…xn)=p(x1)p(x2)…p(xn)②多符号离散无记忆信源，P(X1,X2,…XN)=P(X1)P(X2)P(X3)…P(XN)1/31/20236P(X1,X2,…XN)=P(X1)P(X2)P(X3)…P(XN)在这种假设前提下，可以把多符号离散平稳信源看作单符号离散平稳信源的N次扩展信源。通常N次扩展信源，记为XN。

1/31/20237B.N次扩展信源的信源空间因为信源XN的每一个消息[Xi]=[Xi1,Xi2,……XiN]均由信源X的符号集X:{x1,x2,…xn}中的N个符号组成，所以，XN

的某一个具体符号Xi可以表示为：[Xi]=(Xi1,Xi2,……XiN)Xij∈X:{x1,x2,…xn}，这个关系表明多符号信源中的每个符号取值于同一个单符号信源空间。X:{x1,x2,…xn}。1/31/20238扩展信源XN

就有nN

种不同的符号，可以表示为：[XN]:{[X1],[X2],…[Xi],…[XnN]};(i=1,2,nN)

例如：二元二次扩展信源，n=2,N=2,

[X]={X1,X2};

[XN]:{[X1],[X2],[X3],[X4]}X:{x1=0,x2=1}

[X1]=00;[X2]=01;[X3]=10;[X4]=11;1/31/20239所以离散平稳无记忆信源[X，P]的N次扩展信源的信源空间为：并且有：

表明该信源概率空间也是一个完备空间。1/31/202310C.N次扩展信源的熵根据熵函数的定义：

利用p(Xi)=p(xi1,xi2,…xiN)的关系和p(xi1,xi2,…xiN)=p(xi1)p(xi2)…p(xiN)[无记忆信源]，可以得到：

再考虑到无记忆信源，H(X1)=H(X2)=…=H(XN)可以得到：H(XN)=N.H(X)1/31/202311单符号离散平稳无记忆信源的N次扩展信源是一种最简单的多符号信源。如果单符号离散平稳无记忆信源[X]=[X1,X2,…XN]中的各变量Xi取值于不同的单符号离散无记忆信源[Xi,P]。

这种信源称为多符号离散无记忆信源

1/31/202312可以证明这种多符号离散无记忆信源的熵为：其中H(Xi)为单符号离散信源[Xi,P]的熵。[例2-12]:

离散无记忆信源的N次扩展信源单符号离散无记忆信源为：X:{x1,x2,x3};P(X):{1/4,1/2,1/4}信源X的N=2次扩展信源，[X]=[X1,X2]

1/31/202313[X2]:{X1,X2,X3,…..X9}因为：nN=9。这个2次扩展信源的9个消息符号分别为：X1=x1,x1X4=x2,x1X7=x3,x1X2=x1,x2X5=x2,x2X8=x3,x2X3=x1,x3X6=x2,x3X9=x3,x3其概率关系为：p(Xi)=p(xi,xj)=p(xi)p(xj)，（无记忆信源）。可以得到扩展信源空间：[X2,P]=X1X2X3X4X5X6X7X8X91/161/81/161/81/41/81/161/81/161/31/202314计算可知：H(X2)=3bit/2符号；并可计算原来的单符号离散无记忆信源的熵为：H(X)=1.5bit/符号。可见：H(X2)=2H(X)

1/31/2023152.7.2二维离散平稳有记忆信源的信源熵这里介绍最简单的离散平稳有记忆信源，即二维信源。[X]=X1，X2所谓有记忆信源就是一种相关信源，每个消息由两个符号组成，后一个符号与前一个符号有一个概率表明相关性，（这是一种近似处理方法，只考虑消息组内的相关性）。设离散平稳信源的信源空间为：

1/31/202316且有∑p(xi)=1，同时有一维条件概率为:P{X2=xj/X1=xi}=P{X2+T=xj/X1+T=xi}=p(xj/xi)

，表明为平稳序列。(i=1,2,…,n;j=1,2,…,n)[X]=X1，X2

的符号集合中的一个[Xi]=(xi1,xi2)

xi1,xi2∈X:{x1,x2,…xn};i1,i2=1,2,…,ni=1,2,3,…,n2且有：p(Xi)=p(xi1,xi2)=p(xi1)p(xi2/xi1)这时可得二维信源[X]=X1,X2的信源空间：1/31/202317即信源空间为完备空间。可得二维信源的一个消息（两个符号）所提供的平均信息量为：

其中：H(X1)表示信源发出第一个符号所能提供的平均信息量，H(X2/X1)表示在第一个符号已知的前提下，第二个符号所提供的平均信息量。1/31/202318二维离散平稳有记忆信源每发一个消息所能提供的平均信息量是一种联合熵，这种信源的熵等于第一个随机变量的熵加上第一变量已知的条件下第二个变量的条件熵。其中：

1/31/202319当随机变量X1X2相互独立时，有H(X)=H(X1,X2)=H(X1)+H(X2)。可以证明：二维离散平稳有记忆信源的熵满足：H(X1,X2)≤H(X1)+H(X2)，（作业）

X2,X1X1X2二维离散平稳有记忆信源的理解1/31/202320[例2-15]设某二维离散信源的原始信源空间X={x1,x2,x3};P(X)={1/4,1/4,1/2},

一维条件概率P{X2=xi/X1=xj}为：p(x1/x1)=1/2;p(x2/x1)=1/2;p(x3/x1)=0;p(x1/x2)=1/8;p(x2/x2)=3/4;p(x3/x2)=1/8;p(x1/x3)=0;p(x2/x3)=1/4;p(x3/x3)=3/4;1/31/202321原始信源的熵为：H(X)=1.5bit/符号条件熵：H(X2/X1)=1.4bit/符号可见：H(X2/X1)<H(X)二维信源的熵：H(X1,X2)=H(X1)+H(X2/X1)=2.9bit/消息每个信源符号提供的平均信息量为：H2(X1,X2)=H(X1,X2)/2=1.45bit/符号。1/31/202322注意：二维离散平稳有记忆信源，或者N维离散平稳有记忆信源只是实际有记忆信源的一种简化和近似。对于实际信源来说，是一种无限长的序列，符号间相关性可以延伸到无穷。因此，离散平稳有记忆信源输出一个符号提供的平均信息量为：这个熵称为离散平稳有记忆信源的极限熵。

1/31/2023232-7-3马尔柯夫信源(MarkovSource)为了顺利地讨论马尔柯夫信源，首先介绍一下马尔柯夫链的概念。1/31/202324（1）马尔柯夫链

(Markovchain)①马尔柯夫链定义：一个随机序列{X(t),t=1,2,3,…}取值于正整数空间I={0,1,2,……}，或者为I的子集，如果有：P{X(1)=x1,X(2)=x2,……,X(t)=xt}>0;而且有：P{X(t+1)=xt+1/X(1)=x1,X(2)=x2,……,X(t)=xt}=P{X(t+1)=xt+1/X(t)=xt}xi∈I={0,1,2,……};i=1,2,…则称为序列{X(t)}为马尔柯夫链。

1/31/202325这种特性成为马尔柯夫性，也叫无后致性。②马尔柯夫链的含义：可以这样理解：序列{X(t)}的“将来”只与“现在”有关而与“过去”无关。③马尔柯夫链的状态：马尔柯夫链序列{X(t)}中的某一个符号X(ti)的数值一定为I中的某一个元素i（或j），这时，称i(或j)为随机序列的一个状态Si。1/31/202326④马尔柯夫链的一步转移概率马尔柯夫链的统计特性用条件概率（状态转移概率）来描述。在时刻t和t+1有:P{X(t+1)=j/X(t)=i}=pij(1)(t)=pij(t)

这称为马氏链的一步转移概率。为马尔柯夫链从状态i变为状态j的条件概率。它满足：pij(1)(t)≥0ij∈I1/31/202327⑤马尔柯夫链的K步转移概率：其k步转移概率为：为马尔柯夫链从状态i经过k步（k个单位时间）后变为状态j的条件概率。P{X(t+k)=j/X(t)=i}=pij(k)

(t)

它满足：pij

(k)(t)≥0ij∈I1/31/202328⑥马尔柯夫链的转移概率关系：这里不加证明的给出一个概率关系。马尔柯夫链的n=k+l步转移概率与1步转移概率的基本关系为：其中s也是马尔柯夫链的一个状态。其含义为：马尔柯夫链在时刻t从状态i经过n=k+l步，转移到状态j的n步转移概率，等于这个马尔柯夫链在时刻t从状态i经过k步到达状态s的k步转移概率，乘上在(t+k)时刻从中间状态s经l步到达状态j的l步转移概率，然后再将这个乘积对所有可能的中间状态求和。1/31/202329⑦有限（可列）马尔柯夫链的转移概率矩阵：如果I为整数有限集合（1,2,…r），则相应的马尔柯夫链为可列马尔柯夫链。对于这种马尔柯夫链，其t时刻的n步转移概率共有r2个概率组成。用矩阵表示为：对于马尔柯夫链，我们不加证明地给出如下结论：马尔柯夫链的n步转移概率，可以有起始时刻的概率和中间所有各时刻的所有一步转移概率来完整描述。即[P(n)(t)]=[P(t)][P(t+1)][P(t+2)]……[P(t+n-1)]1/31/202330⑧平稳马尔柯夫链的性质：如果马尔柯夫链是平稳的，与t无关，则有：[P(n)(t)]=[P(n)]=[P][P][P]……[P]=[P]n我们讨论的马尔柯夫链只是这种最简单的情况。这种平稳马氏链称为齐次马氏链。由于这种齐次马尔柯夫链的转移概率与时间无关，因此去掉其时间变量t，其中的一步转移概率为pij(1)=pij，k步转移概率为pij(k)，n步转移概率为pij(n)。一步转移概率矩阵为：其n步转移概率可以有[P]得到：[P(n)]=[P][P]……[P]=[P]n；（齐次马氏链）1/31/202331（2）各态历经定理①各态历经定理：若对一个有限(I为有限正数)齐次马氏链，存在一个正整数n0>1，对于一切i，j=1,2,…,r都有pij(n0)>0（矩阵[P(n0)]中的所有元素大于0）。则对于每个j=1,2,…..,r都存在不依赖i的极限pj（每个状态都以一定的概率出现，而无论其原始状态为何）。则称这个马氏链是各态历经的。1/31/202332其中的极限概率pj={p1,p2,…pr}是方程组

满足条件的唯一解。1/31/202333②各态历经定理的含义：如果一个有限的、齐次的马尔柯夫链满足各态历经定理，则说明经过一定时间后这个马尔柯夫链所有状态均有一个稳定的出现概率。而且这个概率的值与其起始状态无关。各态历经就是各个状态相通，不会有一个或几个状态到一定步骤后总也不出现。定理一方面说明了极限概率的存在性，无限步转移概率就等于极限概率。另一方面给出了极限概率的求法，已知一步转移概率就可以求出极限概率，条件是必须满足定理，并利用边界条件。1/31/202334③状态极限概率的求法：根据各态历经定理，满足这个定理的马尔柯夫链的极限概率就是各状态的稳态概率，注意它不是转移概率，不是条件概率，在信源中它相当于先验概率。pj=p{X(t)=j}=P{X=j}。由各态历经定理给出的方法，如果用矩阵表示极限概率和一步转移概率：状态极限概率：[P]=[Pi]=[Pj]=[p1,p2,p3,……pr]一步转移概率：

则有：[Pj]T=[P(1)]T.[Pj]T1/31/202335

[例2-16]:

设一个马氏链有三个状态，状态取值于X:{0,1,2},其一步转移概率为：其中p>0，q>0。这时pij(1)>0不满足，不能判断是否具有各态历经性，看二步转移矩阵。1/31/202336这时pij(2)>0满足，可以判断具有各态历经性，其状态极限概率（稳态概率）可以得到由一步状态转移矩阵求极限概率的基本关系为：[Pj]T=[P(1)]T.[Pj]T。

p0=qp0+qp1p1=pp0+qp2p2=pp1+pp2;p0+p1+p2=1;pj>0由这四个方程求解。可以得到：p0=？p1=？p2=？1/31/202337（3）状态转移图有限齐次马氏链除了用转移矩阵描述外还可以用状态转移图来表示。例如上面的例题对应的状态图为：①齐次马氏链为一个不可约闭集，即对马氏链中的任意两个状态，总可以从一个状态经过有限步数转移到另一个状态；②齐次马氏链具有非周期性，从一个状态到另一个状态的步数不能具有周期性；1/31/202338（4）马尔柯夫信源①m阶马尔可夫信源定义：马尔柯夫信源是一种特殊的、比较接近实际的离散平稳有记忆信源。如果一个离散平稳有记忆信源：[X]=……X1，X2，…,Xm,Xm+1,Xm+2,……中，任一时刻(m+1)的随机变量Xm+1只依赖于它前面的m个随机变量，与更前面的变量无关，称为记忆长度为m的离散平稳有记忆信源，也称为m阶马尔柯夫信源。1/31/202339②m阶马尔柯夫信源的信源状态：这时把m阶马尔柯夫信源[X(i)]=(X1,X2,…Xm)某一个具体取值(可以理解为信源连续m个输出符号)表示为X(i)=Si=(xk1,xk2,……,xkm)

称为一个状态。xk1,xk2,……,xkm∈X:{x1,x2,…,xr}为原始信源状态空间;k1,k2,…km=1,2,…r;i=1,2,….rm同时把信源下一个符号输出后的信源状态[X(i+1)]=[X(j)]=Sj=(X2,X3,…Xm+1)的某一取值称为另一个状态，Si为Sj的前一状态。m

阶马尔柯夫信源的状态空间为S:{S1,S2,…,Srm}，

1/31/202340③m阶马尔柯夫信源的信源状态转移概率：马尔柯夫信源的一个状态由m个符号组成，当信源再输出一个符号时，信源变为另一个状态，所以从Si到Sj的一步转移概率为：p(Sj/Si)=p(xkm+1/xk1xk2…xkm)为一个条件概率；其中：(k1,k2,…km=1,2,…,r;km+1=1,2,…,r)(i,j=1,2,….rm)也可以简单表示为：1/31/202341④m阶马尔柯夫信源空间：X:{x1x2…xr};P:{p(xkm+1/xk1xk2…xkm)…}且有：或者用状态空间表示：S:{S1,S2,…,Srm}，1/31/202342⑤m阶马尔柯夫信源的极限熵：根据m阶马尔柯夫信源的定义，及平稳性，有：p(xkN/xk1xk2…xkmxkm+1,…xkN-1)=p(xkN/x

kN-mx

kN-m+1,…x

kN-1)=p(xkm+1/xk1xk2…..xkm),

1/31/202343=H(Xm+1/X1X2…Xm)这样，可以得到m阶马尔柯夫信源的极限熵：1/31/202344⑥用状态转移概率表示极限熵：p(Sj/Si)=p(xk/Si)=p(xkm+1/xk1xk2…xkm)或p(xk+1/Si)这时极限熵可以表示为：1/31/202345从以上分析可以看到，m阶马尔柯夫信源的分析是实际信源的一种简化，把一个无限的问题转化为有限量的计算问题。(即：对于信源状态来说是一个马尔可夫链)已知m阶马尔柯夫信源的状态一步转移概率后，求极限熵的问题就在于得到极限概率p(Si)，(i=1,2,…nm)，而p(Si)就是马尔柯夫信源在稳定状态时的各状态的极限概率。所以，首先要判断信源是否具有各态历经性，如果有，则可以由一步转移概率求出极限概率。1/31/202346[例2-17]:

一个二进制二阶(m=2)马尔柯夫信源的原始信源为X：{0，1}，即r=2,m=2，这时的状态空间为：S:{S1=00,S2=01,S3=10,S4=11}，共有rm=22=4个不同的状态。已知其一步转移概率为：

0/0000p(0/00)p(0/S1)p(S1/S1)=0.81/0001p(1/00)p(1/S1)p(S2/S1)=0.20/0110p(0/01)p(0/S2)p(S3/S2)=0.51/0111p(1/01)p(1/S2)p(S4/S2)=0.50/1000p(0/10)p(0/S3)p(S1/S3)=0.51/1001p(1