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

《信息论与编码第2章信源熵.ppt》由会员分享，可在线阅读，更多相关《信息论与编码第2章信源熵.ppt（253页珍藏版）》请在三一办公上搜索。

1、当你感到悲哀痛苦时，最好是去学些什么东西。学习会使你永远立于不败之地。,第1章：概述,第2章：信源熵,第3章：信道容量,第4章：信息率失真函数,第5章：信源编码,第6章：信道编码,第7章：密码体制的安全性测度,信息度量的方法有：结构度量、统计度量、语义度量、语用度量、模糊度量等等。最常用的方法是统计度量。它用事件统计发生概率的对数描述事物的不确定性，得到消息的信息量，建立熵的概念。熵概念是香农信息论最基本最重要的概念。,从随机变量出发来研究信息，正是香农信息论的基本假说。,2.1 单符号离散信源,2.3 连续信源,2.2 多符号离散信源,2.4 离散信源无失真编码定理,2.1.6 各种熵之间的

2、关系,2.1.1 单符号离散信源的数学模型,2.1.2 自信息和信源熵,2.1.3 信源熵的基本性质和定理,2.1.4 加权熵的概念和基本性质,2.1.5 平均互信息,连续信源,单符号离散信源,多符号离散信源,信源输出的是一个个符号，这些符号的取值是有限的或可数的。,只涉及一个随机事件的离散信源。可用离散随机变量来描述。,涉及多个随机事件的离散信源。可用随机矢量来描述。,输出连续消息的信源。可用随机过程来描述。,信源分类,对于离散随机变量，取值于集合,单符号离散信源的数学模型为,(2.1.2),需要注意 的是：大写字母X、Y、Z 代表随机变量，指的是信源整体。带下标的小写字母:代表随机事件的某

3、一结果或信源的某个元素。两者不可混淆。,2.1.4 加权熵的概念和基本性质,2.1.1 单符号离散信源的数学模型,2.1.2 自信息和信源熵,2.1.3 信源熵的基本性质和定理,2.1.5 平均互信息,2.1.6 各种熵之间的关系,随机变量X、Y分别取值于集合,联合随机变量 取值于集合,记,无条件概率、条件概率、联合概率满足下面一些性质和关系：,1,2,3,4,5,6,一、信息量,度量信息的基本思路 考虑一个单符号离散信源，它的输出被传送给对此感兴趣的一方。设 为最大可能的输出，为最小可能的输出。例如，假设信源输出代表天气情况，为晴或多云天气，为冰雹或其它强对流天气。哪个输出包含更多的信息，还

4、是？直观地，传递 给出了更多的信息。由此可以合理地推算信源输出的信息量应该是输出事件的概率的减函数。信息量的另一个直观属性是，某一输出事件的概率的微小变化不会很大地改变所传递的信息量，即信息量应该是信源输出事件概率的连续减函数。,假设与输出 相关的信息能被分成独立的两部分，比如 与，即。例如，假设天气预报中的天气及温度变化是与污染程度相关性很小甚至几乎完全独立的，则信源的每一个输出就能分成独立的两部分。直观地，传递 所包含的信息量是分别传递 和 所得到的信息量的和。若信源中事件 的出现所带来的信息量用 来表示并称之为事件 的自信息量，则概率为 的信源输出 所包含的信息量 必须满足以下几个条件：

5、,信源输出 所包含的信息量 仅依赖于它的概率，而与它的取值无关。2.是 的连续函数。3.是 的减函数，即：如果，则。极限情况，若,则；若,则。4.若两个单符号离散信源（符号集合X,Y）统计 独立,则X中出现、Y中出现 的联合信息量 问题：什么函数能够同时满足以上条件呢？,举例设在甲布袋中，放入p个不同阻值的电阻。如果随意选取出一个，并对取出的电阻值进行事先猜测，其猜测的困难程度相当于概率空间的不确定性。甲布袋的概率空间为：阻值为i的电阻：选取出阻值为i电阻的概率假设电阻选取的概率是相等的，则接收到“选取出阻值为i的电阻”所获得的信息量为,乙布袋中，放入按功率划分的q种不同功率的电阻。如果对任意

6、选取出来的功率值进行事先猜测，那么，可看成为另一概率空间：功率为j的电阻：选取出功率为j的电阻的概率假设q种不同功率的选择也是等概率的，则被告知“选取出功率为j的电阻”所获得的信息量为这两个函数应该是同一类函数,再设在第三个布袋中，放入p种不同阻值，而每一种阻值又有q种不同功率的电阻，即共有pq个电阻。设它们的选取也是等可能性的，其概率空间为则“选取出阻值为i，功率为j的电阻”这一事件提供的信息量应为从第三个布袋中选出一电阻的效果相当于从甲布袋中选择一电阻后再从乙布袋中选择一电阻。“选取出阻值为i，功率为j”这件事提供的信息量应该是“选取出阻值为i”和“选取出功率为j”这两件事提供的信息量之和

7、，即,可以用泛函分析方法解得满足条件的函数形式为所以：显然满足：用概率测度定义信息量：设离散信源X，其概率空间为如果知道事件 已发生，则该事件所含有的自信息定义为,单位：比特(2为底)、奈特、笛特（哈特）三个信息单位之间的转换关系如下：,由式(2.1.3)可知，一个以等概率出现的二进制码元(0,1)所包含的自信息量为1bit。,对于 进制的数字序列,假设每一符号的出现完全随机且概率相等，求任一符号的自信息量。解：设 进制数字序列任一码元 的出现概率为，根据题意，事件的自信息量只与其概率有关，而与它的取值无关。,例2.1.1,这四种气候的自信息量分别为:,某地二月份天气的概率分布统计如下：,信息

8、量与不确定性的关系 信源中某一消息发生的不确定性越大，一旦它发生，并为收信者收到后，消除的不确定性就越大，获得的信息也就越大。由于种种原因（例如噪声太大），收信者接收到受干扰的消息后，对某信息发生的不确定性依然存在或者一点也未消除时，则收信者获得较少的信息或者说一点也没有获得信息。,信息量的直观定义：收到某消息获得的信息量不确定性减少的量(收到此消息前关于某事件发生的不确定性)(收到此消息后关于某事件发生的不确定性)在无噪声时，通过信道的传输，可以完全不失真地收到所发的消息，收到此消息后关于某事件发生的不确定性完全消除，此项为零。因此得收到某消息获得的信息量收到此消息前关于某事件发生的不确定性

9、信源输出的某消息中所含有的信息量,自信息量和该事件的不确定度的含义有本质的区别。不确定度只与事件的概率有关，是一个统计量，在静态状态下也存在；自信息量只有该随机事件出现时才给出，不出现时不给出，因此它是一个动态的概念。,自信息含义当事件 发生以前：表示事件 发生的不确定性。当事件 发生以后：表示事件 所含有（或所提供）的信息量。在无噪信道中，事件 发生后，能正确无误地传输到收信者，所以 可代表接收到消息 后所获得的信息量。这是因为消除了 大小的不确定性，才获得这么大小的信息量。,不确定度表示含有多少信息，信息量表示随机事件发生后可以得到多少信息。,信息论中“比特”与计算机术语中“比特”区别如果

10、，则 比特。所以1比特信息量就是两个互不相容的等可能事件之一发生时所提供的信息量。信息论中“比特”是指抽象的信息量单位；计算机术语中“比特”是代表二元数字；这两种定义之间的关系是：每个二元数字所能提供的最大平均信息量为1比特。,自信息量具有下列性质:,图2.1.1 对数曲线,2,3,联合自信息量,代入式(2.1.3)就有,条件自信息量,的变化而变化。,自信息量、条件自信息量和联合自信息量之间有如下关系式：,联合自信息量和条件自信息也满足非负 和单调递减 性，同时，它们也都是随机变量，其值随着变量,二、互信息量和条件互信息量,由前可知，离散信源X的数学模型为,互信息量,信宿Y 的数学模型为,先验

11、概率：信源发出消息 的概率。后验概率：信宿收到 后推测信源发出 的 概率。互信息量：对 的互信息量定义为后验概 率与先验概率比值的对数。,例2.1.2,继续讨论第一节的例题，即某地二月份天气构成的信源为,一天有人告诉你：“今天不是晴天”。把这句话作为收到的消息，当收到 后，各种天气发生的概率变成后验概率了。=“今天不是晴天”，由于 包含了、，因此,那么,两个不确定度之差，是不确定度被消除的部分，代表已经确定的东西。,？,理想情况:,不确定性发生了一些变化。不确定性变化的部分，即是观察者从接收端获得的关于发送端的信息量。,观察者站在输出端自信息量：对 一无所知的情况下 存在的不确定度；条件自信息

12、量：已知 的条件下 仍然存在的不确定度；互信息量：两个不确定度之差是不确定度被消除的部分，即等于自信息量减去条件自信息量。实际是从 得到的关于 的信息量。,？,理想情况：,不确定性发生了一些变化。不确定性变化的部分，即是观察者从发送端获得的关于接收端的信息量。,观察者在输入端出现 前、后对输出端出现 的不确定度有变化，即从 中也可提取关于 的信息量。观察者得知输入端发出 前、后对输出端出现 的不确定度的差。,观察者站在输入端观察,通信前,先验不定度（联合自信息量）,观察通信系统：,后验不定度,通信后,这样，通信后流经信道的信息量，等于通信前后不定度的差,观察者站在通信系统总体立场上通信前：输入

13、随机变量X和输出随机变量Y之间没有任何关联关系，即X，Y统计独立：先验不确定度通信后：输入随机变量X和输出随机变量Y之间由信道的统计特性相联系，其联合概率密度：后验不确定度通信后的互信息量，等于前后不确定度的差这三种表达式实际上是等效的，在实际应用中可根据具体情况选用一种较为方便的表达式。,互信息的引出，使信息流通问题进入了定量分析的范畴，为信息流通的定量测量打下了坚实的基础，把信息理论发展到了一个更深的层次，可以认为是信息论发展的又一个里程碑。,互信息的性质,对称性,当X和Y相互独立时，互信息为0,互信息量可为正值或负值,1,2,3,条件互信息量,(2.1.13),三.信源熵,已知单符号离散

14、无记忆信源的数学模型,这里的符号是指代表信源整体的X,信源熵,信源熵,各离散消息自信息量的数学期望，即信源的平均信息量。,信源的信息熵；香农熵；无条件熵；熵函数；熵。单位：比特/符号。,例2.1.3,继续讨论第一节的例题，即某地二月份天气构成的信源为,由式(2.1.16)的定义，该信源的熵为,信源熵和平均自信息量两者在数值上是相等的，但含义并不相同。信源熵表征信源的平均不确定度，平均自信息量是消除信源不确定度所需要的信息的量度。信源一定，不管它是否输出离散消息，只要这些离散消息具有一定的概率特性，必有信源的熵值，这熵值在总体平均的 意义上才有意义，因而是 一个确定值。,在离散信源的情况下，信源

15、熵的值是有限的。而信息量只有当信源输出离散消息并被接收后，才有意义。这就是给予接收者的信息度量。这值本身可以是随机量，如前面所讲的自信息量。也可以与接收者的情况有关，如后面要提到的意义信息 量。当信源输出连续消息 时,信息量的值可以是无 穷大。,信源熵与信息量的比较,熵 信息量,总括起来，信源熵有三种物理含义：,信源熵H(X)表示信源输出后，离散消息所提供的平均信息量。,信源熵H(X)表示信源输出前，信源的平均不确定度。,信源熵H(X)反映了变量X的随机性。,1,2,3,举例有两个信源，其概率空间分别为信息熵分别为H(X)=-0.99log0.99-0.01log0.01=0.08 比特/符号

16、H(Y)=-0.5log0.5-0.5log0.5=1 比特/符号 可见H(Y)H(X)本例结论信源Y的二个输出消息是等可能性的，所以在信源没有输出消息以前，事先猜测哪一个消息出现的不确定性要大；信源Y比信源X的平均不确定性大；信源X的二个输出消息不是等概率的，事先猜测些 和 哪一个出现，虽然具有不确定性，但大致可以猜出 会出现，因为 出现的概率大。所以信源X的不确定性要小；信息熵反映的就是信源输出前平均不确定程度的大小。,信源熵与平均获得的信息量信源熵是信源的平均不确定性的描述。在一般情况下它并不等于平均获得的信息量。只有在无噪情况下，接收者才能正确无误地接收到信源所发出的消息，消除了H(X

17、)大小的平均不确定性，所以获得的平均信息量就等于H(X)。在一般情况下获得的信息量是两熵之差，并不是信源熵本身。,例：P22，例。由联合得边界、条件。,条件熵,联合熵,熵的文氏图表示,2.1.4 加权熵的概念和基本性质,2.1.1 单符号离散信源的数学模型,2.1.2 自信息和信源熵,2.1.3 信源熵的基本性质和定理,2.1.6 各种熵之间的关系,2.1.5 平均互信息,例：,非负性,对称性,1,2,定理,信源中包含n个不同离散消息时，信源熵H(X)有,当且仅当X中各个消息出现的概率全相等时，上式取等号。,最大离散熵定理,3,证明：自然对数具有性质,图2.1.4 自然对数的性质,对于单符号离

18、散信源，当信源呈等概率分布时具有最大熵。,如图,时熵与概率的关系,问题？设信源求这信源的熵，并解释原因。,虽然概率很小的事件出现后，给予接收者的信息量很大，但对熵的贡献很小，可以忽略不计。,扩展性,4,确知信源的不确定度为零。,正因为具有可加性，可以证明熵的形式是唯一的。,确定性,可加性,6,5,已知Y后，从中得到了一些关于X的信息，从而使X的不确定度下降。,极值性,7,上式含义：概率分布，它对其它概率分布 的自信息 取数学期望时，必大于 本身的熵。,f 的定义域中任意两个矢量X、Y，若,则称 f 为严格上凸函数,设P、Q为两组归一的概率矢量。即,上凸性,8,则有,（）,证明；几何意义：P21

19、,严格上凸函数在定义域内的极值必为极大值。,2.1.4 加权熵的概念和基本性质,2.1.1 单符号离散信源的数学模型,2.1.2 自信息和信源熵,2.1.3 信源熵的基本性质和定理,2.1.6 各种熵之间的关系,2.1.5 平均互信息,有信源,构造重量空间,重量,，即 权重系数。,加权熵从某种程度上反映了人的主观因素。,加权熵的性质：,信源平均每发出一个消息，总能提供一定的信息量，最差是零。,连续性,非负性,1,2,信源空间中概率分量的微小波动，不会引起加权熵值的很大变动。,表明熵的总体特性。,对称性,3,均匀性,4,等重性,5,与香农熵的性质一致。,确定性,6,在一定程度上反映了认识主体的主

20、观意志，具有效用和意义的含义。,非容性,7,扩展性,线性叠加性,8,9,当所有权重系数都为1时，有,香农最大熵可看成是加权熵在权重系数都为1时的特例。,加权熵的最大值,10,2.1.4 加权熵的概念和基本性质,2.1.1 单符号离散信源的数学模型,2.1.2 自信息和信源熵,2.1.3 信源熵的基本性质和定理,2.1.6 各种熵之间的关系,平均互信息量,平均互信息,一、平均互信息量的定义,平均交互信息量；交互熵,同理，X对Y的平均互信息：,(2.1.44),(2.1.45),信道中流通信息量的整体测度。,二、平均互信息的物理意义,平均互信息量是收到Y前、后关于X的不确定度减少的量，即由Y获得的

21、关于X的平均信息量。,1,平均互信息量是发送X前、后，关于Y的平均不确定度减少的量。,2,3,平均互信息量等于通信前、后，整个系统不确定度减少的量。,信息就是负熵从一个事件获得另一个事件的平均互信息需要消除不确定度，一旦消除了不确定度，就获得了信息。,1,2,3,等概率信源的熵最大。,4,5,6,7,三、平均互信息的性质,对称性,1,非负性,2,极值性,1,3,2,凸函数性,4,证（略）,1,求平均互信息I(X；Y)，如图,2,I(X;Y)随信道变化的曲线，如图,图2.1.10,多次处理信息量将减少,图2.1.8数据处理模型,数据处理定理,5,结论：两级串联信道输入与输出消息之间的平均互信息量

22、既不会超过第级信道输入与输出消息之间的平均互信息量，也不会超过第级信道输入与输出消息之间的平均互信息量。当对信号/数据/消息进行多级处理时，每处理一次，就有可能损失一部分信息，也就是说数据处理会把信号/数据/消息变成更有用的形式，但是绝不会创造出新的信息。这就是所谓的信息不增原理。当已用某种方式取得Y后，不管怎样对Y进行处理，所获得的信息不会超过I(X;Y)。每处理一次，只会使信息量减少，至多不变。也就是说在任何信息流通系统中，最后获得的信息量，至多是信源提供的信息。一旦在某一过程中丢失了一些信息，以后的系统不管怎样处理，如果不能接触到丢失信息的输入端，就不能再恢复已丢失的信息。,例题：p36

23、,多次测量,多次测量的互信息量要比单次测量的互信息量大,证(略),2.1.6 各种熵之间的关系,2.1.1 单符号离散信源的数学模型,2.1.2 自信息和信源熵,2.1.3 信源熵的基本性质和定理,2.1.4 加权熵的概念和基本性质,2.1.5 平均互信息,学而不思而罔，思而不学则殆。孔子,昨晚多几分钟的准备，今天少几小时的麻烦。,2.1 单符号离散信源,2.3 连续信源,2.2 多符号离散平稳信源,2.4 离散信源无失真编码定理,随机矢量中的各随机变量的统计特性都不随时间推移而变化。,2.2.1 序列信息的熵,2.2.3 平稳信源的熵和极限熵,2.2.2 离散平稳信源的数学模型,2.2.4

24、马尔可夫信源,2.2.5 信源冗余度,输出的消息序列中各符号之间无相互依赖关系的信源。亦称为单符号离散平稳无记忆信源的扩展信源。,序列长度就是扩展次数。,单符号信源0，1经过扩展，,变成了：00，01，10，11,可证明序列信息的熵为,单符号信源如下,求二次扩展信源熵,扩展信源：,2.2.1 序列信息的熵,2.2.3 平稳信源的熵和极限熵,2.2.2 离散平稳信源的数学模型,2.2.4 马尔可夫信源,2.2.5 信源冗余度,各维联合概率均与时间起点无关的完全平稳信源。,2.2.1 序列信息的熵,2.2.3 平稳信源的熵和极限熵,2.2.2 离散平稳信源的数学模型,2.2.4 马尔可夫信源,2.

25、2.5 信源冗余度,反映信源记忆特性的两方法：,用联合概率反映信源记忆特性,用条件概率反映信源记忆特性,1,2,二维信源,1,一般地,例,原始信源：,条件概率：,平均符号熵：,N维信源,2,由平稳性：,平均符号熵：,极限熵：,2.2.1 序列信息的熵,2.2.3 平稳信源的熵和极限熵,2.2.2 离散平稳信源的数学模型,2.2.4 马尔可夫信源,2.2.5 信源冗余度,有记忆的特点：,有限的相关符号组构成的序列,有限记忆长度；,发出一个个符号，每发一个符号状态要发生转移。,信源输出不仅与符号集有关，而且与状态有关；,1,2,3,以信源输出符号序列内各符号间条件概率来反映记忆特性的一类信源。,某

26、时刻输出符号仅与此刻信源所处的状态有关；,某时刻所处状态由当前输出符号和前一时刻信源状态唯一确定。,1,2,信源输出当前符号仅与前面m个符号有关的马尔可夫信源。,马尔可夫信源稳定后各状态的极限概率（）,状态极限概率的求法，状态转移图,例,平稳信源（如果不平稳则先把其变成分段平稳的）。,1,2,1,马尔可夫信源发出一个个符号，有限长度有记忆信源发出一组组符号；,一般有记忆信源用联合概率描述符号间的关联关系，马尔可夫信源用条件概率（状态转移概率）来描述符号间的关联关系；,m阶马尔可夫与一般记忆长度为m的有记忆信源的区别：,1,2,2,马尔可夫信源记忆长度虽然有限，但依赖关系延伸到无穷远。长为m的有

27、限记忆信源符号间的依赖关系仅限于每组内，组与组之间没有依赖关系；,3,4,2.2.1 序列信息的熵,2.2.3 平稳信源的熵和极限熵,2.2.2 离散平稳信源的数学模型,2.2.4 马尔可夫信源,2.2.5 信源冗余度,空格：0.2 E：0.105 T：0.072 O：0.0654 A：0.063 N：0.059 I：0.055 R：0.054 S：0.052 H：0.047 D：0.035 L：0.029 C：0.023 F、U：0.025 M：0.021 P：0.175 Y、W：0.012 G：0.011 B：0.0105 V：0.008 K：0.003 X：0.002 J、Q：0.001

28、 Z：0.001,英文各个字符的统计概率如下：,例,英文字母出现概率统计,对于英语信源：,信息熵的相对率：,信源的冗余度：,信息变差：,对英语信源：,冗余度与传输效率,冗余度与传输可靠性,冗余度与英语学习,?,写英语文章时，71%是由语言结构定好的，只有29%是写文字的人可以自由选择的。100页的书，大约只传输29页就可以了，其余71页可以压缩掉。信息的冗余度表示信源可压缩的程度。从提高传输效率的观点出发，总是希望减少或去掉冗余度。冗余度大的消息抗干扰能力强。能通过前后字之间的关联纠正错误。听母语广播和听外语广播的对比说明：听外语费劲是英语冗余度不够造成的。因此，英语听力要过关，除了多听多练以

29、外，其实并无多少捷径可走。,2.1 单符号离散信源,2.3 连续信源,2.2 多符号离散信源,2.4 离散信源无失真编码定理,统计特性与时间起点无关的连续信源。,集平均以概率1等于时间平均的平稳随机过程。,2.3.1 连续信源的熵,2.3.3 连续信源熵的性质及 最大连续熵定理,2.3.2 几种特殊连续信源的熵,2.3.4 熵功率,计算连续信源熵的两种方法：,将连续信源数字化，再用离散熵计算,先进行抽样，再把抽样序列看作量化 单位趋于0时的情况，然后定义计算信源熵。,1,2,一维概率密度函数（边缘概率密度函数）：,条件概率密度函数：,联合概率密度函数：,它们之间的关系：,且：,中值定理：,单变

30、量连续信源的数学模型为：,并满足,连续信源熵（相对熵）定义：,为了在形式上与离散信源熵统一,熵差仍然具有信息的特征,1,2,其他连续熵的定义：,2.3.1 连续信源的熵,2.3.3 连续信源熵的性质及 最大连续熵定理,2.3.2 几种特殊连续信源的熵,2.3.4 熵功率,均匀分布的连续信源的熵,1,高斯分布的连续信源的熵,2,高斯信源的熵仅与方差有关。,指数分布的连续信源的熵,3,2.3.1 连续信源的熵,2.3.3 连续信源熵的性质及 最大连续熵定理,2.3.2 几种特殊连续信源的熵,2.3.4 熵功率,连续信源熵可为负值,连续信源熵的可加性,推广到N个变量的情况,1,2,3,对称性：,数据

31、处理定理：,最大连续熵定理,限峰值功率的最大熵定理,若代表信源的N维随机变量其取值被限定在一定范围内，在有限定义域内当连续信源概率密度函数为均匀分布时达到最大熵。,1,4,可以证明,限平均功率的最大熵定理,信源输出信号的平均功率P和均值m受限，当信源概率密度函数为正态分布时，具有最大熵。,2,当峰值功率受限、平均功率受限，连续信源的统计特性分别与两种常见噪声均匀噪声和高斯噪声的统计特性相一致时，信源具有最大连续熵。因为噪声是一个最不确定的随机过程，而最大的信息量只能从最不确定的事件中获得。,均值受限条件下的最大熵定理,连续信源输出非负信号的均值受限条件下，指数分布的连续信源具有最大熵。,3,连

32、续信源不存在绝对的最大熵。连续最大熵与信源的限制条件有关。在不同的限制条件下，有不同的最大连续熵。,2.3.1 连续信源的熵,2.3.3 连续信源熵的性质及 最大连续熵定理,2.3.2 几种特殊连续信源的熵,2.3.4 熵功率,均值为零、平均功率受限的连续信源是最常见的一种，重点讨论。均值为零、平均功率限定为P的连续信源X，概率密度p(x)为高斯分布时熵值最大其熵值仅随限定功率P的变化而变化。设限定平均功率为，相应的熵为当概率密度函数为其它任何分布q(x)时，其熵 必小于最大熵，即总能找到某一个即 的大小决定了实际信源的熵值。,信息变差：,常见信源是均值为0，平均功率受限信源,熵功率：,推广到

33、N维，假定各随机分量统计独立且各随机分量平均功率限定值为P，均值都是0，熵功率都是，则信息变差为：,2.1 单符号离散信源,2.3 连续信源,2.2 多符号离散信源,2.4 离散信源无失真编码定理,为什么要进行信源编码 信源的两个重要问题 信源输出的信息量计算问题；如何更有效地表示信源输出的问题。为什么要进行信源编码 人们都希望无失真传送，首先要对信源无差错编码；数字技术应用越来越多，模拟信源通过数字化变成数字信号传送。,(2)信源编码的理论依据设无记忆离散信源的信源空间为它的熵为假如将它进行K重扩展而得到K重符号序列，用矢量表示为则这样的符号序列有 个。,当K的值很大时，根据大数定律，这个序

34、列会以很高的概率出现以下情况：符号 约重复出现，符号 约重复出现，符号 约重复出现 次。这意味着当K足够大时，将会以趋向于1的概率出现以下情况：扩展后的很多序列都具有相同的组成，因此也具有相同的概率。也就是说，当K足够大时，扩展后有相当多的符号序列是等概的。可以将具有上述结构的序列称为典型序列，而将其余的序列称为非典型序列，如果典型序列的概率之和很大而非典型序列的概率之和很小，则仅用典型序列来代表扩展信源在很多场合是可行的。,既然所有的非典型序列的概率之和很小，对信源输出来说，忽略它们而引入的误差可以小于任何给定的值。将这一特性应用于信源的压缩编码中，这正是数据压缩的本质。信源符号序列分组定理

35、(也称渐进等分特性)说明了上述的分组是存在的，而且可以估算其典型序列的数目。下面给出信源符号序列分组定理。A.E.P(AsymptoticEquipatitionProperty),信源符号序列分组定理：设无记忆离散信源的信源符号为，其概率分别为。假如将它进行K重扩展而得到重符号序列，则任意给定 和 总能找到一个整数，使得当 时，有 为扩展后符号序列 中取符号 值的次数(i=1,2,K),在信息论中，渐进等分特性是弱大数定律的直接推论。大数定律指出，对于独立同分布的随机变量，只要N足够大,接近其数学期望EX。渐进等分特性指出，若 是独立同分布的随机变量，其联合概率为，只要N足够大,接近于信源熵

36、H(S)。即这些序列的联合概率 接近于。,信源符号序列分组定理说明，对于K重扩展信源，只考虑典型符号序列对信源特性带来的损失可以低到可被忽略的程度，这给出了信源压缩编码的理论依据。,很多学者深入地研究了离散随机序列信源的统计特性，香农(1948)首先发现，后来麦克米伦(1953)和沃尔夫兹(1961)进一步严格证明，这类信源具有渐进等同分割性，简称A.E.P(Asymptotic Equipatition Property)基本思想:一个总数为 种的消息序列信源随着消息序列长度K的增长且足够大时，越来越明显产生两级分化现象：其中一类组成大概率事件的序列集合,它具有如下三个特征：第一，第二，序列

37、的符号熵H(p)收敛于信源输出符号(消息)熵H(p)第三，序列趋于等概率分布而另一类则组成小概率事件的非典型序列集合 它具有特性由，我们无需对全部信源输出符号（消息）进行信源编码，而仅仅只要对其中典型序列集合 中的符号序列进行信源编码即可。,(3)信源编码的概念信源编码定义：指定能够满足信道特性/适合于信道传输的符号序列/码序列，来代表信源输出的消息。完成编码功能的器件称为编码器。离散信源输出的码序列 离散信源输出的消息是由一个个离散符号组成的随机序列 X=(X1X2XlXL)Xlx1,x2,xi,xn信源编码就是把信源输出的随机符号序列变成码序列 Y=(Y1Y2YkYK)Yky1,y2,yj

38、,ym,码符号/码元：编码器的输入是信源符号集x1,x2,xi,xn，同时存在另一符号集，y1,y2,yj,ym，一般元素yj是适合信道传输的,称为码符号/码元。码序列：适合于信道传输的符号序列，也称为码字。编码器功能：把信源输出的随机符号序列变成码序列。码长/码字长度：码字的长度或简称码长。编码就是从信源符号到码符号的一种映射。若要实现无失真编码，这种映射必须是一一对应的，可逆的。,(4)一些码的定义1、二元码：码符号集为X=0,1，所得码字都是一些二元序列。2、定长码/等长码：一组码中所有码字的码长都相同，即ki=K(i=1,2,n)。3、变长码：一组码字中所有码字的码长各不相同，即任意码

39、字由不同长度的码符号序列组成。4、非奇异码：一组码字中所有码字都不相同，即所有信源符号映射到不同的码符号序列。5、奇异码：一组码中有相同的码字。6、惟一可译码/单义可译码：码的任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号。,将码分为奇异码和非奇异码两大类，我们只讨论非奇异码。非奇异码又分为惟一可译码和非惟一可译码两大类，我们只讨论惟一可译码。,码字与信息率的关系 有时消息太多，不可能或者没必要给每个消息都分配一个码字；给多少消息分配码字可以做到几乎无失真译码？传送码字需要一定的信息率，码字越多，所需的信息率越大。编多少码字的问题可以转化为求信息率大小的问题；信息率越小越好，最小能

40、小到多少才能做到无失真译码呢？这些问题就是信源编码定理要研究的问题。,(5)信源编码的方法信源编码有定长和变长两种方法。1、定长编码：码字长度K是固定的，相应的编码定理称为定长信源编码定理，是寻求最小K值的编码方法。2、变长编码：K是变值，相应的编码定理称为变长编码定理。这里的K值最小意味着数学期望最小。,1 定长编码定理一个熵为H(X)的离散无记忆信源X1X2XlXL，若对信源长为L的符号序列进行定长编码，设码字是从m个字母的码符号集中，选取K个码元组成Y1Y2YkYK。对于任意0，0只要满足则当L足够大时，必可使译码差错小于，即译码错误概率能为任意小。反之，若则译码差错一定是有限值，而当L

41、足够大时，译码几乎肯定出错（译码错误概率近似等于1）。,定理中的公式改写成KlogmLH(X)不等式左边表示长为K的码符号序列能载荷的最大信息量，右边代表长为L的信源序列平均携带的信息量。所以定长编码定理告诉我们：只要码字传输的信息量大于信源携带的信息量，总可实现几乎无失真编码。定理的一般性证明是通过计算信源符号自信息的均值与方差，把信源消息分成两个互补集合，一个有编码，一个无编码，再利用契比雪夫不等式，求出有编码集合中码字个数的上下限，分别用上限证明正定理部分，用下限证明逆定理部分。,可以证明：信源熵H(X)就是一个界限/临界值。当编码器输出的信息率超过这个临界值时，就能无失真译码，否则就不

42、行。信源编码定理从理论上说明了编码效率接近于1，即 的理想编码器的存在性，代价是在实际编码时取无限长的信源符号(L)进行统一编码。,给定和用上式规定的L计算所有可能信源消息的概率，按由小到大的次序排列，选用概率较大的消息进行编码，有编码的消息构成一个集合A，直到该集合的概率p(A)1-，意味着译码差错概率必小于，即完成了编码过程；只要足够小，就可实现几乎无失真译码，若足够小，编码效率就接近于1。说明：定长编码定理是在平稳无记忆离散信源的条件下论证的，但它同样适用于平稳有记忆信源，只是要求有记忆信源的极限熵和极限方差存在即可。对于平稳有记忆信源，定理中的熵应改为极限熵。,令它是编码后平均每个信源

43、符号能载荷的最大信息量，称为编码信息率。可见编码信息率大于信源的熵，才能实现几乎无失真编码，为衡量编码效果，引入编码效率因此，最佳等长编码的效率为可得在已知方差和信源熵的条件下，信源序列长度L与编码效率和允许错误概率的关系：,举例例24.1设单符号信源模型为其信息熵为H(X)=2.5525(比特/符号)若要求编码效率为90%，即.由此可见，在差错率和效率要求都不苛刻的情况下，就必须有将近1600多万个信源符号一起编码，技术实现非常困难。,2 变长编码定理1、基本概念变长编码：不等长编码允许把等长的消息变换成不等长的码序列。通常把经常出现的消息编成短码，不常出现的消息编成长码。这样可使平均码长最

44、短，从而提高通信效率，代价是增加了编译码设备的复杂度。例如，在不等长码字组成的序列中要正确识别每个长度不同的码字的起点就比等长码复杂得多。译码延时/译码同步：接收到一个不等长码序列后，有时不能马上断定码字是否真正结束，因而不能立即译出该码，要等到后面的符号收到后才能正确译出。,2、码字分离,如果0、01都是码字，译码时如何分离？,判断以下码字是否可分离？,例,码A：显然不是惟一可译码。“a1”和“a2”对应于同一码字“0”，码0本身是一个奇异码；而“10”可译为“a4”或“a3a1”或“a3a2”。码B：不是惟一可译码。当收到码符号“00”时，可将它译成“a1 a1”，也可译为“a3”;当收到

45、码符号“11”时，可将它译成“a2a2”，也可译为“a4”，这种码从单个码字来看虽然不是奇异的，可从有限长的码序列来看，它仍然是一个奇异码。码C：虽然是惟一可译码，但它要等到下一个“0”收到后才能确定码字的结束，译码有延时。码D：既是惟一可译码，又没有译码延时。码字中的符号“0”起了逗点的作用，故称为逗点码。前缀条件码/异前置码/异字头码/逗点码/即时码/非时延码：如果一个码的任何一个码字都不是其它码字的前缀。码D是即时码。,例2.4.3 一信源X(x1,x2,x3,x4)经编码后得码字集合S(1,01,001,0001)且一一对应。现接收码元序列为，试写出译码结果。该编码规则为：x11,x2

46、01,x3001,x40001，每一码字均以1结尾，见1即可译码。对所接收序列的译码结果为1，01，1，1，0001，001，1，01，01，1即x1,x2,x1,x1,x4,x3,x1，x2，x2，x1。编码中的“1”起到了“逗点”的作用，它既是一个码字，又起到了间隔作用，因此和纯粹的间隔不同。,按上述编码规则编出的码又称为逗点码。对于二进制的信道基本符号来说，其编码方法是：信道基本符号“1”是一个码字，在它的前面加上另一个信道基本符号“0”，就得到了一个新码字，多加“0”可得到更多的新码字。这种编码，译码时不需要考察后续码元，故又称之为即时码。即时码一定是惟一可译码。,例2.4.4 一信源

47、X(x1,x2,x3,x4)，经编码后得码字集合S(1,10,100,1000)且一一对应，现收到码序列，试给出译码结果。该编码规则为：x11，x210，x3100，x41000。它的信道基本符号也是“1”、“0”，也是将“1”作为一个码字，但采用在它的后面加“0”构成新码字的方法。,该编码的特点是：已接收到了一个码字集合中的码字但还不能决定当前的译码结果，因为尚不知它与下一个码元一起能否构成码字集合中的另一个码字。例如：接收到100并不能马上就译为x3，因为下一码元假如是0，则1000应译成x4；若下一码元是1，则只能将前面的3个码元100译成x3，第4个码元还要等到再接收一个或多个码元后才

48、能决定其译码结果。这种译码时要接收多于一个码字所包含的码元才能决定的信源编码，称为非即时码。,m元/m进制 码树图：从树根出发，画m条分支，分支端点称为节。第一节有m个端点，每端点对应一个码字；从第一节每个端点出发，再画m条分支，得第二节。第二节有 个端点；以此类推。树根：最顶部画一个起始点。树枝：从根部引出m条线段，每条线段都称为树枝。一级节点：自根部起，通过一条树枝到达的节点。一级节点最多有m个。n级节点：通过n条树枝达到的节点。最多有。终节点/终端节点：下面不再有树枝的节点。中间节点：除了树根和终节点以外的节点。联枝：串联的树枝。满树：在码树图中，当每一个码字的串联枝数都相 同时，就是定

49、长码。此时的码树称为满树。全树：每个中间节点的后续分支数均为m，（非全树）例如：码长为N的满树的终节点个数为，即可表示 码字。,非满树：有些树枝未用时的码树。非满树构造的就是变长码。如果每一个码字都被安排在终节点上，这种码就是异前置码。满树、非满树、全树、非全树图示,码树图的特征与编码的对应关系树根 码字的起点树枝数 码的进制数节点 码字或码字的一部分终节点/终端节点 码字节数 码长满树 等长码非满树 变长码,3、克拉夫特不等式m元长度为，i=1,2,n的异前置码存在的充要条件是证明必要条件 设异前置码第i个码字的长度为，i=1,2,n，构造一个码树图，若某个长度为 的树枝被选用作码字，则该枝

50、自第 个节点以后的树枝不能再被选用作码字。这样自 以后有 个码枝不能被选用。而某个，是从i=1,2,n中任选的一个，那么就整个码树而言，总共不用的枝数为，它一定小于码树的总树枝数。N级满树第N级上的总枝数已知为，所以必有，两边除以，就得,充分条件如果式 成立，总可以把第N级上的树枝分成n组，各组中从第N级开始删除(i=1,2,n)个枝，相对于N级满树，等于删除了所有可能的 级节点的，在该组中以第 级节点作为终节点，就构造好了第i个码字。对所有码字如法炮制，则总共删除了所有 个节点中的。由于，于是构造了一个异前置码。,充分性设码字长度满足Kraft不等式，不失一般性，假设 取 级节点中任何一个作