第2章信源与信源熵

第2章信源及信源熵2.1信源的描述和分类2.2离散信源熵和互信息2.3离散序列信源熵2.4冗余度2.5连续信源熵和互信息2/1/20231复习信息的概念在信息论中，信源是发出消息的源，信源输出以符号形式出现的具体消息。如果符号是确定的而且预先是知道的，那么该消息就无信息而言。只有当符号的出现是随机的，预先无法确定，那么一旦出现某个符号就给观察者提供了信息。因此，应该用随机变量或随机矢量来表示信源，运用概率论和随机过程的理论来研究信息，这就是香农信息论的基本点。2/1/20232复习信息的概念信息不确定性（随机性）随机变量随机矢量概率论随机过程2/1/202332.1信源的描述和分类按信源在时间和幅度上的分布情况离散信源：文字、数据、电报连续信源：语音、图像按发出符号的数量单个符号信源：指信源每次只发出一个符号代表一个消息符号序列信源：指信源每次发出一组含二个以上符号的符号序列代表一个消息按符号间的关系无记忆信源有记忆信源信源所发出的各个符号是相互独立的，发出的符号序列中的各个符号之间没有统计关联性信源所发出的各个符号的概率是有关联的2/1/20234信源分类信源{无记忆信源有记忆信源{{发出单个符号的无记忆信源发出符号序列的无记忆信源发出符号序列的有记忆信源发出符号序列的马尔可夫信源马尔可夫信源：某一个符号出现的概率只与前面一个或有限个符号有关，而不依赖更前面的那些符号2/1/20235概率空间概率随机现象中事件发生的可能性大小是客观存在的，因此可以对它进行量度。量度的数量指标就是概率。样本空间某事物各种可能出现的不同状态，即所有可能选择的消息集合。每个可能选择的消息是这个样本空间的一个元素。概率空间对于离散消息的集合，概率测度就是对每一个可能选择的消息指定一个概率。一个样本空间和它的概率测度一起构成一个概率空间。2/1/20236概率空间数学定义 一个离散信源发出的各个符号消息的集合为它们的概率分别为该信源的概率空间为显然有信源空间先验概率2/1/20237概率论复习无条件概率P(xi)又称先验概率，指基于以往数据记录统计得到的概率条件概率P(B/A)在已知事件A发生条件下，事件B发生的概率又称后验概率联合概率P(AB)事件A和事件B同时发生的概率2/1/20238概率论复习完备性非负性2/1/20239概率论复习联合概率贝叶斯公式2/1/202310单个符号的离散无记忆信源有些信源可能输出的消息数是有限的或可数的，而且每次只输出其中一个消息。如书信文字、计算机的代码、电报符号、阿拉伯数字码等。例如：掷骰子扔一颗质地均匀的骰子，每次扔掷的结果必然是1点～6点中的某一面朝上，哪一面朝上是随机的。2/1/202311单个符号的离散无记忆信源用一维离散型随机变量X来描述这些信息的输出。数学模型当信源给定，其相应的概率空间就已给定；反之，如果概率空间给定，这就表示相应的信源已给定。信源可能的消息（符号）数是有限的，而且每次必定选取其中一个消息输出，满足完备集条件。2/1/202312单符号连续无记忆信源连续信源：输出在时间和幅度上都是连续分布的连续消息的信源。单符号连续无记忆信源消息数无限或不可数，且每次只输出其中一个消息。可用一维的连续型随机变量X来描述这些消息。

数学描述例：随机取一节干电池测其电压值作为输出符号，符号取值为[0，1.5]之间的所有实数。pX(x)是随机变量X的概率密度函数

2/1/202313符号序列的离散无记忆信源很多实际信源输出的消息往往是由一系列符号组成，这种用每次发出1组含2个以上符号的符号序列来代表一个消息的信源叫做发出符号序列的信源。设信源输出的随机序列为X， 序列中的变量 即序列长为L扔骰子：以三位二进制符号表示结果2/1/202314符号序列的离散无记忆信源最简单的符号序列信源是L＝2的情况，即 信源：

信源空间：当信源无记忆时，2/1/202315符号序列的离散无记忆信源二元信源｛0,1｝单符号离散信源二次扩展信源三次扩展信源三元信源｛0,1,2｝三元二次扩展信源样本N＝3序列长度L＝22/1/202316符号序列的离散无记忆信源L次扩展信源每个随机变量取值有n种，那么序列长为L的随机序列，其样值共有nL种可能取值。这种由信源X输出的L长随机序列X所描述的信源叫做离散无记忆信源X的L次扩展信源。数学描述 其中，2/1/202317离散有记忆信源一般情况下，信源在不同时刻发出的符号之间是相互依赖的，也就是信源输出的平稳随机序列X中，各随机变量xl之间是有依赖关系的。如：袋中摸球 文字序列的前后关系表述有记忆信源比表述无记忆信源困难得多离散有记忆信源发出符号序列的有记忆信源发出符号序列的马尔可夫信源用信源发出的一个符号序列的整体概率(即联合概率)反映有记忆信源的特征一个符号出现的概率只与前面一个或有限个符号有关,而不依赖更前面的那些符号2/1/202318离散有记忆信源例如由英文字母组成单词，字母间是有关联性的，不是任何字母的组合都能成为有意义的单词。例如布袋中有100个球，80个红球，20个白球。先取出一个球，记下颜色后不放回布袋，接着取另一个。取第一个球时的概率p(红球)=，p(白球)=若第1个球为红色，则取第二个球时的概率 p(红球)=，p(白球)=若第1个球为白色，则取第二个球时的概率 p(红球)=，p(白球)=80/10079/9920/9980/9919/9920/1002/1/202319离散有记忆信源有记忆信源的联合概率表示比较复杂，需要引入条件概率来反映信源发出符号序列内各个符号之间的记忆特征。2/1/202320马尔可夫信源马尔可夫信源（相对简单的离散平稳信源）信源在某一时刻发出符号的概率除与该符号有关外，只与此前发出的有限个符号有关。若把这有限个符号记作一个状态S，则信源发出某一符号的概率除与该符号有关外，只与该时刻信源所处的状态有关。在这种情况下，信源将来的状态及其送出的符号将只与信源现在的状态有关，而与信源过去的状态无关。m阶马尔可夫信源信源输出某一符号的概率仅与以前的m个符号有关，而与更前面的符号无关。2/1/202321马尔可夫信源：条件概率一阶马尔可夫信源m阶马尔可夫信源2/1/202322连续平稳信源连续平稳信源若信源输出的消息需用L维随机矢量来描述，

其中每个随机变量Xl都是取值为连续的连续型随机变量，并且满足随机矢量X的各维概率密度函数与时间起点无关，这样的信源称为连续平稳信源。例如语音信号、热噪声信号等在时间上取样离散化后的信源，在时间上是离散的，但每个随机变量Xl的取值都是连续的。2/1/202323随机波形信源随机波形信源实际信源输出的消息常常是时间和取值都是连续的，这类信源称为随机波形信源。这种信源输出的消息可用随机过程来描述。根据取样定理对随机过程进行取样，把随机过程用一系列时间（或频率）域上离散的取样值来表示，每个取样值都是连续型随机变量。这样，就可以把随机过程转换成时间（或频率）上离散的随机序列来处理。2/1/202324信源分类与描述图2/1/202325第2章信源及信源熵2.1信源的描述和分类2.2离散信源熵和互信息2.3离散序列信源的熵2.4冗余度2.5连续信源的熵和互信息2/1/2023262.2离散信源熵和互信息不确定性、先验概率和信息量随机事件的不确定性是客观存在的。只有当信源发出的消息通过信道传输给收信者后，才能消除不确定性并获得信息。随机事件的先验概率越小，事件发生的困难程度就越大，不确定性就越大。收到某消息获得的信息量＝不确定性减少的量＝（收到此信息前关于某事件发生的不确定性）－（收到此信息后关于某事件发生的不确定性）2/1/202327自信息量某事件发生所携带的信息量是和该事件出现的概率有关，概率可以表征自信息量的大小根据客观事实和人们的习惯概念，自信息量应满足以下条件：自信息量应是先验概率的单调递减函数当时，当时，两个独立事件的联合信息量应等于它们分别的信息量之和。2/1/202328自信息量随机事件的自信息量定义为其概率对数的负值，从多个角度理解I(xi)的含义:事件xi

是否发生的不确定性的大小事件xi的发生带给我们的信息量的大小事件xi

是否发生所需的信息量的大小事件xi的发生带给我们的比特数2/1/202329自信息量和不确定度随机事件的不确定度在数量上等于它的自信息量，两者的单位相同，但含义不同。具有某种概率分布的随机事件不管发生与否，都存在不确定度，不确定度表征了该事件的特性而自信息量是在该事件发生后给予观察者的信息量。

2/1/202330自信息量自信息量的单位在信息论中常用的对数底是2，信息量的单位为比特(bit)；若取自然对数，则信息量的单位为奈特(nat);若以10为对数底,则信息量的单位为笛特(det)。1nat＝log2e≈l.433bit1det＝log210≈3.322bit哈特莱Hartley2/1/202331自信息量二进制码元0,1,当符号概率为p(0)=1/4,p(1)=3/4,则这两个符号的自信息量为：

I(0)=－log2p(0)=－log2(1/4)=log24=2bit

I(1)=－log2p(1)=－log2(3/4)=0.415bit一个以等概率出现的二进制码元(0,1)所包含的自信息量为：

I(0)=I(1)=－log2(1/2)=log22=1bit一个m位的二进制数,有

个等概率的可能组合

I=－log2(1/2m)=mbit2m2/1/202332自信息量例：英文字母中“e”出现的概率为0.105，“c”出现的概率为0.023，“z”出现的概率为0.001。分别计算它们的自信息量。解：“e”的自信息量I(e)=－log20.105=3.25bit “c”的自信息量I(c)=－log20.023=5.44bit “z”的自信息量I(z)=－log20.001=9.97bit2/1/202333自信息量的特性I(xi)是非负值当p(xi)=1时，I(xi)=0当p(xi)=0时，I(xi)=∞I(xi)是先验概率p(xi)的单调递减函数，即当p(x1)＞p(x2)时，I(x1)＜I(x2)两个独立事件的联合信息量等于它们分别的信息量之和。即：统计独立信源的信息量等于它们分别的信息量之和。2/1/202334联合自信息量两个消息xi，yj同时出现的联合自信息量当xi,yj相互独立时，有p(xi

yj)=p(xi)p(yj)，那么就有I(xi

yj)=I(xi)+I(yj)。xi

yj所包含的不确定度在数值上也等于它们的自信息量。2/1/202335条件自信息量在事件yj出现的条件下，随机事件xi发生的条件概率为p(xi/yj)，则它的条件自信息量定义为条件概率对数的负值：在给定yj条件下，随机事件xi所包含的不确定度在数值上与条件自信息量相同，但两者含义不同。联合自信息量、条件自信息量和自信息量2/1/202336离散信源熵例：一个布袋内放100个球，其中80个球是红色的，20个球是白色的，若随机摸取一个球，猜测其颜色，求平均摸取一次所能获得的自信息量。解:依据题意，这一随机事件的概率空间为如果摸出的是红球，则获得的信息量是如果摸出的是白球，则获得的信息量是2/1/202337离散信源熵每次摸出一个球后放回袋中，再进行下一次摸取。 如此摸取n次，红球出现的次数为np(x1)次，白球出现的次数为np(x2)次。随机摸取n次后总共所获得信息量为平均随机摸取一次所获得的信息量为平均信息量信源X的熵2/1/202338离散信源熵H(X)定义离散信源熵为信源中各个符号不确定度的数学期望单位为：比特/符号或者比特/符号序列。信息熵H(X)表示信源输出后，每个消息(或符号)所提供的平均信息量。平均不确定度/平均信息量/平均自信息量当某一符号xi的概率p(xi)为零时，p(xi)log2

p(xi)在熵公式中无意义，为此规定这时的p(xi)log2

p(xi)为零。2/1/202339离散信源熵H(X)信源熵的物理含义表示信源输出前信源的平均不确定性表示信源输出后每个符号所携带的平均信息量例：有两个信源，其概率空间分别为H(Y)>H(X)：信源Y比信源X的平均不确定性要大2/1/202340离散信源熵H(X)例：电视屏上约有个格点，按每点有10个不同的灰度等级考虑，则共能组成个不同的画面。按等概率计算，平均每个画面可提供的信息量为2/1/202341离散信源熵H(X)例：有一篇千字文章，假定每字可从万字表中任选，则共有不同的千字文N=100001000=104000篇，仍按等概计算，平均每篇千字文可提供的信息量为Apictureisworthathousandwords2/1/202342离散信源熵H(X)例：信源X输出符号只有两个，设为0和1。输出符号发生的概率分别为p和q，p＋q=l。即信源的概率空间为

二元信源熵为2/1/202343q=1离散信源熵H(X)信源熵H(X)是概率p的函数，通常用H(p)表示，p取值于[0,1]区间。H(p)函数曲线如图所示：如果二元信源的输出符号是确定的,即p=1或q=1,则该信源不提供任何信息。当二元信源符号0和1以等概率发生时,信源熵达到极大值,等于1比特信息量。p=1p=q=0.52/1/202344条件熵在给定yj条件下，xi的条件自信息量为I(xi/yj)，X集合的条件熵在给定Y（即各个yj）条件下，X集合的条件熵在给定X（即各个xi）条件下，Y集合的条件熵条件熵是在联合符号集合XY上的条件自信息量的联合概率加权统计平均值。2/1/202345条件熵例：考虑下面两个随机变量X和Y，其中

计算条件熵H(X/Y)。解：

2/1/202346联合熵联合熵是联合符号集合XY上的每个元素对xiyj的自信息量的概率加权统计平均值联合熵H(XY)表示X和Y同时发生的不确定度。联合熵、信源熵和条件熵之间的关系2/1/202347定理证明证明：2/1/202348联合熵例：令XY具有如下的联合分布，求信源熵和联合熵XY1234Σ11/81/161/321/321/421/161/81/321/321/431/161/161/161/161/441/40001/4Σ1/21/41/81/81解：p(y1)p(x4)比特/符号比特/符号比特/符号2/1/202349例题例：二进制通信系统用符号“0”和“1”，由于存在失真，传输时会产生误码，用符号表示下列事件：

u0：一个“0”发出；u1：一个“1”发出；

v0：一个“0”收到；v1：一个“1”收到。 给定下列概率：

p(u0)＝1/2，p(v0/u0)＝3/4，p(v0/u1)=1/2。求：⑴已知发出一个“0”，求收到符号后得到的信息量；⑵已知发出的符号，求收到符号后得到的信息量；⑶知道发出的和收到的符号，求能得到的信息量；⑷已知收到的符号，求被告知发出的符号得到的信息量。H(V/u0)H(V/U)H(UV)H(U/V)2/1/202350例题解：⑴p(v1/u0)=1－p(v0/u0)=1/4⑵联合概率：

p(u0v0)=p(v0/u0)p(u0)=3/4×1/2=3/8

p(u0v1)=p(v1/u0)p(u0)=1/4×1/2=1/8

p(u1v0)=p(v0/u1)p(u1)=1/2×1/2=1/4

p(u1v1)=p(v1/u1)p(u1)=1/2×1/2=1/42/1/202351例题⑶解法1：解法2：

2/1/202352例题(4)解法1：

p(v0)=p(u0v0)+p(u1v0)=3/8+1/4=5/8

p(v1)=1-p(v0)=3/8 解法2：利用贝叶斯公式

p(u0/v0)=3/5

p(u1/v0)=2/5

p(u0/v1)=1/3p(u1/v1)=2/32/1/202353例题例：一个二进制信源X发出符号集{0,1}，经过离散无记忆信道传输，信道输出用Y表示。由于信道中存在噪声，接收端除收到0和1的符号外，还有不确定符号，用“2”表示。已知X的先验概率为:p(x0)=2/3，p(x1)=1/3符号转移概率：p(y0/x0)=3/4，p(y2/x0)=1/4

p(y1/x1)=1/2，p(y2/x1)=1/2 求：联合熵H(XY)XY010123/41/21/21/42/1/202354例题信源熵：由 得联合概率：p(x0y0)=p(x0)p(y0/x0)=2/3×3/4=1/2p(x1y0)=p(x1)p(y0/x1)=0p(x0y1)=p(x0)p(y1/x0)=0 p(x1y1)=p(x1)p(y1/x1)=1/3×1/2=1/6

p(x0y2)=p(x0)p(y2/x0)=2/3×1/4=1/6p(x1y2)=p(x1)p(y2/x1)=1/3×1/2=1/6条件熵：联合熵：H(XY)＝H(X)＋H(Y/X)=1.8bit/符号2/1/202355另一种解法Ｙ的无条件概率 p(y0)=∑p(xiy0)=p(x0y0)+p(x1y0)=1/2+0=1/2p(y1)=∑p(xiy1)=p(x0y1)+p(x1y1)=0+1/6=1/6

p(y2)=∑p(xiy2)=p(x0y2)+p(x1y2)=1/6+1/6=1/3Y的熵X的条件熵同理p(x0/y1)=0，p(x1/y1)=1；p(x0/y2)=1/2，p(x1/y2)=1/2联合熵：H(XY)=H(Y)+H(X/Y)=1.8bit/符号2/1/202356例题分析分析H(X)=0.92bit/符号未收到任何消息时，接收者对X的平均不确定度H(X/Y)=0.33bit/符号收到消息Y后，接收者对X的平均不确定度 不确定度的减少量（0.59bit/符号）就是接收者通过信道传输收到的信息量，称为X和Y的互信息I(X;Y)2/1/202357互信息设有两个随机事件X和Y，X是信源发出的离散符号集合，Y是信宿收到的离散符号集合。有扰信道干扰源信源X信宿Y2/1/202358互信息如果信道是无噪的，当信源发出消息xi后，信宿必能准确无误地收到该消息，彻底消除对xi的不确定度，所获得的信息量就是xi的不确定度I(xi)，即xi本身含有的全部信息。——理想情况一般而言，信道中总是存在着噪声和干扰，信源发出消息xi，通过信道后信宿只可能收到由于干扰作用引起的某种变型yj。——实际情况信宿收到yj后推测信源发出xi的概率p(xi

/yj)称为后验概率。信源发出消息xi的概率p(xi)称为先验概率。2/1/202359互信息事件xi的不确定性用I(xi)度量。接收到符号yj后，事件xi仍保留的不确定性，用I(xi

/yj)度量。接收到某消息yj后获得的关于事件xi的信息量，用I(xi;yj)表示。互信息等于后验概率与先验概率比值的对数2/1/202360例题例：设信源空间为 如果信宿收到消息

y1＝“不是晴天”，求y1分别与xi之间的互信息量。解：自信息量分别为

I(x1)=-logp(x1)=1bitI(x2)=-logp(x2)=2bit

I(x3)=-logp(x3)=3bit I(x4)=-logp(x4)=3bit

y1

无条件概率：p(y1)=1/2

y1和X的联合概率：

p(x1y1)=0 p(x2y1)=p(x2)=1/4

p(x3y1)=p(x3)=1/8p(x4y1)=p(x4)=1/8 2/1/202361例题

条件概率为：p(x1/y1)=p(x1y1)/p(y1)=0p(x2/y1)=p(x2y1)/p(y1)=1/2p(x3/y1)=p(x3y1)/p(y1)=1/4p(x4/y1)=p(x4y1)/p(y1)=1/4

互信息量为：

I(x1;y1)=log[p(x1/y1)/p(x1)]=0

I(x2;y1)=log[p(x2/y1)/p(x2)]=1bit

I(x3;y1)=log[p(x3/y1)/p(x3)]=1bit I(x4;y1)=log[p(x4/y1)/p(x4)]=1bit信道传送的互信息量是用来解除信源符号的不确定度的。2/1/202362例2-10信源消息二进码字先验概率后验概率收到0后收到01后收到011后x10001/8x20011/8x30101/8x40111/8x51001/8x61011/8x71101/8x81111/800001/41/41/41/40000001/21/2000000012/1/202363互信息的性质对称性当X和Y相互独立时，单符号间互信息量可为正值或负值

平均意义上的互信息量一定大于或等于零2/1/202364平均互信息互信息量I(xi;yj)在X集合上的统计平均值为I(X;yj)在Y集合上的概率加权统计平均值平均互信息（量）2/1/202365平均互信息例：某人研究了当地的天气记录和气象台的预报记录后，得到实际天气和预报天气的联合概率分布，如下表所示。他发现预报只有12/16的准确率，而只预报“明天不下雨”的准确率却是13/16。他把这个想法告诉台长，台长却说他错了。请问这是为什么？

实际预报下雨不下雨下雨1/83/16不下雨1/1610/162/1/202366平均互信息解：设X表示实际天气情况，Y表示预报情况，Z表示“预报不下雨”的情况I(X;Y)<<H(X)天气预报确实不准I(X;Z)=0总是“预报不下雨”不传递信息2/1/202367平均互信息量的物理意义H(X/Y)：信道疑义度，损失熵信源符号通过有噪信道传输后引起的信息量损失。信源X的熵等于接收到的信息量加损失掉的信息量。

H(Y/X)：噪声熵，散布度它反映了信道中噪声源的不确定性。输出端信源Y的熵H(Y)等于接收到关于X的信息量I(X;Y)加上H(Y/X)，这完全是由信道中噪声引起的。2/1/202368平均互信息量的物理意义如果X与Y是相互独立的，无法从Y中去提取关于X的信息，即H(X/Y)=H(X)，故称为全损离散信道。如果Y是X的确定的一一对应函数，I(X;Y)＝H(X)，已知Y就完全解除了关于X的不确定度，所获得的信息就是X的不确定度或熵。这可看成无扰离散信道。疑义度H(X/Y)为零，噪声熵也为零。在一般情况下，X和Y既非相互独立，也不是一一对应，那么从Y获得X的信息必在零与H(X)之间，即常小于X的熵。2/1/202369多变量互信息量符号xi与符号对yjzk之间的互信息量为条件互信息量一个联合事件yjzk出现后提供的有关xi的信息量zk事件出现后提供的有关xi的信息量给定zk条件下再出现yj事件后提供的有关xi的信息量2/1/202370三维联合集的平均互信息量2/1/202371数据处理中信息的变化X是输入消息集合，Y是第一级处理器的输出消息集合，Z为第二级处理器的输出消息集合，假设在Y条件下X与Z相互独立。第一级处理器第二级处理器XYZ输入2/1/202372数据处理中信息的变化当对信号、数据或消息进行多级处理时，每处理一次就有可能损失一部分信息，也就是说数据处理会把信号、数据或消息变成更有用的形式，但是绝不会创造出新的信息，这就是所谓的信息不增性。2/1/202373数据处理中信息的变化编码信道译码UXYV信息经过编码或译码处理后均不可能增加，只会减少从测量结果Y中获得更多关于X的信息量，常用方法是：增加测量次数。测量Y的次数越多，X的条件熵越小，获得的信息量就越大。2/1/202374熵的性质非负性H(X)＝H(x1,x2,……,xn)≥0等号在p(xi)=1时成立对称性H(x1,x2,……,xn)＝H(x2,x1,……,xn)熵函数只与随机变量的总体结构有关2/1/202375熵的性质确定性H(0,1)＝H(1,0,0,……,0)＝0只要信源符号集中有一个符号的出现概率为1，信源熵就等于零扩展性如果集合中有一个或多个事件的概率相比于其他事件非常小，这些小概率事件可以忽略不计。如：编写词典2/1/202376熵的性质最大熵定理离散无记忆信源输出M个不同的信息符号，当且仅当各个符号出现概率相等时（即等概率分布），熵最大条件熵小于无条件熵条件熵小于无条件熵两个条件的条件熵小于一个条件的条件熵联合熵小于信源熵之和2/1/202377互信息量与熵H(X/Y)H(X)H(Y)H(XY)H(Y/X)I(X;Y)维拉图2/1/202378第2章信源及信源熵2.1信源的描述和分类2.2离散信源熵和互信息2.3离散序列信源的熵2.4冗余度2.5连续信源的熵和互信息2/1/202379离散序列信源的熵设信源输出的随机序列为X

=(X1X2…Xl…XL)序列中的变量Xl∈{x1,x2,…

xn}随机序列的概率为式中，2/1/202380离散无记忆信源的序列熵当信源无记忆时 信源的序列熵为2/1/202381离散无记忆信源的序列熵当信源平稳时，即与序号l无关信源的序列熵可以表示为信源序列中，平均每个符号的熵为离散无记忆信源平均每个符号的符号熵HL(X)等于单个符号信源的符号熵H(X)平稳、无记忆2/1/202382例题有一个无记忆信源随机变量X∈(0,1)，等概率分布，若以单个符号出现为一事件，则此时的信源熵：如果以两个符号出现(L=2的序列)为一事件，则随机序列X∈(00,01,10,11)，信源的序列熵信源的符号熵为用1比特表示该事件用2比特表示该事件信源序列的符号熵等于单符号信源熵2/1/202383例题例：有一离散平稳无记忆信源 求：二次扩展信源的熵

解：X2信源的元素

a1

a2a3a4a5a6a7a8a9对应的符号序列

x1x1x1x2x1x3x2x1x2x2x2x3x3x1x3x2x3x3概率p(ai)1/41/81/81/81/161/161/81/161/16信源的序列熵平均每个符号的熵单符号信源熵序列的符号熵序列信源熵2/1/202384离散有记忆信源的序列熵若信源输出一个L长序列，则信源的序列熵为平均每个符号的熵为信源无记忆时满足平稳时2/1/202385例题例：已知离散有记忆信源中各符号的概率空间为: 现信源发出二重符号序列消息(ai,aj)，这两个符号的概率关联性用条件概率p(aj/ai)表示，并由下表给出。求信源的序列熵和平均符号熵。ajaia0a1a2a09/112/110a11/83/41/8a202/97/9ajaia0a1a2a01/41/180a11/181/31/18a201/187/362/1/202386例题解：条件熵

单符号信源熵 信源的序列熵 平均符号熵H2(X)<H(X)：符号序列中的符号之间存在关联性，导 致符号的不确定度减小2/1/202387离散平稳信源离散平稳信源的联合概率具有时间推移不变性即平稳信源发出的符号序列的概率分布与时间起点无关。结论1：H(XL/XL-1)是L的单调非增函数2/1/202388离散平稳信源结论2：HL

(X)≥H(XL/XL-1)结论3：HL

(X)是L的单调非增函数2/1/202389离散平稳信源结论4：当L→∞时，H∞(X)称为极限熵结论4在理论上定义了平稳离散有记忆信源的极限熵，实际上如按此公式计算极限熵是十分困难的。对于一般离散平稳信源，取不太大的L就能得到非常接近H∞(X)的HL(X)，因此实际应用中常取有限L下的条件熵H(XL/XL-1)作为H∞(X)的近似值。2/1/202390马尔可夫信源在很多信源的输出序列中，符号之间的依赖关系是有限的，信源符号发生的概率只与前边已经发出的若干个符号有关，而与更前面的符号无关。为了描述这类信源，除了信源符号集外还要引入状态集。即：信源输出消息符号除与符号本身有关外，还与信源所处的状态有关。若一个信源满足下面两个条件，则称为马尔可夫信源：某一时刻信源输出符号的概率只与当前所处的状态有关，而与以前的状态无关；信源的下一个状态由当前状态和下一刻的输出符号唯一确定。2/1/202391马尔可夫信源对于m阶马尔可夫信源X＝(x1,x2,…,xq)，引入符号条件概率和状态转移概率，可以转化为马尔可夫链。令状态si

=(xi1xi2…xim)，i1,i2,…,im

∈(1,2,…,q)信源符号表中的数目为q，m个符号组成的状态si共有Q=qm种，这些序列组成状态集 S={s1,s2,…,sQ}例：二元序列为…01011100…，若m=2，则Q=qm=22=4，即s1=00s2=01s3=10s4=11 对应的状态序列为：…s2s3s2s4s4s3s1…2/1/202392马尔可夫信源符号条件概率信源在某一时刻出现符号xj的概率与信源此时所处的状态si有关，用条件概率表示为p(xj/si)i=1,2,…,Q

j=1,2,…,q状态转移概率当信源符号xj出现后，信源所处的状态将发生变化，并转入一个新的状态。这种状态的转移可用状态转移概率表示2/1/202393转移概率矩阵若信源处于某一状态si，当发出一个符号后，所处状态就改变了。任何时候信源处于什么状态完全由前一时刻的状态和发出的符号决定。系统在任一时刻可处于状态空间S={s1,s2,…,sQ}中的任意一个状态，状态转移时的转移概率矩阵矩阵中第i行元素对应于从某一个 状态si转移到所有状态sj的转移概率第j列元素对应于从所有状态si转移到同一状态sj的转移概率符号条件概率矩阵2/1/202394马尔可夫信源一步转移概率（基本转移概率）Pij(m,n)中n=m+1，即Pij(m,m+1)，记为Pij(m)pij(m)=p{Sm+1=sj/Sm=si}=p(sj/si)齐次马尔可夫链其转移概率具有推移不变性，即只与状态有关，与时刻m无关pij(m)=p{Sm+1=sj/Sm=si}=p(S2=sj/S1=si)=pij性质：2/1/202395齐次马尔可夫链切普曼－柯尔莫郭洛夫方程k步转移概率与l(l<k)步和(k-l)步转移概率之间的关系当l＝1时，若用矩阵表示，齐次马尔可夫链的一步转移概率完全决定了k步转移概率2/1/202396状态转移图（香农线图）齐次马尔可夫链可以用其状态转移图（香农线图）表示每个圆圈代表一种状态

状态之间的有向线代表从某一状态向另一状态的转移有向线一侧的符号和数字分别代表发出的符号和条件概率sos1x2/0.6x1/0.3x1/0.4s2x2/0.2x1/0.8x2/0.7p(x1/s2)=0.8p(s2/s2)=0.82/1/202397例题例：设有一个二进制二阶马尔可夫信源，信源符号集为{0,1}，条件概率为 绘制该信源的状态转移图。S1=00S2=01S3=10S4=11s1s2s3s40/0.81/0.20/0.51/0.50/0.51/0.50/0.21/0.8状态转移矩阵符号条件概率矩阵2/1/202398例题例：如图所示是一个相对码编码器。输入的码Xr(r=1,2,…)是相互独立的，取值0或1，且已知p(X=0)=p,p(X=1)=1－p=q，输出的码是Yr，显然 Yr是一个一阶马氏链，Yr确定后，Yr+1概率分布只与Yr有关，与Yr-1、Yr-2…等无关 p00=p(Y2=0/Y1=0)=p(X=0)=p p01=P(Y2=1/Y1=0)=p(X=1)=q p10=P(Y2=0/Y1=1)=p(X=1)=q p11=p(Y2=1/Y1=1)=p(X=0)=pTXrYr＋01pqqp2/1/202399稳定的马尔可夫信源不可约性对任意一对i和j，都存在至少一个k，使pij(k)＞0若对所有k，pij(k)＝0，意味着一旦出现状态si就不再可能到达状态sj，无法各态遍历非周期性所有pij(n)＞0的n中没有比1大的公因子非不可约马氏链周期性马氏链2/1/2023100马尔可夫信源遍历性的直观意义不论质点从哪一个状态si出发，当转移步数k足够大时，转移到sj的概率pij(k)都近似等于某个常数Wj 即：如果转移步数k充分大，就可以用常数Wj作为k步转移概率pij(k)的近似值平稳马尔可夫信源的含义经过足够长时间之后，信源的每种状态出现的概率逐渐稳定下来，不再发生变化。状态的稳定分布与初始状态无关，即无论信源一开始处在什么状态，最终都将达到同样的稳定分布。2/1/2023101初始状态的影响初始状态状态序列符号序列信源分布00000000000202222002202210100111122331101123101123非平稳2/1/2023102稳定的马尔可夫信源极限概率Wj一个不可约的、非周期的、状态有限的马尔可夫链，其k步转移概率pij(k)在k→∞时趋于一个和初始状态无关的概率，即不论起始状态如何，这种马氏链都可以最后达到稳定。平稳分布Wj可用下列方程组求得2/1/2023103例题例：有一个二元二阶马尔可夫信源，信源符号集为{0,1},状态变量S={00,01,10,11}。已知符号条件概率：

p(0/00)=1/2 p(1/00)=1/2

p(0/01)=1/3 p(1/01)=2/3

p(0/10)=1/4 p(1/10)=3/4

p(0/11)=1/5 p(1/11)=4/5求：⑴信源全部状态及状态转移概率 ⑵画出完整的二阶马尔可夫信源状态转移图。