第12章 信源与信息熵.ppt

1,信源与信息熵,第二章,2,2.1 信源的描述和分类 2.2 离散信源熵和互信息 2.3 离散序列信源的熵 2.4 连续信源的熵和互信息 2.5 冗余度,内容,3,本章重点,信源熵和离散/连续互信息,本章难点,离散序列有记忆信源的熵,4,2.1 信源的描述和分类,5,信源,信源 产生消息(符号)、消息序列和连续消息的来源 产生随机变量、随机序列和随机过程的源。 在通信系统中收信者在未收到消息以前对信源发出什么消息是不确定的,是随机的，所以可用随机变量、随机序列或随机过程来描述信源输出的消息,或者说用一个样本空间及其概率测度概率空间来描述信源 信源的基本特性：具有随机不确定性。,6,香农信息论的基本点,用随机变量或随机矢量来表示信源 用概率论和随机过程的理论来研究信息,7,信源,离散信源: 文字、数据、电报随机序列,连续信源: 话音、图像随机过程,信源的分类,按照信源发出的消息在时间上和幅度上的分布情况可将信源分成离散信源和连续信源两大类,连续信源 指发出在时间和幅度上都是连续分布的连续消息（模拟消息）的信源，如语言、图像、图形等都是连续消息。,8,离散 信源,离散无记忆信源,离散有记忆信源,发出单个符号的无记忆信源,发出符号序列的无记忆信源,发出符号序列的有记忆信源,发出符号序列的马尔可夫信源,信源的分类,离散信源 指发出在时间和幅度上都是离散分布的离散消息的信源，如文字、数字、数据等符号都是离散消息。,9,2.1.1 无记忆信源,离散无记忆信源 所发出的各个符号是相互独立的，发出的符号序列中的各个符号之间没有统计关联性，各个符号的出现概率是它自身的先验概率。,例如扔骰子，每次试验结果必然是16点中的某一个面朝上。,用一个离散型随机变量x来描述这个信源输出的消息。,10,发出单个符号的信源 指信源每次只发出一个符号代表一个消息； 发出符号序列的信源 指信源每次发出一组含二个以上符号的符号序列代表一个消息,离散无记忆信源,11,信源的描述,一个离散信源发出的各个符号消息的集合为：,它们的概率分别为,p(xi): xi的先验概率,单符号离散信源的数学模型概率空间,a,b,c,z,12,离散信源的统计特性,离散消息是从有限个符号组成的符号集中选择排列组成的随机序列（组成离散消息的信息源的符号个数是有限的） 在形成消息时，从符号集中选择各个符号的概率不同 。 组成消息的基本符号之间有一定的统计相关特性 。,13,信源的描述,连续信源： 输出在时间和幅度上都是连续分布的消息 单符号连续无记忆信源的概率空间,随机取一节干电池测其电压值作为输出符号,符号取值为0,1.5之间的所有实数。 该信源就是发出单符号的连续无记忆信源,14,信源的描述,发出符号序列的信源,设信源输出的随机序列为 x =(x1x2xlxl) 序列中的变量xlx1,x2, xn 这种由信源x输出的l长随机序列x所描述的信源称为离散无记忆信源x的l次扩展信源,15,信源的描述,随机序列的概率,当信源无记忆时,16,一般情况下,信源在不同时刻发出的符号之间是相互依赖的，也就是信源输出的平稳随机序列x中，各随机变量xl之间是有依赖的。 如在汉字序列中前后文字的出现是有依赖的，不能认为是彼此不相关的。 表述有记忆信源要比表述无记忆信源困难得多 离散有记忆信源 所发出的各个符号的概率是有关联的。 发出符号序列的有记忆信源 发出符号序列的马尔可夫信源,2.1.2 有记忆信源,用信源发出的一个符号序列的整体概率(即联合概率)反映有记忆信源的特征,一个符号出现的概率只与前面一个或有限个符号有关,而不依赖更前面的那些符号,17,概率论基础,无条件概率、条件概率、联合概率的性质和关系 ,18,概率论基础,无条件概率、条件概率、联合概率的性质和关系 ,19,2.1.3 马尔可夫信源,马尔可夫信源 一类相对简单的离散平稳信源 该信源在某一时刻发出字母的概率除与该字母有关外,只与此前发出的有限个字母有关 m阶马尔可夫信源： 信源输出某一符号的概率仅与以前的m个符号有关，而与更前面的符号无关。 条件概率,马氏链的基本概念,一阶马尔可夫信源：,若把有限个字母记作一个状态s，则信源发出某一字母的概率除与该字母有关外，只与该时刻信源所处的状态有关。 信源将来的状态及其送出的字母将只与信源现在的状态有关，而与信源过去的状态无关。,21,马氏链的基本概念,令si = (xi1, xi2, xim) xi1,xi2, xim (a1, a2, an) 状态集s = s1,s2,sq q = nm 信源输出的随机符号序列为：x1, x2,x i-1, x i 信源所处的随机状态序列为：s1,s2,si-1 ,si, 例：二元序列为01011100 考虑m = 2，q = nm =22= 4 s1 = 00 s2 = 01 s3 = 10 s4 = 11 变换成对应的状态序列为 s2 s3 s2 s4 s4 s3 s1,22,马尔可夫信源,设信源在时刻m处于si状态,它在下一时刻(m+1)状态转移到sj的转移概率为： pij(m) = psm+1=sj| sm= si=psj | si pij(m)：基本转移概率（一步转移概率） 若pij(m)与m 的取值无关,则称为齐次马尔可夫链 pij= psm+1=sj| sm= si= ps2=sj| s1= si pij具有下列性质： pij0,23,若信源处于某一状态si ,当它发出一个符号后,所处状态就变了,任何时候信源处于什么状态完全由前一时刻的状态和发出符号决定。 系统在任一时刻可处于状态空间s = s1,s2,sq中的任意一个状态,状态转移时,转移概率矩阵,符号条件概率矩阵,24,例2-1，如图所示是一个相对码编码器,输入的码xr(r=1,2,)是相互独立的，取值0或1，且已知p(x=0)=p, p(x=1)=1p=q，输出的码是yr，显然,yr是一个马氏链,yr确定后,yr+1概率分布只与yr有关,与yr-1 、yr-2 等无关,且知yr序列的条件概率,25,so,s1,p,q,q,p,p00= p(y2=0/y1=0)= p(x=0)= p p01= p(y2=1/y1=0)= p(x=1)= q p10= p(y2=0/y1=1)= p(x=1)= q p11= p(y2=1/y1=1)= p(x=0)= p,26,马尔可夫信源,一个不可约的、非周期的、状态有限的马尔可夫链其k步转移概率pij(k)在k时趋于一个和初始状态无关的极限概率wj，它是满足方程组 的唯一解； wj ：马尔可夫链的一个平稳分布， wj p(sj)就是系统此时处于状态sj的概率。,27,so,s1,1/0.6,0/0.3,0/0.4,s2,1/0.2,0/0.8,1/0.7,例,28,例2-2：有一个二元二阶马尔可夫信源,其信源符号集为0，1，已知符号条件概率： p(0|00) = 1/2 p(1|00)=1/2 p(0|01) = 1/3 p(1|01)=2/3 p(0|10) = 1/4 p(1|10)=3/4 p(0|11) = 1/5 p(1|11)=4/5 求： 信源全部状态及状态转移概率 画出完整的二阶马尔可夫信源状态转移图。 求平稳分布概率,29,状态转移概率矩阵,符号条件概率矩阵,(1)1/2,(0)1/2,30,稳态分布概率,稳态后的符号概率分布,31,例 一个二元二阶马尔可夫信源,其信源符号集为0,1信源开始时：p(0) = p(1) = 0.5发出随机变量x1。 下一单位时间：输出随机变量x2与x1有依赖关系,p(x2|x1),再下一单位时间：输出随机变量x3与x2x1有依赖关系,p(x3|x1x2),32,从第四单位时间开始，随机变量xi只与前面二个单位时间的随机变量xi-2xi-1有依赖关系: p(xi| xi-1 xi-2x2 x1) = p(xi| xi-1 xi-2) (i3) 且 p(xi| xi-1 xi-2) = p(x3| x2x1) (i3),解: 设信源开始处于s0状态,并以等概率发出符号0和1,分别到达状态s1和s2 : 若处于s1 ,以0.3和0.7的概率发出0和1到达s3和s4 若处于s2,以0.4和0.6的概率发出0和1到达s5和s6,00,01,10,11,(0)0.5,(1)0.5,(0)0.3,(0)0.4,(1)0.7,(1)0.6,s1,s2,s0,s6,s5,s4,s3,33,信源发完第2个符号后再发第3个及以后的符号。 从第3单位时间以后信源必处在s3 s4 s5 s6四种状态之一。在i3后,信源的状态转移可用下图表示:,10,11,01,00,(0)0.3,(0)0.4,(1)0.7,(0)0.2,(1)0.8,(1)0.6,(0)0.4,(1)0.6,状态s1和s5功能是完全相同 状态s2和s6功能是完全相同 可将二图合并成,s3,s4,s5,s6,s0,(0)0.5,(1)0.5,s0是过渡状态 s3 s4 s5 s6组成一个不可约闭集,并且具有遍历性。,34,由题意,此马尔可夫信源的状态必然会进入这个不可约闭集,所以我们计算信源熵时可以不考虑过渡状态及过渡过程。 由,得稳态分布概率,35,当马尔可夫信源达到稳定后,符号0和符号1的概率分布：,信源达到稳定后，信源符号的概率分布与初始时刻的概率分布是不同的，所以，一般马尔可夫信源并非是平稳信源。 但当时齐、遍历的马尔可夫信源达到稳定后，这时就可以看成一个平稳信源。：,36,习题,2-1 2-2,37,信源与信息熵,第二章,38,2.1 信源的描述和分类 2.2 离散信源熵和互信息 2.3 离散序列信源的熵 2.4 连续信源的熵和互信 2.5 冗余度,内容,39,离散 信源,离散无记忆信源,离散有记忆信源,发出单个符号的无记忆信源,发出符号序列的无记忆信源,发出符号序列的有记忆信源,发出符号序列的马尔可夫信源,信源的分类,离散信源 指发出在时间和幅度上都是离散分布的离散消息的信源，如文字、数字、数据等符号都是离散消息。,40,信源的描述,一个离散信源发出的各个符号消息的集合为：,它们的概率分别为,p(xi): xi的先验概率,单符号离散信源的数学模型概率空间,41,so,s1,1/0.6,0/0.3,0/0.4,s2,1/0.2,0/0.8,1/0.7,符号 状态,马氏链的基本概念,42,例2-2：有一个二元二阶马尔可夫信源,其信源符号集为0，1，已知符号条件概率： p(0|00) = 1/2 p(1|00)=1/2 p(0|01) = 1/3 p(1|01)=2/3 p(0|10) = 1/4 p(1|10)=3/4 p(0|11) = 1/5 p(1|11)=4/5 求： 信源全部状态及状态转移概率 画出完整的二阶马尔可夫信源状态转移图。 求平稳分布概率,43,00,01,11,10,状态转移概率矩阵,符号条件概率矩阵,(1)1/2,(1)3/4,(0)1/3,(0)1/4,(0)1/2,(0)1/5,(1)2/3,(1)4/5,s2,s1,s4,s3,稳态分布概率,稳态后的符号概率分布,45,2.2 离散信源熵和互信息,46,离散信源熵和互信息,问题： 什么叫不确定度？ 什么叫自信息量？ 什么叫平均不确定度？ 什么叫信源熵？ 什么叫平均自信息量？ 什么叫条件熵？ 什么叫联合熵？ 联合熵、条件熵和熵的关系是什么？,47,离散信源熵和互信息,问题： 什么叫后验概率？ 什么叫互信息量？ 什么叫平均互信息量？ 什么叫疑义度？ 什么叫噪声熵（或散布度）？ 数据处理定理是如何描述的？ 熵的性质有哪些？,48,2.2.1 自信息量,设离散信源x，其概率空间为,如果知道事件xi已发生,则该事件所含有的信息量定义为:,49,自信息量,i (xi) 含义: 当事件xi发生以前,表示事件xi 发生的不确定性 当事件xi发生以后,表示事件xi所含有的信息量 自信息的单位的确定 在信息论中常用的对数底是2,信息量的单位为比特(bit)； 若取自然对数,则信息量的单位为奈特(nat); 若以10为对数底,则信息量的单位为笛特(det) 1 natlog2e l.433 bit， l detlog2103.322 bit,50,自信息量,不确定度 定义： 随机事件的不确定度在数量上等于它的自信息量。 说明: 两者的单位相同，但含义却不相同。 具有某种概率分布的随机事件不管发生与否，都存在不确定度，不确定度表征了该事件的特性，而自信息量是在该事件发生后给予观察者的信息量。,51,自信息量,二进制码元0,1,当符号概率为p(0)=1/4, p(1)=3/4,则这两个符号的自信息量为： i(0) =log2 (1/4)=log24= 2bit i(1) =log2 (3/4) =0.4151 bit,一个以等概率出现的二进制码元(0，1)所包含的自信息量为： i(0)= i(1)= log2 (1/2)=log22=1 bit,一个m位的二进制数,有2m个等概率的可能组合 i=log2(1/2m)=m bit,52,自信息量,i(xi)的特性： i (xi)是非负值 当p(xi) = 1时，i(xi) = 0 当p(xi) = 0时，i(xi) = i(xi)是先验概率p(xi)的单调递减函数，即 当p(x1)p(x2)时，i (x1)i (x2) 两个独立事件的联合信息量等于它们分别的信息量之和。 即统计独立信源的信息量等于它们分别的信息量之和。,53,自信息量,一个出现概率接近于1的随机事件，发生的可能性很大，所以它包含的不确定度就很小； 一个出现概率很小的随机事件，很难猜测在某个时刻它能否发生，所以它包含的不确定度就很大； 若是确定性事件，出现概率为1，则它包含的不确定度为0。,54,自信息量,联合自信息量 两个消息xi，yj同时出现的联合自信息量,注意: 当xi,yj相互独立时，有p(xiyj)=p(xi)p(yj)，那么就有 i(xiyj)=i(xi)+i(yj)。 xiyj所包含的不确定度在数值上也等于它们的自信息量。,55,自信息量,条件自信息量 在事件yj出现的条件下，随机事件xi发生的条件概率为p(xi | yj) ，则它的条件自信息量定义为条件概率对数的负值：,注意: 在给定yj条件下,随机事件xi所包含的不确定度在数值上与条件自信息量相同,但两者含义不同。,56,例 2-3 英文字母中“e” 出现的概率为0.105，“c”出现的概率为0.023，“o”出现的概率为0.001。 分别计算它们的自信息量。,解：“e”的自信息量 i(e) =log2 0.105=3.25 bit “c”的自信息量 i(c) =log2 0.023=5.44 bit “o”的自信息量 i(o) =log2 0.0019.97 bit,57,例 一个布袋内放100个球，其中80个球是红色的，20个球是白色的，若随机摸取一个球，猜测其颜色，求平均摸取一次所能获得的自信息量。 解: 依据题意,这一随机事件的概率空间为,2.2.2 离散信源熵,其中：x1表示摸出的球为红球事件， x2表示摸出的 球是白球事件 .,58,如果摸出的是红球，则获得的信息量是 i (x1)=log2p (x1) = log20.8 bit 如果摸出的是白球，则获得的信息量是 i (x2)=log2p (x2) = log20.2 bit 如果每次摸出一个球后又放回袋中，再进行 下一次摸取。则如此摸取n次，红球出现的次数为np(x1)次，白球出现的次数为 np (x2)次。随机摸取n次后总共所获得的信息量为 np(x1) i (x1)+ np(x2) i (x2),59,平均自信息量,平均随机摸取一次所获得的信息量为,h(x):平均信息量,称为信源x的熵。 信源熵、香农熵,60,离散信源熵,离散信源熵h(x) (平均不确定度/平均信息量/平均自信息量) 定义 信源的平均不确定度h(x)为信源中各个符号不确定度的数学期望，即：,单位为比特/符号或比特/符号序列,61,信源熵,信息熵： 从平均意义上来表征信源的总体信息测度的一个量。 自信息： 指某一信源发出某一消息所含有的信息量。 所发出的消息不同,它们所含有的信息量也就不同。 自信息i (xi)是一个随机变量,不能用它来作为整个信源的信息测度。,62,信源熵,例如有两个信源，其概率空间分别为:,h(y) h(x) 信源y比信源x的平均不确定性要大。,63,信源熵,信源熵具有以下三种物理含意： 信息熵h(x)表示信源输出后,每个离散消息所提供的平均信息量。 信息熵h(x)表示信源输出前,信源的平均不确定性。 信息熵h(x)反映了变量x的随机性,64,例：甲地天气预报,甲地提供的平均信息量大于乙地,乙地天气预报,求：两地天气预报各自提供的平均信息量,65,甲、乙地天气预报为两极端情况：,信源是一确定信源，所以不存在不确定性，信息熵等于零。,limlog=0,66,甲、乙地天气预报为两极端情况：,这种情况下,信源的不确定性最大,信息熵最大。 甲地比乙地提供更多的信息量。因为甲地可能出现的消息数多于乙地可能出现的消息数。,67,例26 电视屏上约有 500 600= 3105个格点，按每点有 10个不同的灰度等级考虑，则共能组成 个不同的画面。按等概率 计算，平均每个画面可提供的信息量为,3 105 3.32 比特/画面,68,有一篇千字文章，假定每字可从万字表中任选，则共有不同的千字文 n=100001000=104000 篇 仍按等概率1/100001000计算，平均每篇千字文可提供的信息量为 h(x) log2n 4 103 3.32 1.3 104 比特/千字文,比较: “一个电视画面”平均提供的信息量远远超过“一篇千字文”提供的信息量。,69,例27 该信源x输出符号只有两个,设为0和1输出符号发生的概率分别为p和q，pq=l。即信源的概率空间为,则二元信源熵为 h(x)= plogpqlogq = plogp (1 p)log(1p) =h(p),70,信源信息熵h(x)是概率p的函数,通常用h(p)表示p取值于0，1区间。 h(p)函数曲线如图所示。,如果二元信源的输出符号是确定的,即p=1或q=1,则该信源不提供任何信息。当二元信源符号0和1以等概率发生时,信源熵达到极大值,等于1比特信息量。,71,几个概念,条件熵 在给定yj条件下，xi的条件自信息量为i(xi| yj), x 集合的条件熵h(x|yj)为,在给定y(即各个yj )条件下,x集合的条件熵h(x|y),72,几个概念,条件熵是在联合符号集合(x,y)上的条件自信息量的联合概率加权统计平均值。 条件熵h(x|y)表示已知y后，x的不确定度。 相应地，在给定x(即各个xi)条件下， y集合的条件熵h(y|x)定义为,73,几个概念,联合熵 联合熵是联合符号集合(x,y)上的每个元素对(xi,yj)的自信息量的概率加权统计平均值。,联合熵h(x,y)表示x 和y同时发生的不确定度。,74,h(xy)与h(x)、h(x/y)之间的关系,h(x,y)h(x)h(y|x) h(x,y)h(y)h(x|y),75,例2-9二进制通信系统用符号“0”和“1”,由于存在失真,传输时会产生误码,用符号表示下列事件： u0：一个“0”发出：u1：一个“1”发出 v0：一个“0”收到；v1：一个“1”收到。 给定下列概率： p(u0)1/2, p(v0 |u0)3/4，p(v0 |u1)=1/2 求： 已知发出一个“0”,求收到符号后得到的信息量； 已知发出的符号,求收到符号后得到的信息量 知道发出的和收到的符号,求能得到的信息量； 已知收到的符号，求被告知发出的符号得到的信息量。,76,解： p(v1 |u0) =1p(v0 |u0) =1/4 联合概率： p(u0v0) = p(v0 |u0) p(u0) = 3/41/2 = 3/8 p(u0v1) = p(v1 |u0) p(u0) = 1/41/2 = 1/8 p(u1v0) = p(v0 |u1) p(u1) = 1/21/2 = 1/4 p(u1v1) = p(v1 |u1) p(u1) = 1p(v0 |u1) =1/21/2 = 1/4,77,解法1： 解法2 h(uv) = h(u) + h(v|u) = 1+0.91 = 1.91比特/符号,78, 解法1 解法2：利用贝叶斯公式: 同理: p(u1|v0)=2/5，p(u0|v1)=1/3，p(u1|v1)=2/3,79,例2-8:一个二进信源x发出符号集0,1,经过离散无记忆信道传输,信道输出用y表示.由于信道中存在噪声,接收端除收到0和1的符号外,还有不确定符号“2” 已知x的先验概率: p(x0)=2/3, p(x1)= 1/3, 符号转移概率： p(y0|x0)=3/4, p(y2|x0)=1/4 p(y1|x1)=1/2, p(y2|x1)=1/2，,x,y,0,1,0,1,2,3/4,1/2,1/2,1/4,信源熵,80,得联合概率： p(x0y0) = p(x0) p(y0 |x0) = 2/33/4 = 1/2 p(x0y1) = p(x0) p(y1 |x0) = 0 p(x0y2) = p(x0) p(y2 |x0) = 2/31/4 = 1/6 p(x1y0) = p(x1) p(y0 |x1) = 0 p(x1y1) = p(x1) p(y1 |x1) = 1/31/2=1/6 p(x1y2) = p(x1) p(y2 |x1) = 1/31/2=1/6 条件熵,由,81,联合熵 h(x,y)h(x)h(y|x)=1.8bit/符号,得 p(y0) = p(xiy0) = p(x0y0) +p(x1y0) =1/2+0 = 1/2 p(y1) = p(xiy1) = p(x0y1) +p(x1y1) = 0+1/6 =1/6 p(y2) = p(xiy2) = p(x0y2) +p(x1y2) = 1/6+1/6=1/3,由,82,由,得,同理 p(x0 |y1)=0 ； p(x1 |y1)=1 p(x0 |y2)=1/2； p(x1 |y2)=1/2,83,概率论基础,无条件概率、条件概率、联合概率的性质和关系 ,84,概率论基础,无条件概率、条件概率、联合概率的性质和关系 ,85,习题,2-5 2-7,86,信源与信息熵,第二章,87,2.1 信源的描述和分类 2.2 离散信源熵和互信息 2.3 离散序列信源的熵 2.4 连续信源的熵和互信 2.5 冗余度,内容,88,2.2 离散信源熵和互信息,89,离散信源熵和互信息,问题： 什么叫不确定度？ 什么叫自信息量？ 什么叫平均不确定度？ 什么叫信源熵？ 什么叫平均自信息量？ 什么叫条件熵？ 什么叫联合熵？ 联合熵、条件熵和熵的关系是什么？,90,离散信源熵和互信息,问题： 什么叫后验概率？ 什么叫互信息量？ 什么叫平均互信息量？ 什么叫疑义度？ 什么叫噪声熵（或散布度）？ 数据处理定理是如何描述的？ 熵的性质有哪些？,91,自信息量,设离散信源x，其概率空间为,i (xi) 含义: 当事件xi发生以前,表示事件xi 发生的不确定性 当事件xi发生以后,表示事件xi所含有的信息量,92,自信息量,自信息量,条件自信息量,联合自信息量,93,离散信源熵,离散信源熵h(x),信源熵具有以下三种物理含意： 信息熵h(x)表示信源输出后,每个离散消息所提供的平均信息量。 信息熵h(x)表示信源输出前,信源的平均不确定性。 信息熵h(x)反映了变量x的随机性 。,94,信源熵,无条件熵,条件熵,联合熵,95,2.2.3 互信息,设有两个随机事件x和y ,x取值于信源发出的离散消息集合, y取值于信宿收到的离散符号集合,有扰信道,干扰源,信源x,信宿y,96,互信息,如果信道是无噪的,当信源发出消息xi后,信宿必能准确无误地收到该消息,彻底消除对xi的不确定度,所获得的信息量就是xi的不确定度i(xi),即xi本身含有的全部信息。 一般而言,信道中总是存在着噪声和干扰,信源发出消息xi,通过信道后信宿只可能收到由于干扰作用引起的某种变型yj 。 信宿收到yj 后推测信源发出xi的概率p(xi|yj)称为后验概率。 信源发出消息xi的概率p(xi) 称为先验概率。,97,互信息,互信息 定义为 xi的后验概率与先验概率比值的对数,互信息i(xi;yj)表示接收到某消息yj后获得的关于事件xi的信息量。,98,例某地二月份天气 构成的信源为：,若得知“今天不是晴天”,把这句话作为收到的消息y1 当收到y1后,各种天气发生的概率变成后验概率了 p(x1|y1) = 0, p(x2|y1) = 1/2 , p(x3|y1) = 1/4 , p(x4|y1) = 1/4,求得自信息量分别为,99,表明从y1分别得到了x2 x3 x4各 1比特的信息量。 消息y1使x2 x3 x4的不确定度各减少1bit 。,100,例2-8:一个二进信源x发出符号集0,1,经过离散无记忆信道传输,信道输出用y表示,由于信道中存在噪声,接收端除收到0和1的符号外,还有不确定符号“2” 已知x的先验概率: p(x0)=2/3, p(x1)= 1/3, 符号转移概率： p(y0|x0)=3/4, p(y2|x0)=1/4 p(y1|x1)=1/2, p(y2|x1)=1/2，,x,y,0,1,0,1,2,3/4,1/2,1/2,1/4,信源熵,101,得联合概率： p(x0y0) = p(x0) p(y0 |x0) = 2/33/4 = 1/2 p(x0y1) = p(x0) p(y1 |x0) = 0 p(x0y2) = p(x0) p(y2 |x0) = 2/31/4 = 1/6 p(x1y0) = p(x1) p(y0 |x1) = 0 p(x1y1) = p(x1) p(y1 |x1) = 1/31/2=1/6 p(x1y2) = p(x1) p(y2 |x1) = 1/31/2=1/6 条件熵,由,102,联合熵 h(x,y)h(x)h(y|x)=1.8bit/符号,得 p(y0) = p(xiy0) = p(x0y0) +p(x1y0) =1/2+0 = 1/2 p(y1) = p(xiy1) = p(x0y1) +p(x1y1) = 0+1/6 =1/6 p(y2) = p(xiy2) = p(x0y2) +p(x1y2) = 1/6+1/6=1/3,由,103,由,得,同理 p(x0 |y1)=0 ； p(x1 |y1)=1 p(x0 |y2)=1/2； p(x1 |y2)=1/2,104,h(x)： 表示接收到输出符号y前关于输入变量x的平均不确定度。 h(x|y)： 表示接收到输出符号y 后关于输入变量x的平均不确定度。,这个对x尚存在的平均不确定度是由于干扰(噪声)引起的,105,平均互信息,平均互信息定义,信息= 先验不确定性后验不确定性 = 不确定性减少的量,y未知,x 的不确定度为h(x) y已知,x 的不确定度变为h(x |y),106,平均互信息,有扰信道,干扰源,信源x,信宿y,通信系统中,若发端的符号为x ,收端的符号为y 如果是一一对应信道,接收到y后,对x的不确定性将完全消除：h(x|y) = 0 一般情况： h(x |y) h(x),即了解y后对x的不确定度将减少 通过信道传输消除了一些不确定性,获得了一定的信息。,107,平均互信息,平均互信息的另一种定义方法：,108,例假设一条电线上串联了8个灯泡x1, x2，x8如图，这8个灯泡损坏的概率相等p(xi) = 1/8，现假设只有一个灯泡已损坏，致使串联灯泡都不能点亮。,未测量前,8个灯泡都有可能损坏,它们损坏的先验概率: p(xi)=1/8,这时存在的不确定性：,109,第1次测量后,可知4个灯泡是好的,另4个灯泡中有一个是坏的,这时后验概率p(xi|y) =1/4 尚存在的不确定性,所获得的信息量就是测量前后不确定性减少的量, 第1次测量获得的信息量：,110,第2次测量后变成猜测哪2个灯泡中一个是损坏的,这时后验概率为： p(xi|yz) = 1/2 尚存在的不确定性：,第2次测量获得的信息量：,第3次测量完全消除了不确定性，能获知哪个灯泡是坏了的。尚存在的不确定性等于零。 第3次测量获得的信息量：,111,要从8个等可能损坏的串联灯泡中确定哪个灯泡是坏的,至少要获得3个bit的信息量,112,互信息量,在有3个变量的情况下,符号xi与符号yj , zk之间的互信息量定义为,同理,113,条件互信息,我们定义在已知事件zk的条件下,接收到yj后获得关于某事件xi的条件互信息,114,平均互信息与各类熵的关系,熵只是平均不确定性的描述; 不确定性的消除(两熵之差)才等于接收端所获得的信息量。 获得的信息量不应该和不确定性混为一谈,115,维拉图,h(x|y),h(x),h(y),h(xy),h(y|x),i(x;y),116,条件熵,h(x|y)：信道疑义度，损失熵 信源符号通过有噪信道传输后所引起的信息量的损失。 信源x的熵等于接收到的信息量加上损失掉的信息量。 h(y|x)：噪声熵，散布熵 它反映了信道中噪声源的不确定性。 输出端信源y 的熵h(y)等于接收到关于x的信息量i(x;y)加上h(y|x),这完全是由于信道中噪声引起的。,117,收发两端的熵关系,118,若信道是无噪一一对应信道,信道传递概率：,计算得:,119,若信道输入端x与输出端y完全统计独立,则:,120,2.2.4 数据处理中信息的变化,数据处理定理 : 当消息通过多级处理器时,随着处理器数目增多,输入消息与输出消息间的平均互信息量趋于变小 假设y条件下x和z相互独立(证明见p26),121,数据处理定理,数据处理定理说明： 当对信号、数据或消息进行多级处理时,每处理一次,就有可能损失一部分信息,也就是说数据处理会把信号、数据或消息变成更有用的形式，但是绝不会创造出新的信息,这就是所谓的信息不增原理。,122,三维联合集xyz上的平均互信息量,123,2.2.5 熵的性质,1.非负性 h(x)h(p1，p2，pn)0 式中等号只有在pi =1时成立。 2.对称性 h(p1，p2，pn) = h(p2，p1，pn) 例如下列信源的熵都是相等的：,124,熵的性质,3.确定性 h(x)h(p1，p2，pn)0 只要信源符号中有一个符号出现概率为1,信源熵就等于零。 4.极值性(香农辅助定理) 对任意两个消息数相同的信源,125,熵的性质,5.最大熵定理 离散无记忆信源输出m个不同的信息符号,当且仅当各个符号出现概率相等时即( pi1/m)熵最大。,6.条件熵小于无条件熵,126,习题,2-13 2-16,127,2.1 信源的描述和分类 2.2 离散信源熵和互信息 2.3 离散序列信源的熵 2.4 连续信源的熵和互信息 2.5 冗余度,内容,128,2.2 离散信源熵和互信息,129,2.2.4 数据处理中信息的变化,数据处理定理 : 当消息通过多级处理器时,随着处理器数目增多,输入消息与输出消息间的平均互信息量趋于变小 假设y条件下x和z相互独立,130,数据处理定理,数据处理定理说明： 当对信号、数据或消息进行多级处理时,每处理一次,就有可能损失一部分信息,也就是说数据处理会把信号、数据或消息变成更有用的形式，但是绝不会创造出新的信息,这就是所谓的信息不增原理。,131,三维联合集xyz上的平均互信息量,132,2.2.5 熵的性质,1.非负性 h(x)h(p1，p2，pn)0 式中等号只有在pi =1时成立。 2.对称性 h(p1，p2，pn) = h(p2，p1，pn) 例如下列信源的熵都是相等的：,133,熵的性质,3.确定性 h(x)h(p1，p2，pn)0 只要信源符号中有一个符号出现概率为1,信源熵就等于零。 4.极值性(香农辅助定理) 对任意两个消息数相同的信源,134,熵的性质,5.最大熵定理 离散无记忆信源输出m个不同的信息符号,当且仅当各个符号出现概率相等时即( pi1/m)熵最大。,6.条件熵小于无条件熵,135,2.3 离散序列信源的熵,136,离散 信源,离散无记忆信源,离散有记忆信源,发出单个符号的无记忆信源,发出符号序列的无记忆信源,发出符号序列的有记忆信源,发出符号序列的马尔可夫信源,2.3.1 离散无记忆信源的序列熵,发出单个符号的信源 指信源每次只发出一个符号代表一个消息； 发出符号序列的信源 指信源每次发出一组含二个以上符号的符号序列代表一个消息。,137,发出符号序列的信源,发出单个符号的信源,138,离散无记忆信源的序列熵,随机序列的概率为,设信源输出的随机序列为 x =(x1x2xlxl) 序列中的变量xlx1,x2, xn x称为离散无记忆信源x的l次扩展信源,139,离散无记忆信源的序列熵,当信源无记忆时,信源的序列熵,140,离散无记忆信源的序列熵,若又满足平稳特性,即与序号l无关时：,信源的序列熵,平均每个符号(消息)熵为,141,例:有一个无记忆信源随机变量x(0,1),等概率分布,若以单个符号出现为一事件,则此时的信源熵:,即用 1比特就可表示该事件。 如果以两个符号出现(l=2的序列)为一事件，则随机序列x(00,01,10,11)，信源的序列熵,即用2比特才能表示该事件。 信源的符号熵,142,例:有一离散平稳无记忆信源,求：二次扩展信源的熵,143,平均每个符号(消息)熵为,信源的序列熵,144,离散有记忆信源的序列熵,对于有记忆信源,就不像无记忆信源那样简单,它必须引入条件熵的概念,而且只能在某些特殊情况下才能得到一些有价值的结论。 对于由两个符号组成的联合信源,有下列结论:,当前后符号无依存关系时,有下列推论：,145,若信源输出一个l长序列,则信源的序列熵为,平均每个符号的熵为：,若当信源退化为无记忆时:,若进一步又满足平稳性时,146,例已知离散有记忆信源中各符号的概率空间为:,设发出的符号只与前一个符号有关,这两个符号的概率关联性用条件概率p(aj|ai)表示,如表,p(aj|ai),求离散信源的序列熵和平均每个符号的熵?,147,由 p(ai,aj) = p(ai) p(aj| ai) 计算得联合概率p(ai aj)如表,当信源符号之间无依赖性时,信源x的信息熵为,当考虑符号之间有依赖性时,计算得条件熵,h(x2| x1)h(x) 信源的条件熵比无依赖时的熵h(x)减少了0.671比特,这正是因为符号之间有依赖性所造成的结果。,148,联合熵h(x1,x2)表示平均每二个信源符号所携带的信息量。 我们用1/2h(x1,x2)作为二维平稳信源x的信息熵的近似值。那么平均每一个信源符号携带的信息量近似为:,符号之间存在关联性,发二重符号序列的熵,比较,149,离散平稳信源,对于离散平稳信源,有下列结论： 条件熵h (xl|xl-1) 随l的增加是非递增的 条件较多的熵必小于或等于条件较少的熵，而条件熵必小于或等于无条件熵。,150, hl(x)是l的单调非增函数 hl(x)hl-1(x) ,h称为平稳信源的极限熵或极限信息量 h0(x)h1(x)h2(x)h(x), l给定时,平均符号熵条件熵： h l(x)h (xl|xl-1),151,马尔可夫信源的信息熵,马尔可夫信源,齐次、遍历的马尔可夫信源的熵,152,s2,s3,1/0.6,1/0.2,0/0.5,s1,1/0.5,1/0.1,0/0.9,例三状态马尔可夫信源,0/0.8,153,154,2.5 冗余度,155,冗余度,冗余度(多余度、剩余度) 表示信源在实际发出消息时所包含的多余信息。 冗余度： 信源符号间的相关性。 相关程度越大,信源的实际熵越小 信源符号分布的不均匀性。 等概率分布时信源熵最大。,156,冗余度,对于有记忆信源,极限熵为h(x)。 这就是说我们需要传送这一信源的信息,理论上只需要传送h(x)即可。但必须掌握信源全部概率统计特性,这显然是不现实的。 实际上,只能算出hm(x)。那么与理论极限值相比,就要多传送hm(x)h(x)。,为了定量地描述信源的有效性,定义:,信息效率,冗余度,157,冗余度,由于信源存在冗余度,即存在一些不必要传送的信息,因此信源也就存在进一步压缩其信息率的可能性。 信源冗余度越大,其进一步压缩的潜力越大。这是信源编码与数据压缩的前提与理论基础。 例：英文字母： 等概率 h0 = log27 = 4.76比特/符号 不等概率 h1 = 4.03比特/符号 考虑相关性 h2 = 3.32比特/符号 极限熵 h =1.4比特/符号 冗余度,英语文章有71%是由语言结构定好的,只有29%是自由选择,158,习题,2-13 2-16 2-26 2-30,159,本章小结,160,信源的描述,一个离散信源发出的各个符号消息的集合为：,它们的概率分别为,p(xi): xi的先验概率,单符号离散信源的数学模型概率空间,a,b,c,z,161,00,01,11,10,状态转移概率矩阵,符号条件概率矩阵,(1)1/2,(