第2章1信息论与编码.ppt

1、2020/8/5,1,第2章信源及信源熵,2.1 信源的描述和分类 2.2 离散信源熵和互信息 2.3 离散序列信源熵 2.4 连续信源熵和互信息 2.5 冗余度,2020/8/5,2,复习信息的概念,在信息论中，信源是发出消息的源，信源输出以符号形式出现的具体消息。 如果符号是确定的而且预先是知道的，那么该消息就无信息而言。只有当符号的出现是随机的，预先无法确定，那么一旦出现某个符号就给观察者提供了信息。 因此，应该用随机变量或随机矢量来表示信源，运用概率论和随机过程的理论来研究信息，这就是香农信息论的基本点。,2020/8/5,3,2.1 信源的描述和分类,按信源在时间和幅度上的分布情况

2、离散信源：文字、数据、电报 连续信源：语音、图像 按发出符号的数量 单个符号信源：指信源每次只发出一个符号代表一个消息 符号序列信源：指信源每次发出一组含二个以上符号的符号序列代表一个消息 按符号间的关系 无记忆信源 有记忆信源,信源所发出的各个符号是相互独立的，发出的符号序列中的各个符号之间没有统计关联性,信源所发出的各个符号的概率是有关联的,2020/8/5,4,信源分类,信源,无记忆信源,有记忆信源,发出单个符号的无记忆信源,发出符号序列的无记忆信源,发出符号序列的有记忆信源,发出符号序列的马尔可夫信源,马尔可夫信源：某一个符号出现的概率只与前面一个或有限个符号有关，而不依赖更前面的那些

3、符号,2020/8/5,5,概率空间,概率 随机现象中事件发生的可能性大小是客观存在的，因此可以对它进行量度。量度的数量指标就是概率。 样本空间 某事物各种可能出现的不同状态，即所有可能选择的消息集合。 每个可能选择的消息是这个样本空间的一个元素。 概率空间 对于离散消息的集合，概率测度就是对每一个可能选择的消息指定一个概率。 一个样本空间和它的概率测度一起构成一个概率空间。,2020/8/5,6,概率空间,数学定义 一个离散信源发出的各个符号消息的集合为,它们的概率分别为,该信源的概率空间为,显然有,信源空间,先验概率,2020/8/5,7,概率论复习,无条件概率P(xi) 又称先验概率，指

4、基于以往数据记录统计得到的概率 条件概率P(B/A) 在已知事件A发生条件下，事件B发生的概率 又称后验概率 联合概率P(AB) 事件A和事件B同时发生的概率,2020/8/5,8,概率论复习,完备性,非负性,2020/8/5,9,概率论复习,联合概率,贝叶斯公式,2020/8/5,10,单个符号的离散无记忆信源,有些信源可能输出的消息数是有限的或可数的，而且每次只输出其中一个消息。 如书信文字、计算机的代码、电报符号、阿拉伯数字码等。 例如：掷骰子 扔一颗质地均匀的骰子，每次扔掷的结果必然是 1点6点中的某一面朝上，哪一面朝上是随机的。,2020/8/5,11,单个符号的离散无记忆信源,用一

5、维离散型随机变量X来描述这些信息的输出。 数学模型,当信源给定，其相应的概率空间就已给定；反之，如果概率空间给定，这就表示相应的信源已给定。 信源可能的消息（符号）数是有限的，而且每次必定选取其中一个消息输出，满足完备集条件。,2020/8/5,12,单符号连续无记忆信源,连续信源：输出在时间和幅度上都是连续分布的连续消息的信源。 单符号连续无记忆信源 消息数无限或不可数，且每次只输出其中一个消息。可用一维的连续型随机变量X来描述这些消息。 数学描述 例：随机取一节干电池测其电压值作为输出符号，符号取值为0，1.5之间的所有实数。,pX(x)是随机变量X的概率密度函数,2020/8/5,13,

6、符号序列的离散无记忆信源,很多实际信源输出的消息往往是由一系列符号组成，这种用每次发出1组含2个以上符号的符号序列来代表一个消息的信源叫做发出符号序列的信源。 设信源输出的随机序列为X， 序列中的变量 即序列长为L 扔骰子：以三位二进制符号表示结果,2020/8/5,14,符号序列的离散无记忆信源,最简单的符号序列信源是L2的情况，即 信源： 信源空间： 当信源无记忆时，,2020/8/5,15,符号序列的离散无记忆信源,二元信源0,1 单符号离散信源 二次扩展信源 三次扩展信源 三元信源0,1,2 三元二次扩展信源,样本N3 序列长度L2,2020/8/5,16,符号序列的离散无记忆信源,L

7、次扩展信源 每个随机变量取值有n种，那么序列长为L的随机序列，其样值共有nL种可能取值。这种由信源X输出的L长随机序列X所描述的信源叫做离散无记忆信源X的L次扩展信源。 数学描述 其中，,2020/8/5,17,离散有记忆信源,一般情况下，信源在不同时刻发出的符号之间是相互依赖的，也就是信源输出的平稳随机序列X中，各随机变量xl之间是有依赖关系的。 如：袋中摸球 文字序列的前后关系 表述有记忆信源比表述无记忆信源困难得多 离散有记忆信源 发出符号序列的有记忆信源 发出符号序列的马尔可夫信源,用信源发出的一个符号序列的整体概率(即联合概率)反映有记忆信源的特征,一个符号出现的概率只与前面一个或有

8、限个符号有关,而不依赖更前面的那些符号,2020/8/5,18,离散有记忆信源,例如由英文字母组成单词，字母间是有关联性的，不是任何字母的组合都能成为有意义的单词。 例如布袋中有100个球，80个红球，20个白球。先取出一个球，记下颜色后不放回布袋，接着取另一个。 取第一个球时的概率 p(红球)=80/100，p(白球)=20/100 若第1个球为红色，则取第二个球时的概率 p(红球)=79/99，p(白球)=20/99 若第1个球为白色，则取第二个球时的概率 p(红球)=80/99，p(白球)=19/99,2020/8/5,19,离散有记忆信源,有记忆信源的联合概率表示比较复杂，需要引入条件

9、概率来反映信源发出符号序列内各个符号之间的记忆特征。,2020/8/5,20,马尔可夫信源,马尔可夫信源（相对简单的离散平稳信源） 信源在某一时刻发出符号的概率除与该符号有关外，只与此前发出的有限个符号有关。 若把这有限个符号记作一个状态S，则信源发出某一符号的概率除与该符号有关外，只与该时刻信源所处的状态有关。 在这种情况下，信源将来的状态及其送出的符号将只与信源现在的状态有关，而与信源过去的状态无关。 m阶马尔可夫信源 信源输出某一符号的概率仅与以前的m个符号有关，而与更前面的符号无关。,2020/8/5,21,马尔可夫信源：条件概率,一阶马尔可夫信源,m阶马尔可夫信源,2020/8/5,

10、22,连续平稳信源,连续平稳信源 若信源输出的消息需用L维随机矢量来描述， 其中每个随机矢量Xl都是取值为连续的连续型随机变量，并且满足随机矢量X的各维概率密度函数与时间起点无关，这样的信源称为连续平稳信源。 例如语音信号、热噪声信号等在时间上取样离散化后的信源，在时间上是离散的，但每个随机变量Xl的取值都是连续的。,2020/8/5,23,随机波形信源,随机波形信源 实际信源输出的消息常常是时间和取值都是连续的，这类信源称为随机波形信源。 这种信源输出的消息可用随机过程来描述。 根据取样定理对随机过程进行取样，把随机过程用一系列时间（或频率）域上离散的取样值来表示，每个取样值都是连续型随机变

11、量。这样，就可以把随机过程转换成时间（或频率）上离散的随机序列来处理。,2020/8/5,24,信源分类与描述图,2020/8/5,25,第2章信源及信源熵,2.1 信源的描述和分类 2.2 离散信源熵和互信息 2.3 离散序列信源的熵 2.4 连续信源的熵和互信息 2.5 冗余度,2020/8/5,26,2.2 离散信源熵和互信息,不确定性、先验概率和信息量 随机事件的不确定性是客观存在的。只有当信源发出的消息通过信道传输给收信者后，才能消除不确定性并获得信息。 随机事件的先验概率越小，事件发生的困难程度就越大，不确定性就越大。,收到某消息获得的信息量不确定性减少的量 （收到此信息前关于某事

12、件发生的不确定性） （收到此信息后关于某事件发生的不确定性）,2020/8/5,27,自信息量,某事件发生所携带的信息量是和该事件出现的概率有关，概率可以表征自信息量的大小,根据客观事实和人们的习惯概念，自信息量应满足以下条件： 自信息量应是先验概率的单调递减函数 当时， 当时， 两个独立事件的联合信息量应等于它们分别的信息量之和。,2020/8/5,28,自信息量,随机事件的自信息量定义为其概率对数的负值，即,I (xi) 含义: 当事件xi发生以前，表示事件xi发生的不确定性 当事件xi发生以后，表示事件xi所含有的信息量,2020/8/5,29,自信息量和不确定度,随机事件的不确定度在数

13、量上等于它的自信息量，两者的单位相同，但含义不同。 具有某种概率分布的随机事件不管发生与否，都存在不确定度，不确定度表征了该事件的特性 而自信息量是在该事件发生后给予观察者的信息量。,2020/8/5,30,自信息量,自信息量的单位 在信息论中常用的对数底是2，信息量的单位为比特(bit)； 若取自然对数，则信息量的单位为奈特(nat); 若以10为对数底,则信息量的单位为笛特(det) 1 natlog2e l.433 bit 1 detlog2103.322 bit,哈特莱 Hartley,2020/8/5,31,自信息量,二进制码元0,1,当符号概率为p(0)=1/4, p(1)=3/4

14、,则这两个符号的自信息量为： I(0) =log2 p(0)= log2 (1/4)=log24= 2 bit I(1) =log2 p(1)= log2 (3/4) =0.415 bit 一个以等概率出现的二进制码元(0,1)所包含的自信息量为： I(0)= I(1)= log2 (1/2)=log22=1 bit 一个m位的二进制数,有2m个等概率的可能组合 I=log2(1/2m)=m bit,2020/8/5,32,自信息量,例：英文字母中“e” 出现的概率为0.105，“c”出现的概率为0.023，“o”出现的概率为0.001。分别计算它们的自信息量。 解：“e”的自信息量 I(e)

15、 =log20.105=3.25 bit “c”的自信息量 I(c) =log20.023=5.44 bit “o”的自信息量 I(o) =log20.001=9.97 bit,2020/8/5,33,自信息量的特性,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) 两个独立事件的联合信息量等于它们分别的信息量之和。即：统计独立信源的信息量等于它们分别的信息量之和。,2020/8/5,34,联合自信息量,两个消息xi，yj同时出现的联合自

16、信息量 当xi, yj相互独立时，有p(xi yj)=p(xi)p(yj)，那么就有 I(xi yj)=I(xi)+I(yj)。 xi yj所包含的不确定度在数值上也等于它们的自信息量。,2020/8/5,35,条件自信息量,在事件yj出现的条件下，随机事件xi发生的条件概率为p(xi / yj) ，则它的条件自信息量定义为条件概率对数的负值： 在给定yj条件下，随机事件xi所包含的不确定度在数值上与条件自信息量相同，但两者含义不同。 联合自信息量、条件自信息量和自信息量,2020/8/5,36,离散信源熵,例：一个布袋内放100个球，其中80个球是红色的，20个球是白色的，若随机摸取一个球，

17、猜测其颜色，求平均摸取一次所能获得的自信息量。 解: 依据题意，这一随机事件的概率空间为 如果摸出的是红球，则获得的信息量是 如果摸出的是白球，则获得的信息量是,2020/8/5,37,离散信源熵,每次摸出一个球后放回袋中，再进行下一次摸取。 如此摸取n次，红球出现的次数为np(x1)次，白球出现的次数为np(x2)次。随机摸取n次后总共所获得信息量为 平均随机摸取一次所获得的信息量为,平均信息量,信源X的熵,2020/8/5,38,离散信源熵H(X),定义 离散信源熵为信源中各个符号不确定度的数学期望 单位为：比特/符号 或者 比特/符号序列。 信息熵H(X)表示信源输出后，每个消息(或符号

18、)所提供的平均信息量。 平均不确定度/平均信息量/平均自信息量 当某一符号xi的概率p(xi)为零时， p(xi)log2 p(xi)在熵公式中无意义，为此规定这时的p(xi)log2 p(xi)为零。,2020/8/5,39,离散信源熵H(X),信源熵的物理含义 表示信源输出前信源的平均不确定性 表示信源输出后每个符号所携带的平均信息量 例：有两个信源，其概率空间分别为,H(Y) H(X) ：信源Y比信源X的平均不确定性要大,2020/8/5,40,离散信源熵H(X),例：电视屏上约有 个格点，按每点有 10个不同的灰度等级考虑，则共能组成 个不同的画面。按等概率计算，平均每个画面可提供的信

19、息量为,2020/8/5,41,离散信源熵H(X),例：有一篇千字文章，假定每字可从万字表中任选，则共有不同的千字文N=100001000 =104000 篇，仍按等概计算，平均每篇千字文可提供的信息量为 例：某信源空间为 则信源熵为,2020/8/5,42,离散信源熵H(X),例：信源X输出符号只有两个，设为0和1。输出符号发生的概率分别为p和q，pq=l。即信源的概率空间为 二元信源熵为,2020/8/5,43,q=1,离散信源熵H(X),信源熵H(X)是概率p的函数，通常用H(p)表示，p取值于0,1区间。 H(p)函数曲线如图所示：,如果二元信源的输出符号是确定的,即p=1或q=1,则

20、该信源不提供任何信息。 当二元信源符号0和1以等概率发生时,信源熵达到极大值,等于1比特信息量。,p=1,p=q=0.5,2020/8/5,44,条件熵,在给定yj条件下，xi的条件自信息量为I(xi/yj)，X集合的条件熵 在给定Y（即各个yj）条件下，X集合的条件熵 在给定X（即各个xi）条件下，Y集合的条件熵 条件熵是在联合符号集合XY上的条件自信息量的联合概率加权统计平均值。 条件熵H(X/Y)表示已知Y后，X的平均不确定度。,2020/8/5,45,条件熵,例：考虑下面两个随机变量X和Y，其中 计算条件熵H(X/Y)。 解：,2020/8/5,46,联合熵,联合熵是联合符号集合 XY

21、上的每个元素对xiyj的自信息量的概率加权统计平均值 联合熵H(XY)表示X和Y同时发生的不确定度。 联合熵、信源熵和条件熵之间的关系,2020/8/5,47,定理证明,证明：,2020/8/5,48,联合熵,例：令XY具有如下的联合分布，求信源熵和联合熵,解：,p(y1),p(x4),比特/符号,比特/符号,比特/符号,2020/8/5,49,例题,例：二进制通信系统用符号“0”和“1”，由于存在失真，传输时会产生误码，用符号表示下列事件： u0：一个“0”发出；u1：一个“1”发出； v0：一个“0”收到； v1：一个“1”收到。 给定下列概率： p(u0)1/2， p(v0/u0)3/4

22、，p(v0/u1)=1/2。求： 已知发出一个“0”，求收到符号后得到的信息量； 已知发出的符号，求收到符号后得到的信息量； 知道发出的和收到的符号，求能得到的信息量； 已知收到的符号，求被告知发出的符号得到的信息量。,H(V/u0),H(V/U),H(UV),H(U/V),2020/8/5,50,例题,解： p(v1/u0) =1p(v0/u0) =1/4 联合概率： p(u0v0) = p (v0/u0) p(u0) = 3/41/2 = 3/8 p (u0v1) = p (v1/u0) p(u0) = 1/41/2 = 1/8 p (u1v0) = p (v0/u1) p(u1) = 1

23、/21/2 = 1/4 p (u1v1) = p (v1/u1) p(u1) = 1/21/2 = 1/4,2020/8/5,51,例题,解法1： 解法2：,2020/8/5,52,例题,(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/3 p (u1/v1)=2/3,2020/8/5,53,例题,例：一个二进信源X发出符号集0,1，经过离散无记忆信道传输，信道输出用Y表示。由于信道中存在噪声，接收端除收到0和

24、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),2020/8/5,54,例题,信源熵： 由 得联合概率： p(x0y0) = p(x0) p(y0/x0) = 2/33/4 = 1/2 p(x1y0) = p(x1) p(y0/x1) = 0 p(x0y1) = p(x0) p(y1/x0) = 0 p(x1y1) = p(x1) p(y1/x1) = 1/31/2=1/6 p(x0y2)

25、= p(x0) p(y2/x0) = 2/31/4 = 1/6 p(x1y2) = p(x1) p(y2/x1) = 1/31/2=1/6 条件熵： 联合熵：H(XY)H(X)H(Y/X)=1.8bit/符号,2020/8/5,55,另一种解法,的无条件概率 p(y0) = p(xiy0) = p(x0y0) +p(x1y0) =1/2+0 = 1/2 p(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/3 Y的熵 Y的条件熵 同理p(x0 /y1)=0 ，

26、p(x1/ y1)=1； p(x0 / y2)=1/2， p(x1/ y2)=1/2 联合熵：H(XY)=H(Y)+H(X/Y)= 1.8bit/符号,2020/8/5,56,例题分析,分析 对于接收者，在未收到任何消息时，对X的平均不确定度为 H(X)= 0.92 bit/符号 收到消息Y后，对X的平均不确定度降至 H(X/Y)= 0.33 bit/符号 不确定度的减少量（0.59 bit/符号）就是接收者通过信道传输收到的信息量，称为X和Y的互信息I(X;Y),2020/8/5,57,互信息,设有两个随机事件X和Y，X是信源发出的离散符号集合，Y是信宿收到的离散符号集合。,2020/8/5

27、,58,互信息,如果信道是无噪的，当信源发出消息xi后，信宿必能准确无误地收到该消息，彻底消除对xi的不确定度，所获得的信息量就是xi的不确定度I(xi)，即xi本身含有的全部信息。 一般而言，信道中总是存在着噪声和干扰，信源发出消息xi，通过信道后信宿只可能收到由于干扰作用引起的某种变型yj 。 信宿收到yj 后推测信源发出xi的概率p(xi / yj)称为后验概率。 信源发出消息xi的概率p(xi) 称为先验概率。,2020/8/5,59,互信息,定义： xi的后验概率与先验概率比值的对数 事件xi是否发生具有不确定性，用I(xi)度量。 接收到符号yj后，事件xi是否发生仍保留有一定的不

28、确定性，用I(xi / yj)度量。 接收到某消息yj后获得的关于事件xi的信息量，用I(xi; yj)表示。,2020/8/5,60,例题,例：设信源空间为 如果信宿收到消息 y1“不是晴天”，求y1分别与xi之间的互信息量。 解：自信息量分别为 I(x1)=-logp(x1)=1 bit I(x2)=-logp(x2)=2 bit I(x3)=-logp(x3)=3 bit I(x4)=-logp(x4)=3 bit y1 无条件概率：p(y1)=1/2 y1和X的联合概率： p(x1y1)=0 p(x2y1)=p(x2)=1/4 p(x3y1)=p(x3)=1/8 p(x4y1)=p(x

29、4)=1/8,2020/8/5,61,例题,条件概率为： p(x1/y1)= p(x1y1)/ p(y1 )=0 p(x2/y1)= p(x2y1)/ p(y1 )=1/2 p(x3/y1)= p(x3y1)/ p(y1 )=1/4 p(x4/y1)= p(x4y1)/ p(y1 )=1/4 互信息量为： I(x1; y1)=logp(x1/y1)/ p(x1 )=0 I(x2; y1)=logp(x2/y1)/ p(x2 )=1 bit I(x3; y1)=logp(x3/y1)/ p(x3 )=1 bit I(x4; y1)=logp(x4/y1)/ p(x4 )=1 bit 信道传送的互

30、信息量是用来解除信源符号的不确定度的。,2020/8/5,62,例2-10,0 0 0 0,1/4 1/4 1/4 1/4,0 0 0 0,0 0 1/2 1/2,0 0 0 0,0 0 0 1,2020/8/5,63,互信息的性质,对称性 当X和Y相互独立时， 单符号间信息量可为正值或负值,平均意义上的互信息量一定大于或等于零,2020/8/5,64,平均互信息,互信息量 I(xi; yj)在X集合上的统计平均值为 I(X; yj)在Y集合上的概率加权统计平均值,平均互信息（量）,2020/8/5,65,平均互信息量的物理意义,H(X/Y)：信道疑义度，损失熵 信源符号通过有噪信道传输后引起的信息量损失。 信源X的熵等于接收到的信息量加损失掉的信息量。 H(Y/X) ：噪声熵，散布度 它反映了信道中噪声源的不确定性。 输出端信源Y的熵H(Y)等于接收到关于X的信息量I(X;Y)加上H(Y/X)，这完全是由信道中噪声引起的。,2020/8/5,66,平均互信息量的物理意义,如果X与Y是相互独立的，无法从Y中去提取关于X的信息，即H(X/Y)=H(X)，故称为全损离散信