《信息论基本概念》PPT课件.ppt

第二章信息论基本概念,2.1信源的分类,2.2自信息量和条件自信息量一.自信息量一个随机事件的自信息量定义为其出现概率对数的负值若随机事件Xi出现概率为P(Xi)，那么它的自信息量I(Xi)为：比特奈特哈脱奈1nat1.433bit1hartley3.322bit,由定义式可知，若一个以等概率出现的二进制码元（0，1）,即当P(0)P(1)1/2时I(0)I(1)1bit在此引入不确定度概念若出现概率1（发生可能性大，包含的不确定度小）出现概率0（发生可能性小，包含的不确定度大）出现概率1（包含的不确定度为0）注意：随机事件的不确定度在数量上等于它的自信息量，两者单位相同，但含义却不相同。具有某种概率分布的随机事件不管发生与否，都存在不确定度，不确定度表征了该事件的特性，而自信息量是在该事件发生后给予观察者的信息量。,例某地二月份气候的概率分布根据气象资料统计下表：则四种气候的不确定度分别为：I(X1)1bitI(X2)2bitI(X3)3bitI(X4)3bit二.联合自信息量在二维联合集XY上的元素对xiyj的自信息量定义为：式中，P(xiyj)是元素对xiyj的联合概率。当xi和yj相互独立时，有P(xiyj)P(xi)P(yj)就有I(xiyj)I(xi)I(yj)元素对xiyj的不确定度在数值上也等于它们的自信息量,三.条件自信息量条件自信息量定义为条件概率对数的负值设在yj的条件下，随机事件xi的条件概率为P(xi|yj)，那么它的条件自信息量I(xi|yj)定义为：在给定yj的条件下，随机事件xi所包含的不确定度在数值上与条件自信息量相同因为一个随机事件的概率和条件概率总是在闭区间0，1内，所以自信息量、联合自信息量与条件自信息量均为非负值,2.3互信息量和条件互信息量一.互信息量设有一个简单的通信系统模型两个离散符号的消息集合X和Y，X是信源发出的符号集合，Y是信宿收到的符号集合通常实际中，可以知道信息X发出的各个符号消息的集合，以及它们的概率分布，也就是知道信源X的概率空间对于XX1，X2，XN，其相应各个元素的概率为P(x1)，P(x2)，P(xN)xi和P(Xi)（i1，2，n）的两个集合就称为概率空间，记作X，PX在这里，各个符号xi的概率称为先验概率,当信宿收到一个符号yj后，信宿可以计算信源各消息的条件概率P(xi|yj)（i1，2，n），这种条件概率就称作后验概率如观察输入为xi观察结果为yj。从yj中会得到有关输入符号xi的信息，记该信息为I(xi;yj)，称为xi与yj之间的互信息量，也叫事件信息。信息是先验不确定性减去后验不确定性，应等于为xi在观察到yj前后的不确定性之差，即xi的yj先验不确定性减去xi的后验不确定性再由自信息量和条件自信息量的定义式，不难推出互信息量的概率计算式,二.互信息量的性质1.对称性I(xi;yj)I(yj;xi)推导如下：I(xi;yj)logP(xi|yj)/P(xi)logP(xi|yj)P(yj)/P(xi)P(yj)logP(xiyj)/P(xi)P(yj)logP(xiyj)/P(xi)/P(yj)logP(yj|xi)/P(yj)I(yj;xi)由对称性可知随机事件xi与yj之间的统计约束程度。当后验概率P(xi|yj)大于先验概率P(xi)时，互信息量为正值；说明信宿收到yj提供了有关xi的信息，这样，信宿对信源发出的符号消息xi的不确定度减小了,2.当xi和yj相互独立时，互信息量为0当xi和yj相互独立时，有P(xiyj)P(xi)P(yj)I(xi;yj)logP(xi|yj)P(yj)/P(xi)P(yj)logP(xiyj)/P(xi)P(yj)log210这表示xi和yj之间不存在统计约束关系3.互信息量可为正值或负值4.互信息量不可能大于符号的实在信息，即由互信息量的定义，考虑条件自信息量的非负性，不难证明上式成立。其物理意义是：认识主体获得的某符号的信息，不可能大于该符号的实在信息。,例：根据2.2节的例题，我们来讨论互信息量的意义，即某地二月份气候的概率空间为若把“今天不是晴天”，作为收到消息X1。当收到X1后，各种气候的概率变成了后验概率其中：P(x1|X1)0P(x2|X1)1/2P(x3|X1)1/4P(x4|X1)1/4根据式I(xi;yj)logP(xi|yj)/P(xi)得X1与X2，X3，X4的互信息量均为1bit说明：收到X1后，可以使X2，X3，X4的不确定度减少1bit，即“今天不是晴天”这个条件提供了1bit的信息量。,符号xi对联合事件符号yjzk之间的互信息量定义为：I(xi;yjzk)logP(xi|yjzk)/P(xi)*三.条件互信息量含义：在给定zk条件下，xi与yj之间的互信息量条件互信息量I(xi;yj|zk)定义为：I(xi;yj|zk)logP(xi|yjzk)/P(xi|zk)从上式，可使*式写成：I(xi;yjzk)I(xi;zk)I(xi;yj|zk)推导如下:I(xi;yjzk)logP(xi|yjzk)/P(xi)logP(xi|yjzk)/P(xi|zk)P(xi|zk)/P(xi)logP(xi|yjzk)/P(xi|zk)logP(xi|zk)/P(xi)I(xi;zk)I(xi;yj|zk),*式表明：一个联合事件yjzk出现后所提供的有关xi的信息量等于事件zk出现后所提供的有关xi的信息量I(xi;zk)，加上在zk条件下再出现yj所提供的有关xi的信息量I(xi;yj|zk)*式中yj和zk的位置可互换，得I(xi;yjzk)I(xi;yj)I(xi;zk|yj)2.4通信熵一.熵（平均不确定度）例：一个布袋放100个球，其中80个球红色，20个球白色。若随机取一个球，猜测其颜色，求平均摸取一次所能获得的自信息量。解：这一事件的概率空间为其中X1表示摸出的球为红球事件,X2表示摸出的球为白球事件,若告知摸出的是红球，则事件的自信息量为I(X1)logP(X1)log20.8bit若告知摸出的是白球，则事件的自信息量为I(X2)logP(X2)log20.2bit若取回后又放回摸取，如此摸取n此，红球出现的次数nP(X1)，白球出现的次数为nP(X2)，则总信息量为InP(X1)I(X1)nP(X2)I(X2)而平均随机摸取一次所获得的信息量为H（X）1/nnP(X1)I(X1)nP(X2)I(X2)P(X1)logP(X1)P(X2)logP(X2)P(Xi)logP(Xi),一个信源总是包含着多个符号消息，各个符号消息又按概率空间的先验概率分布，它的不确定度是各个符号的不确定度的数学期望（即概率加权的统计平均值）它的熵（平均不确定度）H（X）定义为：H（X）EI(x)P(X)I(X)P(X)log2P(X)若信源X中的符号的概率空间简化表示为：则熵（平均不确定度）H（X）可写成：H（X）PilogPi注意：I(X)为非负，P(X)为非负，且0P(X)1H（X）也为非负,H(X)的值可作为信源X中任一符号消息所携带的平均信息量,也是唯一地确定信源X中任一符号消息时所需的最小平均信息量二.条件熵条件熵是在联合符号集合XY上的条件自信息量的联合概率加权统计平均值在给定Y(即各个y)条件下，X集合的条件熵H（X|Y）定义为：H（X|Y）P(xy)I(x|y)P(xy)logP(x|y)在给定Y(即各个x)条件下，Y集合的条件熵H（Y|X）定义为：H（Y|X）P(xy)I(y|x)P(xy)logP(y|x),下面推导说明求条件熵用联合概率加权的理由先取在一个条件y下，X集合的条件熵H(X|y)为:H（X|y）P(x|y)I(x|y)P(x|y)logP(x|y)进一步把H(X|y)在Y集合上取数学期望，就得条件熵H(X|Y)为：H（X|Y）P(y)H（X|y）P(y)P(x|y)logP(x|y)P(xy)logP(x|y)三.共熵共熵是联合符号集合XY上的每个元素对xy的自信息量的联合概率加权统计平均值，即共熵H(XY)定义为：H（XY）P(xy)I(xy)P(xy)logP(xy),共熵H(XY)与熵H(X)及条件熵H(X|Y)之间有如下关系：H(XY)H(X)H(Y|X)推导如下：P（xy）P（x）P（y|x）I（xy）I（x）+I（y|x）H（XY）H（X）H（Y|X）同理存在：H(XY)H(Y)H(X|Y)三维联合符号集合XYZ上的共熵H（XYZ）定义为H（XYZ）P(xyz)logP(xyz)由上面所述可得：H（XYZ）H(XY)+H(Z|XY)H(X)+H(Y|X)+H(Z|XY)H（XYZ）H(X)+H(Y)+H(Z),取对数,取统计平均,条件熵与信源熵之间存在关系H（Y|X）H（Y）当且仅当P(y|x)P(y)，即y和x相互独立时，式取等证明：H(Y|X)H(Y)P(xy)log1/P(y|x)P(y)log1/P(y)P(xy)log1/P(y|x)P(y)P(x|y)log1/P(y)P(xy)log1/P(y|x)P(xy)log1/P(y)P(xy)logP(y)/P(y|x)在这里同样利用自然对数性质：ln1,0当且仅当1时，式取等令P(y)/P(y|x)，引用ln1H(Y|X)H(Y)P(xy)P(y)/P(y|x)1logeP(x)P(y)P(xy)loge（11）loge0,（续上）当且仅当P(y)/P(y|x)1时，即P(y|x)P(y)时，式取等同理有：H（X|Y）H（X）此定理说明：条件熵小于或等于原符号集合的熵两个条件下的条件熵与一个条件下的条件熵之间存在关系H（Z|XY）H（Z|Y）当且仅当P(z|xy)P(z|y)时，式取等强调指出：条件熵的条件越多，其条件熵的值就越小H（Z|XY）H（Z|Y）H（Z）,四.各种熵的性质非负性对称性扩张性可加性确定性熵函数具有凸性极值性信源X中包含M个不同符号时，信源熵H(X)有H（X）logM当且仅当X中各个符号的概率相等时，式取等,证明：H(X)logMP(X)log1/P(X)P(X)logMP(X)log1/P(X)M在这里利用自然对数性质：ln1,0当且仅当1时，式取等令1/P(X)M,引用上述性质，得H(X)logMP(X)1/P(X)M1loge1/MP(X)loge1/MP(X)loge括号中1/M和P(X)的值均为1所以，H(X)logM0，即H（X）logM当且仅当1/P(X)M1,即P(X)1/M时，式取等此定理说明：当X集合中的各个符号消息以等概率分布出现时，可得最大信源熵为H(X)maxlogM,2.5平均互信息量一.首先讨论互信息量在X集合上的统计平均值I(X；y)P(x|y)I（x；y）P(x|y)logP(x|y)/P(x)平均互信息量I（X；Y）为I(X；y)上述在Y集合上的概率加权统计平均值，即I（X；Y）为I（X；Y）P(y)I（x；y）P(y)P(x|y)logP(x|y)/P(x)P(xy)logP(x|y)/P(x)对于I(X；Y)，当XY中的各个x和y相互独立时，则各个I(x；y)为0，此时有I(X；Y)0,二.平均互信息量的性质1.对称性I(X；Y)I(Y；X)此性质可根据互信息量对称性I(x；y)I(y；x)可得2.I(X；Y)H(X)H(X|Y)I(X；Y)H(Y)H(Y|X)推导如下：I(X；Y)P(xy)logP(x|y)/P(x)P(xy)logP(x)P(xy)logP(x|y)H(X)H(X|Y)同理可得：I(X；Y)H(Y)H(Y|X)根据对称性，得：I(X；Y)H(X)H(X|Y)H(Y)H(Y|X),3.I(X；Y)H(X)I(X；Y)H(Y)4.I(X；Y)H(X)H(Y)H(XY)推导如下：I(X；Y)H(Y)H(Y|X)H(XY)H(X)H(Y|X)I(X；Y)H(X)H(Y)H(XY)5.I(X；Y)0当且仅当X和Y相互独立时，式取等,为了便于记忆公式，可用如下方法：三维联合集上XYZ上的平均互信息量，有：I(X；YZ)I(X；Y)I(X；Z|Y)根据互信息量的对称性，由上式，可得：I(X；YZ)I(X；ZY)I(X；Z)I(X；Y|Z)I(YZ；X)I(Y；X)I(Z；X|Y),对于信宿收到的消息，通常用处理器对其进行处理，如下图三.数据处理定理当消息通过多级处理器时，随着处理器数目的增多，输入消息与输出消息之间的平均互信息量趋于变小即对于上图所示的两级级连处理器，有I(X；Z)I(Y；Z)I(X；Z)I(X；Y)此定理说明：任何信息处理过程总会失掉信息，最多保持原来的信息，一旦失掉信息，用任何手段也不可能再恢复丢失的信息,四.平均互信息量的物理意义I(X；Y)H(X)H(X|Y)I(X；Y)H(Y)H(Y|X)当信源符号集合为X，信宿符号集合为Y时，平均互信息量I(X；Y)表示在有扰离散信道上传输的平均信息量条件熵H(X|Y)可看作由于信道上存在干扰和噪声而损失掉的平均信息量；也可看作信道上的干扰和噪声所造成的对信源符号x的平均不确定度（疑义度）H(X)是符号集合X的熵或不确定度，而H(X|Y)是当Y已知时的X的不确定度，那么可见“Y已知”这件事使X的不确定度减少了I(X；Y)，这意味着“Y已知后”获得的关于X的信息量是I(X；Y)条件熵H(Y|X)可看作唯一地确定信道噪声所需的平均信息量（噪声熵或散布度）对于无扰离散信道：H(X|Y)H(Y|X)I(X；Y)H(X)H(Y)对于全损离散信道：H(X)H(X|Y)或H(Y)H(Y|X)I(X；Y)0,2.6离散信源的熵一、各种离散信源的熵1.发出单个符号消息的离散无记忆信源熵若信源发出N个不同符号X1，X2，Xi，XN,代表N种不同的消息，各个符号的概率分别为P1，P2，Pi，PN因为这些符号相互独立，所以该信源熵为：H（X）PilogPibit/符号2.发出符号序列消息的离散无记忆信源熵发出K重符号序列消息的离散无记忆信源熵为共熵H(XK)，它与单个符号消息信源熵H(X)有如下关系：H(XK)KH(X)KPilogPibit/符号序列,3.发出符号序列消息的离散有记忆信源熵发出K重符号序列消息的离散有记忆信源熵也为共熵H(XK)当K2时H(X2)H(X)H(X|X)H(X|X)H(X)H(X2)H(X2)2.412可见H(X2)2H(X),4.发出符号序列消息的马尔可夫信源熵马尔可夫过程和马尔可夫链马尔可夫过程对于任意的大于2的自然数n，在连续的时间T轴上有n个不同时刻，t1，t2，tn满足，在tn时刻的随机变量Xn与其前面（n1）个时刻的随机变量X1，X2，Xn1的关系可用它们之间的转移概率密度函数来表示，且满足下式：p(Xn，tn|Xn1，tn1，Xn2，tn2，X1，t1)p(Xn，tn|Xn1，tn1)则这种随机过程称为单纯马尔可夫过程（一阶马尔可夫过程）K阶马尔可夫过程的特征为：p(Xn，tn|Xn1，tn1，Xn2，tn2，X1，t1)p(Xn，tn|Xnk，tnk),马尔可夫链当马尔可夫过程的随机变量幅度和时间参数均取离散值时，就称作马尔可夫链设随机过程在时间域上Tt1，t2，tk1，tk，tn1，tn的n个离散时刻上的状态Xk(k1，2，3，n)都是离散型的随机变量，并且有M个不同的取值S1,S2,SM，这M个取值便构成一个状态空间S，SS1,S2,SM.在n个时刻上的n个状态构成一个随机序列（X1，X2，Xk1，Xk，Xn1，Xn）,对于这个随机序列，若有：则此序列称为单纯马尔可夫链（一阶马尔可夫链）一阶马尔可夫链在tn时刻的取值XnSin的概率仅与前一状态Xn-1有关，与其它时刻状态无关若与它前面K个时刻tn-1，tn-2，tn-k有关，则为K阶马尔可夫链设一阶马尔可夫链在时刻tk1随机序列的取值Xk1Si，而在下一时刻tk，随机序列的取值XkSj，则条件概率为:因为P(j|i)仅取决于状态Sj和Si，因此称P(j|i)为由状态Si向Sj的转移概率,对于具有M个不同的状态空间，M2个转移概率可排成一转移矩阵：每行元素代表同一起始状态到M个不同终止状态的转移概率每列元素代表M个不同起始状态到同一终止状态的转移概率显然有：P(j|i)1（i=1,2,M）K阶马尔可夫链每个状态由K个符号组成。若信源符号有D种，则状态数目M为：MDK同时转移概率的数目为：DMDK+1,马尔可夫链可以用香农线图表示。(a),(b),(c)分别表示信源含两种字母(D2)的一阶、二阶和三阶马尔可夫链的线图。(d),(e)分别表示D3和D4的一阶马尔可夫链的线图。,利用马尔可夫链各状态之间的转移概率，可求得稳定条件下各状态的概率举例说明：设两位二进制码所代表的四个状态分别为00，01，10，11，其符号转移概率和状态转移概率由下列两表给出：试求稳定条件下各状态的概率,解：据题意，可画出相应的香农线图设稳定状态下，各个状态的概率为P(S0)P0，P(S1)P1，P(S2)P2，P(S3)P3根据图示，可得P01/2P01/4P2P11/2P03/4P2P21/3P11/5P3P34/5P32/3P1P0P1P2P31由上面五个方程，可得：P03/35，P16/35,P26/35，P34/7,马尔可夫信源熵是条件熵由前一状态Ei发出符号后转移到后一状态Ej。假设在这个转移中能发出l种符号，则就有L条同方向的转移线，且各条转移线上的转移概率为。那么从Ei状态转移到Ej状态的总转移概率为若从Ei状态转移到后一状态有多种可能性，则信源由Ei状态发出一个符号的为,再进一步，对前一状态Ei的全部可能性作统计平均，就得出马尔可夫信源熵H为其中，熵函数表示信源处于某一状态Si时发出一个消息符号的平均不确定性；p(i)是马尔可夫链的平稳分布。需注意，虽然马尔可夫信源发出的是符号序列消息，但上式计算的信源熵的单位是bit/符号。,二、各种离散信源的时间熵信源的时间熵在单位时间内信源发出的平均信息量，单位为s(秒)或其他特定的时间单位1.发出单个符号消息的离散无记忆信源的时间熵已知离散无记忆信源各符号的概率空间由于发出各符号所占有时间是不同的可设符号X1的长度为b1，X2为b2，Xi为bi，XN为bN单位均为s(秒)则信源各符号的平均长度是各个的概率加权平均值，即,s/符号,则信源的时间熵Ht为：若各符号时间长度相同，均为b(s)，则可直接得又若信源每秒平均发出n个符号，有此时，信源熵Ht为：,bit/s,符号/s,bit/s,2.发出符号序列消息的离散无记忆信源的时间熵对K重符号序列的离散无记忆信源的信源熵为：H(XK)KH(X)bit/符号序列K重符号序列消息的平均长度为信源各符号平均长度的K倍，即这种信源的时间熵Ht为：可见，它在数值上与上面一种信源的时间熵相同,s/符号序列,bit/s,若该信源每秒内平均发出n个K重符号序列消息，则有：此时Ht为：3.发出符号序列消息的离散有记忆信源的时间熵计算方法与发出符号序列无记忆信源的时间熵一致，但H(XK)KH(X)同样若信源在每秒内平均发出n个K重符号序列消息，有,符号序列/s,bit/s,bit/s,符号序列/s,bit/s,