《[工学]第三章 信源及信源熵》由会员分享，可在线阅读，更多相关《[工学]第三章 信源及信源熵（78页珍藏版）》请在金锄头文库上搜索。
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： 设 为马氏链的状态转移矩阵，则该马氏链平稳分布存在的充要条件是，存在一个正整数 ，使矩阵 中的所有元素均大于零。,单符号信源,连续信源,多符号信源,信源分类,第三章：信源及信源熵,4. 马尔可夫信源（续18）,例5：求二阶马尔可夫信源的极限熵。,解： 1）首先根据定理2检查该信源是否存在稳态分布：,所有元素均大于0，稳态分布存在。,单符号信源,连续信源,多符号信源,信源分类,第三章：信
