《信息论与编码-第6讲-第2章信源及信息度量.ppt》由会员分享,可在线阅读,更多相关《信息论与编码-第6讲-第2章信源及信息度量.ppt(37页珍藏版)》请在三一办公上搜索。
1、2.2 多符号离散信源,2.2.1 多符号离散信源2.2.2 离散平稳无记忆信源2.2.3 离散平稳有记忆信源2.2.4 马尔可夫信源2.2.5 信源冗余度及信息变差,2.2.1 多符号离散信源,(1)多符号离散信源(2)随机矢量/随机变量序列(3)多符号离散平稳信源,(1)多符号离散信源,实际的信源输出的消息是时间或空间上离散的一系列随机变量。这类信源每次输出的不是一个单个的符号,而是一个符号序列。在信源输出的序列中,每一位出现哪个符号都是随机的,而且一般前后符号的出现是有统计依赖关系的。这种信源称为多符号离散信源。,(2)随机矢量/随机变量序列,多符号离散信源可用随机矢量/随机变量序列描述
2、,即 X=X1,X2,X3,信源在不同时刻的随机变量Xi和Xi+r的概率分布P(Xi)和P(Xi+r)一般来说是不相同的,即随机变量的统计特性随着时间的推移而有所变化。,(3)多符号离散平稳信源,为了便于研究,假定随机矢量X中随机变量的各维联合概率分布均不随时间的推移变化。或者说,信源所发符号序列的概率分布与时间的起点无关,这种信源称为多符号离散平稳信源。,2.2.2 离散平稳无记忆信源,(1)离散无记忆信源(2)离散平稳无记忆信源的熵(3)举例,(1)离散无记忆信源,基本概念 序列的成组传送 离散无记忆信源的数学模型,基本概念,离散无记忆信源:为了方便,假定随机变量序列的长度是有限的,如果信
3、源输出的消息序列中符号之间是无相互依赖关系/统计独立,则称这类信源为离散平稳无记忆信源/离散平稳无记忆信源的扩展。,序列的成组传送,把信源输出的序列看成是一组一组发出的。例1:电报系统中,可以认为每二个二进制数字组成一组。这样信源输出的是由二个二进制数字组成的一组组符号。这时可以将它们等效看成一个新的信源,它由四个符号00,01,10,11组成,把该信源称为二进制无记忆信源的二次扩展。例2:如果把每三个二进制数字组成一组,这样长度为3的二进制序列就有8种不同的序列,可等效成一个具有8个符号的信源,把它称为二进制无记忆信源的三次扩展信源。二进制无记忆信源的N次扩展:把每N个二进制数字组成一组,则
4、信源等效成一个具有2N个符号的新信源,把它称为二进制无记忆信源的N次扩展信源。,离散无记忆信源的数学模型,离散无记忆信源X=x1,x2,xn,对它的输出消息序列,可以用一组组长度为N的序列来表示它。这时它就等效成了一个新信源;新信源输出的符号是N长的消息序列,用N维离散随机矢量来描述。ai=(xi1,xi2,xiN)i=1,2,n 每个分量xik(k=1,2,N)都是随机变量,都取值于同一信源X,并且分量之间统计独立。由随机矢量X组成的新信源称为离散无记忆信源X的N次扩展信源。用N重概率空间来描述它。,N次扩展信源的数学模型单符号离散信源的数学模型为信源X的N次扩展信源用XN表示,它是具有nN
5、个符号的离散信源,其数学模型为其中q=nN,每个符号ai是对应于某一个由N个xi组成的序列ai的概率p(ai)是对应的N个xi组成的序列的概率因为信源是无记忆的,所以消息序列,(2)离散平稳无记忆信源的熵,因为是无记忆的/统计独立 若ai=(xi1,xi2,xi3,xiN)则p(ai)=p(xi1)p(xi2)p(xiN)其中i1,i2,iN1,2,n 根据信息熵的定义,N次扩展信源的熵可以证明:离散无记忆信源X的N次扩展信源的熵等于离散信源X的熵的N倍,即H(X)=H(XN)=NH(X),证明:H(X)=H(XN)=NH(X),设 ai是XN概率空间中的一个符号,对应于由N个xi组成的序列a
6、i=(xi1,xi2,xiN)而 p(ai)=p(xi1)p(xi2)p(xiN)i1,i2,iN1,2,nN次扩展信源的熵求和号是对信源XN中所有nN个符号求和,所以求和号共有nN个。这种求和号可以等效于N个求和号,其中的每一个又是对X中的n个符号求和,所以,因此上式共有N项,考察其中第一项因为所以 H(X)=H(XN)=H(X)+H(X)+H(X)=NH(X),(3)举 例,有一离散无记忆信源 求这个离散无记忆信源的二次扩展信源,扩展信源的每个符号是信源X的输出长度为2的符号序列。因为信源X共有3个不同符号,所以由信源X中每两个符号组成的不同排列共有32=9种,得二次扩展信源共有9个不同的
7、符号。因为信源X是无记忆的,则有,可以算得H(X)=1.5 比特/符号(此处的符号是指X信源的输出符号xi)H(X)=H(X2)=3 比特/符号(此处的符号是指扩展信源的输出符号ai,它是由二个xi符号组成)所以 H(X)=2H(X)对上述结论的解释:因为扩展信源XN的每一个输出符号ai是由N个xi所组成的序列,并且序列中前后符号是统计独立的。现已知每个信源符号xi含有的平均信息量为H(X),那么,N个xi组成的无记忆序列平均含有的信息量就为NH(X)(根据熵的可加性)。因此信源XN每个输出符号含有的平均信息量为NH(X)。,2.2.3 离散平稳有记忆信源,(1)离散平稳有记忆信源的数学模型(
8、2)离散平稳有记忆信源的信源熵(3)离散平稳有记忆信源的极限熵,(1)离散平稳信源的数学模型,一维平稳信源 二维平稳信源 离散平稳信源,一维平稳信源,对于随机矢量X=X1X2XN,若任意两个不同时刻i和j(大于1的任意整数),信源发出消息的概率分布完全相同,即P(Xi=x1)=P(Xj=x1)=p(x1)P(Xi=x2)=P(Xj=x2)=p(x2)P(Xi=xn)=P(Xj=xn)=p(xn)一维平稳信源无论在什么时刻均以p(x1),p(x2),p(xn)分布发出符号。,二维平稳信源,除上述条件外,如果联合概率分布P(XiXi+1)也与时间起点无关,即P(XiXi+1)=P(XjXj+1)(
9、i,j为任意整数,且ij)这种信源在任何时刻发出两个符号的概率完全相同。,离散平稳信源,如果各维联合概率分布均与时间起点无关,即对两个不同的时刻i和j,有 P(Xi)=P(Xj)P(XiXi+1)=P(XjXj+1)P(XiXi+1Xi+2)=P(XjXj+1Xj+2)P(XiXi+1Xi+N)=P(XjXj+1Xj+N)这种各维联合概率均与时间起点无关的完全平稳信源称为离散平稳信源。,(2)离散平稳有记忆信源的信源熵,二维平稳信源的信源熵 离散平稳信源的信源熵,二维平稳信源的信源熵,二维平稳信源的数学模型二维平稳信源的信源熵离散无记忆信源是离散平稳信源的特例举例,二维平稳信源的数学模型,最简
10、单的离散平稳信源:二维平稳信源 X=X1X2每两个符号看做一组,每组代表信源X=X1X2的一个消息;每组中的后一个符号和前一个符号有统计关联,这种概率性的关系与时间起点无关;假定符号序列的组与组之间是统计独立的。这与实际情况不符,由此得到的信源熵仅仅是近似值。但是当每组中符号的个数很多时,组与组之间关联性比较强的只是前一组末尾的一些符号和后一组开头的一些符号,随着每组序列长度的增加,这种差距越来越小。,设X1,X2 x1,x2,xn,则矢量Xx1x1,x1xn,x2x1,x2xn,xnx1,xnxn 令X的数学模型,二维平稳信源的信源熵,根据信源熵的定义,结论:两个有相互依赖关系的随机变量X1
11、和X2所组成的随机矢量X=X1X2的联合熵H(X),等于第一个随机变量的熵H(X1)与第一个随机变量X1已知的前提下,第二个随机变量X2的条件熵H(X2/X1)之和。,离散无记忆信源是离散平稳信源的特例,当随机变量X1和X2相互统计独立时,则因此,结论:随机变量X1和X2统计独立时,二维离散平稳无记忆信源X=X1X2的熵H(X)等于X1的熵H(X1)和X2的熵H(X2)之和。当X1和X2取值于同一集合时,H(X1)=H(X2)=H(X),H(X)=H(X2)=2H(X),与离散无记忆信源二次扩展信源的情况相同。可以把离散无记忆信源的二次扩展信源看成是二维离散平稳信源的特例;反过来又可以把二维离
12、散平稳信源看成是离散无记忆信源的二次扩展信源的推广。前面已证明H(X2/X1)H(X2),所以H(X2X1)H(X1)+H(X2)。即二维离散平稳有记忆信源的熵小于等于二维平稳无记忆信源的熵。,举 例,例2.2.2 设二维离散信源X=X1X2的原始信源X的信源模型为X=X1X2中前后两个符号的条件概率列于上表。原始信号X的熵由上表的条件概率确定条件熵,条件熵H(X2/X1)比信源熵/无条件熵H(X)减少了0.672比特/符号,这是由于符号之间的依赖性造成的;信源平均每发一个消息提供的信息量,即联合熵H(X1X2)=H(X1)+H(X2/X1)=1.542+0.870=2.412(比特/符号)每
13、一个信源符号提供的平均信息量H2(X)=(1/2)H(X)=(1/2)H(X1X2)=1.206(比特/符号)H2(X)小于信源提供的平均信息量H(X),这同样是由于符号之间的统计相关性所引起。,离散平稳信源的信源熵,将二维离散平稳有记忆信源推广到N维的情况H(X)=H(X1)+H(X2/X1)+H(X3/X1X2)+H(XN/X1X2XN-1)结论:多符号离散平稳有记忆信源X的熵H(X)是X中起始时刻随机变量X1的熵与各阶条件熵之和。由于信源是平稳的,这个和值与起始时刻无关。,(3)离散平稳有记忆信源的极限熵,条件熵的非递增性 极限熵 结论,条件熵的非递增性,条件熵H(XN/X1X2XN-1
14、)随N的增加是非递增的,即H(XN/X1X2XN-1)H(XN/X1X2XN-2)证明 根据前面已证明的 H(X2/X1)H(X2),同理可证 H(X3/X1X2)H(X3/X2),由于信源是平稳的,所以 H(X3/X2)=H(X2/X1),故得 H(X3/X1X2)H(X2/X1)H(X1)对于平稳信源递推 H(XN/X1X2XN-1)H(XN-1/X1X2XN-2)H(XN-2/X1X2XN-3)H(X3/X1X2)H(X2/X1)H(X1),极限熵,H(X)/矢量熵=H(X1X2XN-1XN)/联合熵表示平均发一个消息(由N个符号组成)提供的信息量。平均符号熵:信源平均每发一个符号提供的
15、信息量为极限熵:当N时,平均符号熵取极限值称之为极限熵或极限信息量。用H表示,即,极限熵的存在性:当离散有记忆信源是平稳信源时,从数学上可以证明,极限熵是存在的,且等于关联长度N时,条件熵H(XN/X1X2XN-1)的极限值,即,结 论,极限熵的含义:代表了一般离散平稳有记忆信源平均每发一个符号提供的信息量。多符号离散平稳信源实际上就是原始信源在不断地发出符号,符号之间的统计关联关系也并不仅限于长度N之内,而是伸向无穷远。所以要研究实际信源,必须求出极限熵H,才能确切地表达多符号离散平稳有记忆信源平均每发一个符号提供的信息量。极限熵的计算:必须测定信源的无穷阶联合概率和条件概率分布,这是相当困难的。有时为了简化分析,往往用条件熵或平均符号熵作为极限熵的近似值。在有些情况下,即使N值并不大,这些熵值也很接近H,例如马尔可夫信源。,