《信息论与编码》课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,信息论基础,B,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,信息论基础,B,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,信息论基础,B,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,2,章 信源与信息熵,信源描述与分类,离散信源的信息熵和互信息,离散序列信源的熵,连续信源的熵与互信息,冗余度,1,2.1,信源的描述与分类,信源是产生消息（符号）、消息序列和连续消息的来源。从数学上，由于消息的不确定性，因此，信源是产生随机变量、随机序列和随机过程的源,信源的基本特性是,具有随机不确定性,2,2.1,信源特性与分类,分类,时间 离散 连续,幅度 离散 连续,记忆 有 无,三大类：,单符号离散信源,符号序列信源（有记忆和无记忆）,连续信源,3,2.1,信源特性与分类,离散无记忆序列信源,布袋摸球实验，若每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色放回布袋，再取另一个球。,4,2.1,信源特性与分类,离散有记忆序列信源,布袋摸球实验，每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色,不放回布袋,，再取另一个球。,5,2.1,信源特性与分类,马尔可夫信源,当信源的记忆长度为,m+1,时，该时该发出的符号与前,m,个符号有关联性，而与更前面的符号无关。,6,2.1,信源描述与分类,描述：通过,概率空间,描述,单符号离散信源,例如：对二进制数字与数据信源,7,2.1,信源描述与分类,连续信源,8,2.1,信源描述与分类,离散序列信源,以,3,位,PCM,信源为例,9,2.1,信源描述与分类,当p=1/2,10,2.1,信源描述与分类,离散无记忆序列信源,布袋摸球实验，若每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色放回布袋，再取另一个球。,11,2.1,信源描述与分类,离散有记忆序列信源,布袋摸球实验，每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色,不放回布袋,，再取另一个球。,12,2.1,信源描述与分类,马尔可夫信源,当信源的记忆长度为,m+1,时，该时该发出的符号与前,m,个符号有关联性，而与更前面的符号无关。,13,2.1,信源描述与分类,马尔可夫信源,由于高阶马尔可夫信源需要引入矢量进行分析，现方法将矢量转化为,状态,变量。定义状态：,信源在某一时刻出现符号概率,x,j,与信源此时所处状态,s,i,有关，用条件概率表示,p(x,j,/s,i,),状态转移概率表示为,p(s,j,/s,i,),14,2.1,信源描述与分类,马尔可夫信源,更一般，经过,n-m,步后转移至,s,j,的概率,15,2.1,信源描述与分类,马尔可夫信源,特别关心,n-m=1,情况，,p,ij,(m,m+1),16,2.1,信源描述与分类,马尔可夫信源,系统在任一时刻可处于状态空间的任意一状态，状态转移时，转移概率是一个矩阵， 一步转移转移矩阵为,17,2.1,信源描述与分类,马尔可夫信源,k,步转移概率,p,ij,(k,),与,l,步和,k-l,步转移概率之间满足切普曼,-,柯尔莫郭洛夫方程。,定义,：如果从状态,I,转移到状态,j,的概率与,m,无关，则称这类,MovKov,链为齐次,对于齐次马尔可夫链，一步转移概率完全决定了,k,步转移概率。,18,2.1,信源描述与分类,马尔可夫信源,定义：若齐次马尔可夫链对一切,I,j,存在不依赖于,I,的极限，则称其具有遍历性，,p,j,称为平稳分布,19,2.1,信源描述与分类,马尔可夫信源,定理：设有一齐次马尔可夫链，其状态转移矩阵为,P,，,其稳态分布为,w,j,20,2.1,信源描述与分类,不可约性，对于任意一对,I,和,j,，,都存在至少一个,k,，使,p,ij,(k,),0.,非周期性，所有,p,ij,(n,),0,的,n,中没有比1,大的公因子。,定理：设,P,是某一马尔可夫链的状态转移矩阵，则该稳态分布存在的充要条件是存在一个正整数,N,，,使矩阵,P,N,中的所有元素均大于零。,21,2.1,信源描述与分类,Eg,.,一个相对编码器，,求平稳分布,22,2.1,信源描述与分类,Eg,.,二阶马氏链，,X,0,1,求平稳分布,起始状态,00,01,10,11,1/2,0,1/4,0,1/2,0,3/4,0,0,1/3,0,1/5,0,2/3,0,4/5,S,1,(00),S,2,(01),S,3,(10),S,4,(11),23,2.2,离散信源熵与互信息,信息量,自信息量,联合自信息量,条件自信息量,单符号离散信源熵,符号熵,条件熵,联合熵,24,2.2,离散信源熵与互信息,信息,不确定性的消除,信息的度量,随机性、概率,相互独立符合事件概率相乘、信息相加,熵,事件集的平均不确定性,25,2.2,离散信源熵与互信息,直观推导信息测度,信息,I,应该是消息概率,p,的,递降函数,由两个不同的消息（相互统计独立）所提供的信息等于它们分别提供信息之和（可加性）,26,2.2,离散信源熵与互信息,定义：对于给定的离散概率空间表示的信源，,x=,a,i,事件所对应的（自）信息为,以,2,为底，,单位,为比特（,bit),以,e,为底，单位为奈特（,nat,) 1nat=1.433bit,以,10,为底，单位为笛特（,det,) 1det=3.322bit,27,2.2,离散信源熵与互信息,定义：联合概率空间中任一联合事件的联合（自）信息量为：,定义：联合概率空间中，事件,x,在事件,y,给定条件下的条件,（自）信息量为,：,28,2.2,离散信源熵与互信息,联合自信息、条件自信息与自信息间的关系,29,2.2,离散信源熵与互信息,Eg1,设在一正方形棋盘上共有,64,个方格，如果甲将一粒棋子随意地放在棋盘中的某方格内，让乙猜测棋子所在的位置：,（,1,）,将方格按顺序编号，令乙猜测棋子所在方格的顺序号,（,2,）将方格按行和列编号，甲将棋子所在的方格的行（或列）编号告诉乙，再令乙猜测棋子所在列（或行）所在的位置,。,30,2.2,离散信源熵与互信息,解：由于甲将一粒棋子随意地放在棋盘中的某方格内，因此棋子在棋盘中所处位置为二维等概率分布,（,1,）,联合（自）信息量为,（,2,）条件（自）信息量为,31,2.2,离散信源熵与互信息,Eg2.,一个布袋内放,100,个球，其中,80,个球为红色，,20,球为白色。若随机摸取一个球，猜测其颜色，求平均摸取一次所获得的（自）信息量。,解：随机事件的概率空间为,32,2.2,离散信源熵与互信息,33,2.2,离散信源熵与互信息,单符号离散信源熵,定义：对于给定离散概率空间表示的信源所定义的随机变量,I,的数学期望为,信源的信息熵,，,单位为,比特,/,符号,34,2.2,离散信源熵与互信息,离散信源条件熵,定义：对于给定离散概率空间表示的信源所定义的随机变量,I,（,x/y),在集合,X,上的数学期望为给定,y,条件下,信源的条件熵,，,单位为,比特,/,序列,35,2.2,离散信源熵与互信息,离散信源联合熵,定义：对于给定离散概率空间表示的信源所定义的随机变量,I,（,x,，,y),的数学期望为集合,X,和集合,Y,的,信源联合熵，,单位为,比特,/,序列,36,2.2,离散信源熵与互信息,联合熵、条件熵与熵的关系,37,2.2,离散信源熵与互信息,单符号离散信源互信息,定义：对于给定离散概率空间表示的信源，在出现,y,事件后所提供有关事件,x,的信息量定义互信息,，,单位为,比特,38,2.2,离散信源熵与互信息,单符号离散信源互信息,39,2.2,离散信源熵与互信息,条件互信息量与联合互信息量,定义：对于给定离散概率空间表示的信源，在事件,z,给定条件下，事件,x,与事件,y,之间的条件互信息量为：,40,2.2,离散信源熵与互信息,条件互信息量与联合互信息量,定义：对于给定离散概率空间表示的信源，在事件,x,与,联合事件,yz,之间的联合互信息量为：,41,2.2,离散信源熵与互信息,Eg1(p23),设信源发出,8,种消息符号，各消息等概发送，各符号分别用,3,位二进码元表示，并输出事件。通过对输出事件的观察来推测信源的输出。假设信源发出的消息,x,4,，,用二进码,011,表示， 接收到每个二进制码元后得到有关,x,4,信息。,42,2.2,离散信源熵与互信息,43,2.2,离散信源熵与互信息,平均互信息量,其中,44,2.2,离散信源熵与互信息,熵的性质,对称性,非负性,确定性,香农辅助定理,最大熵定理,条件熵小于无条件熵,45,2.2,离散信源熵与互信息,非负性,46,2.2,离散信源熵与互信息,对称性,47,2.2,离散信源熵与互信息,确定性,香农辅助定理,48,2.2,离散信源熵与互信息,最大熵定理,条件熵小于无条件熵,49,2.2,离散信源熵与互信息,平均互信息的性质,非负性,互易性,与熵和条件熵及联合熵关系,极值性,凸性函数性质,信息不增性原理,50,2.2,离散信源熵与互信息,非负性,51,2.2,离散信源熵与互信息,互易性,52,2.2,离散信源熵与互信息,平均互信息与熵的关系,53,2.2,离散信源熵与互信息,互信息量与熵的关系,54,2.2,离散信源熵与互信息,极值性,55,2.2,离散信源熵与互信息,凸性函数,当条件概率分布给定时，平均互信息量是输入概率分布的上凸函数,当集合,X,的概率分布保持不变时，平均互信息量是条件概率分布的下凸函数,56,2.2,离散信源熵与互信息,信息不增性,57,2.3,离散序列信源的熵,离散无记忆信源的序列熵,离散有记忆信源的序列熵,58,2.3,离散序列信源的熵,离散无记忆信源的序列熵,59,2.3,离散序列信源的熵,离散无记忆信源的序列熵,平均每个符号熵（消息熵）,60,2.3,离散序列信源的熵,离散有记忆信源的序列熵和消息熵,61,2.3,离散序列信源的熵,Eg,求信源的序列熵和平均符号熵,a,1,a,2,a,3,a,1,a,2,a,3,9/11,1/8,0,2/11,3/4,2/9,0,1/8,7/9,62,2.3,离散序列信源的熵,离散有记忆信源的序列熵和消息熵,结论,1,是,L,的单调非增函数,结论,2,结论,3,是,L,的单调非增函数,结论,4,63,2.3,离散序列信源的熵,马氏链极限熵,64,2.3,离散序列信源的熵,65,2.3,离散序列信源的熵,Eg,求马氏链平均符号熵（三个状态）,66,2.4,连续信源的熵与互信息,幅度连续的单个符号信源熵,67,2.4,连续信源的熵与互信息,幅度连续的单个符号信源熵,68,2.4,连续信源的熵与互信息,波形信源熵,69,2.4,连续信源的熵与互信息,最大熵定理,70,2.4,连续信源的熵与互信息,最大熵定理,限平均功率最大熵定理：对于相关矩阵一定随机变量,X,，,当它是正态分布时具有最大熵,71,2.5,冗余度,冗余,度，表示给定信源在实际发出消息时所包含的多余信息。它来自两个方面，一是,信源符号间的相关性,；二是,信源符号分布的不均匀性,72,2.5,冗余度,Eg,.,计算英文字母冗余度,73,