信源与信息熵分析.ppt

《信源与信息熵分析.ppt》由会员分享，可在线阅读，更多相关《信源与信息熵分析.ppt（74页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第2章章 信源与信息熵信源与信息熵n n信源的描述与分类n n离散信源熵和互信息n n离散序列信源熵n n连续信源熵和互信息n n冗余度1普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.1信源的描述与分类信源的描述与分类n n信源是产生消息（符号）、消息序列和连续消息的来源。从数学上，由于消息的不确定性，因此，信源是产生随机变量、随机序列和随机过程的源n n信源的基本特性是具有随机属性和概率统计特性2普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.1 信源的描述与分类信源的描述与分类n n分类 时间时间 离散离散 连续连续 幅度幅度 离散离散 连续连续 记忆记

2、忆 有有 无无 三大类：三大类：单符号离散信源单符号离散信源 符号序列信源（有记忆和无记忆）符号序列信源（有记忆和无记忆）连续信源连续信源3普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.1 信源的描述与分类信源的描述与分类n n描述：通过概率空间描述uu单符号离散信源单符号离散信源 显然有显然有p p(x xi i)0 0，例如：对二进制数字与数据信源例如：对二进制数字与数据信源4普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.1 信源的描述与分类信源的描述与分类uu连续信源连续信源uu显然应满足显然应满足p pX X(x x)0 0，5普通高等教育“十五”国

3、家级规划教材信息论与编码 曹雪虹等编著2.1 信源的描述与分类信源的描述与分类uu离散序列信源离散序列信源 以以3 3位位PCMPCM信源为例信源为例6普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.1 信源的描述与分类信源的描述与分类 当当p=1/2p=1/27普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著独立同分布信源独立同分布信源 在离散无记忆信源中，信源输出的每个符号在离散无记忆信源中，信源输出的每个符号是是统计独立统计独立的，且具有的，且具有相同的概率空间相同的概率空间，即有，即有 p1(X1)=p(X1)=p(Xi),则该信源是离散平稳无记忆信源，亦称

4、为则该信源是离散平稳无记忆信源，亦称为独立同独立同分布分布(independently identical distribution，i.i.d.)信源信源。8普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n离散有记忆序列信源：离散有记忆序列信源：当信源输出的随机当信源输出的随机矢量中矢量中各个分量之间不相互独立各个分量之间不相互独立而可以是而可以是任意相关的任意相关的,则称此类信源为有记忆信源。则称此类信源为有记忆信源。uu布袋摸球实验，每次取出两个球，由两个球的颜色组成的消息就是符号序列。uu若先取出一个球，记下颜色不放回布袋，再取第二个球。2.1信源的分类及描述信源的分

5、类及描述9普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著用采样定理将波形信号转换成多维连续的信号:n n时域采样：频带受限fm的时间连续函数f(t),不失真采样频率fs 2fm，若时间上受限0 t tB，采样点数为tB(1/2fm)2fmtB。可见，频率受限fm、时间受限tB的任何时间连续函数，完全可以由2fmtB个采样值来描述。随机波形信源随机波形信源10普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n频域频域采样：采样：时间受限于时间受限于t tB B的频域连续函数，在的频域连续函数，在0 02 2 的数字的数字频域上要采频域上要采L L点的条件是时域延拓周

6、期点的条件是时域延拓周期LT LT t tB B，若频率受限，若频率受限f fm m，则采样点数，则采样点数L L t tB B/T/Tt tB Bf fs s 2 2f fm mt tB B。n n但是，从理论上说任何时间受限的函数，其频谱是无限的；但是，从理论上说任何时间受限的函数，其频谱是无限的；反之，任何频带受限的函数，其时间上是无限的。反之，任何频带受限的函数，其时间上是无限的。n n实际中，可认为函数在频带实际中，可认为函数在频带f fm m、时间、时间t tB B以外的取值很小，不以外的取值很小，不至于引起函数的严重失真。至于引起函数的严重失真。随机波形信源随机波形信源11普通高

7、等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n所以，波形信号只要是时间上或频率上有限，都可通过采样变成时间上或频率上离散的连续符号序列。如果原来的随机过程是平稳的，那么采样后的随机序列也是平稳的。n n一般情况下，采样得到的2fmtB个随机变量之间是线性相关的，也就是说这L2fmtB维连续型随机序列是有记忆的。因此随机波形信源也是一种有记忆信源。随机波形信源随机波形信源12普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著（4）马尔可夫信源uu当信源的记忆长度为当信源的记忆长度为m+1m+1时，该时刻发出时，该时刻发出的符号与前的符号与前mm个符号有关联性，而与更前个符

8、号有关联性，而与更前面的符号无关。面的符号无关。uu齐次马尔可夫信源：与时间起点无关。齐次马尔可夫信源：与时间起点无关。13普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n马尔可夫信源uu由于高阶马尔可夫信源需要引入矢量进行由于高阶马尔可夫信源需要引入矢量进行分析，现方法将矢量转化为分析，现方法将矢量转化为状态状态变量。定变量。定义状态：义状态：uu信源在某一时刻出现符号概率信源在某一时刻出现符号概率x xj j与信源此与信源此时所处状态时所处状态s si i有关，用符号条件概率表示有关，用符号条件概率表示p p(x xj j/s si i)，状态转移概率表示为，状态转移概率

9、表示为p p(s sj j/s si i)2.1信源的分类及描述信源的分类及描述14普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n马尔可夫信源uu特别关心特别关心n-m=1n-m=1情况，情况，p pij ij(m,m+1)(m,m+1)2.1信源的分类及描述信源的分类及描述15普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n马尔可夫信源uu系统在任一时刻可处于状态空间的任意一系统在任一时刻可处于状态空间的任意一状态，状态转移时，转移概率是一个矩阵，状态，状态转移时，转移概率是一个矩阵，一步转移概率矩阵为一步转移概率矩阵为2.1信源的分类及描述信源的分类及

10、描述16普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n马尔可夫信源马尔可夫信源uu对于齐次马尔可夫链，一步转移概率完全决定了对于齐次马尔可夫链，一步转移概率完全决定了k k步步转移概率。转移概率。uu定义：若齐次马尔可夫链对一切定义：若齐次马尔可夫链对一切i i,j,j存在不依赖于存在不依赖于i i的极的极限，则称其具有遍历性，限，则称其具有遍历性，p pj j称为平稳分布称为平稳分布2.1信源的分类及描述信源的分类及描述17普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n马尔可夫信源uu定理：设有一齐次马尔可夫链，其状态转定理：设有一齐次马尔可夫链，其状

11、态转移矩阵为移矩阵为P P，其稳态分布为其稳态分布为w wj j=p p(s sj j)2.1信源的分类及描述信源的分类及描述18普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2.3离散序列信源的熵离散序列信源的熵uu不可约性，对于任意一对I和j，都存在至少一个k，使pij(k)0.uu非周期性，所有pij(n)0的n中没有比1大的公因子。uu定理：设P是某一马尔可夫链的状态转移矩阵，则该稳态分布存在的充要条件是存在一个正整数N，使矩阵PN中的所有元素均大于零。19普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2.3离散序列信源的熵离散序列信源的熵n nEg.一

12、个相对编码器，求平稳分布20普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2.3离散序列信源的熵离散序列信源的熵n nEg.二阶马氏链，X0,1,求平稳分布起始状态000110111/201/401/203/4001/301/502/304/5S1(00)S2(01)S3(10)S4(11)21普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著解：令各状态的稳态分布概率为W1，W2，W3，W4，可得方程组 解得稳态分布的概率为：22普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n信息量uu自信息量自信息量uu

13、联合自信息量联合自信息量uu条件自信息量条件自信息量n n单符号离散信源熵uu符号熵符号熵uu条件熵条件熵uu联合熵联合熵23普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n信息n n不确定性不确定性n n信息的度量n n随机性、概率随机性、概率n n相互独立符合事件概率相乘、信息相加相互独立符合事件概率相乘、信息相加n n熵n n事件集的平均不确定性事件集的平均不确定性24普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息G G直观推导信息测度C C信息信息I I应该是消息概率应该

14、是消息概率p p的的递降函数递降函数C C由两个不同的消息（相互统计独立）所提供的信由两个不同的消息（相互统计独立）所提供的信息等于它们分别提供信息之和（可加性）息等于它们分别提供信息之和（可加性）25普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息l l定义：对于给定的离散概率空间表示的信源，x=ai事件所对应的（自）信息为 以以2 2为底，为底，单位单位为比特（为比特（bit)bit)以以e e为底，单位为奈特（为底，单位为奈特（natnat)1nat=1.433bit)1nat=1.433bit 以以1010为底，单位为笛特（为底，单

15、位为笛特（detdet)1det=3.322bit)1det=3.322bit26普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息l l定义：联合概率空间中任一联合事件的联合（自）定义：联合概率空间中任一联合事件的联合（自）信息量为：信息量为：l l定义：联合概率空间中，事件定义：联合概率空间中，事件x x在事件在事件y y给定条件给定条件下的条件下的条件（自）信息量为（自）信息量为：27普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n联合自信息、条件自信息与自信息间的关系联合自信

16、息、条件自信息与自信息间的关系28普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息 例例2.2.一个布袋内放一个布袋内放100100个球，其中个球，其中8080个球为红色，个球为红色，2020球为白色。若随机摸取一个球，猜测其颜色，球为白色。若随机摸取一个球，猜测其颜色，求平均摸取一次所获得的（自）信息量。求平均摸取一次所获得的（自）信息量。解：随机事件的概率空间为解：随机事件的概率空间为29普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息30普通高等教育“十五”国家级规划教材信息论与编

17、码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n单符号离散信源熵l l定义：对于给定离散概率空间表示的信源所定义的随机变量I的数学期望为信源的信息熵，单位为比特/符号31普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n离散信源条件熵离散信源条件熵l l定义：对于给定离散概率空间表示的信源所定义定义：对于给定离散概率空间表示的信源所定义的随机变量的随机变量I I（x/y)x/y)在集合在集合X X上的数学期望为给定上的数学期望为给定y y条件下条件下信源的条件熵，信源的条件熵，单位为单位为比特比特/序列序列32普通高等教

18、育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n离散信源联合熵离散信源联合熵l l定义：对于给定离散概率空间表示的信源所定义定义：对于给定离散概率空间表示的信源所定义的随机变量的随机变量I I（x x，y)y)的数学期望为集合的数学期望为集合X X和集合和集合Y Y的的信源联合熵，信源联合熵，单位为单位为比特比特/序列序列33普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著n n单符号离散信源熵uu符号熵符号熵uu条件熵条件熵uu联合熵联合熵2.2离散信源熵与互信息离散信源熵与互信息34普通高等教育“十五”国家级规划教材信息论与编码

19、 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n联合熵、条件熵与熵的关系联合熵、条件熵与熵的关系35普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n单符号离散信源互信息l l定义：对于给定离散概率空间表示的信源，在出现y事件后所提供有关事件x的信息量定义互信息，单位为比特36普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n单符号离散信源互信息37普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n条件互信息

20、量与联合互信息量l l定义：对于给定离散概率空间表示的信源，在事件z给定条件下，事件x与事件y之间的条件互信息量为：38普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n条件互信息量与联合互信息量l l定义：对于给定离散概率空间表示的信源，在事件x与联合事件yz之间的联合互信息量为：39普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n nEg1(p23)Eg1(p23)设信源发出设信源发出8 8种消息符号，各消息等概发种消息符号，各消息等概发送，各符号分别用送，各符号分别用3 3位

21、二进码元表示，并输出事件。位二进码元表示，并输出事件。通过对输出事件的观察来推测信源的输出。假设通过对输出事件的观察来推测信源的输出。假设信源发出的消息信源发出的消息x x4 4，用二进码用二进码011011表示，表示，接收到每接收到每个二进制码元后得到有关个二进制码元后得到有关x x4 4信息。信息。40普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息41普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n平均互信息量 其中42普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等

22、编著2.2离散信源熵与互信息离散信源熵与互信息n n非负性43普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n互易性44普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n极值性45普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n凸性函数uu当条件概率分布给定时，平均互信息量是输入概率分布的上凸函数uu当集合X的概率分布保持不变时，平均互信息量是条件概率分布的下凸函数46普通高等教育“十五”国家级规划教材信息论与编码 曹

23、雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n信息不增性47普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n熵的性质uu非负性非负性uu对称性对称性uu确定性确定性uu香农辅助定理香农辅助定理uu最大熵定理最大熵定理uu条件熵小于无条件熵条件熵小于无条件熵48普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n非负性49普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n对称性50普通高等教育“十五”国家级规划教

24、材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n确定性 n n香农辅助定理51普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n最大熵定理 n n条件熵小于无条件熵52普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n平均互信息与熵的关系53普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2.2离散信源熵与互信息离散信源熵与互信息n n互信息量与熵的关系54普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2.3离散序列信源的熵

25、离散序列信源的熵n n离散无记忆信源的序列熵n n离散有记忆信源的序列熵55普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2.3离散序列信源的熵离散序列信源的熵n n离散无记忆信源的序列熵56普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2.3离散序列信源的熵离散序列信源的熵n n离散无记忆信源的序列熵n n平均每个符号熵（消息熵）57普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2.3离散序列信源的熵离散序列信源的熵n n离散有记忆信源的序列熵和消息熵58普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2.3离散序列信源的熵离散序

26、列信源的熵n nEg 求信源的序列熵和平均符号熵 a a1 1a a2 2a a3 3a a1 1a a2 2a a3 39/119/111/81/80 02/112/113/43/42/92/90 01/81/87/97/959普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2.3离散序列信源的熵离散序列信源的熵n n离散有记忆信源的序列熵和消息熵结论结论1 1 是是L L的单调非增函数的单调非增函数结论结论2 2结论结论3 3 是是L L的单调非增函数的单调非增函数结论结论4 460普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2.3离散序列信源的熵离散序列信

27、源的熵n n马氏链极限熵61普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2.3离散序列信源的熵离散序列信源的熵62普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2.3离散序列信源的熵离散序列信源的熵n nEg 求马氏链平均符号熵（三个状态）63普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2.4连续信源的熵与互信息连续信源的熵与互信息n n幅度连续的单个符号信源熵64普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2.4连续信源的熵与互信息连续信源的熵与互信息n n幅度连续的单个符号信源熵65普通高等教育“十五”国家级规划教材信息

28、论与编码 曹雪虹等编著 2.4连续信源的熵与互信息连续信源的熵与互信息n n波形信源熵66普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2.4连续信源的熵与互信息连续信源的熵与互信息n n最大熵定理最大熵定理67普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2.4连续信源的熵与互信息连续信源的熵与互信息n n最大熵定理限平均功率最大熵定理：对于相关矩阵一定随机变量限平均功率最大熵定理：对于相关矩阵一定随机变量X X，当它是正态分布时具有最大熵当它是正态分布时具有最大熵68普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2.5冗余度冗余度n n冗余冗

29、余度，表示给定信源在实际发出消息时所包含的多度，表示给定信源在实际发出消息时所包含的多余信息。它来自两个方面，一是余信息。它来自两个方面，一是信源符号间的相关性信源符号间的相关性；二是二是信源符号分布的不均匀性信源符号分布的不均匀性69普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2.5冗余度冗余度n nEgEg.计算英文字母冗余度计算英文字母冗余度70普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著第二章复习第二章复习 概念概念(1)n n信息是可以定量描述的，可以比较大小。由概率决定；n n对应特定信源，可以求出所含不确定度，也就是消除不确定度所需的信息量；n

30、n可通过对信源的观察、测量获得信息，以减少对信源的不确定度；71普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著概念概念(2)n n考虑信源符号概率分布和符号之间的相关性，信源不确定度会下降：n nH(X)就是信源无失真时必需输出的最小信息量；72普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著概念概念(3)n n通过传输，信宿可以得到信息I(X;Y)，从而减小对信源的不确定度：H(X/Y)=H(X)-I(X;Y)n n信息通过系统传输，只会丢失信息，不会增加。丢失部分H(X/Y)是由噪声引起的。73普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著定义、计算公式、相互关系定义、计算公式、相互关系n n自信息量、信源熵、相对熵n n互信息、条件熵、联合熵n n序列熵、平均符号熵、极限熵n n冗余度74普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著