李梅 李亦农 《信息论基础教程》 课件教案 第三章 信源及信源熵.ppt

1、第三章：信源及信源熵,一、信源的分类及其数学模型,二、离散单符号信源,三、离散多符号信源,四、连续信源,信源的分类及其数学模型,第三章：信源及信源熵,信源是产生消息（符号）、消息序列（符号序列）以及时间连续的消息的来源。,信源的主要问题： 如何描述信源的输出（信源的建模问题） 怎样确定信源产生的信息量、产生信息的速率 信源编码 （第五章）,多符号信源,连续信源,信源分类,单符号信源,根据信源输出消息在时间和取值上是离散或连续分类：,本章重点研究离散平稳无记忆信源，以及较简单的有记忆信源马尔可夫信源。,根据信源发出的单个消息取值是离散值还是连续值，信源可分为离散信源/连续信源。,根据信源发出的消

2、息之间是否有统计依赖关系，信源可分为有记忆信源/无记忆信源。,信源的分类及其数学模型,多符号信源,连续信源,信源分类,单符号信源,第三章：信源及信源熵,根据信源发出的消息序列中的消息，统计特性是否 保持不变，信源可分为平稳信源/非平稳信源。,信源的分类及其数学模型,多符号信源,连续信源,信源分类,单符号信源,第三章：信源及信源熵,离散单符号信源,离散单符号信源：输出离散取值的单个符号的信源。 离散单符号信源是最简单、最基本的信源，是组成实际信源的基本单元，可以用一个离散随机变量来表示。,离散单符号信源X的概率空间：,多符号信源,连续信源,单符号信源,信源分类,第三章：信源及信源熵,离散单符号信

3、源（续）,信源输出的所有消息的自信息的 统计平均值，定义为信源的平均自信息（信息熵）：,信息熵表示离散单符号信源的平均不确定性。,多符号信源,连续信源,单符号信源,信源分类,第三章：信源及信源熵,一：信源的分类及其数学模型,二：离散单符号信源,三：离散多符号信源,1. 预备知识 2. 离散平稳无记忆信源 3. 离散平稳有记忆信源 4. 马尔可夫信源 5. 信源的相关性和剩余度,四：连续信源,第三章：信源及信源熵,1. 预备知识,实际信源输出往往是符号序列，称为离散多符号信源。 离散多符号信源可以用随机矢量/随机变量序列来描述，即 一般来说，信源的统计特性随着时间的推移而有所变化。为了便于研究，

4、我们常常假定在一个较短的时间段内，信源是平稳信源。,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,1. 预备知识（续1）,定义1：对于离散随机变量序列 ，若任意两个不同时刻i和j (大于1的任意整数) 信源发出消息的概率分布完全相同，即对于任意的 ， 和 具有相同的概率分布。也就是 即各维联合概率分布均与时间起点无关的信源称为离散平稳信源。,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,1. 预备知识（续2）,对离散平稳信源，由联合概率与条件概率的关系可以推出：,因此：,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,1. 预备知识（续

5、3）,定义2：随机变量序列中，对前N个随机变量的联合熵求平均称为平均符号熵：,如果当 时上式极限存在，则 被称为熵率，或极限熵，记为,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,2. 离散平稳无记忆信源,为了研究离散平稳无记忆信源的极限熵，把信源输出的符号序列看成是一组一组发出的。 例1：电报系统中，可以认为每2个二进制数字组成一组。这样信源输出的是由2个二进制数字组成的一组组符号。这时可以将它们等效看成一个新的信源，它由四个符号00，01，10，11组成，把该信源称为二进制无记忆信源的二次扩展。 例2：如果把每三个二进制数字组成一组，这样长度为3的二进制序列就有8种不同

6、的符号，可等效成一个具有8个符号的信源，把它称为二进制无记忆信源的三次扩展信源。,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,2. 离散平稳无记忆信源（续1）,假定信源输出的是N长符号序列，把它看成是一个新信源，称为离散平稳无记忆信源的N次扩展信源，用N维离散随机矢量来表示： N次扩展信源的概率空间为：,是一个长为N的序列，,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,2. 离散平稳无记忆信源（续2）,N次扩展信源的熵： 离散平稳无记忆信源的N次扩展信源的熵等于离散单符号信源熵的N倍：,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵

7、,2. 离散平稳无记忆信源（续3）,离散平稳无记忆信源的熵率：,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,2. 离散平稳无记忆信源（续4）,例1：设有一离散无记忆信源X，其概率空间为 求该信源的熵率及二次扩展信源的熵。,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,2. 离散平稳无记忆信源（续5）,解： 离散单符号信源熵,比特/符号,熵率：,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,2. 离散平稳无记忆信源（续6）,二次扩展信源的概率空间：,二次扩展信源的熵：,比特/二个符号,单符号信源,连续信源,多符号信源,信源分类,第三章

8、：信源及信源熵,3. 离散平稳有记忆信源,实际信源常常是有记忆信源。设信源输出N长的符号序列，则可以用N维随机矢量 来表示信源，其中每个随机变量之间存在统计依赖关系。 N维随机矢量的联合熵为：,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,3. 离散平稳有记忆信源（续1）,定理：对于离散平稳信源，如果 ，则有,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,3. 离散平稳有记忆信源（续2）,证明：,（1）首先证明极限条件熵存在： 只要X的样本空间有限，则必然有 。 根据条件熵的性质，以及信源的平稳性有,是单调有界数列， 极限 必然存在，且极限为0和 之间的

9、某一个值。,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,3. 离散平稳有记忆信源（续3）,（2）对于收敛的实数列，有以下结论成立： 如果 是一个收敛的实数列，那么,利用上述结论可以推出：,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,3. 离散平稳有记忆信源（续4）,例2：信源X的信源模型为 输出符号序列中，只有前后两个符号之间有记忆，条件概率空间见右边的表。求熵率并比较 H(X) 、H(X2|X1) 、 1/2H(X1X2)。,条件概率,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,3. 离散平稳有记忆信源（续5）,解：,1),比

10、特/符号,2) 如果不考虑符号间的相关性，则信源熵为,比特/符号,3) 如果把信源发出的符号看成是分组发出的，每两个符号为一组，这个新信源的熵为,比特/两个符号,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,3. 离散平稳有记忆信源（续6）,结论：,如何从理论上解释这个结果？,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源,(1) 定义,(2) 熵率,(3) 马尔可夫信源 马尔可夫链,(4) 马尔可夫链,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续1）,实际的有记忆信源，符号间的相关性可以追溯

11、到很远，使得熵率的计算比较复杂。 马尔可夫信源是一类相对简单的有记忆信源。信源在某一时刻发出某一符号的概率，除与该符号有关外，只与此前发出的有限个符号有关。,(1) 定义,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续2）,对于m阶马尔可夫信源，,(2) 熵率,如何计算条件熵？ 条件概率 通常是已知的，我们需要求解的是联合概率 。,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续3）,(3) 马尔可夫信源 马尔可夫链,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续4）,例

12、3： 设一个二元一阶马尔可夫信源，信源符号集为 ， 输出符号的条件概率为,用状态转移图来描述该信源。,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续5）,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续6）,例4： 设一个二元二阶马尔可夫信源，信源符号集为 ，输出符号的条件概率为,求该信源的状态转移图。,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续7）,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续8）,对于 m 阶马尔可夫信源

13、，,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续9）,(4) 马尔可夫链,有限状态马尔可夫链 状态转移概率 齐次马尔可夫链 Chapman-Kolmogorov方程 马尔可夫链的平稳分布,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续10）,马尔可夫链： 设 为一随机序列，如果对所有 ，有 则称 为马尔可夫链。,如果马尔可夫链的状态空间 有限，则被称为有限状态马尔可夫链；如果状态空间 是无穷集合，则被称为可数无穷状态的马尔可夫链。,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可

14、夫信源（续11）,状态转移概率（描述马氏链最重要的参数）： 状态转移概率的性质： 一步转移概率： k步转移概率：,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续12）,齐次马尔可夫链： 如果马氏链状态转移概率与起始时刻无关，即对任意m，有 ，则称为时齐马尔可夫链或齐次马尔可夫链，也称为具有平稳转移概率的马尔可夫链。,齐次马氏链可以用转移概率矩阵或状态转移图来描述。,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续13）,Chapman-Kolmogorov方程：,或用矩阵表示为,单符号信源,连续信源,多符号信源,

15、信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续14）,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续15）,遍历性： 若齐次马尔可夫链， ，存在不依赖于 的极限 且满足 则称其具有遍历性（各态历经性）。 为平稳分布。,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续16）,定理1： 是满足方程组 和 的唯一解。,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续17）,定理2： 设 为马氏链的状态转移矩阵，则该马氏链平稳分布存在的充要条件是，存在一个正整数 ，使矩阵

16、中的所有元素均大于零。,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续18）,例5：求二阶马尔可夫信源的极限熵。,解： 1）首先根据定理2检查该信源是否存在稳态分布：,所有元素均大于0，稳态分布存在。,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续19）,2）设状态的平稳分布为 ，根据定理1有,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续20）,3）求熵率：,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续21）, 如何求信源发

17、出的符号的极限概率？,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,符号的平稳概率分布为：,如果不考虑符号间的相关性，则由符号的平稳概率分布可得信源熵 H(X) = 1比特/符号，而考虑符号间的相关性后，该信源的熵率 0.80 比特/符号,4. 马尔可夫信源（续22）,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,例1：设有一马氏链，其状态转移矩阵为：,问是否存在稳态分布。如果存在，求其极限熵。,4. 马尔可夫信源（续23）,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,5. 信源的相关性和剩余度,信源的相关性就是信源符号间的依赖程度

18、。 对于不同平稳信源可以分别计算它的熵（设信源有q个符号）：,（独立等概信源）,（无记忆信源）,（一阶马尔可夫信源）,（m阶马尔可夫信源）,（记忆长度无限的信源）,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,5. 信源的相关性和剩余度（续）,对同一信源，采用不同的模型（假定相关程度不同），计算得到的熵的关系为,结论： 符号间相关性越大，熵越小。,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,5. 信源的相关性和剩余度（续1）,定义1：熵的相对率,定义2：信源的剩余度,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,英文信源： H0=4

19、.76 H1=4.03 H2=3.32 H3=3.1 H5=1.65 =1.4,5. 信源的相关性和剩余度（续2）,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,英文 法文 德文 西班牙文 中文 （按8千汉字计算）,5. 信源的相关性和剩余度（续3）,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,例 3.7： 计算汉字的剩余度。假设常用汉字约为 10000个，其中 140 个汉字出现的概率占 50%， 625个汉字（含140个）出现的概率占 85%，2400个汉字（含625个）出现的概率占 99.7%，其余 7600个汉字出现的概率占 0.3%，不考虑符

20、号间的相关性，只考虑它的概率分布，在这一级近似下计算汉字的剩余度。,5. 信源的相关性和剩余度（续4）,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,解：为了计算方便，假设每类中汉字出现是等概的，得表,H1=H(X) =9.773 bit/汉字 H0=13.288 bit/汉字,5. 信源的相关性和剩余度（续5）,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,一：信源的分类及其数学模型,二：离散单符号信源,三：离散多符号信源,四：连续信源,1. 连续信源的微分熵 2. 连续信源的最大熵 3. 连续信源的熵功率,第三章：信源及信源熵,单符号信源,多符号信源

21、,信源分类,连续信源,第三章：信源及信源熵,1. 连续信源的微分熵,离散：,（一）数学模型,单符号信源,多符号信源,信源分类,连续信源,第三章：信源及信源熵,1. 连续信源的微分熵 （续1）,单符号信源,多符号信源,信源分类,连续信源,第三章：信源及信源熵,1. 连续信源的微分熵 （续2）,（二）H(X)：信息熵,量化分层,连续,离散,单符号信源,多符号信源,信源分类,连续信源,第三章：信源及信源熵,1. 连续信源的微分熵 （续3）,p(x),-1 -0.5 0 0.5 1 x,单符号信源,多符号信源,信源分类,连续信源,第三章：信源及信源熵,1. 连续信源的微分熵 （续4）,单符号信源,多符

22、号信源,信源分类,连续信源,第三章：信源及信源熵,1. 连续信源的微分熵 （续5）,单符号信源,多符号信源,信源分类,连续信源,第三章：信源及信源熵,1. 连续信源的微分熵 （续6）,微分熵： h(X) 又称为差熵,确定值部分,无限大常数项,同样，我们可以定义两个连续随机变量的联合熵： 及条件熵 并且它们之间也有与离散随机变量一样的相互关系：,单符号信源,多符号信源,信源分类,连续信源,第三章：信源及信源熵,1. 连续信源的微分熵 （续7）,单符号信源,多符号信源,信源分类,连续信源,第三章：信源及信源熵,1. 连续信源的微分熵 （续8）,例3.8：求均匀分布的随机变量的微分熵：,单符号信源,多符号信源,信源分类,连续信源,第三章：信源及信源熵,1. 连续信源的微分熵 （续9）,微分熵无非负性