信息论基本概念.ppt

《信息论基本概念.ppt》由会员分享，可在线阅读，更多相关《信息论基本概念.ppt（44页珍藏版）》请在三一办公上搜索。

1、第二章 信息论基本概念,2.1 信源的分类,2.2 自信息量和条件自信息量 一.自信息量 一个随机事件的自信息量定义为其出现概率对数的负值 若随机事件Xi出现概率为P(Xi)，那么它的自信息量I(Xi)为：比特 奈特 哈脱奈 1nat 1.433 bit 1hartley 3.322 bit,由定义式可知，若一个以等概率出现的二进制码元（0，1）,即当P(0)P(1)1/2时 I(0)I(1)1bit 在此引入不确定度概念 若 出现概率 1（发生可能性大，包含的不确定度小）出现概率 0（发生可能性小，包含的不确定度大）出现概率 1（包含的不确定度为0）注意：随机事件的不确定度在数量上等于它的自

2、信息量，两者单位相同，但含义却不相同。具有某种概率分布的随机事件不管发生与否，都存在不确定度，不确定度表征了该事件的特性，而自信息量是在该事件发生后给予观察者的信息量。,例 某地二月份气候的概率分布根据气象资料统计下表：则四种气候的不确定度分别为：I(X1)1bit I(X2)2bit I(X3)3bit I(X4)3bit二.联合自信息量 在二维联合集XY上的元素对xiyj的自信息量定义为：式中，P(xiyj)是元素对xiyj的联合概率。当xi 和 yj相互独立时，有P(xiyj)P(xi)P(yj)就有 I(xiyj)I(xi)I(yj)元素对xiyj的不确定度在数值上也等于它们的自信息量

3、,三.条件自信息量 条件自信息量定义为条件概率对数的负值 设在yj的条件下，随机事件xi的条件概率为P(xi|yj)，那么它的条件自信息量I(xi|yj)定义为：在给定yj的条件下，随机事件xi所包含的不确定度在数值上与条件自信息量相同 因为一个随机事件的概率和条件概率总是在闭区间0，1内，所以自信息量、联合自信息量与条件自信息量均为非负值,2.3 互信息量和条件互信息量 一.互信息量 设有一个简单的通信系统模型 两个离散符号的消息集合X和Y，X是信源发出的符号集合，Y是信宿收到的符号集合 通常实际中，可以知道信息X发出的各个符号消息的集合，以及它们的概率分布，也就是知道信源X的概率空间 对于

4、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的后验不确定性 再由自信息量和条

5、件自信息量的定义式，不难推出互信息量的概率计算式,二.互信息量的性质 1.对称性 I(xi;yj)I(yj;xi)推导如下：I(xi;yj)log P(xi|yj)/P(xi)log P(xi|yj)P(yj)/P(xi)P(yj)log P(xiyj)/P(xi)P(yj)log P(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相互

6、独立时，互信息量为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)log21 0 这表示xi和yj之间不存在统计约束关系 3.互信息量可为正值或负值 4.互信息量不可能大于符号的实在信息，即 由互信息量的定义，考虑条件自信息量的非负 性，不难证明上式成立。其物理意义是：认识主体获得的某符号的信息，不可能大于该符号的实在信息。,例：根据2.2节的例题，我们来讨论互信息量的意义，即某地二月份气候的概率空间为 若把“今天不是晴天”，作为收到消息X1。当收到X1后，各种气候的

7、概率变成了后验概率 其中：P(x1|X1)0 P(x2|X1)1/2 P(x3|X1)1/4 P(x4|X1)1/4 根据式 I(xi;yj)logP(xi|yj)/P(xi)得 X1与X2，X3，X4 的互信息量均为1bit 说明：收到X1后，可以使X2，X3，X4的不确定度减少1bit，即“今天不是晴天”这个条件提供了1bit的信息量。,符号xi对联合事件符号yj zk之间的互信息量定义为：I(xi;yj zk)logP(xi|yj zk)/P(xi)*三.条件互信息量 含义：在给定zk条件下，xi与yj之间的互信息量 条件互信息量I(xi;yj|zk)定义为：I(xi;yj|zk)log

8、P(xi|yj zk)/P(xi|zk)从上式，可使*式写成：I(xi;yj zk)I(xi;zk)I(xi;yj|zk)推导如下:I(xi;yj zk)log P(xi|yj zk)/P(xi)log P(xi|yj zk)/P(xi|zk)P(xi|zk)/P(xi)log P(xi|yj zk)/P(xi|zk)log P(xi|zk)/P(xi)I(xi;zk)I(xi;yj|zk),*式表明：一个联合事件yj zk出现后所提供的有关xi的信息量等于事件zk出现后所提供的有关xi的信息量I(xi;zk)，加上在zk条件下再出现yj所提供的有关xi的信息量I(xi;yj|zk)*式中yj

9、和zk的位置可互换，得 I(xi;yj zk)I(xi;yj)I(xi;zk|yj)2.4 通信熵一.熵（平均不确定度）例：一个布袋放100个球，其中80个球红色，20个球白色。若随机取一个球，猜测其颜色，求平均摸取一次所能获得的自信息量。解：这一事件的概率空间为 其中X1表示摸出的球为红球事件,X2表示摸出的球为白球事件,若告知摸出的是红球，则事件的自信息量为 I(X1)logP(X1)log20.8 bit 若告知摸出的是白球，则事件的自信息量为 I(X2)logP(X2)log20.2 bit 若取回后又放回摸取，如此摸取n此，红球出现的次数nP(X1)，白球出现的次数为nP(X2)，则

10、总信息量为 InP(X1)I(X1)nP(X2)I(X2)而平均随机摸取一次所获得的信息量为 H（X）1/n nP(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)为

11、非负，且0P(X)1 H（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

12、(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)log P(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

13、(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)/

14、P(y|x)在这里同样利用自然对数性质：ln 1,0 当且仅当1时，式取等 令P(y)/P(y|x)，引用 ln 1 H(Y|X)H(Y)P(xy)P(y)/P(y|x)1loge P(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）,四.各种

15、熵的性质非负性对称性扩张性可加性确定性熵函数具有凸性极值性 信源X中包含M个不同符号时，信源熵H(X)有 H（X）logM 当且仅当X中各个符号的概率相等时，式取等,证明：H(X)logM P(X)log1/P(X)P(X)logM P(X)log1/P(X)M在这里利用自然对数性质：ln 1,0 当且仅当1时，式取等 令1/P(X)M,引用上述性质，得 H(X)logM P(X)1/P(X)M1loge 1/MP(X)loge 1/M P(X)loge 括号中 1/M 和 P(X)的值均为1 所以，H(X)logM 0，即 H（X）logM 当且仅当1/P(X)M1,即P(X)1/M时，式取

16、等 此定理说明：当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(

17、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 当且仅

18、当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)此定理说明：任何信息处理过程总会失掉信息，最多保持原来的信息，一旦失掉信息

19、，用任何手段也不可能再恢复丢失的信息,四.平均互信息量的物理意义 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)可看作唯一地确定信道

20、噪声所需的平均信息量（噪声熵或散布度）对于无扰离散信道：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）PilogPi bit/符号 2.发出符号序列消息的离散无记忆信源熵 发出K重符号序列消息的离散无记忆信源熵为共熵H(XK)，它与单个符号消息信源熵H(X)有如下关系：H(XK

21、)KH(X)K PilogPi bit/符号序列,3.发出符号序列消息的离散有记忆信源熵 发出K重符号序列消息的离散有记忆信源熵也为共熵H(XK)当K2时 H(X2)H(X)H(X|X)H(X|X)H(X)H(X2)2H(X)推广到K重 例：已知离散有记忆信源中各符号的概率空间为,现信源发出二重符号序列消息（ai，aj），这两个符号的概率关连性用条件概率P（aj|ai）表示，并由下表给出。求该信源熵H(X2)解：条件熵H(X2|X1)为 H(X2|X1)P（ai aj）log P（aj|ai）0.870 bit/符号 在这里 P（ai aj）P（ai）P（aj|ai）,单符号信源熵H(X1)为

22、 H(X1)P（ai）log P（ai）1.542 bit/符号 发出二重符号序列消息的信源熵为 H(X2)H(X1)H(X2|X1)1.5420.870 2.412 bit/符号 比较 H(X2)和 2H(X)2H(X)21.5423.084 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

23、|Xn 1，tn1，Xn2，tn2，X1，t1)p(Xn，tn|Xn 1，tn 1)则这种随机过程称为单纯马尔可夫过程（一阶马尔可夫过程）K阶马尔可夫过程的特征为：p(Xn，tn|Xn 1，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个状态构成一个随机序列（

24、X1，X2，Xk1，Xk，Xn1，Xn）,对于这个随机序列，若有：则此序列称为单纯马尔可夫链（一阶马尔可夫链）一阶马尔可夫链在tn时刻的取值Xn Sin的概率仅与前一状态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个不同终止状态的转移概率 每列元素代表

25、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，其符号转移概率和状态转移概率由下列两表给出：试求稳定条件下各状态的概率,解：据题意，可画

26、出相应的香农线图 设稳定状态下，各个状态的概率为 P(S0)P0，P(S1)P1，P(S2)P2，P(S3)P3 根据图示，可得 P0 1/2P0 1/4P2 P1 1/2P0 3/4P2 P2 1/3P1 1/5P3 P3 4/5P3 2/3P1 P0 P1 P2 P3 1 由上面五个方程，可得：P03/35，P16/35,P26/35，P34/7,马尔可夫信源熵是条件熵 由前一状态Ei发出符号 后转移到后一状态Ej。假设在这个转移中能发出l种符号，则就有L条同方向的转移线，且各条转移线上的转移概率为。那么从Ei状态转移到Ej状态的总转移概率为 若从Ei状态转移到后一状态有多种可能性，则信源

27、由Ei状态发出一个符号的 为,再进一步，对前一状态Ei的全部可能性作统计平均，就得出马尔可夫信源熵H为 其中，熵函数 表示信源处于某一状态Si时发出一个消息符号的平均不确定性；p(i)是马尔可夫链的平稳分布。需注意，虽然马尔可夫信源发出的是符号序列消息，但上式计算的信源熵的单位是bit/符号。,二、各种离散信源的时间熵 信源的时间熵在单位时间内信源发出的平均信息量，单位 为s(秒)或其他特定的时间单位 1.发出单个符号消息的离散无记忆信源的时间熵 已知离散无记忆信源各符号的概率空间 由于发出各符号所占有时间是不同的 可设符号X1的长度为b1，X2为b2，Xi为bi，XN为bN 单位均为s(秒)

28、则信源各符号的平均长度是各个的概率加权平均值，即,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,