讲义21 - 第一章引论.doc

信息论研究生课程讲义第二章 离散信源的熵2-1离散信源的数学模型2-1-1 单符号离散信源的数学模型单符号离散信源是最简单的一种离散信源，离散信源特性：根据Shannon信息论的观点，信源要含有一定的信息，必须具有随机性，即有不确定性，可以用其概率来表示。离散信源空间：信源的符号（状态）随机地取值于一个离散集合X=（x1,x2,xn）中，一个离散信源可以用一个概率空间P=(p1,p2,pn)表示。 这种表示称为离散无记忆信源的信源空间。信源空间必为一个完备空间，即其概率和为1。信源数学模型描述的条件：用信源空间来表示信源的条件是信源符号（状态）的先验概率是可知的，这是Shannon信息论的一个基本假说。2-1-2信源符号不确定性的度量不确定性：只有不确定性存在，才有信息存在，获得消息后消除了不确定性才得到信息。在一个通信系统中，收信者所获取的信息量，在数量上等于通信前后对信源的不确定性的减少量。不确定性的度量（不确定度）：猜测摸某一随机事件是否会发生的难易程度。例2-1：从一个袋子里取出不同颜色小球的不确定性。a. 99个红球，1个白球，b. 50个红球，50个白球，c. 25个红球，25个白球，25个黑球，25个黄球，可见，a的不确定性最小，b的不确定性为最大。I(x1)=I(红球)，I(x2)=I(白球)，I(x3)=I(黑球)，I(x4)=I(黄球)，自信息量：在假设信道没有干扰（无噪声）的情况下，信源发出信源符号xi，接收者就会收到xi，这是接收者收到的信息量就等于信源符号xi本身含有的信息量（不确定度），称为信源符号xi的自信息量，记为I(xi)。Hartly公式：由上例可以看出： 信源不确定度的大小与信源的消息符号数有关；符号数越多，不确定度越大； 信源不确定度的大小与信源的消息符号概率有关；概率越小，不确定度越大；即，如果p(x1)p(x2)，则I(x1)I(x2) 信源不确定度应具有可加性； 同时应当满足：如果p(xi)=0，则I(xi)=，如果p(xi)=1，则I(xi)=0。因此为了满足以上四个条件，应把信源不确定度写为对数形式： 可以看出信息度量用对数表示的合理性，通常取K=1。2-1-3信源符号的自信息量自信息量的定义：收信者收到一个消息状态得到的信息量，等于收到后对这个消息状态不确定度的减少量。即 I（信息量）=不确定度的减少量。无噪声信道下的自信息量：在假设信道没有干扰（无噪声）的情况下，信源发出信源状态xi，接收者就会收到xi，这是接收者收到的信息量就等于信源状态xi本身含有的信息量（不确定度），称为信源状态xi的自信息量，记为I(xi)。这时，接收到xi所获得的信息量等于信源输出发出的信息量。有噪声信道下的互信息量：在有噪声信道下，信源发出的状态为xi，接收者收到的状态为yj，接收者收到yj后，从yj中获取到关于xi的信息量，就是信源发出xi后，接收者收到的信息量，称为互信息量。记为I(xi,yj)。（接收到yj后，信源实际发出xi时接收者所获得的信息量。）这时，由于噪声的干扰，接收者收到的信息量小于信源发出的信息量。NYXChannel H(xi)为信源各状态具有的不确定性； H(xi/yj)为接收到一个yj后，信源各状态仍存在的不确定度；收到yj后，信源状态xi的不确定性应有所变化。例2-2：求离散信源的自信息量。一次掷两个色子，作为一个离散信源，求下列事件产生后提供的信息两。a.仅有一个为3；b.至少有一个为4；c.两个之和为偶数；解：一个色子有6个符号，两个色子的总数（信源符号数）为36。a. 事件样本数=52=10（另外一个不能为3）b. 事件样本数=52+1=11（加上一个双4）c. 事件样本数=63=18（第一个的6个符号分别与第二个的3个符号构成事件）则：p(a)=10/36=5/18; p(b)=11/36; p(c)=18/36=1/2;I(a)=log(18/5)=1.848 (bit); I(b)=log(36/11)=1.7105 (bit); I(c)=log2=1 (bit);2-2单符号离散信源的熵2-2-1信源熵的概念 信源熵的定义：信源一个消息状态所具有的平均信息量。 离散无记忆信源的熵（独立熵）： 信源熵的推导：得到第j个消息获得的信息量为Ij=log(1/p(xj);假设发出n个消息，其中有n.p(xj)个xj，其信息量为：In=n.p(xj).log(1/p(xj)发出后总的信息量则为平均信息量为：H(X)表示信源发出任何一个消息状态所携带的平均信息量，也等于在无噪声条件下，接收者收到一个消息状态所获得的平均信息量。熵的物理意义： 熵的本意为热力学中表示分子状态的紊乱程度； 信息论中熵表示信源中消息状态的不确定度； 信源熵与信息量有不同的意义；(1) H(X)表示信源X每一个状态所能提供的平均信息量；(2) H(X)表示信源X在没有发出符号以前，接收者对信源的平均不确定度；(3) H(X)表示随机变量X的随机性；例2-3：求一个独立信源的熵二元信源X:0,1，其概率空间p(0),p(1)= p, 1-p ，H(X)= - p(0)logp(0) - p(1) logp(1)=-plogp-(1-p)log(1-p)p(0)=0, p(1)=1, H(X)=0p(0)=1, p(1)=0, H(X)=0p(0)=p(1)=1/2, H(X)=1 bit给出图H(x)p011/2 在解决这类问题时，主要是确定信源空间，信源空间确定后，就可以得到自信息量和信源熵。 确定信源空间时主要是概率论的问题，例如信源符号状态数（事件样本总数）；符号产生概率。2-2-2熵函数的性质熵函数可以表示为：性质1：非负性；H(X)0由于0pi1,所以logpi0，-logpi0，则总有H(X)0。性质2：对称性；根据加法交换律可以证明，当变量交换顺序时熵函数的值不变。 信源的熵只与概率空间的总体结构有关，而与个概率分量对应的状态顺序无关； 同时反映了Shannon信息熵的局限性，不能描述主观意义。性质3：确定性；当信源X的信源空间X，P中。任一个概率分量等于1，根据完备空间特性，其它概率分量必为0，这时信源为一个确知信源，其熵为0。 如果一个信源的输出符号几乎必然为某一状态，那么这个信源没有不确定性，信源输出符号后不提供任何信息量。性质4：连续性；当信源的某一概率分量发生微小波动，而要求符号状态数保持不变时，其它分量必然发生相应的微小变化，形成另一个信源X，其信源空间为：X:x1x2xixnP:p1+1p2+2pI-ipn+n其中信源X的熵为：当微小波动趋于0时，有这说明熵函数为一个连续函数。性质5：扩展性当信源的某一概率分量发生微小波动，而要求符号状态数保持不变时，其它分量必然发生相应的微小变化，形成另一个信源X，其信源空间为：X:x1x2xixnxn+1xn+kP:p1p2pi-ipnpn+1pn+k其中:信源X的熵为：当微小波动趋于0时，有 这说明信源空间中增加某些概率很小的符号，虽然当发出这些符号时，提供很大的信息量，但由于其概率接近于0，在信源熵中占极小的比重，使信源熵保持不变。2-2-3离散信源的最大熵（一） 一般离散信源的最大熵在数学上可以证明熵函数存在最大值，离散信源的熵函数有n个变量，有一个约束条件，作一个辅助函数： 其中：为待定系数，由=0，可得n个方程：即：-(1+logpi)+=01+logpi=; 取以e为底pi=e-1再由约束方程可得：ne(-1)=1; e(-1)=1/n; 可知：pi=1/n可知：当p1=p2=pn=1/n时,Hmax(X)=H(1/n, 1/n,1/n)=logn这个结果称为离散信源得最大熵定理。它表明，在所有符号数相同，而概率分布不同的离散信源中，当先验概率相等时得到的熵最大。最大熵的值取决于符号状态数，状态数越多，熵越大。（二） 均值受限的离散信源的最大熵在增加一个约束条件的情况下，求离散信源的最大熵，做辅助函数：这时可求得离散信源得最大熵为（作为作业）2-3共熵与条件熵2-3-1联合信源的共熵联合信源的概率空间：联合信源可以认为有两个信源X，Y组成：X:x1, x2, xi xnP(X):p(x1),p(x2),p(xi),p(xn)Y:y1, y2, yi, ynP(Y):p(y1),p(y2),p(yi),p(yn)用这两个信源组成一个联合信源，其联合概率空间为：(X,Y):x1y1, x1ym, x2y1, x2ym, xny1,xnymP(X,Y):P(x1,y1)p(x1,ym),p(x2,y1)p(x2,ym),p(xny1)p(xn,ym)其中状态（xi,yj）为联合信源输出的一个状态。联合信源共熵的表达式：联合信源的共熵：联合信源输出一个组合消息状态(xi,yj)所发出的平均信息量。联合信源的独立熵：将联合信源看成两个独立的信源（当然实际上可能并不是相互独立的）时，各自信源的熵即为独立熵。概率的基本关系：当X，Y独立时，有p(x,y)=p(x)p(y)。 2-3-2联合信源的条件熵一个联合信源（X，Y）的条件熵定义为：信源Y（或X）输出任一状态后，信源X（或Y）输出任一状态所发出的平均信息量。2-4 离散信道的平均交互信息量以上讨论的信源符号状态的自信息量和信源的熵是描述信源的特性，但是对于一个通信系统来说，最主要的问题是接收者收到信息的能力。在信源与接收者之间是由信道连接的，这里要开始讨论信道的问题。2-4-1离散信道的数学模型设离散信道的输入为一个随机变量X，相应的输出的随机变量为Y，如图所示：规定一个离散信道应有三个参数： 输入符号集：X=x1,x2,.xn 输出符号集：Y=y1,y2,.ym 信道转移概率：P(Y/X)=p(y1/x1),p(y2/x1),p(ym/x1),p(y1/xn)p(ym/xn)P(Y/X) X Y离散信道主要有三种描述方法。(1) 概率空间描述X=x1,x2,xnP(Y/X)=p(yj/xi) (i=1,2,n; j=1,2,m)Y=y1,y2,ym0p(yj/xi)1(2) 转移矩阵描述矩阵P称为转移矩阵或信道矩阵；表示为：P=y1y2ymx1p(y1/x1)p(y2/x1)p(ym/x1)x2p(y1/x2)p(y2/x2)p(ym/x2)xnp(y1/xn)p(y2/xn)p(ym/xn)P矩阵为一个nm矩阵，其每行元素之和等于1。(3) 图示法描述 p(y1/x1) x1 y1 p(y2/x1) x2 y2 p(ym/x1) xn ym以上是离散信道数学模型的三种表示方法，可以根据具体问题选用。例2-6 二元对称信道（BSC） X=0,1; Y=0,1; p(0/0)=p(1/1)=1-p; p(0/1)=p(1/0)=p;P=0101-pp1p1-p 0 1-p 0 p p 1 1-p 1例2-7 二元删除信道X=0,1; Y=0,?,1P=0?101-pp010p1-p 0 1-p 0 p p 1 1-p 12-4-2 X与Y的关系这里可以把X看作信道的输入，Y看作信道的输出；也可以把XY看作一个联合信源的输出。假设X的信源空间为：X:x1, x2, xi xnP(X):p(x1),p(x2), p(xI),p(xn)信道转移矩阵为P；P=y1y2ymx1p(y1/x1)p(y2/x1)p(ym/x1)x2p(y1/x2)p(y2/x2)p(ym/x2)xnp(y1/xn)p(y2/xn)p(ym/xn)(1) 联合概率 P(X=xi,Y=yj)=p(xi,yj) p(xi,yj)=p(xi)p(yj/xi)=p(yj)p(xi/yj) (i=1,2,n) (j=1,2,m)(2) yj的概率P(Y=yj)=p(yj) p(y1),p(y2),p(ym)=p(x1),p(x2),p(xn)P(3) 后验概率P(X=xi/Y=yj)=p(xi/yj)(i=1,2,n) (j=1,2,m)并且有：这表明：当信道输出一个符号yj时，一定是有一个输入符号xi输入信道。对于给定的信道P，如果已知先验概率p(xi)，则可以求出p(xi,yj)、P(xi/yj)和p(yj)。2-4-3 交互信息量(1) 定义：信息传输的根本问题是，对于给定的信道计算收到一个yj后，从yj中获取关于xi的信息量。这个信息量称为互信息量，记为I(xi,yj)。I(xi,yj)=接收yj前接收者对xi存在的不确定度- 接收yj后接收者对xi仍存在的不确定度 =通信前后接收者对xi不确定度的变化量（减少量） =H(xi)-H(xi/yj)=I(xi)-I(xi/yj)其中：(2) 由p(xi,yj)=p(xi)p(yj/xi)=p(yj)p(xi/yj)可以得到如下结果： I(xi,yj)=I(xi)-I(xi/yj)=I(yj)-I(yj/xi) I(xi,yj)=I(yj,xi) 称为交互信息量(3) 得到两个公式由以上两个公式可以看到：只要已知某一个信源符号的先验概率及相应的转移概率，就可以得到相应的交互信息量。(4) 后验概率与交互信息量已知交互信息量=log(后验概率/先验概率)，这里分析后验概率对交互信息量的影响。 p(xi/yj)=1 I(xi,yj)=log(1/p(xi)=I(xi) H(xi/yj)=0收到yj后可以准确无误地判断xi，相当于无噪声信道，收到yj获得的信息量就等于xi的自信息量。 p(xi)p(xi/yj)0 H(xi)H(xi/yj)收到yj后判断信源发出xi的概率，大于收到yj之前判断信源发出xi的概率，通信后接收者对信源符号xi的不确定度减少了，获得的信息量大于0。 p(xi/yj)=p(xi) I(xi,yj)=0 H(xi)=H(xi/yj)收到yj后判断信源发出xi的概率，等于收到yj之前判断信源发出xi的概率，通信后接收者对信源符号xi的不确定度没有变化，获得的信息量等于0。 0p(xi/yj)p(xi) I(xi,yj)0 H(xi)p(xi=M)=1/2I(S,S)=0.585 bit; p(xi=S/yj=S)=3/4p(xi=S)=1/2I(S,M)=-0.415 bit; p(xi=S/yj=M)=3/8 p(xi=S)=1/2I(M,S)=-1 bit p(xi=M/yj=S)=1/4 p(xi=M)=1/22-4-4平均交互信息量(1) 定义：交互信息量接收者通过某一个信道P从一个信源p(xi)获得某一符号xi信息量的问题，但它不能完全反映一个信道的整体特性，因此，这里定义平均交互信息量。对于给定的信道模型；X, P(Y/X), Y，其平均互信息量为：这个关系可以这样来理解：将I(xi,yj)在X空间取平均： 其中(j=1,2,m)，然后在将I(X,yj)在Y空间取平均： 根据概率关系可得： 进一步还可以得到： 平均交互信息量给出了信道传输一个信源符号所传递的平均信息量，对于给定的信道和信源平均交互信息量是一个确定的量， 平均交互信息量实际上就是接收者收到一个符号通过信道从信源所获得的平均信息量，因此也称为平均接收信息量。(2) 利用熵的概念来描述交互信息量， 疑义度I(X,Y)=H(X)-H(X/Y)其中条件熵H(X/Y)称为疑义度，可疑度，它表示接收者收到Y后，对信源X仍然存在的平均不确定度。对于接收者来说，H(X)称为先验不确定度，H(X/Y)称为后验不确定度。平均交互信息量等于不确定度的变化量。 扩散度（噪声熵）I(X,Y)=H(Y)-H(Y/X)其中条件熵H(X/Y)称为扩散度，噪声熵，它表示发信者发出X后，对信道输出Y仍然存在的平均不确定度。对于发信者来说，H(Y)称为先验不确定度，H(Y/X)称为后验不确定度。平均交互信息量等于不确定度的变化量。 联合熵（共熵）I(X,Y)=H(X)+H(Y)-H(X,Y)其中熵H(X,Y)称为联合熵，共熵，它表示通信完成之后，观察者对通信系统仍然存在的平均不确定度。对于观察来说，H(X)+H(Y)称为先验不确定度，H(X,Y)称为后验不确