信息论第二讲-离散信源的熵.ppt

2019/4/28,1,离散信源特性： 根据Shannon信息论的观点，信源要含有一定的信息，必然具有随机性，即有不确定性，可以用其概率来表示。,2、离散信源的熵,2.1 离散信源的数学模型,2.1.1 单符号离散信源的数学模型,2019/4/28,2,离散信源空间： 信源的符号（状态）随机地取值于一个离散集合X=（x1,x2,xn）中，一个离散信源可以用一个离散随机变量的概率空间表示。P=(p1,p2,pn) 这种表示称为离散无记忆信源的信源空间。 信源空间必为一个完备空间， 即其概率和为1。,2019/4/28,3,信源数学模型描述的条件： 用信源空间（离散随机变量）来表示信源的条件是信源符号（状态）的先验概率是可知的，这是Shannon信息论的一个基本假说。,2019/4/28,4,信息的理解,1 只有信息的概念没有信息的定义； 2 山农信息论认为：“正如熵表示分子无组织程度的度量一样，离散信源中所包含的信息就是信源符号不确定程性的度量”。 组织程度的度量； 有序程度的度量； 用以减少不确定性的东西； 3 还有其它的描述： 信息就是使概率分布发生变化的东西； 信息是反映事物的形式、关系和差异的东西，信息包含在事物的差异之中，而不在事物本身。,2019/4/28,5,不确定性： 只有不确定性存在，才有信息存在，获得消息后消除了不确定性才得到信息。在一个通信系统中，收信者所获取的信息量，在数量上等于通信前后对信源的不确定性的减少量。 不确定性的度量（不确定度）： 不确定度应该等于猜测某一随机事件是否会发生的难易程度。,2.1.2 信源符号不确定性的度量(uncertainty),2019/4/28,6,Hartly公式： 信源不确定度的大小与信源的消息符号数有关；符号数越多，不确定度越大； 信源不确定度的大小与信源的消息符号概率有关；概率越小，不确定度越大； 信源不确定度应具有可加性； 同时应当满足：如果p(xi)=0，则I(xi)=，如果p(xi)=1，则I(xi)=0。 因此为了满足以上四个条件，应把信源不确定度写为对数形式：,2019/4/28,7,自信息量的定义： 收信者收到一个消息状态得到的信息量，等于收到后对这个消息状态不确定度的减少量。 I（信息量）=不确定度的减少量。,2.1.3 信源符号的自信息量,2019/4/28,8,无噪声信道下的自信息量： 在假设信道没有干扰（无噪声）的情况下，信源发出信源状态xi，接收者就会收到xi，这时接收者收到的信息量就等于信源状态xi本身含有的信息量（不确定度），称为信源状态xi的自信息量，记为I(xi)。 这时，接收到xi所获得的信息量等于信源输出发出的信息量。,2019/4/28,9,有噪声信道下的互信息量： 在有噪声信道下，信源发出的状态为xi，接收者收到的状态为yj，接收者收到yj后，从yj中获取到关于xi的信息量，就是信源发出xi后，接收者收到的信息量，称为互信息量。记为I(xi,yj)。 接收到yj后，信源实际发出xi时接收者所获得的信息量。 由于噪声的干扰，接收者收到的信息量小于信源发出的信息量。,2019/4/28,10,H(xi)为信源状态xi本身具有的不确定性； H(xi/yj)为接收到一个yj后，信源状态xi仍存在的不确定度；收到yj后，信源状态xi的不确定性应有所变化，这个变化量就称为信源状态xi的互信息量。,这个互信息量在什么条件下为大于零？等于零？小于零？,2019/4/28,11,（1）信源熵的定义： 信源一个消息状态所具有的平均信息量。 离散无记忆信源的熵（独立熵）：,2.2 单符号离散信源的熵,2.2.1 信源熵的概念(Entropy),H(X)表示信源发出任何一个消息状态所携带的平均信息量，也等于在无噪声条件下，接收者收到一个消息状态所获得的平均信息量。,2019/4/28,12,（2）熵的物理意义： 熵的本意为热力学中表示分子状态的紊乱程度； 信息论中熵表示信源中消息状态的不确定度； （3）信源熵与信息量有不同的意义； H(X)表示信源X每一个状态所能提供的平均信息量； H(X)表示信源X在没有发出符号以前，接收者对信源的平均不确定度； H(X)表示随机变量X的随机性；,2019/4/28,13,熵函数可以表示为：,2.2.2 熵函数的性质,性质1：非负性； H(X)0 性质2：对称性； 性质3：确定性；,2019/4/28,14,性质4：连续性；性质5：扩展性；,2.2.3 离散信源的最大熵,（一）一般离散信源的最大熵 在数学上可以证明熵函数存在最大值，离散信源的熵函数有n个变量，有一个约束条件，作一个辅助函数：,2019/4/28,15,Hmax(X)=H(1/n, 1/n,1/n)=logn 这个结果称为离散信源得最大熵定理。它表明，在所有符号数相同，而概率分布不同的离散信源中，当先验概率相等时得到的熵最大。最大熵的值取决于符号状态数，状态数越多，熵越大。,2019/4/28,16,这时可求得离散信源得最大熵为,（二）均值受限的离散信源的最大熵 在增加一个约束条件的情况下，求离散信源的最大熵，做辅助函数：,2019/4/28,17,加权熵,上面定义的信源熵是没有考虑信息的主观因素，也称为“概率信息”或客观信息。我们可以利用加权熵描述不同信息对于不同对象的重要性差异。,2019/4/28,18,联合信源的概率空间： 联合信源可以认为有两个信源X，Y组成：,2.3 共熵与条件熵,2.3.1 联合信源的共熵(Joint Entropy),2019/4/28,19,联合信源,X：x1,x2,x3,xn,Y：y1,y2,y3,ym,多元随机变量的概率。 P(X), P(Y), P(X,Y) P(X/Y) P(Y/X),2019/4/28,20,用这两个信源组成一个联合信源，其联合概率空间为：,其中状态（xi, yj）为联合信源输出的一个状态。,2019/4/28,21,联合信源共熵的表达式： 联合信源的共熵：联合信源输出一个组合消息状态(xi,yj)所发出的平均信息量。 联合信源的独立熵： 将联合信源看成两个独立的信源（当然实际上可能并不是相互独立的）时，各自信源的熵即为独立熵。,2019/4/28,22,概率的基本关系： 当X，Y独立时，有p(x,y)=p(x)p(y)。,2019/4/28,23,2019/4/28,24,2.3.1 联合信源的条件熵(Conditional Entropy),一个联合信源（X，Y）的条件熵定义为： 信源Y（或X）输出任一状态后，信源X（或Y）输出任一状态所发出的平均信息量。,2019/4/28,25,以上讨论的信源符号状态的自信息量和信源的熵是描述信源的特性，但是对于一个通信系统来说，最主要的问题是接收者收到信息的能力。在信源与接收者之间是由信道连接的，这里要开始讨论信道的问题。,2.4 离散信源的平均交互信息量,2019/4/28,26,设离散信道的输入为一个随机变量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),2.4.1 离散信道的数学模型,2019/4/28,27,离散信道主要有三种描述方法。 概率空间描述 X=x1,x2,xn P(Y/X)=p(yj/xi) (i=1,2,n; j=1,2,m) Y=y1,y2,ym 0p(yj/xi)1 这表明信道有一个输入就一定有一个输出。,2019/4/28,28,转移矩阵描述 矩阵P称为转移矩阵或信道矩阵；表示为：,P矩阵为一个nm矩阵，其每行元素之和等于1。,2019/4/28,29,图示法描述 离散信道的图示法描述如图所示。,2019/4/28,30,2.4.2 X与Y的关系,当信道输出一个符号yj时，一定是有一个输入符号xi输入信道。 对于给定的信道P，如果已知先验概率p(xi)，则可以求出p(xi,yj)、P(xi/yj)和p(yj)。 先验概率；联合概率； 信道转移概率；后验概率；,2019/4/28,31,2.4.3 交互信息量(Mutual Information),定义： 信息传输的根本问题是，对于给定的信道计算收到一个yj后，从yj中获取关于xi的信息量。这个信息量称为互信息量，记为I(xi, yj)。 I(xi, yj)=接收yj前接收者对xi存在的不确定度- 接收yj后接收者对xi仍存在的不确定度 =通信前后接收者对xi不确定度的变化量（减少量） I(xi, yj) =H(xi)-H(xi/yj)=I(xi)-I(xi/yj),2019/4/28,32,交互关系 由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) 称为交互信息量,2019/4/28,33,两个公式,由以上两个公式可以看到： 只要已知某一个信源符号的先验概率及相应的转移概率，就可以得到相应的交互信息量。,2019/4/28,34,后验概率与交互信息量 已知交互信息量=log(后验概率/先验概率)， 这里分析后验概率对交互信息量的影响。 H(xi/yj)=0 收到yj后可以准确无误地判断xi，相当于无噪声信道，收到yj获得的信息量就等于xi的自信息量。 H(xi)H(xi/yj) 收到yj后判断信源发出xi的概率，大于收到yj之前判断信源发出xi的概率，通信后接收者对信源符号xi的不确定度减少了，获得的信息量大于0。,2019/4/28,35,H(xi)=H(xi/yj) 收到yj后判断信源发出xi的概率，等于收到yj之前判断信源发出xi的概率，通信后接收者对信源符号xi的不确定度没有变化，获得的信息量等于0。 H(xi)H(xi/yj) 收到yj后判断信源发出xi的概率，小于收到yj之前判断信源发出xi的概率，通信后接收者对信源符号xi的不确定度不但没减少，反而增加了，获得的信息量小于0。,2019/4/28,36,离散无记忆信道DMC,离散无记忆信道是一种简单的通信信道模型。 离散：某一时刻的输入输出为有限的符号集合； 无记忆：某一时刻的输出只与这一时刻的输入有关；,X: x1,x2,xn,Y: y1,y2,ym,2019/4/28,37,二元对称信道BSC,n=m=2,2019/4/28,38,二元删除信道,0,1,1,0,1-p,1-q,p,q,?,n=2; m=3,2019/4/28,39,后验熵H(X/Y),接收者(观测者)收到Y后,对信源X仍然存在的不确定量,2019/4/28,40,定义： 交互信息量接收者通过某一个信道P从一个信宿符号yj中获得某一信源符号xi信息量的问题，但它没有反映一个信道的整体特性，因此，这里定义平均交互信息量。 对于给定的信道模型；X, P(Y/X), Y，其平均互信息量为：I(X,Y)=H(X)-H(X/Y),2.4.4 平均交互信息量,2019/4/28,41,关系：,进一步还可以得到：,平均交互信息量给出了信道传输一个信源符号所传递的平均信息量，对于给定的信道和信源平均交互信息量是一个确定的量， 平均交互信息量实际上就是接收者收到一个符号通过信道从信源所获得的平均信息量，因此也称为平均接收信息量。,2019/4/28,42,利用熵的概念来描述交互信息量： 疑义度 I(X,Y)=H(X)-H(X/Y) 其中条件熵H(X/Y)称为疑义度，可疑度，它表示接收者收到Y后，对信源X仍然存在的平均不确定度。 扩散度（噪声熵） I(X,Y)=H(Y)-H(Y/X) 其中条件熵H(X/Y)称为扩散度，噪声熵，它表示发信者发出X后，对信道输出Y仍然存在的平均不确定度。 联合熵（共熵） I(X,Y)=H(X)+H(Y)-H(X,Y) 其中熵H(X,Y)称为联合熵，共熵，它表示通信完成之后，观察者对通信系统仍然存在的平均不确定度。,2019/4/28,43,I(X,Y)=H(X)-H(X/Y)=H(Y)-H(Y/X)=H(X)+H(Y)-H(X,Y) 图给出了平均交互信息量、信源熵，信宿熵，联合熵，疑义度和扩散度之间的关系。,2019/4/28,44,2.4.5 平均交互信息量的特性,2.5.1 I(X,Y)的非负性 2.5.2 平均交互信息量的交互性 2.5.3 平均交互信息量的极值性 2.5.4 平均交互信息量的凸函数性 2.5.5 平均交互信息量的不增性,2019/4/28,45,2.5.1 I(X,Y)的非负性,当x为大于0的实数时，底大于1的对数logx是x的严格上凸函数。可以证明若f(x)为上凸函数，则有：fpixipif(xi)，如f(x)=logx，则有： logpixipilogxi,根据这个关系，考虑平均交互信息量， I(X,Y)= p(xi, yj) logp(xi,yj) / p(xi) p(yj) 则： -I(X,Y)= p(xi,yj)logp(xi)p(yj)/p(xi,yj) logp(xi,yj)p(xi)p(yj)/p(xi,yj) =logp(xi) p(yj)=0 所以有：I(X,Y) 0,2019/4/28,46,2.5.2 平均交互信息量的交互性,由于p(xi, yj)=p(yj, xi) 则：I(X,Y)=I(Y,X)（对于一个信息系统来说） 交互性表明在Y中含有关于X的信息，I(X,Y)；在X中含有关于Y的信息，I(Y,X)；而且两者相等。实际上I(X,Y)和I(Y,X)只是观察者的立足点不同，对信道的输入X和输出Y的总体测度的两种表达形式。,2019/4/28,47,X和Y相互独立，交互性最小， I(X,Y) =0； X和Y完全相关，交互性最大， I(X,Y) =H(X)=H(Y)； H(X/Y)=H(Y/X)=0， 相当于信道无信息损失。,2019/4/28,48,这种信道的特点是： n=m，每行只有一个元素为1，每列只有一个元素为1。其转移概率不为1，就为0。,2019/4/28,49,这时有：,所以有：I(X,Y)=I(Y,X)=H(X)=H(Y),2019/4/28,50,2.5.3 平均交互信息量的极值性,平均交互信息量I(X,Y)不可能超过信源熵H(X)， 因为H(X/Y) 0 所以有I(X,Y)=H(X)-H(X/Y)H(X) 因为H(Y/X) 0 所以有I(X,Y)=H(Y)-H(Y/X)H(Y),疑义度、噪声熵总是大于等于0，平均交互信息量总是小于信源熵或信宿熵。 在信道的输出端Y得到的关于输入端X的信息量不会超过信源X的平均信息量。,2019/4/28,51,扩展性无噪声信道,由于其矩阵的每一列元素只有一个非零元素，所以后验概率不等于1，就等于0. 即：,2019/4/28,52,这时可知疑义度H(X/Y)=0，平均交互信息量达到最大值I(X,Y)=H(X)。从平均意义上讲，这种信道可以把信源的信息全部传递给信宿。这种每列只有一个非0元素的信道也是一种无噪声信道，称为具有扩展性能的无噪声信道。,这时：H(Y/X)=H(Y)-H(X) 因为：H(Y/X) 0， 所以：H(Y) H(X)； 得到的结论为： 这时的信宿熵将大于信源熵，因此称为扩展信道。,2019/4/28,53,并归性无噪声信道,这类信道的转移概率等于1或者等于0，每一列的元素可有一个或多个1，可知其噪声熵H(Y/X)=0，此时的平均交互信息量达到最大值。I(X,Y)=H(Y)-H(Y/X)=H(Y),这时可以证明： 疑义度 H(X/Y)=H(X)-H(Y), 并且H(X)H(Y)，,2019/4/28,54,通过这两个例题可以进一步理解条件熵的概念，疑义度和噪声熵都是由于信道噪声引起的，当信道转移概率是一一对应的确定关系时，疑义度和噪声熵等于0，无噪声信道。 一个X产生多个Y，称为扩展信道，在扩展信道中若P中每列只有一个非0元素，H(X/Y)=0，即疑义度=0，称为扩展性无噪声信道，否则称为扩展噪声信道。 多个X产生一个Y，称为归并信道，在归并信道中若P中元素为0或1，H(Y/X)=0，即噪声熵=0，称为归并性无噪声信道，否则称为归并噪声信道。,2019/4/28,55,平均交互信息量先验概率p(xi)和信道转移概率p(yj/xi)的函数，可以记为：I(X,Y)=Ip(xi),p(yj/xi) 如果信道固定，I(X,Y) 是先验概率的函数; 如果信源固定，I(X,Y)是信道转移概率的函数。 可以进一步证明： 当信道一定时，I(X,Y)是信源先验概率的上凸函数；这就是说，