第2章信源与信息熵-Qtech.ppt

《第2章信源与信息熵-Qtech.ppt》由会员分享，可在线阅读，更多相关《第2章信源与信息熵-Qtech.ppt（85页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1联络邮箱：联络邮箱：联络邮箱：联络邮箱：密码：密码：密码：密码：1234561234562第第第第2 2章章章章 信源与信息熵信源与信息熵信源与信息熵信源与信息熵v信源描述与分类信源描述与分类信源描述与分类信源描述与分类v离散信源的信息熵和互信息离散信源的信息熵和互信息离散信源的信息熵和互信息离散信源的信息熵和互信息v离散序列信源的熵离散序列信源的熵离散序列信源的熵离散序列信源的熵v连续信源的熵与互信息连续信源的熵与互信息连续信源的熵与互信息连续信源的熵与互信息v冗余度冗余度冗余度冗余度32.12.1信源的描述与分类信源的描述与分类信源的描述与分类信源的描述与分类v信源是产生消息（符号）、消

2、息序列和连续消息信源是产生消息（符号）、消息序列和连续消息信源是产生消息（符号）、消息序列和连续消息信源是产生消息（符号）、消息序列和连续消息的来源。从数学上，由于消息的不确定性，因此，的来源。从数学上，由于消息的不确定性，因此，的来源。从数学上，由于消息的不确定性，因此，的来源。从数学上，由于消息的不确定性，因此，信源是产生随机变量、随机序列和随机过程的源信源是产生随机变量、随机序列和随机过程的源信源是产生随机变量、随机序列和随机过程的源信源是产生随机变量、随机序列和随机过程的源v信源的基本特性是信源的基本特性是信源的基本特性是信源的基本特性是具有随机不确定性具有随机不确定性具有随机不确定性

3、具有随机不确定性42.12.1信源特性与分类信源特性与分类信源特性与分类信源特性与分类v分类分类分类分类 时间时间时间时间 离散离散离散离散 连续连续连续连续 幅度幅度幅度幅度 离散离散离散离散 连续连续连续连续 记忆记忆记忆记忆 有有有有 无无无无 三大类：三大类：三大类：三大类：单符号离散信源单符号离散信源单符号离散信源单符号离散信源 符号序列信源（有记忆和无记忆）符号序列信源（有记忆和无记忆）符号序列信源（有记忆和无记忆）符号序列信源（有记忆和无记忆）连续信源连续信源连续信源连续信源52.12.1信源描述与分类信源描述与分类信源描述与分类信源描述与分类v描述：通过描述：通过概率空间概率空

4、间描述描述u单符号离散信源单符号离散信源 例如：对二进制数字与数据信源例：扔色子62.12.1信源描述与分类信源描述与分类信源描述与分类信源描述与分类uu连续信源连续信源连续信源连续信源有的信源输出的消息也是单个符号，但消息的数量是无限的，如符号集A的取值是介于a和b之间的连续值，或者取值为实数集R等。7条件概率条件概率条件概率条件概率v定义定义定义定义条件概率条件概率就是事件 A 在另外一个事件 B 已经发生条件下的发生概率。条件概率表示为 P(A|B)，读作“在 B 条件下 A 的概率”。联合概率联合概率表示两个事件共同发生的概率。A 与 B 的联合概率表示为P(A,B)。82.12.1信

5、源描述与分类信源描述与分类信源描述与分类信源描述与分类vv有记忆信源有记忆信源有记忆信源有记忆信源 一般情况一下，信源在不同时刻发出的符号之间是相互一般情况一下，信源在不同时刻发出的符号之间是相互一般情况一下，信源在不同时刻发出的符号之间是相互一般情况一下，信源在不同时刻发出的符号之间是相互依赖的。依赖的。依赖的。依赖的。表征方法：引入条件概率来反映信源发出符号序列内各个符号之间的记忆特征。92.12.1信源描述与分类信源描述与分类信源描述与分类信源描述与分类uu离散序列信源离散序列信源离散序列信源离散序列信源以以3 3位位PCMPCM信源为例信源为例实际信源输出的信息往往是由一系列符号组成，

6、这种用每次发出1组含2个以上符号的符号序列来代表一个消息的信源叫做发出符号序列的信源。要用随机序列来描述信源输出的消息，用联合概率分布来表示信源特性。102.12.1信源描述与分类信源描述与分类信源描述与分类信源描述与分类 当当当当p p（p0=p1p0=p1）=1/2=1/2112.22.2离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息v信息量信息量信息量信息量uu自信息量自信息量uu联合自信息量联合自信息量uu条件自信息量条件自信息量v单符号离散信源熵单符号离散信源熵单符号离散信源熵单符号离散信源熵uu符号熵符号熵uu条件熵条件熵uu联合熵联合熵122.22.2离

7、散信源熵与互信息离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息v信息信息信息信息 不确定性的消除不确定性的消除v信息的度量信息的度量信息的度量信息的度量 随机性、概率随机性、概率 相互独立符合事件概率相乘、信息相加相互独立符合事件概率相乘、信息相加v熵熵熵熵 事件集的平均不确定性事件集的平均不确定性132.22.2离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息G直观推导信息测度直观推导信息测度直观推导信息测度直观推导信息测度C C信息信息信息信息I I应该是消息概率应该是消息概率应该是消息概率应该是消息概率p p的递降函数的递降函数的递降函数的递降函数C C由

8、两个不同的消息（相互统计独立）所提供的信息由两个不同的消息（相互统计独立）所提供的信息由两个不同的消息（相互统计独立）所提供的信息由两个不同的消息（相互统计独立）所提供的信息等于它们分别提供信息之和（可加性）等于它们分别提供信息之和（可加性）等于它们分别提供信息之和（可加性）等于它们分别提供信息之和（可加性）142.22.2离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息l定义：对于给定的离散概率空间表示的信源，定义：对于给定的离散概率空间表示的信源，定义：对于给定的离散概率空间表示的信源，定义：对于给定的离散概率空间表示的信源，x=ax=ai i事件所对应的（自）信息

9、为事件所对应的（自）信息为事件所对应的（自）信息为事件所对应的（自）信息为 以以以以2 2为底，为底，为底，为底，单位单位单位单位为比特（为比特（为比特（为比特（bit)bit)以以以以e e为底，单位为奈特（为底，单位为奈特（为底，单位为奈特（为底，单位为奈特（nat)1nat=1.433bitnat)1nat=1.433bit 以以以以1010为底，单位为笛特（为底，单位为笛特（为底，单位为笛特（为底，单位为笛特（det)1det=3.322bitdet)1det=3.322bit15v例：若发出二进制码元例：若发出二进制码元例：若发出二进制码元例：若发出二进制码元0 0和和和和1 1信源

10、，当符号概率为信源，当符号概率为信源，当符号概率为信源，当符号概率为0出现的概率小，因而一旦出现，给予观察者的信息量就很大。16vv符号的不确定度符号的不确定度符号的不确定度符号的不确定度 具有某种概率的信源符号在发出前，存在不确定度，不确定度表具有某种概率的信源符号在发出前，存在不确定度，不确定度表具有某种概率的信源符号在发出前，存在不确定度，不确定度表具有某种概率的信源符号在发出前，存在不确定度，不确定度表征该符号的特性。征该符号的特性。征该符号的特性。征该符号的特性。自信息量与符号不确定度的区别：1、不确定度是信源符号固有的，不管符号是否发出 2、自信息量是信源符号发出后给予收信者的17

11、vv自信息量特性：自信息量特性：自信息量特性：自信息量特性：1、2、3、非负性由于一个符号出现在概率总是在闭区间0，1内，所以自信息量为非负值。4、单调递减性 若5、可加性 若有两个符号同时出现，可用联合概率来表示，这时自信息量为当它们相互独立时，有，那么就有若两个符号的出现不是独立的，而是有相互联系的，则可用条件概率，它们的自信息量可定义为条件概率对数的负值18例题例题例题例题2-32-3v英文字母英文字母英文字母英文字母“e e”的出现概率为的出现概率为的出现概率为的出现概率为0.1050.105，“c c”的出现的出现的出现的出现概率为概率为概率为概率为0.0230.023，“o o”的

12、出现概率为的出现概率为的出现概率为的出现概率为0.0010.001，求它，求它，求它，求它们的自信息量。们的自信息量。们的自信息量。们的自信息量。v解：根据公式解：根据公式解：根据公式解：根据公式 ，v“e e”的自信息量：的自信息量：的自信息量：的自信息量：I I（e e）=-lb(0.105)=3.25B=-lb(0.105)=3.25Bv“c c”的自信息量：的自信息量：的自信息量：的自信息量：I I（c)=-lb(0.023)=5.44Bc)=-lb(0.023)=5.44Bv“o o”的自信息量：的自信息量：的自信息量：的自信息量：I I（o)=-lb(0.001)=9.97Bo)=

13、-lb(0.001)=9.97B192.22.2离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息l l定义：联合概率空间中任一联合事件的联合（自）定义：联合概率空间中任一联合事件的联合（自）定义：联合概率空间中任一联合事件的联合（自）定义：联合概率空间中任一联合事件的联合（自）信息量为：信息量为：信息量为：信息量为：定义：联合概率空间中，事件定义：联合概率空间中，事件x x在事件在事件y y给定条件下的条给定条件下的条件件（自）信息量为：（自）信息量为：202.22.2离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息vv联合自信息、条件自信息与自

14、信息间的关系联合自信息、条件自信息与自信息间的关系联合自信息、条件自信息与自信息间的关系联合自信息、条件自信息与自信息间的关系212.22.2离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息 例例例例1 1 设在一正方形棋盘上共有设在一正方形棋盘上共有设在一正方形棋盘上共有设在一正方形棋盘上共有6464个方格，如果甲将个方格，如果甲将个方格，如果甲将个方格，如果甲将一粒棋子随意地放在棋盘中的某方格内，让乙猜测一粒棋子随意地放在棋盘中的某方格内，让乙猜测一粒棋子随意地放在棋盘中的某方格内，让乙猜测一粒棋子随意地放在棋盘中的某方格内，让乙猜测棋子所在的位置：棋子所在的位置：

15、棋子所在的位置：棋子所在的位置：（1 1）将方格按顺序编号，令乙猜测棋子所在方格）将方格按顺序编号，令乙猜测棋子所在方格）将方格按顺序编号，令乙猜测棋子所在方格）将方格按顺序编号，令乙猜测棋子所在方格的顺序号的顺序号的顺序号的顺序号 （2 2）将方格按行和列编号，甲将棋子所在的方格）将方格按行和列编号，甲将棋子所在的方格）将方格按行和列编号，甲将棋子所在的方格）将方格按行和列编号，甲将棋子所在的方格的行（或列）编号告诉乙，再令乙猜测棋子所在列的行（或列）编号告诉乙，再令乙猜测棋子所在列的行（或列）编号告诉乙，再令乙猜测棋子所在列的行（或列）编号告诉乙，再令乙猜测棋子所在列（或行）所在的位置（或

16、行）所在的位置（或行）所在的位置（或行）所在的位置。222.22.2离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息 解：由于甲将一粒棋子随意地放在棋盘中的某方格内，解：由于甲将一粒棋子随意地放在棋盘中的某方格内，解：由于甲将一粒棋子随意地放在棋盘中的某方格内，解：由于甲将一粒棋子随意地放在棋盘中的某方格内，因此棋子在棋盘中所处位置为二维等概率分布因此棋子在棋盘中所处位置为二维等概率分布因此棋子在棋盘中所处位置为二维等概率分布因此棋子在棋盘中所处位置为二维等概率分布 （2 2）条件（自）信息量为）条件（自）信息量为 （1 1）联合（自）信息量为）联合（自）信息量为232

17、.22.2离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息 例例2.一个布袋内放一个布袋内放100个球，其中个球，其中80个球为红色，个球为红色，20球为白色。若随机摸取一个球，猜测其颜色，求平均摸球为白色。若随机摸取一个球，猜测其颜色，求平均摸取一次所获得的（自）信息量。取一次所获得的（自）信息量。解：随机事件的概率空间为解：随机事件的概率空间为242.2离散信源熵与互信息离散信源熵与互信息v单符号离散信源熵单符号离散信源熵l定义：对于给定离散概率空间表示的信源所定义的自定义：对于给定离散概率空间表示的信源所定义的自信息量的数学期望为信息量的数学期望为信源的信息熵，信

18、源的信息熵，单位为单位为比特比特/符符号号信源熵是在平均意义上来表征信源的总体特性，它是信源X的函数，一般写成H（X）25vv例：设信源符号集例：设信源符号集例：设信源符号集例：设信源符号集每个符号发生的概率分别为，则信源熵为：例：电视屏幕上约有个格点，按每点有10个不同的灰度等级考虑，则可组成个不同画面。按等概率计算，平均每个画面可提供的信息量为另外有一篇千字文章，假定每字可从万字表中任选，则不同的千字文的总篇数为平均每篇千字文可提供的信息量为26例例例例2-72-7v二元信源是离散信源的一个特例。该信源二元信源是离散信源的一个特例。该信源二元信源是离散信源的一个特例。该信源二元信源是离散信

19、源的一个特例。该信源XX输出输出输出输出符号只有符号只有符号只有符号只有2 2个个个个：（：（：（：（0 0，1 1），其发生概率分别为），其发生概率分别为），其发生概率分别为），其发生概率分别为p p，q q，p+q=1p+q=1，信源的概率空间为：，信源的概率空间为：，信源的概率空间为：，信源的概率空间为：v二元信源熵为：二元信源熵为：二元信源熵为：二元信源熵为：H(X)=-plogp-qlogq=-H(X)=-plogp-qlogq=-plogp-(1-p)log(1-p)=H(p)plogp-(1-p)log(1-p)=H(p)27例例例例2-72-7vv二元信源熵为：二元信源熵为：二

20、元信源熵为：二元信源熵为：H(X)=-plogp-H(X)=-plogp-qlogq=-plogp-(1-p)log(1-qlogq=-plogp-(1-p)log(1-p)=H(p)p)=H(p)vvP P的取值空间在的取值空间在的取值空间在的取值空间在00，11区间区间区间区间；H(p)H(p)的的的的曲线如图所示。曲线如图所示。曲线如图所示。曲线如图所示。vv如二元信源的输出符号是确定的，如二元信源的输出符号是确定的，如二元信源的输出符号是确定的，如二元信源的输出符号是确定的，即即即即p=1p=1或或或或q=1q=1，则该信源不提供任何信，则该信源不提供任何信，则该信源不提供任何信，则该

21、信源不提供任何信息；反之，二元信源符号息；反之，二元信源符号息；反之，二元信源符号息；反之，二元信源符号0 0或或或或1 1以等概以等概以等概以等概率发生时，信源熵达到最大值，等于率发生时，信源熵达到最大值，等于率发生时，信源熵达到最大值，等于率发生时，信源熵达到最大值，等于1bit1bit。282.22.2离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息vv离散信源条件熵离散信源条件熵离散信源条件熵离散信源条件熵l l定义：对于给定离散概率空间表示的信源所定义的定义：对于给定离散概率空间表示的信源所定义的定义：对于给定离散概率空间表示的信源所定义的定义：对于给定离散概

22、率空间表示的信源所定义的随机变量随机变量随机变量随机变量I I（x/y)x/y)在集合在集合在集合在集合XX上的数学期望为给定上的数学期望为给定上的数学期望为给定上的数学期望为给定y y条条条条件下件下件下件下信源的条件熵，信源的条件熵，信源的条件熵，信源的条件熵，单位为单位为单位为单位为比特比特比特比特/序列序列序列序列Y为条件的集合为条件的集合292.22.2离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息l l定义：对于给定离散概率空间表示的信源所定义的定义：对于给定离散概率空间表示的信源所定义的定义：对于给定离散概率空间表示的信源所定义的定义：对于给定离散概率空

23、间表示的信源所定义的随机变量随机变量随机变量随机变量I I（x x，y)y)的数学期望为集合的数学期望为集合的数学期望为集合的数学期望为集合XX和集合和集合和集合和集合Y Y的的的的信源联合熵，信源联合熵，信源联合熵，信源联合熵，单位为单位为单位为单位为比特比特比特比特/序列序列序列序列302.22.2离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息离散信源熵与互信息vv联合熵、条件熵与熵的关系联合熵、条件熵与熵的关系联合熵、条件熵与熵的关系联合熵、条件熵与熵的关系解：可直接求出：解：可直接求出：联合概率：联合概率：同理可得：同理可得：则条件熵：则条件熵：从而得到联合熵：从而得到联合熵：

24、31例2-8：一个二进制信源x发出符号集0，1，经过离散无记忆信道传输，信道输出用Y表示。由于信道中存在噪声，接受端受到0和1的符号外，还有不确定的符号，有“？”表示。已知X的先验概率为符号转移概率为其余为0；求：H(x),H(Y|X),H(X,Y),H(X|Y)32例：二进制通信系统使用符号0和1，由于存在失真，传输时会产生误码，用符号表示下列事件。U0：一个0发出；u1:一个1发出；v0：一个0收到；v1：一个1收到。给定下列概率：（1）已知发出一个0，求收到符号后得到的信息量；（2）已知发出的符号，求收到符号后得到的信息量；（3）已知发出和收到的符号，求能得到的信息量；（4）已知收到的符

25、号，求被告知发出的符号得到的信息量。解：（1）（2）联合概率（3）方法）方法1：方法方法2：因为：因为（4）可以求得：）可以求得：方法方法1：方法方法2：利用贝叶斯定理：利用贝叶斯定理同样：同样：3334内容回顾内容回顾v自信息量：自信息量：v单符号离散信源熵单符号离散信源熵v离散信源条件熵离散信源条件熵离散信源条件熵离散信源条件熵v离散信源联合熵离散信源联合熵离散信源联合熵离散信源联合熵35362.2离散信源熵与互信息离散信源熵与互信息v单符号离散信源互信息单符号离散信源互信息l例例2-8中中 ，在已知，在已知Y（或接收到）后，（或接收到）后，X的不确定度减少了。不确定度的减少量就是接收的不

26、确定度减少了。不确定度的减少量就是接收者通过者通过信道传输信道传输收到的信源收到的信源X的信息量，称为的信息量，称为X与与Y的互信息的互信息I(X;Y);372.2离散信源熵与互信息离散信源熵与互信息v定义：对于给定离散概率空间表示的信源，在出现定义：对于给定离散概率空间表示的信源，在出现y事件后所提供有关事件事件后所提供有关事件x的信息量定义为互信息，的信息量定义为互信息，单位为单位为比特；比特；符号后验概率与先验概率比值的对数；符号后验概率与先验概率比值的对数；382.2离散信源熵与互信息离散信源熵与互信息v单符号离散信源互信息单符号离散信源互信息单符号离散信源互信息单符号离散信源互信息3

27、9v条件互信息量与联合互信息量条件互信息量与联合互信息量l定义：对于给定离散概率空间表示的信源，在事定义：对于给定离散概率空间表示的信源，在事件件z给定条件下，事件给定条件下，事件x与事件与事件y之间的条件互信之间的条件互信息量为：息量为：2.2离散信源熵与互信息离散信源熵与互信息40v条件互信息量与联合互信息量条件互信息量与联合互信息量条件互信息量与联合互信息量条件互信息量与联合互信息量l定义：对于给定离散概率空间表示的信源，在事定义：对于给定离散概率空间表示的信源，在事定义：对于给定离散概率空间表示的信源，在事定义：对于给定离散概率空间表示的信源，在事件件件件x x与联合事件与联合事件与联

28、合事件与联合事件yzyz之间的联合互信息量为：之间的联合互信息量为：之间的联合互信息量为：之间的联合互信息量为：2.2离散信源熵与互信息离散信源熵与互信息41vvEg1(p23)Eg1(p23)设信源发出设信源发出设信源发出设信源发出8 8种消息符号，各消息等概率发送，种消息符号，各消息等概率发送，种消息符号，各消息等概率发送，种消息符号，各消息等概率发送，各符号分别用各符号分别用各符号分别用各符号分别用3 3位二进码元表示，并输出事件。通过对输位二进码元表示，并输出事件。通过对输位二进码元表示，并输出事件。通过对输位二进码元表示，并输出事件。通过对输出事件的观察来推测信源的输出。假设信源发出

29、的消息为出事件的观察来推测信源的输出。假设信源发出的消息为出事件的观察来推测信源的输出。假设信源发出的消息为出事件的观察来推测信源的输出。假设信源发出的消息为x x4 4，用二进码用二进码用二进码用二进码011011表示。作为观察者，已知信源各消息符表示。作为观察者，已知信源各消息符表示。作为观察者，已知信源各消息符表示。作为观察者，已知信源各消息符号等概率出现，但不知道某时刻发出什么符号。当观察道号等概率出现，但不知道某时刻发出什么符号。当观察道号等概率出现，但不知道某时刻发出什么符号。当观察道号等概率出现，但不知道某时刻发出什么符号。当观察道输出的二进制码后，可计算出各消息符号的后验概率，

30、如输出的二进制码后，可计算出各消息符号的后验概率，如输出的二进制码后，可计算出各消息符号的后验概率，如输出的二进制码后，可计算出各消息符号的后验概率，如表所示。表所示。表所示。表所示。2.2离散信源熵与互信息离散信源熵与互信息422.2离散信源熵与互信息离散信源熵与互信息信源输出消息信源输出消息二进制码二进制码后验概率后验概率先验概率先验概率收到收到0后后收到收到01后后收到收到001后后x10001/81/400 x20011/81/400 x30101/81/41/20 x40111/81/41/21x51001/8000 x61011/8000 x71101/8000 x81111/80

31、00等概率二进制码字的后验概率等概率二进制码字的后验概率432.2离散信源熵与互信息离散信源熵与互信息有关有关x4x4的信息量的信息量信源输出符号的先验概率不等时，后验概率的变信源输出符号的先验概率不等时，后验概率的变化情况有所不同，有关化情况有所不同，有关X4的信息量也有所不同；的信息量也有所不同；（自行验证）（自行验证）44v平均平均平均平均互信息量互信息量 其中其中其中其中2.2离散信源熵与互信息离散信源熵与互信息vv平均平均平均平均互信息量的物理含义：互信息量的物理含义：有有扰扰离离散散信信道道上上传传输输的的平平均均信信息息量量，等等于于信信宿宿对对信信源源符符号号不不确定度的平均减

32、少量。确定度的平均减少量。45v熵的性质熵的性质熵的性质熵的性质uu对称性对称性uu非负性非负性uu确定性确定性uu香农辅助定理香农辅助定理uu最大熵定理最大熵定理uu条件熵小于无条件熵条件熵小于无条件熵2.2离散信源熵与互信息离散信源熵与互信息46v非负性非负性非负性非负性2.2离散信源熵与互信息离散信源熵与互信息47v对称性对称性对称性对称性2.2离散信源熵与互信息离散信源熵与互信息48v确定性确定性确定性确定性 v香农辅助定理香农辅助定理香农辅助定理香农辅助定理2.2离散信源熵与互信息离散信源熵与互信息意义：对任意概率分布意义：对任意概率分布意义：对任意概率分布意义：对任意概率分布p p

33、i i，他对其他概率分布，他对其他概率分布，他对其他概率分布，他对其他概率分布q qi i的自的自的自的自信息量信息量信息量信息量 取数学期望时，必然大于其本身的熵。取数学期望时，必然大于其本身的熵。取数学期望时，必然大于其本身的熵。取数学期望时，必然大于其本身的熵。49v最大熵定理（各个符号出现概率相等时，熵最大）最大熵定理（各个符号出现概率相等时，熵最大）最大熵定理（各个符号出现概率相等时，熵最大）最大熵定理（各个符号出现概率相等时，熵最大）v条件熵小于无条件熵条件熵小于无条件熵条件熵小于无条件熵条件熵小于无条件熵2.2离散信源熵与互信息离散信源熵与互信息50v互信息量与熵的关系互信息量与

34、熵的关系互信息量与熵的关系互信息量与熵的关系2.2离散信源熵与互信息离散信源熵与互信息51 2.3离散序列信源的熵离散序列信源的熵v离散无记忆序列信源离散无记忆序列信源离散无记忆序列信源离散无记忆序列信源v离散有记忆序列信源离散有记忆序列信源离散有记忆序列信源离散有记忆序列信源v马尔可夫信源马尔可夫信源马尔可夫信源马尔可夫信源v离散无记忆信源的序列熵离散无记忆信源的序列熵离散无记忆信源的序列熵离散无记忆信源的序列熵v离散有记忆信源的序列熵离散有记忆信源的序列熵离散有记忆信源的序列熵离散有记忆信源的序列熵52v离散无记忆序列信源离散无记忆序列信源离散无记忆序列信源离散无记忆序列信源u布袋摸球实验

35、，若每次取出两个球，由两个布袋摸球实验，若每次取出两个球，由两个布袋摸球实验，若每次取出两个球，由两个布袋摸球实验，若每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先取球的颜色组成的消息就是符号序列。若先取球的颜色组成的消息就是符号序列。若先取球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色放回布袋，再取另一个出一个球，记下颜色放回布袋，再取另一个出一个球，记下颜色放回布袋，再取另一个出一个球，记下颜色放回布袋，再取另一个球。球。球。球。2.3离散序列信源的熵离散序列信源的熵53v离散有记忆序列信源离散有记忆序列信源离散有记忆序列信源离散有记忆序列信源u布袋摸球实验，每次取出

36、两个球，由两个球布袋摸球实验，每次取出两个球，由两个球布袋摸球实验，每次取出两个球，由两个球布袋摸球实验，每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先取出的颜色组成的消息就是符号序列。若先取出的颜色组成的消息就是符号序列。若先取出的颜色组成的消息就是符号序列。若先取出一个球，记下颜色一个球，记下颜色一个球，记下颜色一个球，记下颜色不放回布袋不放回布袋不放回布袋不放回布袋，再取另一个，再取另一个，再取另一个，再取另一个球。球。球。球。2.3离散序列信源的熵离散序列信源的熵v每次得到的消息与前面的消息有关联性，称为每次得到的消息与前面的消息有关联性，称为每次得到的消息与前面的消息有关

37、联性，称为每次得到的消息与前面的消息有关联性，称为“有记忆有记忆有记忆有记忆”。54v马尔可夫信源马尔可夫信源马尔可夫信源马尔可夫信源u当信源的记忆长度为当信源的记忆长度为当信源的记忆长度为当信源的记忆长度为m+1m+1时，该时该发出的时，该时该发出的时，该时该发出的时，该时该发出的符号与前符号与前符号与前符号与前mm个符号有关联性，个符号有关联性，个符号有关联性，个符号有关联性，而与更前面的而与更前面的而与更前面的而与更前面的符号无关符号无关符号无关符号无关。2.3离散序列信源的熵离散序列信源的熵55v马尔可夫信源马尔可夫信源马尔可夫信源马尔可夫信源u由于高阶马尔可夫信源需要引入矢量进行分析

38、，由于高阶马尔可夫信源需要引入矢量进行分析，由于高阶马尔可夫信源需要引入矢量进行分析，由于高阶马尔可夫信源需要引入矢量进行分析，现方法将矢量转化为现方法将矢量转化为现方法将矢量转化为现方法将矢量转化为状态状态状态状态变量。定义状态：变量。定义状态：变量。定义状态：变量。定义状态：u信源在某一时刻出现符号概率信源在某一时刻出现符号概率信源在某一时刻出现符号概率信源在某一时刻出现符号概率x xj j与信源此时所与信源此时所与信源此时所与信源此时所处状态处状态处状态处状态s si i有关，用条件概率表示有关，用条件概率表示有关，用条件概率表示有关，用条件概率表示p(xp(xj j/s/si i),)

39、,状态状态状态状态转移概率表示为转移概率表示为转移概率表示为转移概率表示为p(sp(sj j/s/si i)2.3离散序列信源的熵离散序列信源的熵56v马尔可夫信源马尔可夫信源马尔可夫信源马尔可夫信源u更一般，在时刻更一般，在时刻更一般，在时刻更一般，在时刻mm系统处于状态系统处于状态系统处于状态系统处于状态i i的条件下，经过的条件下，经过的条件下，经过的条件下，经过n-mn-m步后转移至步后转移至步后转移至步后转移至s sj j的概率的概率的概率的概率 2.3离散序列信源的熵离散序列信源的熵57v马尔可夫信源马尔可夫信源马尔可夫信源马尔可夫信源u特别关心特别关心特别关心特别关心n-m=1n

40、-m=1情况，即情况，即情况，即情况，即p pijij(m,m+1)(m,m+1)2.3离散序列信源的熵离散序列信源的熵58v马尔可夫信源马尔可夫信源马尔可夫信源马尔可夫信源u系统在任一时刻可处于状态空间的任意一状态，系统在任一时刻可处于状态空间的任意一状态，系统在任一时刻可处于状态空间的任意一状态，系统在任一时刻可处于状态空间的任意一状态，状态转移时，转移概率是一个矩阵，状态转移时，转移概率是一个矩阵，状态转移时，转移概率是一个矩阵，状态转移时，转移概率是一个矩阵，一步转移一步转移一步转移一步转移转移矩阵为转移矩阵为转移矩阵为转移矩阵为 2.3离散序列信源的熵离散序列信源的熵第第第第i i行

41、元素：从某一状态行元素：从某一状态行元素：从某一状态行元素：从某一状态s si i转移到所有状态转移到所有状态转移到所有状态转移到所有状态s sj j的转的转的转的转移概率，其和为移概率，其和为移概率，其和为移概率，其和为1 1；列元素之和不一定为；列元素之和不一定为；列元素之和不一定为；列元素之和不一定为1 1；59v马尔可夫信源马尔可夫信源马尔可夫信源马尔可夫信源uk k步转移概率步转移概率步转移概率步转移概率p pijij(k)(k)与与与与L L步和步和步和步和k-k-L L步转移概率之间满步转移概率之间满步转移概率之间满步转移概率之间满足切普曼足切普曼足切普曼足切普曼-柯尔莫郭洛夫方

42、程。柯尔莫郭洛夫方程。柯尔莫郭洛夫方程。柯尔莫郭洛夫方程。u定义定义定义定义：如果从状态：如果从状态：如果从状态：如果从状态I I转移到状态转移到状态转移到状态转移到状态j j的概率与的概率与的概率与的概率与mm无关，无关，无关，无关，则称这类则称这类则称这类则称这类MovKovMovKov链为齐次；链为齐次；链为齐次；链为齐次；u对于齐次马尔可夫链，一步转移概率完全决定了对于齐次马尔可夫链，一步转移概率完全决定了对于齐次马尔可夫链，一步转移概率完全决定了对于齐次马尔可夫链，一步转移概率完全决定了k k步转移概率。步转移概率。步转移概率。步转移概率。2.3离散序列信源的熵离散序列信源的熵式子右

43、侧是对第式子右侧是对第L步的所有可能取值求和，也就步的所有可能取值求和，也就是是k步转移概率。步转移概率。60v马尔可夫信源马尔可夫信源马尔可夫信源马尔可夫信源u定义：若齐次马尔可夫链对一切定义：若齐次马尔可夫链对一切定义：若齐次马尔可夫链对一切定义：若齐次马尔可夫链对一切I,jI,j存在不依赖于存在不依赖于存在不依赖于存在不依赖于I I的极限，则称其具有遍历性，的极限，则称其具有遍历性，的极限，则称其具有遍历性，的极限，则称其具有遍历性，p pj j称为平稳分布；称为平稳分布；称为平稳分布；称为平稳分布；2.3离散序列信源的熵离散序列信源的熵61v马尔可夫信源马尔可夫信源马尔可夫信源马尔可夫

44、信源u定理：设有一齐次马尔可夫链，其状态转移定理：设有一齐次马尔可夫链，其状态转移定理：设有一齐次马尔可夫链，其状态转移定理：设有一齐次马尔可夫链，其状态转移矩阵为矩阵为矩阵为矩阵为P P，其稳态分布为，其稳态分布为，其稳态分布为，其稳态分布为wwj j；2.3离散序列信源的熵离散序列信源的熵62u不可约性，对于不可约性，对于任意任意一对一对I和和j，都存在至少一个，都存在至少一个k，使，使pij(k)0.（从（从si开始，总有可能到达开始，总有可能到达sj）u非周期性，非周期性，所有所有pij(n)0的的n中没有比中没有比1大的公因大的公因子。（子。（注：当存在至少一个状态经过一个注：当存在

45、至少一个状态经过一个固定的固定的时间段时间段后连续返回，则这个过程被称为是后连续返回，则这个过程被称为是“周期周期的的”。）u定理：设定理：设P是某一马尔可夫链的状态转移矩阵，是某一马尔可夫链的状态转移矩阵，则该稳态分布存在的充要条件是存在一个正整数则该稳态分布存在的充要条件是存在一个正整数N，使矩阵，使矩阵PN中的所有元素均大于零。中的所有元素均大于零。2.3离散序列信源的熵离散序列信源的熵63vEg.Eg.有一个相对编码器，有一个相对编码器，有一个相对编码器，有一个相对编码器，求平稳分布求平稳分布求平稳分布求平稳分布。2.3离散序列信源的熵离散序列信源的熵u输入码输入码输入码输入码XrXr

46、是相互独立的，取值是相互独立的，取值是相互独立的，取值是相互独立的，取值0 0或或或或1 1，已知，已知，已知，已知P(X=0)=p,P(X=1)=1-p=q;P(X=0)=p,P(X=1)=1-p=q;显然：显然：显然：显然：uY1=X1,Y2=X2 Y1,Y1=X1,Y2=X2 Y1,uYrYr为一个马尔科夫链；（为一个马尔科夫链；（为一个马尔科夫链；（为一个马尔科夫链；（WhyWhy？）？）？）？）64 2.3离散序列信源的熵离散序列信源的熵u且知且知且知且知YrYr序列的条件概率为：序列的条件概率为：序列的条件概率为：序列的条件概率为：u即存在转移矩阵：即存在转移矩阵：即存在转移矩阵：

47、即存在转移矩阵：，其与，其与，其与，其与r r无关，因而是齐无关，因而是齐无关，因而是齐无关，因而是齐次的。其状态转移图如下：次的。其状态转移图如下：次的。其状态转移图如下：次的。其状态转移图如下：该马尔科夫链具有不可约性与非周期性。该马尔科夫链具有不可约性与非周期性。该马尔科夫链具有不可约性与非周期性。该马尔科夫链具有不可约性与非周期性。01qqpp65 2.3离散序列信源的熵离散序列信源的熵u由方程组由方程组由方程组由方程组 可求得稳态概率分布：可求得稳态概率分布：可求得稳态概率分布：可求得稳态概率分布：，所以该马，所以该马，所以该马，所以该马尔科夫链是可遍历的。尔科夫链是可遍历的。尔科夫

48、链是可遍历的。尔科夫链是可遍历的。66vEg.Eg.二阶马氏链，二阶马氏链，二阶马氏链，二阶马氏链，XX 0,1,0,1,求平稳分布求平稳分布求平稳分布求平稳分布。起始状态000110111/21/31/41/51/22/33/44/501 2.3离散序列信源的熵离散序列信源的熵符号其符号条件概率其符号条件概率p(aJ|si)为：为：67 2.3离散序列信源的熵离散序列信源的熵其符号条件概率矩阵为：其符号条件概率矩阵为：68起始状态000110111/201/401/203/4001/301/502/304/5S1(00)S2(01)S3(10)S4(11)2.3离散序列信源的熵离散序列信源的

49、熵其状态转移概率其状态转移概率p(sJ|si)为：为：69 2.3离散序列信源的熵离散序列信源的熵其状态转移矩阵为：其状态转移矩阵为：70 2.3离散序列信源的熵离散序列信源的熵令各状态的稳态分布概率为令各状态的稳态分布概率为W1,W2,W3,W4,则有：则有：可求得：可求得：W1=3/35,W2=6/35,W3=6/35,W4=4/7。7172v离散无记忆信源的序列熵离散无记忆信源的序列熵离散无记忆信源的序列熵离散无记忆信源的序列熵设输出信源为随机序列设输出信源为随机序列X，X=（X1，X2，Xl,XL）,序列中序列中的单个符号的单个符号 2.3离散序列信源的熵离散序列信源的熵73v离散无记

50、忆信源的序列熵离散无记忆信源的序列熵离散无记忆信源的序列熵离散无记忆信源的序列熵当信源无记忆时，当信源无记忆时，2.3离散序列信源的熵离散序列信源的熵74v平均每个符号熵（消息熵）平均每个符号熵（消息熵）2.3离散序列信源的熵离散序列信源的熵v若序列满足平稳性，若序列满足平稳性，即熵与即熵与序号序号L无关，那么无关，那么离散无记忆信源平均每个符号的符号熵等于单个符号离散无记忆信源平均每个符号的符号熵等于单个符号信源的符号熵。信源的符号熵。75v离散有记忆信源的序列熵和消息熵离散有记忆信源的序列熵和消息熵离散有记忆信源的序列熵和消息熵离散有记忆信源的序列熵和消息熵 2.3离散序列信源的熵离散序列