信息论与编码第2章信源与熵.ppt

1、1,第2章 信源熵,2.0 信源的数学模型及其分类 2.1 单符号离散信源 2.2 多符号离散平稳信源 2.3 连续信源 2.4 离散无失真信源编码定理(*),2,本节内容,通信的根本问题是将信源的输出信息在接收端尽可能精确地复现出来。 需要讨论：如何描述信源的输出，即如何计算信源输出的信息量。 信源的数学模型 信源的分类,3,什么是信源？,信源信息的发源地，如人、生物、机器等等。 由于信息十分抽象，所以我们通过信息载荷者，即消息来研究信源，并将信源的具体输出称作消息。 消息的形式多样：离散消息（如汉字、符号、字母）；连续消息（如模拟图像、语音）。 信源建模：信源消息中的信息是一个时变的不可预

2、知的函数。 描述信源消息或对信源建模，随机过程是一个有效的工具，通过随机过程的特性来描述信源的特性。,4,信源输出的描述,信源发出消息，消息载荷信息，而消息又具有不确定性，所以可用随机变量或随机序列（矢量）来描述信源输出的消息，或者说用概率空间来描述信源。信源的输出被抽象为一个随机变量序列（随机过程）。,5,离散信源和连续信源,用随机变量或随机矢量来描述信源的输出消息，用概率空间来描述信源时，则信源就是一个概率场： 离散信源：信源输出的随机变量取值于某一离散符号集合，消息在时间和幅值上均是离散的，就叫做离散信源。 比如平面图像 X(x，y)和电报、书信、文稿等等 离散信源只涉及一个随机事件，称

3、为单符号离散信源，可用离散随机变量来描述； 若离散信源涉及多个随机事件，称为多符号离散信源，可用离散随机矢量来描述。 连续信源：信源输出的随机变量取值于某一连续区间，为连续信号，消息的个数是无穷值，就叫做连续信源。 比如人发出的语音信号X(t)、模拟的电信号等等,6,离散和连续信源的数学模型,7,单/多符号信源模型,单符号信源：信源输出的是单个消息符号，用一维离散或连续随机变量X及其概率分布P来描述。 多符号信源：信源输出的是多个消息符号，用N维随机矢量，N重离散概率空间的数学模型来描述。 如自然语言信源就是把人类的语言作为信源，以汉字为例，就是随机地发出一串汉字序列。 我们可以把这样信源输出

4、的消息视为时间上或空间上离散的随机变量序列，即随机矢量。 于是，信源的输出可用N维随机矢量(Xk,k=1,2,.,N)来描述，N一般为有限正整数。,8,多符号信源的数学模型 N重离散概率空间,9,信源的分类,主要基于两方面： 1. 信源消息取值的集合以及消息取值时刻的集合 离散信源、连续信源 或数字信源、模拟信源（波形信源） 2. 信源消息的统计特性 由此可分为无记忆信源、有记忆信源、 平稳信源、非平稳信源、 高斯信源、马尔可夫信源等。 实际使用的是二者的组合 如离散无记忆信源等。,10,信源的分类离散平稳信源,如果随机序列中各个变量具有相同的概率分布，则称为离散平稳信源。 如果离散平稳信源的

5、输出序列中各个变量是相互独立的，即前一个符号的出现不影响以后任何一个符号出现的概率，则称为离散无记忆平稳信源，否则称为离散有记忆平稳信源,11,信源的分类无记忆信源,如果信源发出的消息符号间彼此是统计独立的，并且它们具有相同的概率分布，且N维随机矢量的联合概率分布为： 我们称之为离散无记忆信源。 同样，若N维随机矢量中X每个变量Xk是连续随机变量，且相互独立，则X的联合概率密度函数 为 ，这种信源叫连续型无记忆信源,12,信源的分类有记忆信源,一般情况下，信源发出的符号间是彼此相互依存和关联的（如小说文字），是有记忆信源，通常用联合概率或条件概率来描述这种关联性。 按记忆长度划分有： 有限记忆

6、信源（马尔可夫信源） 有限状态马尔可夫链 无限记忆信源,13,混合信源,按信源输出时间和取值划分： 时间连续，取值连续或随机的，称之为随机波形信源，表示为X(t)。 输出既有连续分量又有离散分量，称之为混合信源。 重点研究离散信源产生消息的不确定性，不研究信源的内部结构和消息的如何产生。,14,信源的分类,随机过程x(t)：随机波形信源 信源输出的消息是时间（或空间）上 和取值上都是连续的函数,离散无记忆信源的N次扩展信源：输出的 平稳随机序列X中各随机变量统计独立。 每个随机变量xi取值于同一概率空间。 每N个符号构成一组，等效为一个新的信源,随机 变量,离散信源：可能输出的消息数有限,连续

7、信源：可能输出的消息数是无限的或不可数的,非平稳 信源,平稳 信源,连续平稳信源,离散平稳信源：输出的随机序列X中每个随机变量取值是离散的， 并且随机矢量X的各维概率分布不随时间平移而改变,有限记忆信源：输出的平稳随机序列 X中各随机变量之间有 依赖关系，但记忆长度有限,马尔可夫信源：输出的随机序列X中各随机变量之间有依赖关系 ，但记忆长度有限，并满足马尔可夫链的条件式,随机 序列,15,第2章 信源熵,2.0 信源的数学模型及其分类 2.1 单符号离散信源 2.2 多符号离散平稳信源 2.3 连续信源 2.4 离散无失真信源编码定理,16,第2章 信源熵,2.1 单符号离散信源 2.1.1

8、单符号离散信源的数学模型 2.1.2 自信息和信源熵 2.1.3 信源熵的基本性质和定理 2.1.4 加权熵的概念及基本性质 2.1.5 各种熵之间的关系,17,2.1.1 单符号离散信源的数学模型,定义：单符号离散无记忆信源的数学模型,18,第2章 信源熵,2.1 单符号离散信源 2.1.1 单符号离散信源的数学模型 2.1.2 自信息和信源熵 2.1.3 信源熵的基本性质和定理 2.1.4 加权熵的概念及基本性质 2.1.5 各种熵之间的关系,19,随机事件与信息量,你的同学告诉你：“昨天中国男子足球队以3：0战胜了巴西队”，你的感觉如何？ 如果你的同学又告诉你： “昨天中国男子乒乓球队以

9、3：0战胜了巴西队”，你的感觉又如何？ 比较从这两件事情当中你获得信息量的大小？,20,自信息量定义,定义 2.1.1 任意随机事件的自信息量定义为该事件发生概率的对数的负值。 自信息量的单位取决于对数选取的底。 单位：比特bit、奈特nat、哈特Hart。 当对数的底取2时，单位为比特bit 当以自然数e为底时，单位为奈特nat 当以10为底时，单位为哈特hart,21,自信息量的单位,在现代数字通信系统中，一般采用二进制的记数方式。在信息量的计算中也多采用以2为底的方式，一般默认以2为底 三个信息单位比特bit、奈特nat、哈特Hart之间的转换关系如下：,22,对数及常用公式,23,信息

10、量、不确定度和惊讶度,在事件发生前有不确定度：不确定度与事件发生与否无关，它表征的是事件的特性； 在事件发生时有惊讶度； 在事件发生后带来信息量： 因此，当一个概率很低的随机事件发生，我们就会感到非常惊讶，并得到很大的信息量。 如：9.11事件，美国纽约世贸大厦被炸； 彗星撞地球,24,自信息量,从信息源获取信息的过程是信源不确定度缩减的过程。 随机事件包含的信息与其不确定度紧密相关 在统计分析中，使用概率作为衡量不确定性的一种指标。 可以推论出：随机事件包含信息的度量应是其概率的函数。,25,自信息量与不确定度(例),例：有一本n页书，每页200字，作者使用的词汇有1000个字。那么，100

11、0个字每次取200个字构成一页，其总排列组合数也就是一页书总的状态数共有1000200=N1，对于n页书，则不同状态数将增加到N1n ，即Nn= N1n =(1000)200 n = 1000200n 假定每种状态是等概的，则n页书中对应每一种状态的概率为Pn=1/ Nn=1/ N1n = 1/1000200n 用概率倒数的对数来度量其不确定度，则为log(1/Pn)= log(Nn)=nlog(N1) 记1页（n页）书每种状态的不确定度为H1（Hn） 则Hn = log(1/Pn)= log(Nn)=nlog(N1)= nH1 = Hn 也就是说n页书包含的信息量是1页书包含信息量的n倍。,

12、26,自信息量的性质,值得注意的是：,27,自信息量（例）,某地二月份天气的概率分布统计如下： 这四种气候的自信息量分别为： 可见不同天气情况具有不同的自信息量， 自信息量具有随机变量的性质,28,联合自信息量,定义 2.1.2 二维联合集XY上的元素（ ）的联合自信息量定义为 式中 为积事件； 为元素 的二维联合概率。 当X和Y相互独立时，,29,条件自信息量,定义 2.1.3 联合集XY中，对事件 和 ，事件 在事件 给定的条件下的条件自信息量定义为 由于每个随机事件的条件概率都处于0 1范围内，所以条件自信息量均为非负值。,30,几种自信息量之间的关系,自信息量、联合自信息量、条件自信息

13、量都满足非负性和单调递减性 三者都是随机变量，其值随着变量xi，yj的变化而变化。 三者之间有如下关系式：,31,例：联合自信息量,设在一正方形棋盘上共有64个方格，如果甲将一粒棋子随意地放在棋盘中的某方格且让乙猜测棋子所在位置： 将方格按顺序编号，令乙猜测棋子所在方格的顺序号； 解：,x,y,32,例：条件自信息量,设在一正方形棋盘上共有64个方格，将方格按行和列编号，甲将棋子所在方格的行（或列）编号告诉乙之后，再令乙猜测棋子所在列（或行）的位置。 解：,x,y,33,自信息量不能作为信源的整体信息测度,自信息量 是指某一信源X发出某一信息符号 所含有的信息量。发出的信息符号不同，它们所含有

14、的信息量就不同。 信源发出的信息符号可用随机事件来描述。 自信息量是一个随机变量，它反映了信源发出某一信息符号的不确定性，不能反映整个信源的不确定性。它不能用来作为整个信源的信息测度。,34,信源的概率空间描述,用概率空间来描述信源。 用这个概率空间的可能状态数目及其概率来描述信源的不确定程度： 其中： X是信源的状态空间，为一个离散集，表示了随机事件的状态数； P(X)是随机事件各种可能状态的概率分布，且P(x)=1， 各状态是相互独立的。 通常记为X,P(x),35,信源的不确定度举例,分析整个信源的不确定性 有一个布袋，装有100个对手感觉一样的球，但颜色不同，每种颜色球的数量也不同。随

15、意从中拿出一球，猜测球的颜色。 1、90个红球，10个白球 -容易猜测 2、50个红球，50个白球-较难猜测 3、红、白、黑、黄球各25个-更难猜测 容易看出：信源的不确定度与信源所包含的随机事件的可能状态数目和每种状态的概率有关。,36,信源不确定度的几个结论,关于信源不确定度的几个结论： 信源的不确定程度与信源概率空间的状态数及其概率分布有关 如果信源概率空间的状态数确定，概率分布为等概时，不确定程度最大 等概时，不确定程度与信源概率空间的可能状态数（或相应的概率）有关，状态数越多（或相应的概率越小），不确定程度就越大。 信源的不确定程度可以用信源概率空间的概率分布来描述。通常记为H(X)

16、=H(p1, p2,.pN) 对于上面的例子，有 H3(1/4,1/4,1/4,1/4) H2(1/2,1/2) H1(0.90,0.10),37,平均自信息量信息熵,自信息量是随机变量，它反映了信源发出某一信息符号的不确定性，但不能用来作为整个信源的信息测度。因此，我们引入平均自信息量，即信息熵。 定义 2.3.1 集X上，随机变量I(xi)的数学期望定义为平均自信息量 集X的平均自信息量又称做是集X的信息熵，简称做熵。含义上信息熵与热熵有相似之处。,38,平均不确定性,集X的平均自信息量表示集X中事件出现的平均不确定性 在观测之前，确定集合X中出现一个事件平均所需的信息量； 观测之后，集合

17、X中每出现一个事件平均给出的信息量。 例：,39,信息熵的单位,离散集合X信息熵的单位取决于对数选取的底。 如果一个离散集合X的概率分布为n个状态等概，选取对数底为n，由信息熵定义 可以说此集合X包含了1个n进制单位的信息量，用一个n进制的数就可以表示此集合的信息。 在现代数字通信系统中，一般采用二进制的记数方式。在信息熵的计算中也多采用以2为底的方式，且默认记为H(X)。由对数公式可以得到r进制与二进制之间的关系：,40,从布袋中摸球（例）,如果每次摸出一个球后又放回袋中，再进行下一次摸取。那么如此摸取n次，红球出现的次数为np(x1)次，白球出现的次数为np(x2)次。随机摸取n次后总共所

18、获得的信息量为： np(x1)I(x1)+ np(x2)I(x2) 平均随机摸取一次所获得的信息量则为： 从此例可以看出，平均自信息量，亦即信息熵H(X)是从平均意义上来表征信源的总体特征的一个量，它表征信源的平均不确定性,41,从布袋中摸球（例）,继续从布袋中摸球 使用信息熵定义计算三种情况下信源的平均不确定性,42,信源熵与平均自信息量,信源熵与平均自信息量数值相等，含义不同 信源熵表征信源的平均不确定度； 平均自信息量是消除信源不确定度所需要的信息的度量； 信源熵H(X)的三种物理含义： 表示信源输出后，每个离散消息所提供的平均信息量； 表示信源输出前，信源的平均不确定度； 反映了变量X

19、的随机性。,43,条件熵,定义 2.3.3 联合集XY上，条件自信息量I(x|y)的概率加权平均值定义为条件熵。其定义式为 上式称为联合集XY中，集Y相对于集X的条件熵。 条件熵又可写成 式中取和的范围包括XY二维空间中的所有点。这里要注意条件熵用联合概率p(xy)，而不是用条件概率p(y|x)进行加权平均。,44,为什么条件熵要用联合概率进行加权平均？,45,联合熵,定义 2.3.4 联合集XY上，每对元素的自信息量的概率加权平均值定义为联合熵。 根据联合自信息量的定义，联合熵又可定义为 联合熵又可称为共熵。,46,第2章 信源熵,2.1 单符号离散信源 2.1.1 单符号离散信源的数学模型

20、 2.1.2 自信息和信源熵 2.1.3 信源熵的基本性质和定理 2.1.4 加权熵的概念及基本性质 2.1.5 各种熵之间的关系,47,熵函数的数学特征,随机变量集X的熵H(X)只是其概率分布 的函数，称为熵函数。所以H(X)又可以记为 根据此式，再由概率的完备性， ，可知H(P)实际上是(q-1)元函数。 如二元熵，有 为讨论熵函数的性质，需借用凸函数的概念,48,熵函数的基本性质,非负性 对称性 极值性 极值性特例最大离散熵定理 凸函数性 扩展性 确定性 可加性,49,熵函数的性质 1. 非负性,非负性 其中，等号成立的充要条件是当且仅当对某 即，信源虽然有不同的输出符号，但它只有一个符

21、号几乎必然出现，而其它符号几乎都不可能出现，那么，这个信源是一个确知信源，其信源熵等于零。 这种非负性对于离散信源的熵是正确的，但是对于连续信源来说，该性质不存在。,50,熵函数的性质 2. 对称性,当概率矢量 中的各分量的次序任意变更时，熵值不变。 该性质说明信源的熵仅与信源总体的统计特性有关。如果统计特性相同，不管其内部结构如何，其信源熵值都相同。 例，A,B两地天气情况的平均不确定性为,51,熵函数的性质 3.极值性、最大熵定理,该性质表明，在离散情况下，集合X中的各事件依等概率发生时，熵达到极大值。这个重要结论称为最大熵定理。 集合中元素的数目n越多，其熵值就越大 对数函数的单调上升性

22、。,52,熵函数的性质 4.扩展性,证明： 所以通过熵函数的定义可以证明上式成立。 含义：若集合X有q个事件，另一个集合X有q+1个事件，但X和X集的差别只是多了一个概率接近于零的事件，则两个集的熵值一样。 换言之，一个事件的概率与其中其它事件的概率相比很小时，它对集合的熵值的贡献可以忽略不计。,53,熵函数的性质 5. 确定性,集合X中只要有一个事件为必然事件，则其余事件为不可能事件。 此时，集合X中每个事件对熵的贡献都为零，因而熵必为零。,54,熵函数的性质 6. 可加性,可加性： 如果有两个随机变量X，Y，它们不是相互独立的，则二维随机变量（X，Y）的熵等于X的无条件熵加上当X已给定时Y

23、的条件概率定义的熵的统计平均值，即 强可加性： 当二维随机变量X，Y相互统计独立时，则有,55,熵函数的性质 可加性证明,56,熵函数的性质 7. 上凸性,是概率分布 的严格上凸函数 可以通过凸函数的概念和詹森(Jenson)不等式证明。 上凸函数如： 二元熵函数 三元熵函数,二元熵函数,57,上凸性证明凸函数的概念,定义2.3.2 设 为一多元函数。若对于任意一个小于1的正数 以及函数f(X)定义域内的任意两个矢量 有 则称f(X)为定义域上的凸函数。 若有： 则称f(X)为定义域上的上凸函数（Cap型函数）或严格上凸函数。反之， 若有： 则称f(X)为定义域上的下凸函数（Cup型函数）或严

24、格下凸函数。,58,上凸性证明詹森(Jenson)不等式,引理 若f(x)是定义在区间a,b上的实值连续上凸函数，则对于任意一组 和任意一组非负实数 ： 当取xk为一个离散无记忆信源的信源符号，k取为相应的概率时，显然满足引理条件。 若取f(.)为对数函数，上述不等式可写为 Elogxlog(Ex) 或对于一般的凸函数f(.)，写成Ef(x)f(Ex),59,第2章 信源熵,2.1 单符号离散信源 2.1.1 单符号离散信源的数学模型 2.1.2 自信息和信源熵 2.1.3 信源熵的基本性质和定理 2.1.4 加权熵的概念及基本性质 2.1.5 各种熵之间的关系,60,加权熵,熵的对称性，显露

25、出它无法描述主观意义上对事件的判断的差别，从而淹没了个别事件的重要性。 为了把主观价值和主观意义反映出来，引入加权熵的概念。它是通过引入事件的重量，来度量事件的重要性或主观价值。 一般情况下事件的重量与事件发生的客观概率不一致，事件的重量可以反映主观的特性（就人们的主观目的来说），也可以反映事件本身的某些客观的性质。,61,加权熵,设有随机变量X，引入事件的重量后，其概率空间如下， 其中,62,加权熵定义和性质,定义2.1.10 离散无记忆信源X P W的加权熵定义为 加权熵的一些重要性质: 性质1 非负性 性质2 等重性若权重 ，则 。即若每一事件都被赋于同样的重量，则加权熵退化为香农熵。

26、性质3 确定性。 若 ，而 则加权熵为零,即,63,加权熵的性质,性质4 这一性质表明：某些事件有意义（ ），但不发生（ ）；而另外一些事件虽然发生（ ），但毫无意义（ ）。所以从主观效果来看，人们并没有获在得任何有意义的信息。,64,加权熵的性质,性质5 对称性 性质6 均匀性 性质7 非容性 性质8 扩展性 性质9 线性叠加性 性质10 加权熵的最大值,65,第2章 信源熵,2.1 单符号离散信源 2.1.1 单符号离散信源的数学模型 2.1.2 自信息和信源熵 2.1.3 信源熵的基本性质和定理 2.1.4 加权熵的概念及基本性质 2.1.5 各种熵之间的关系,66,各种熵之间的关系,1

27、.联合熵与信息熵、条件熵的关系 2.联合熵与信息熵的关系 3.条件熵与通信熵的关系,67,1.联合熵与信息熵、条件熵,H(XY)=H(X)+H(Y/X); H(YX)=H(Y)+H(X/Y) H(X)+H(Y/X)=H(Y)+H(X/Y) H(X)H(X|Y)=H(Y)H(Y|X) 如果集X和集Y相互统计独立，则有：H(XY)=H(X)+H(Y) 还可将此性质推广到多个随机变量构成的概率空间之间的关系 。设有N个概率空间X1,X2,XN 其联合熵可表示为 如果N个随机变量相互独立，则有,68,联合熵与信息熵、条件熵关系式的证明,证明：对于离散联合集XY，共熵为,69,2.联合熵与信息熵的关系,

28、若集合X和Y统计独立，则 该性质可以推广到N个概率空间的情况 同理，上式等号成立的充要条件是：,70,H(XY)H(X)+H(Y) 的证明,71,3.条件熵与通信熵的关系H(Y/X)H(Y),72,H(Y/X)H(Y) 证明（续）,73,例2.3.4 求联合集X,Y上的各种熵,设一系统的输入符号集X=(x1,x2,x3,x4,x5）输出符号集Y=（y1,y2,y3,y4），如图所示。输入符号与输出符号的联合分布为,74,例2.3.4 计算先验概率、后验概率,75,例2.3.4 计算后验概率（续）,76,例2.3.4计算联合熵、信息熵(续),77,例2.3.4 计算条件熵(续),78,例2.3.

29、4（续）例题验证关系式,H(XY)=2.665比特/符号 H(X)=2.066比特/符号;H(Y)=1.856比特/符号 H(X/Y)=0.809比特/符号;H(Y/X)=0.600比特/符号 有： H(XY)=2.6653.922=H(X)+H(Y) H(X)+H(Y)=2.066+1.856=3.922 H(Y)+H(X/Y)=1.856+0.809=2.665 H(X)+H(Y/X)=2.066+0.600=2.666 注意到： H(XY)= H(Y)+H(X/Y)=H(X)+H(Y/X) H(XY)H(X)+H(Y) H(Y/X) H(Y); H(X/Y) H(X),79,总结,给出了

30、信息熵的定义和熵函数的数学特征及性质。介绍了联合符号集上的条件熵和联合熵的定义。简单讨论了加权熵的概念和意义。在信息熵、条件熵和联合熵定义的基础上，分析了几种熵函数之间的关系和性质，并通过例题，具体讲解了各种熵的计算及其含义。,80,第2节 多符号离散信源,2.2 .1平稳信源的定义及分类 2.2.2 离散无记忆信源的N次扩展信源 2.2.3 一般离散平稳信源 2.2.4 马尔可夫信源 2.2.5 信源的相关性和剩余度,81,多符号信源,多符号信源：信源输出的是多个消息符号，用N维随机矢量，N重离散概率空间的数学模型来描述。 如自然语言信源就是把人类的语言作为信源，以汉字为例，就是随机地发出一

31、串汉字序列。 我们可以把这样信源输出的消息视为时间上或空间上离散的随机变量序列，即随机矢量。 于是，信源的输出可用N维随机矢量(Xk,k=1,2,.,N)来描述，N一般为有限正整数。,82,多符号信源的数学模型N重离散概率空间,83,平稳信源,84,平稳信源一维平稳,85,平稳信源二维平稳,86,平稳信源N维平稳,87,平稳信源离散平稳信源,88,离散平稳信源,离散平稳信源分为有记忆的或无记忆的，区别是信源发出的各个符号之间是否具有统计关联关系。 无记忆：如离散无记忆信源的N次扩展信源 有记忆：马尔可夫信源 统计关联性即记忆性的表示方式： 用信源发出的一个符号序列的整体概率，即N个符号的联合概

32、率来反映有记忆信源的特征，这种信源一般是指发出符号序列的离散平稳有记忆信源。 用信源发出符号序列中各个符号之间的条件概率来反映记忆特征，这种信源代表是马尔可夫信源。,89,第2节 多符号离散信源,2.2 .1平稳信源的定义及分类 2.2.2 离散无记忆信源的N次扩展信源 2.2.3 一般离散平稳信源 2.2.4 马尔可夫信源 2.2.5 信源的相关性和剩余度,90,2.2.2 离散无记忆信源的N次扩展信源,最简单的离散信源 单符号离散信源 N次扩展信源 离散无记忆二进制信源的扩展信源 离散无记忆信源的扩展信源 N次扩展信源的熵,91,最简单的离散信源,92,N次扩展信源,1. 离散无记忆二进制

33、信源的二次扩展信源 如图，二次扩展信源的输出消息是符号序列，分组发出，每两个二进制符号构成一组。其数学模型为,93,N次扩展信源（续）,2. 离散无记忆二进制信源的三次扩展信源 三次扩展信源X3(X1X2X3)共输出qN个消息符号，其中q=2，N3，即8个长为3的二进制系列符号，它等效为一个拥有8个消息符号的新信源X。,94,N次扩展信源（续）,定义设X是一个离散无记忆信源，其概率空间 其中q为信源符号个数，piP(X=ai) i=1,2,q。则X的N次扩展信源XN是具有qN个消息符号的离散无记忆信源，其概率空间为,95,N次扩展信源的熵,96,N次扩展信源的熵(证明),97,N次扩展信源的熵

34、（证明）,98,N次扩展信源的熵例题,例：设有一离散无记忆信源X，其概率空间为,99,N次扩展信源的熵例题(续),100,第2节 多符号离散信源,2.1 .1平稳信源的定义及分类 2.2.2 离散无记忆信源的N次扩展信源 2.2.3 一般离散平稳（有记忆）信源 平稳信源的熵 极限熵 2.2.4 马尔可夫信源 2.2.5 信源的相关性和剩余度,101,二维平稳信源的熵联合熵,以最简单的二维平稳信源为例,它是长度为2的有记忆平稳信源。,102,二维平稳信源的熵与无记忆二次扩展信源的关系,当X1和X2取值于同一集合（概率空间）时， H(X1)=H(X2) 当X1和X2无记忆时 H(X)=2H(X)=

35、H(X2) 所以离散无记忆信源的二次扩展信源可看成是二维离散平稳信源的特例。,103,二维平稳信源的熵与无记忆二次扩展信源的关系,由于条件熵小于无条件熵，所以 H(X1X2)= H(X1)+ H(X2/X1) H(X1X2)H(X1)+ H(X2) 说明二维离散平稳有记忆信源的熵小于等于无记忆二次扩展信源的熵 对于二维离散平稳无记忆信源X2=X1X2来说，X1对X2不产生任何影响。 对于二维离散平稳有记忆信源，由于X1和X2有统计依赖关系， X1的发生会提供X2的部分相关信息。,104,二维平稳信源的熵-例题,105,二维平稳信源的熵-例题(续),106,二维平稳信源的熵-例题(续),107,

36、第2节 多符号离散信源,2.1 .1平稳信源的定义及分类 2.2.2 离散无记忆信源的N次扩展信源 2.2.3 一般离散平稳信源 平稳信源的熵 极限熵 2.2.4 马尔可夫信源 2.2.5 信源的相关性和剩余度,108,N维平稳有记忆信源的熵联合熵,由二维平稳有记忆信源推广到N2的N维平稳有记忆信源的熵。,109,N维平稳有记忆信源的熵联合熵的分解式,110,N维平稳有记忆信源的熵条件熵随N增加而递减,111,N维平稳有记忆信源的熵平均符号熵,离散平稳有记忆信源的联合熵(X1X2.XN)，表示平均发出一个消息所提供的信息量。这里的一个消息是由N个符号组成的序列。 信源平均发出一个符号所提供的信

37、息量称为平均符号熵。,112,N维平稳有记忆信源的熵极限熵,当N趋于无穷大时的平均符号熵，称为极限熵或极限信息量，记为H。,113,N维平稳有记忆信源的熵极限熵的意义,对于多符号离散平稳信源，实际上它在不断地发出符号，符号之间的统计关联关系并不仅限于长度N，而是伸向无穷远。研究实际信源，必须求出信源的极限熵H。 H是否存在？ 如何求H？ 当信源是离散平稳信源时，H是存在的，且等于关联长度N趋于时，条件熵的极限值。即有,114,N维平稳有记忆信源的熵极限熵存在定理,115,N维平稳有记忆信源的熵极限熵存在定理（续）,116,N维平稳有记忆信源的熵极限熵存在定理（续）,117,离散平稳信源-小结,

38、1.实际信源往往比较复杂，在其定义上加入平稳性约束条件即为平稳信源，而平稳信源通常都是有记忆信源。 2.极限熵代表了一般离散平稳有记忆信源平均每发出一个符号所提供的信息量。 3.计算联合熵或极限熵很困难，需要测定信源的无穷阶联合概率和条件概率。一般可用条件熵或平均符号熵作为极限熵的近似值。,118,第2节 多符号离散信源,2.2 .1平稳信源的定义及分类 2.2.2 离散无记忆信源的N次扩展信源 2.2.3 一般离散平稳信源 2.2.4 马尔可夫信源 有限状态马尔可夫链 马尔可夫信源 2.2.5 信源的相关性和剩余度,119,有限状态马尔可夫链定义,120,有限状态马尔可夫链转移概率pij(m

39、,n),为了知道系统状态的转化情况，引入转移概率 转移概率表示：已知在时刻m系统处于状态ei的条件下，经(n-m)步后，转移到状态ej的概率。它是一个条件概率。 转移概率的性质：,121,有限状态马尔可夫链_基本（一步）转移概率,122,有限状态马尔可夫链_k步转移概率,123,有限状态马尔可夫链_K步转移矩阵,124,有限状态马尔可夫链_时齐性,125,有限状态马尔可夫链_切普曼-柯尔莫哥洛夫方程,126,有限状态马尔可夫链_切普曼-柯尔莫哥洛夫方程（证明）,127,有限状态马尔可夫链_遍历性,128,有限状态马尔可夫链_马尔可夫链的稳态分布,129,有限状态马尔可夫链_状态分布矢量的递推运

40、算,130,有限状态马尔可夫链_稳态分布存在性定理一,131,有限状态马尔可夫链_状态极限概率的求解,132,有限状态马尔可夫链_稳态分布存在性定理二,133,有限状态马尔可夫链_例题（遍历性的判断）,134,有限状态马尔可夫链例题（稳态分布的求解）,135,第2节 多符号离散信源,2.2 .1平稳信源的定义及分类 2.2.2 离散无记忆信源的N次扩展信源 2.2.3 一般离散平稳信源 2.2.4 马尔可夫信源 有限状态马尔可夫链 马尔可夫信源 2.2.5 信源的相关性和剩余度,136,马尔可夫信源定义,137,马尔可夫信源状态的一步转移概率,马尔可夫信源输出的符号序列Xl完全由信源所处的状态

41、Sl决定。所以，可将信源的输出符号系列变换成状态系列，即，信源在l-1时刻的状态ei，当它发出一个符号后，所处的状态变成l时刻的状态ej，这种状态间的变化可用一步转移概率描述,138,马尔可夫信源_时齐遍历性,时齐性： 转移概率与时间起点无关。 遍历性： 当转移步数足够大时，转移概率与起始状态无关，即达到平稳分布 时齐遍历马尔可夫信源： 同时满足时齐性和遍历性,139,m阶马尔可夫信源,m阶马尔可夫信源： 有记忆离散信源，若记忆长度为m1，即信源每次发出的符号仅与前面m个符号有关，与更前面的符号无关，这样的信源称为m阶马尔可夫信源。 m阶马尔可夫信源的记忆关系用条件概率描述为：,140,m阶马

42、尔可夫信源的数学模型,141,m阶马尔可夫信源状态转移图（例1）,通常我们用马尔可夫链的状态转移图来描述马尔可夫信源。,信源状态转移图,142,m阶马尔可夫信源状态转移图（例2）,143,m阶马尔可夫信源状态转移图（例2续）,144,m阶马尔可夫链状态转移图（例3）,145,m阶马尔可夫链状态转移图（例3续）,146,m阶马尔可夫链状态转移图（例3续）,一步转移矩阵为P,147,M阶马尔可夫信源极限熵H Hm+1,当时间足够长时，遍历的m阶马尔可夫信源可以视为平稳信源，又因为信源发出的符号只与最近的m个符号有关，所以由极限熵定理,148,M阶马尔可夫信源Hm+1的计算,149,计算此马尔可夫信

43、源熵-例题,150,马尔可夫信源熵-例题(续),151,第2节 多符号离散信源,2.1 .1平稳信源的定义及分类 2.2.2 离散无记忆信源的N次扩展信源 2.2.3 一般离散平稳信源 2.2.4 马尔可夫信源 2.2.5 信源的相关性和剩余度,152,信源的相关性,153,为了衡量信源的相关性程度，引入剩余度概念,信源剩余度,154,信源熵和剩余度的概念英语信源,155,信源熵和剩余度的概念英语信源(续),156,小结,讨论了具有平稳性和遍历性的马尔可夫信源，了解马尔可夫信源极限熵的存在条件：信源的状态极限概率存在；给出了马尔可夫信源极限熵的求解方法。 设计实际通信系统时，信源剩余度的存在对

44、传输是不利的，应当尽量压缩信源剩余度，以使信源发出的每个符号携带的平均信息量最大。反之，若考虑通信中的抗干扰问题时，则信源剩余度是有利的，常常人为的加入某种特殊的剩余度，以增强通信系统的抗干扰能力。它们分别对应着后续章节的信源编码和信道编码。,157,第2章 信源与熵,2.0 信源分类 2.1 单符号离散信源 2.2 多符号离散信源 2.3 连续信源 2.3.1 连续信源与连续熵 2.3.2 几种特殊连续信源的熵 2.3.3连续熵的性质 2.3.4熵功率,158,随机波形信源,随机波形信源：输出是时间和取值都连续的随机消息，可用随机过程 来描述，例如：语音、视频信号。 相关概念： 样本函数 随

45、机变量 概率密度函数 随机过程的平稳性 随机过程的遍历性,159,随机过程的各态历经性(遍历性),160,波形信源的离散化连续信源,根据采样定理，对于时间受限于T，频率受限于F的连 续时间函数，可由2FT个采样值完整地描述，采样间隔 为 通过采样，波形信源转化为时间离散，幅度连续的信源，对样本函数 的描述转化为N维随机序列X，X由N2FT个随机变量组成。 与单符号和多符号离散信源类似，连续信源也有单变 量（一维）和多变量（N维）之分。这里只讨论单变量 连续信源。对多变量连续信源，可以近似转换为无记 忆信源来处理。,161,连续随机变量的概率描述,单变量连续信源输出的消息取值是连续变化的，通常

46、用连续随机变量来描述这些连续变化的消息值。 连续随机变量用各种概率密度函数来描述。 变量的一维概率密度函数（边缘概率密度函数） p(x)和p(y) 变量间的条件概率密度函数p(x/y)和p(y/x) 联合概率密度函数p(xy) 各种概率密度函数间的关系,162,单变量连续信源的模型,单变量连续信源的模型为 并满足,163,连续信源的熵变量离散化,如果将连续随机变量看作是离散随机变量的极限情况，则我们可以这样来研究连续随机变量的信息熵。 令连续随机变量X的取值区间是 ，把它分割成n个小区间,并且各小区间设为等宽 那么X处于第i个小区间的概率是 于是事件 的自信息量为,164,连续信源的熵绝对熵,变量离散化后的连续信源的熵为 当时，得连续信源的熵为 式中第二项将趋于无穷大，这说明连续随机变量的潜在信息量是无穷的。,165,连续信源的熵相对