第三章 信源及信源熵

第三章信源及信源熵第1页，课件共60页，创作于2023年2月第三章信源及信源熵信源的主要问题：信源的描述（数学建模）；信源输出信息能力的定量分析（信源熵）；信源信息的有效表示（信息编码）。编码器信道译码器信宿噪声源信源第2页，课件共60页，创作于2023年2月第三章信源及信源熵3.1信源的分类及其数学模型3.2离散单符号信源3.3离散多符号信源3.3.1离散平稳信源3.3.2离散平稳无记忆信源3.3.3离散平稳有记忆信源3.3.4马尔可夫信源3.4信源的相关性和剩余度第3页，课件共60页，创作于2023年2月3.1信源的分类及其数学模型信源的分类分类1：根据信源输出的消息在时间和取值上是离散或连续分。时间（空间)取值信源种类举例数学描述离散离散离散信源（数字信源）文字、数据、离散化图像

离散随机变量序列

离散连续连续信号跳远比赛的结果、语音信号抽样以后

连续随机变量序列

连续连续波形信源（模拟信源）

语音、音乐、热噪声、图形、图像

随机过程

连续离散不常见第4页，课件共60页，创作于2023年2月3.1信源的分类及其数学模型分类2：根据各维随机变量的概率分布是否随时间的推移而变化分。 1）平稳信源 2）非平稳信源分类3：根据随机变量间是否统计独立分。 1）有记忆信源 2）无记忆信源第5页，课件共60页，创作于2023年2月3.1信源的分类及其数学模型实际信源分类：信源第6页，课件共60页，创作于2023年2月3.2离散单符号信源定义输出单个离散取值的符号的信源称为离散单符号信源。是最简单也是最基本的信源，是组成实际信源的基本单元。用一个离散随机变量表示。数学模型第7页，课件共60页，创作于2023年2月3.2离散单符号信源信源输出信息能力信源的平均自信息量（信息熵）：信源输出的所有消息的自信息的统计平均值。举例1 二元信源X输出符号只有两个，设为0和1。输出符号发生的概率分别为p和q，p+q=1。即信源的概率空间为则该信源的熵为： 第8页，课件共60页，创作于2023年2月3.2离散单符号信源举例2 掷骰子： 为六元信源。则该信源的熵为： 第9页，课件共60页，创作于2023年2月3.3离散多符号信源定义离散多符号信源：输出为符号序列。用离散随机变量序列（随机矢量）表示，即：举例以抛掷N次硬币为研究对象的试验中文自然语言文字离散多符号信源的实质不是多个信源而是以由一个信源发出的多个符号为研究对象的等价信源。第10页，课件共60页，创作于2023年2月3.3离散多符号信源理清与离散多符号信源相关的几种常见信源的关系：离散平稳信源

离散多符号信源输出的随机变量序列的统计特性往往比较复杂，分析起来比较困难。 为了便于分析，假设信源输出的是平稳随机序列，即：

序列的统计特性与时间的推移（起点）无关。 实际中很多信源也满足这个假设。举例以抛掷N次硬币为研究对象的试验中文自然语言文字离散平稳信源又分为无记忆信源和有记忆信源。均为离散平稳信源第11页，课件共60页，创作于2023年2月3.3离散多符号信源离散平稳无记忆信源

信源发出的各个符号彼此是统计独立的。 对于多符号信源X=(X1X2…XN)，各随机变量Xi(i=1,2,…,N)之间是统计独立的，即： 称该多符号信源为离散无记忆信源的N次扩展信源。举例以抛掷N次硬币为研究对象的试验一般情况下，信源在不同时刻发出的符号之间是相互依赖的，这种信源就为有记忆信源。

第12页，课件共60页，创作于2023年2月3.3离散多符号信源离散平稳有记忆信源

实际上，许多信源发出的符号往往只与前若干个符号的依赖关系强，而与更前面符号的依赖关系弱。因此，在研究分析时可限制随机序列的记忆长度。 当记忆长度为m+1时，称这种有记忆信源为m阶马尔可夫信源，即：

信源每次发出的符号只与前m个符号有关，与更前面的符号无关。举例（离散平稳有记忆信源）中文自然语言文字第13页，课件共60页，创作于2023年2月3.3.1离散平稳信源

定义：对于随机变量序列，在任意两个不同时刻和(和为大于1的任意整数)信源发出消息的概率分布完全相同，即对于任意的，和具有相同的概率分布。也就是:即各维联合概率分布均与时间起点无关的信源称为离散平稳信源。第14页，课件共60页，创作于2023年2月3.3.1离散平稳信源推论1

离散平稳信源的条件概率分布与时间起点无关，只与关联长度N有关。第15页，课件共60页，创作于2023年2月3.3.1离散平稳信源推论2

第16页，课件共60页，创作于2023年2月

离散多符号平稳信源不确定度的度量：

对于离散多符号信源,我们引入熵率的概念，它表示信源输出的符号序列中，平均每个符号所携带的信息量。定义（熵率）：

随机变量序列中，对前N个随机变量的联合熵求平均：

称为平均符号熵。如果当

时上式极限存在，则称为熵率，或称为极限熵，记为

3.3.1离散平稳信源第17页，课件共60页，创作于2023年2月3.3.2离散平稳无记忆信源定义

信源发出的各个符号彼此是统计独立的。 对于多符号信源X=(X1X2…XN)，各随机变量Xi(i=1,2,…,N)之间是统计独立的，即： 称该多符号信源为离散无记忆信源的N次扩展信源。举例以抛掷N次硬币为研究对象的试验

第18页，课件共60页，创作于2023年2月3.3.2离散平稳无记忆信源分析信源熵

N次扩展信源（N长离散平稳无记忆信源）的熵等于单符号离散信源熵的N倍。

对N个独立的随机变量X1,X2,……,XN，有：平稳第19页，课件共60页，创作于2023年2月3.3.2离散平稳无记忆信源熵率 离散平稳无记忆信源的熵率等于单符号离散信源熵。例1

离散无记忆信源为：X:{a1,a2,a3}；P(X):{1/4,1/2,1/4}，试求： 1）该信源的熵； 2）写出该信源的二次扩展信源，并求其概率分布； 3）根据2）中结果求该信源二次扩展信源的信源熵及熵率。第20页，课件共60页，创作于2023年2月3.3.2离散平稳无记忆信源 2）写出该信源的二次扩展信源，并求其概率分布；解： 二次扩展信源为： 信源符号为： 其概率分布为：：{A1…A9}A1=a1a1A2=a1a2A3=a1a3A4=a2a1A5=a2a2A6=a2a3A7=a3a1A8=a3a2A9=a3a3A1A2A3A4A5A6A7A8A91/161/81/161/81/41/81/161/81/16第21页，课件共60页，创作于2023年2月3.3.2离散平稳无记忆信源 3）根据2）中结果求该信源二次扩展信源的信源熵及熵率。 计算可得： 可见：A1A2A3A4A5A6A7A8A91/161/81/161/81/41/81/161/81/16第22页，课件共60页，创作于2023年2月3.3.3离散平稳有记忆信源离散平稳有记忆信源定义

信源发出的符号间相互有依赖关系。分析信源熵独立熵函数的链规则：对N个随机变量X1,X2,……,XN，有：第23页，课件共60页，创作于2023年2月回顾上节课的内容信源及信源熵信源的主要问题信源的描述（数学建模）；信源输出信息能力的定量分析（信源熵）；第24页，课件共60页，创作于2023年2月回顾上节课的内容离散单符号信源数学模型信息熵第25页，课件共60页，创作于2023年2月回顾上节课的内容离散多符号信源描述方法

实质不是多个信源而是以由一个信源发出的多个符号为研究对象的等价信源。信息不确定程度的度量：熵率第26页，课件共60页，创作于2023年2月回顾上节课的内容实际信源分类：信源第27页，课件共60页，创作于2023年2月3.3.3离散平稳有记忆信源离散平稳有记忆信源的几个结论：（1）条件熵

随N的增加是递减的；

含义：记忆长度越长，条件熵越小； 即：序列的统计约束关系增加时，不确定性减少。（2）N给定时平均符号熵大于等于条件熵，即（3）平均符号熵随N的增加是递减的；

含义：序列的统计约束关系增加时，由于符号间的相关性，平均每个符号所携带的信息量减少。第28页，课件共60页，创作于2023年2月3.3.3离散平稳有记忆信源（4）如果，则存在，并且

含义：给出了计算熵率的另一种方法。 法1： 法2： 一般情况下，平稳信源输出的符号序列其相关性可追溯到最初的一个符号，故要准确计算需确定无穷维联合概率和条件概率，这相当困难。为此：

常用N不太大时的平均符号熵或条件熵来作为熵率的近似值。第29页，课件共60页，创作于2023年2月3.3.3离散平稳有记忆信源马尔可夫信源（离散平稳有记忆信源的特例）：定义：信源在某时刻发出的符号仅与在此之前发出的有限个符号有关，而与更早些时候发出的符号无关，这称为马尔可夫性，这类信源称为马尔可夫信源。 如果信源在某时刻发出的符号仅与在此之前发出的m个符号有关，则称为m阶马尔可夫信源。m阶马尔可夫信源熵率计算：马尔可夫性平稳性记忆长度？第30页，课件共60页，创作于2023年2月3.3.3离散平稳有记忆信源例2

离散有记忆信源为：X:{x1,x2,x3}；P(X):{1/4,4/9,11/36}，输出符号序列中，只有前后两个符号有记忆，条件概率P(X2|X1)如下表所示：

求：1）该信源熵率； 2）比较H(X2|X1),½*H(X1X2),H(X)。x1x2x3x17/92/90x21/83/41/8x302/119/11X2X1第31页，课件共60页，创作于2023年2月3.3.3离散平稳有记忆信源解：

1)只有前后两个符号有记忆，故为马尔可夫信源，则： 2）比较H(X2|X1),½*H(X1X2),H(X)。可见：第32页，课件共60页，创作于2023年2月3.3.4马尔可夫信源定义： 信源在某时刻发出的符号仅与在此之前发出的有限个符号有关，而与更早些时候发出的符号无关，这称为马尔可夫性，这类信源称为马尔可夫信源。

随机矢量序列符号序列状态序列（集）马尔可夫链第33页，课件共60页，创作于2023年2月3.3.4马尔可夫信源马尔可夫信源模型：对于一般的阶马尔可夫信源，它的概率空间可以表示成：令，从而得到马尔可夫信源的状态空间为：状态空间由所有状态及状态间的状态转移概率组成。

符号转移概率第34页，课件共60页，创作于2023年2月3.3.4马尔可夫信源状态转移概率计算：马尔可夫链的状态转移图 1）每个圆圈代表一种状态； 2）状态之间的有向线代表某一状态向另一状态的转移； 3）有向线一侧的符号和数字分别代表发出的符号和条件概率。二元一阶马尔可夫信源状态转移图举例：

一阶马尔可夫信源的状态转移概率等于符号转移概率（信源输出符号的条件概率）。

1：0.750：0.50：0.251：0.5第35页，课件共60页，创作于2023年2月3.3.4马尔可夫信源状态转移概率算法（以二元二阶马尔可夫信源为例）： 设一个二元二阶马尔可夫信源，原始符号集为{1,0}，信源输出符号条件概率为： P(0|00)=P(1|11)=0.8P(1|00)=P(0|11)=0.2P(0|01)=P(0|10)=P(1|01)=P(1|10)=0.5试求其状态转移概率。解：1）确定状态数：

由题得：可能的状态为：qm第36页，课件共60页，创作于2023年2月3.3.4马尔可夫信源

2）由条件概率分析状态转移概率：

信源输出符号条件概率为： P(0|00)=P(1|11)=0.8P(1|00)=P(0|11)=0.2P(0|01)=P(0|10)=P(1|01)=P(1|10)=0.5信源的状态为：状态之间的转移概率为：p(s1|s1)=p(s2|s1)=p(s3|s1)=p(s4|s1)=p(s1|s2)=p(s2|s2)=p(s3|s2)=p(s4|s2)=p(s1|s3)=p(s2|s3)=p(s3|s3)=p(s4|s3)=p(s1|s4)=p(s2|s4)=p(s3|s4)=p(s4|s4)=第37页，课件共60页，创作于2023年2月3.3.4马尔可夫信源 则状态转移图为： 也可写作状态转移矩阵形式：01100:0.51:0.20:0.2000:0.8111:0.81:0.50:0.51:0.5ij第38页，课件共60页，创作于2023年2月3.3.4马尔可夫信源m阶马尔可夫信源熵率的计算：即：m阶马尔可夫信源的极限熵H∞等于条件熵Hm+1。（只介绍齐次遍历马尔可夫信源极限熵的计算。）（补充齐次遍历马尔可夫链的定义。）马尔可夫性平稳性第39页，课件共60页，创作于2023年2月3.3.4马尔可夫信源（补充内容）补充：对一般的马尔可夫链，其状态转移概率可表示为：含义为：

马尔可夫链在m时刻处于si的条件下，在m+n时刻处于sj的转移概率。当n=1时，，称为一步转移概率，其对应的矩阵记为：当n=k≠1时，，称为k步转移概率，其对应的矩阵记为：第40页，课件共60页，创作于2023年2月3.3.4马尔可夫信源（补充内容）齐次（时齐）马尔可夫链： 马尔可夫链的转移概率只与状态si、sj和时间间隔n有关，而与时间起点m无关。则，记为：当n=1时，，称为一步转移概率，其对应的矩阵记为P。当n=k≠1时，，称为k步转移概率，其对应的矩阵记为。对于齐次马尔可夫链，一步转移概率完全决定k步转移概率，即：第41页，课件共60页，创作于2023年2月3.3.4马尔可夫信源m阶马尔可夫信源熵率的计算：

即：齐次性马尔可夫信源处于Si状态的概率一步转移概率第42页，课件共60页，创作于2023年2月3.3.4马尔可夫信源（补充内容）某时刻的状态的概率分布的确定：

在k时刻，马尔可夫信源处于sj状态的概率为： 其中，为初始概率。遍历性（各态历经性）：

若齐次马尔可夫链对一切i，j存在不依赖于i的极限：，并且，则称其具有遍历性（各态历经性），这时称为极限分布或平稳分布。含义： 马尔可夫信源在初始时刻可以处于任意状态，然后经过足够长的时间之后，信源所处的状态已与初始状态无关，这时，各种状态出现的概率已达到一种稳定分布，即平稳分布，并将此分布记为Wj。第43页，课件共60页，创作于2023年2月3.3.4马尔可夫信源（补充内容）时齐遍历马尔可夫信源某状态概率分布的确定：

法1: 法2：

Wj是满足方程组的唯一解。不易求解。Wj常用求解方法。第44页，课件共60页，创作于2023年2月3.3.4马尔可夫信源m阶马尔可夫信源熵率的计算：

即：齐次性极限分布Wi一步转移概率第45页，课件共60页，创作于2023年2月3.3.4马尔可夫信源例：求图示二阶马尔可夫信源 的极限熵。 解： 由图得，该马尔可夫信源为遍历的，则：

1）求极限分布。

01100:0.51:0.20:0.2000:0.8111:0.81:0.50:0.51:0.5由状态转移图中指向某状态的箭头确定。第46页，课件共60页，创作于2023年2月3.3.4马尔可夫信源2）求H∞。第47页，课件共60页，创作于2023年2月3.3.4马尔可夫信源2）求H∞。01100:0.51:0.20:0.2000:0.8111:0.81:0.50:0.51:0.5由状态转移图中从某状态发出的箭头确定。第48页，课件共60页，创作于2023年2月3.4信源的相关性和剩余度信源的相关性：定义：

信源输出符号间的依赖关系。对于平稳信源，可以用条件概率来描述信源间的相关性，且有：

离散平稳信源m阶Markov信源一阶Markov信源实际信源离散无记忆信源等概的离散无记忆信源第49页，课件共60页，创作于2023年2月3.4信源的相关性和剩余度信源的相关性：信源的记忆长度越长，信源熵越小。信源的记忆长度越短，信源熵越大。当信源符号间彼此没有任何依赖关系且呈等概率分布时，信源熵达到最大值。

对于固定的符号集，记忆长度短且概率分布相对均匀的信源更能有效地传递信息。第50页，课件共60页，创作于2023年2月3.4信源的相关性和剩余度举例：

设信源符号集中符号个数为4。 则：符号独立且等概时的最大熵H0为：log4=2bit； 若符号间有相关性且不等概分布，使得极限熵为1.2bit，则对由该符号集中10个符号构成的消息，其信息熵为：1.2*10=12bit。 则： 1）信源1的10个符号可以表示的信息量为：20bit。 2）由信源2表示的12bit信息用信源1则只需6个符号即可。可见： 1）符号独立且等概时的信源传递信息的效率高； 2）信源2中有4个符号是用于描述符号间的相关性的，而不是用于传输信息的，对于传输信息而言，这4个符号是冗余的。信源1信源2第51页，课件共60页，创作于