《第3章离散信源精选文档.ppt》由会员分享，可在线阅读，更多相关《第3章离散信源精选文档.ppt（93页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第3章离散信源1本讲稿第一页，共九十三页离散信源的分类及其描述离散信源的分类及其描述离散信源的熵离散信源的熵信源的冗余度信源的冗余度信源符号序列分组定理信源符号序列分组定理平稳离散信源及其性质平稳离散信源及其性质本章内容提要本章内容提要2本讲稿第二页，共九十三页通信系统的任务是通信系统的任务是将信源的消息有效可将信源的消息有效可靠地传送到信宿靠地传送到信宿。信源消息是信源消息是多种多样多种多样的。的。本章将重点讨论信源的本章将重点讨论信源的数学模型数学模型以及以及如如何度量何度量信源消息中的信息。信源消息中的信息。第第3章离散信源章离散信源3本讲稿第三页，共九十三页从从信源发出的消息在时间上和
2、幅度上的分布信源发出的消息在时间上和幅度上的分布分为离散信源和连续信源；分为离散信源和连续信源；从信源消息是模拟的还是数字的从信源消息是模拟的还是数字的分为模拟信源和数字信源；分为模拟信源和数字信源；对数字信源还可分为二进制信源和多进制信源。对数字信源还可分为二进制信源和多进制信源。对于离散信源对于离散信源，根据，根据符号的特点符号的特点以及符号间的以及符号间的关联性关联性可分可分无记忆无记忆离散信源和离散信源和有记忆有记忆离散信源离散信源对于对于前者前者，又可分为发出单个符号的无记忆离散信源和发，又可分为发出单个符号的无记忆离散信源和发出符号序列的无记忆离散信源出符号序列的无记忆离散信源对于
3、对于后者后者，又可分为发出符号序列的有记忆离散信源和，又可分为发出符号序列的有记忆离散信源和发出符号序列的马尔可夫（发出符号序列的马尔可夫（Markov）信源）信源3.1离散信源的分类及其描述离散信源的分类及其描述3.1.1信源的分类信源的分类4本讲稿第四页，共九十三页从从描述信源消息的随机过程的平稳性角度描述信源消息的随机过程的平稳性角度分为平稳信源和非平稳信源分为平稳信源和非平稳信源按按随机过程的类别随机过程的类别分为高斯信源、马尔可夫信源等分为高斯信源、马尔可夫信源等根据根据人们对信源消息的感知人们对信源消息的感知分为数据信源、文本信源、语音信源、图像信分为数据信源、文本信源、语音信源、
4、图像信源等，其中文本信源和语音信源都是针对人类语源等，其中文本信源和语音信源都是针对人类语言、文字、声乐等感知的，又通称为自然语信源。言、文字、声乐等感知的，又通称为自然语信源。3.1离散信源的分类及其描述离散信源的分类及其描述3.1.1信源的分类信源的分类5本讲稿第五页，共九十三页信源的分类方法可以有多种，但信源的分类方法可以有多种，但本质上本质上主要基于两主要基于两方面的考虑：方面的考虑：一是信源消息一是信源消息取值的取值的集合以及消息取值集合以及消息取值时刻的时刻的集集合，由此可分为离散信源、连续信源或数字信源、合，由此可分为离散信源、连续信源或数字信源、模拟信源等；模拟信源等；二是信源
5、消息的二是信源消息的统计特性统计特性，由此可分为无记忆，由此可分为无记忆（Memoryless）信源、有记忆（）信源、有记忆（Memory）源、平）源、平稳信源、非平稳信源、高斯信源、马尔可夫信源稳信源、非平稳信源、高斯信源、马尔可夫信源等。等。3.1离散信源的分类及其描述离散信源的分类及其描述3.1.1信源的分类信源的分类6本讲稿第六页，共九十三页本章讨论本章讨论离散信源离散信源，包括，包括无记忆和有记忆两类无记忆和有记忆两类。前者分为发出单个符号的离散无记忆信源和发出前者分为发出单个符号的离散无记忆信源和发出符号序列的离散无记忆信源两种，符号序列的离散无记忆信源两种，后者分为发出符号序列的
6、离散有记忆信源和发出后者分为发出符号序列的离散有记忆信源和发出符号序列的马尔可夫信源两种。符号序列的马尔可夫信源两种。离散无记忆信源发出的各个消息符号是相互独立的离散无记忆信源发出的各个消息符号是相互独立的发出单个符号的离散无记忆信源：每次只发出一个符号且发出单个符号的离散无记忆信源：每次只发出一个符号且每个符号代表一个消息每个符号代表一个消息发出符号序列的离散无记忆信源：每次发出一组不少于两个的发出符号序列的离散无记忆信源：每次发出一组不少于两个的符号序列来代表一个消息。符号序列来代表一个消息。3.1离散信源的分类及其描述离散信源的分类及其描述3.1.1信源的分类信源的分类7本讲稿第七页，共
7、九十三页离散有记忆信源发出的各个消息符号是离散有记忆信源发出的各个消息符号是相互关联相互关联的的发出符号序列的离散有记忆信源发出符号序列的离散有记忆信源关联性关联性可用其联合概率来表示可用其联合概率来表示发出符号序列的马尔可夫信源发出符号序列的马尔可夫信源关联性可用其关联性可用其条件概率条件概率来表示来表示3.1离散信源的分类及其描述离散信源的分类及其描述3.1.1信源的分类信源的分类8本讲稿第八页，共九十三页研究信源最主要的目的是研究信源最主要的目的是为信源编码服务为信源编码服务。信源编码的信源编码的目标目标是用尽可能少的是用尽可能少的码元符号码元符号或尽可或尽可能低的能低的数据速率数据速率
8、来描述信源输出的消息。来描述信源输出的消息。怎样的信源编码才是好的或者说是怎样的信源编码才是好的或者说是有效的有效的?信源信源参数测量参数测量离散信源的离散信源的数学模型数学模型及其及其信息的度量信息的度量3.1离散信源的分类及其描述离散信源的分类及其描述3.1.1信源的分类信源的分类9本讲稿第九页，共九十三页可以简单地将自然语信源定义为以人类的自然语言可以简单地将自然语信源定义为以人类的自然语言作为输出消息的信源。作为输出消息的信源。自然语言又可以分为自然语言又可以分为书面书面语言和语言和声音声音语言两大类语言两大类书面语言由一个个文字符号构成，是一种典型的离散书面语言由一个个文字符号构成，
9、是一种典型的离散信源，信源，也是信息论中首先讨论和研究最多的信源，也是信息论中首先讨论和研究最多的信源，以英文和中文为例讨论书面语言，以英文和中文为例讨论书面语言，声音语言的信源放在第声音语言的信源放在第6章讨论。章讨论。3.1离散信源的分类及其描述离散信源的分类及其描述3.1.2自然语信源自然语信源10本讲稿第十页，共九十三页英文信源英文信源先将英文看成仅由先将英文看成仅由26个字母和空格构成，即暂不考虑标点个字母和空格构成，即暂不考虑标点符号及其他。符号及其他。英文中字母的组合构成单词，单词的组合构成句子，句子的组合英文中字母的组合构成单词，单词的组合构成句子，句子的组合构成段落和文章。构
10、成段落和文章。在某一个统计集合中能得出其字母、单词、句子的分布概率。在某一个统计集合中能得出其字母、单词、句子的分布概率。例如通过大量统计得到的例如通过大量统计得到的26个字母和空格的出现概率如表个字母和空格的出现概率如表3.1所所示。它构成了英文字母和空格的信源空间。示。它构成了英文字母和空格的信源空间。仅仅按照表中的出现概率随机构成的一串字母序列通常并不能构仅仅按照表中的出现概率随机构成的一串字母序列通常并不能构成英文单词，。成英文单词，。其构成还有许多语法和修辞方面的制约，这种制约在数学其构成还有许多语法和修辞方面的制约，这种制约在数学关系上的反映就是其关联性。关系上的反映就是其关联性。
11、3.1离散信源的分类及其描述离散信源的分类及其描述3.1.2自然语信源自然语信源11本讲稿第十一页，共九十三页表表3.1的一维概率分布是反映不出英文构成的关联性。的一维概率分布是反映不出英文构成的关联性。3.1离散信源的分类及其描述离散信源的分类及其描述3.1.2自然语信源自然语信源12本讲稿第十二页，共九十三页中文信源中文信源，通常指，通常指汉字汉字由字组词、由词组句、由句成文的由字组词、由词组句、由句成文的本质本质与英文一样与英文一样中文与英文的中文与英文的重要区别重要区别是每个单字都有明确的意义，而且数量是每个单字都有明确的意义，而且数量巨大巨大收入收入辞海辞海的汉字有的汉字有1.5万左
12、右万左右收入收入康熙字典康熙字典、汉语大字典汉语大字典分别超过了分别超过了4万个和万个和6万个。万个。要给出汉字的信源空间，须对大量的汉字文献进行统计要给出汉字的信源空间，须对大量的汉字文献进行统计新华社曾对新华社曾对2亿左右的汉字作了统计，得出了亿左右的汉字作了统计，得出了1850个汉字的使用个汉字的使用率为率为98%的结论的结论当被统计的数量趋于无穷时，每个汉字的使用频率应该趋于平稳当被统计的数量趋于无穷时，每个汉字的使用频率应该趋于平稳3.1离散信源的分类及其描述离散信源的分类及其描述3.1.2自然语信源自然语信源13本讲稿第十三页，共九十三页汉字统计的成果已被总结成国家标准汉字统计的成
13、果已被总结成国家标准例如：例如：GB2312-80、GB18030-2000等，等，给出了一级字库、二级字库和三级字库给出了一级字库、二级字库和三级字库由于文字的使用总是由于文字的使用总是与时俱进与时俱进的，这种的，这种统计的工作必然一直是有意义的。统计的工作必然一直是有意义的。与英文类似，汉字同样必须考虑其与英文类似，汉字同样必须考虑其关联关联性性。3.1离散信源的分类及其描述离散信源的分类及其描述3.1.2自然语信源自然语信源14本讲稿第十四页，共九十三页可以用符号的可以用符号的联合概率或条件概率来描述自然语信源的关联联合概率或条件概率来描述自然语信源的关联性性。对于英文，可以将包含对于英
14、文，可以将包含K个字母的单词看成是具有个字母的单词看成是具有K个字母的个字母的符号序列，或称为符号序列，或称为K重符号序列，将其作为一个整体消息，重符号序列，将其作为一个整体消息，其联合概率就已考虑了字母与字母间的关联性了。其联合概率就已考虑了字母与字母间的关联性了。也可以把由汉字组成的中文词汇作为符号序列。也可以把由汉字组成的中文词汇作为符号序列。还可以将句子、段落甚至整篇文章分别作为符号序列来考还可以将句子、段落甚至整篇文章分别作为符号序列来考虑，用联合概率来描述。虑，用联合概率来描述。有了符号或符号序列的信源空间就可以度量它们出现时有了符号或符号序列的信源空间就可以度量它们出现时所给出的
15、信息量，并可以计算它们的信源熵。所给出的信息量，并可以计算它们的信源熵。3.1离散信源的分类及其描述离散信源的分类及其描述3.1.2自然语信源自然语信源15本讲稿第十五页，共九十三页但无论是符号概率还是符号序列的联合概率都具但无论是符号概率还是符号序列的联合概率都具有先验概率的性质，只能有先验概率的性质，只能描述静态描述静态的情形，不能的情形，不能描述动态描述动态的过程。的过程。条件概率描述了符号间的记忆特性，但它同时给出了条件概率描述了符号间的记忆特性，但它同时给出了符号间的符号间的转移特性转移特性，故也称之为，故也称之为转移概率转移概率。以用第一个字母为以用第一个字母为T来构成来构成3个字
16、母的英文单词为例，第二个字母为个字母的英文单词为例，第二个字母为H的概的概率可以用条件概率率可以用条件概率 P(H|T)来表示，第三个字母为来表示，第三个字母为E的概率可以用条件概率的概率可以用条件概率P(E|TH)来表示，其他各种可能的组合也都可用其条件概率来表示。来表示，其他各种可能的组合也都可用其条件概率来表示。用用转移概率转移概率来描述的信源是一种来描述的信源是一种典型的马尔可夫信源典型的马尔可夫信源。3.1离散信源的分类及其描述离散信源的分类及其描述3.1.2自然语信源自然语信源16本讲稿第十六页，共九十三页1.马尔可夫过程和马尔可夫链的定义马尔可夫过程和马尔可夫链的定义定义定义3.
17、1设设X(t)为一个随机过程，若对任意的为一个随机过程，若对任意的t1t2 tn时刻的随机变量时刻的随机变量X(t1)，X(t2)，X(tn)，有，有P(xn;tn|xn1,xn2,x1;tn1,tn2,t1)=P(xn;tn|xn1;tn1)(3.1)则称则称X(t)为为单纯马尔可夫过程单纯马尔可夫过程或或一阶马尔可一阶马尔可夫过程夫过程。一阶马尔可夫过程在一阶马尔可夫过程在tn时刻的随机变量时刻的随机变量xn，仅仅和它前一时刻和它前一时刻tn-1的随机变量的随机变量xn-1有关有关。3.1离散信源的分类及其描述离散信源的分类及其描述3.1.3马尔可夫过程和马尔可夫链马尔可夫过程和马尔可夫链
18、17本讲稿第十七页，共九十三页定义定义3.2设设X(t)为一个随机过程，若对任意的为一个随机过程，若对任意的t1t2tn kH(X2|X1)H(X2)2H(X)3.2离散信源的熵离散信源的熵3.2.3发出符号序列消息离散有记忆信源的熵发出符号序列消息离散有记忆信源的熵37本讲稿第三十七页，共九十三页上述结论说明上述结论说明符号间的关联性使信源输出的信息量减符号间的关联性使信源输出的信息量减少少根据根据2.4.1讨论的熵的链接准则讨论的熵的链接准则对于对于2重扩展信源，有重扩展信源，有H(X 2)=H(X)+H(X|X)对于对于K重扩展信源，有重扩展信源，有(3.13)且且H(XK)KH(X)(
19、3.14)对比对比2.4.1和和2.4.3中讨论的熵的链接准则和熵的界，中讨论的熵的链接准则和熵的界，K重扩展信源是多维随机变量的一种特例，故重扩展信源是多维随机变量的一种特例，故有时也称有时也称式式(3.13)为熵的链接公式为熵的链接公式。3.2离散信源的熵离散信源的熵3.2.3发出符号序列消息离散有记忆信源的熵发出符号序列消息离散有记忆信源的熵38本讲稿第三十八页，共九十三页马尔可夫信源在马尔可夫信源在发生状态转移时发出消息发生状态转移时发出消息。设当前状态为设当前状态为Ei，下一状态，下一状态Ej，则其，则其转移过程转移过程可表可表示为示为假设在这个转移中假设在这个转移中可能发出可能发出
20、L个符号个符号，则有，则有L个转移个转移概率概率P1(Ej|Ei)，P2(Ej|Ei)，PL(Ej|Ei)。因此从状态因此从状态Ei转移到状态转移到状态Ej的总的转移概率为的总的转移概率为3.2离散信源的熵离散信源的熵3.2.4发出符号序列消息的马尔可夫信源的熵发出符号序列消息的马尔可夫信源的熵39本讲稿第三十九页，共九十三页设发一个符号有设发一个符号有J种转移，则信源由种转移，则信源由Ei状状态发出一个符号的熵为态发出一个符号的熵为(3.16)再假设当前状态共有再假设当前状态共有I 种可能，则有种可能，则有(3.17)可见，可见，马尔可夫信源的熵为条件熵马尔可夫信源的熵为条件熵。3.2离散信
21、源的熵离散信源的熵3.2.4发出符号序列消息的马尔可夫信源的熵发出符号序列消息的马尔可夫信源的熵40本讲稿第四十页，共九十三页将式将式(2.9)重写如下：重写如下：可见，可见，马尔可夫信源的熵是一般条件熵的一个特例马尔可夫信源的熵是一般条件熵的一个特例。虽然马尔可夫信源发出的是符号序列消息，但上面推虽然马尔可夫信源发出的是符号序列消息，但上面推出的熵，是出的熵，是平均每发出一个符号所给出的信息量平均每发出一个符号所给出的信息量，因此因此其量纲仍为比特其量纲仍为比特/符号符号，故和一般的条件熵在表，故和一般的条件熵在表达上完全相同。达上完全相同。3.2离散信源的熵离散信源的熵3.2.4发出符号序
22、列消息的马尔可夫信源的熵发出符号序列消息的马尔可夫信源的熵41本讲稿第四十一页，共九十三页3.2离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵应用中通常习惯于看应用中通常习惯于看单位时间里发出的平均信息量单位时间里发出的平均信息量，由此得出由此得出时间熵时间熵的概念。的概念。时间熵就是用单位时间来表示的熵时间熵就是用单位时间来表示的熵通常用通常用Ht表示，表示，单位时间的主量纲用秒（单位时间的主量纲用秒（s）表示，因此）表示，因此Ht的主量的主量纲为纲为比特每秒（比特每秒（b/s或或bps）也常用也常用kb/s、Mb/s、Gb/s、Tb/s（或（或kbps、Mbps
23、、Gbps、Tbps）等，分别表示千比特每秒、兆比特）等，分别表示千比特每秒、兆比特每秒、吉比特每秒每秒、吉比特每秒。42本讲稿第四十二页，共九十三页1.发出单个符号消息的离散无记忆信源的时间熵发出单个符号消息的离散无记忆信源的时间熵首先定义首先定义符号消息的平均长度符号消息的平均长度定义定义3.9若信源为具有若信源为具有N个单个符号消息的离个单个符号消息的离散信源，第散信源，第i个符号消息占有的时间为个符号消息占有的时间为bi秒，秒，对应的概率为对应的概率为Pi，i1，2，N，则称，则称bi的的统计平均值为该信源符号消息的统计平均值为该信源符号消息的平均时间长平均时间长度或平均长度度或平均长
24、度，用，用表示，表示，主量纲为秒主量纲为秒/符号符号。即即3.2离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵秒/符号(3.18)43本讲稿第四十三页，共九十三页对发出单个符号消息的离散无记忆信源，对发出单个符号消息的离散无记忆信源，若其信源熵为若其信源熵为H(X)，则其时间熵为，则其时间熵为3.2离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵若信源每秒平均发若信源每秒平均发n个符号，个符号，即即符号符号/秒秒 则则 Ht=nH(X)b/s(3.20)b/s(3.19)44本讲稿第四十四页，共九十三页2.发出符号序列消息的无记忆信源的时间
25、熵发出符号序列消息的无记忆信源的时间熵设发出符号序列消息的无记忆信源是单个符号消息的设发出符号序列消息的无记忆信源是单个符号消息的离散无记忆信源的离散无记忆信源的K重扩展，重扩展，K重符号序列消息的平均长重符号序列消息的平均长度用度用表示，则有表示，则有3.2离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵由于信源无记忆，故有由于信源无记忆，故有信源的时间熵为信源的时间熵为45本讲稿第四十五页，共九十三页其数值与发出单个符号消息的离散无记忆信源相其数值与发出单个符号消息的离散无记忆信源相同，但若该信源每秒平均发出同，但若该信源每秒平均发出n个个K重符号序列消重符号序列
26、消息，则有息，则有3.2离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵因此因此 Ht=nKH(X)b/s(3.24)与式与式(3.20)比较，这种情况的时间熵比单个符号消息比较，这种情况的时间熵比单个符号消息离散无记忆信源时大了离散无记忆信源时大了K倍，这是由于倍，这是由于n个个K重符号序重符号序列消息的缘故。列消息的缘故。符号序列符号序列/秒秒(3.23)46本讲稿第四十六页，共九十三页3.发出符号序列消息的有记忆信源的时间熵发出符号序列消息的有记忆信源的时间熵消息之间的关联性消息之间的关联性体现在信源熵中而不体现在体现在信源熵中而不体现在平均长度中平均长度中若其
27、信源熵为若其信源熵为H(XK)，符号序列消息的平均长，符号序列消息的平均长度为度为，则其时间熵依然应该是，则其时间熵依然应该是3.2离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵由于信源有记忆由于信源有记忆:这时的时间熵同样不会大于无记忆情况。这时的时间熵同样不会大于无记忆情况。b/s(3.25)47本讲稿第四十七页，共九十三页当然，可以用熵的链接公式当然，可以用熵的链接公式(3.13)来变换来变换H(XK)的形式，而平均长度仍可用式的形式，而平均长度仍可用式(3.18)来求。来求。这时，若该信源也是每秒平均发出这时，若该信源也是每秒平均发出n个个K重符号序列消息，
28、即重符号序列消息，即符符号序列号序列/秒，则其时间熵又可表示为秒，则其时间熵又可表示为 Ht=nH(XK)b/s(3.26)3.2离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵48本讲稿第四十八页，共九十三页4.发出符号序列消息的马尔可夫信源的时间熵发出符号序列消息的马尔可夫信源的时间熵发出符号序列消息的马尔可夫信源的时间熵仍发出符号序列消息的马尔可夫信源的时间熵仍可用可用来求。其信源熵来求。其信源熵H(X)已如式已如式(3.17)所示。所示。下面讨论信源发出所有符号的平均长度下面讨论信源发出所有符号的平均长度。假设从状态假设从状态Ei转移到状态转移到状态Ej时，信
29、源发出符号时，信源发出符号为为，其长度为，其长度为，发出该符号的概率为，发出该符号的概率为Pl(j/i)，Ei状态的概率为状态的概率为P(i)，其余假设同前，其余假设同前从状态从状态Ei到状态到状态E j状态转移图如图状态转移图如图3.2所示，则其平均长度所示，则其平均长度为为3.2离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵秒秒/符号符号 (3.26)49本讲稿第四十九页，共九十三页图图3.2马尔可夫信源状态马尔可夫信源状态Ei到状态到状态E j的状态转移图的状态转移图3.2离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵50本讲稿第五
30、十页，共九十三页所以所以b/s(3.27)3.2离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵51本讲稿第五十一页，共九十三页讨论信源的最主要目的是为了讨论信源的最主要目的是为了得到高效率的信源得到高效率的信源编码编码。衡量信源编码效率的尺度衡量信源编码效率的尺度是什么呢？是什么呢？或者说能够使信源编码或者说能够使信源编码提高效率的根本原因提高效率的根本原因是什是什么呢？么呢？本节讨论的信源冗余度将回答这些问题。本节讨论的信源冗余度将回答这些问题。3.3信源的冗余度信源的冗余度52本讲稿第五十二页，共九十三页定理定理3.1设信源设信源X中包含中包含M个不同符号，其信
31、源熵为个不同符号，其信源熵为H(X)，有，有H(X)lbM(3.28)当且仅当当且仅当X中各个符号的概率全相等时，上式取中各个符号的概率全相等时，上式取等号，此时得到最大熵等号，此时得到最大熵H(X)max=lbM(3.29)这一定理的证明，需要引用如下关系：这一定理的证明，需要引用如下关系：ln 1(0)(3.30)当且仅当当且仅当=1时，上式取等号。时，上式取等号。3.3.1最大信源熵最大信源熵3.3信源的冗余度信源的冗余度53本讲稿第五十三页，共九十三页证明证明H(X)lbM=(3.31)令令=1/MP(x)，因为，因为ln 1，(0)，将其代入式，将其代入式(3.31)并利用换底公式，
32、有并利用换底公式，有 即即H(X)lbM当且仅当当且仅当=1/MP(x)=1，即，即P(x)=1/M时等号成立。时等号成立。证毕。证毕。H(X)lbM 3.3信源的冗余度信源的冗余度3.3.1最大信源熵最大信源熵54本讲稿第五十四页，共九十三页定理定理3.1说明说明:当一个信源中所有的符号消息为等概时，当一个信源中所有的符号消息为等概时，该信源的熵最大。该信源的熵最大。上一章式上一章式(2.29)和式和式(2.36)已分别对二维和已分别对二维和n维随机变量的情况，证明了其共熵不大维随机变量的情况，证明了其共熵不大于它们各自的熵之和。于它们各自的熵之和。这里从最大熵的角度给出共熵和这里从最大熵的
33、角度给出共熵和K重扩展重扩展信源最大熵的两个定理。信源最大熵的两个定理。3.3信源的冗余度信源的冗余度3.3.1最大信源熵最大信源熵55本讲稿第五十五页，共九十三页定理定理3.2两个集合两个集合X,Y的共熵的共熵H(XY)与这两个集合与这两个集合的信源熵的信源熵H(X),H(Y)之间存在关系之间存在关系 H(XY)H(X)+H(Y)当且仅当两个集合相互独立时，上式取等号，此时得当且仅当两个集合相互独立时，上式取等号，此时得最大熵最大熵 H(XY)max=H(X)+H(Y)(3.32)其证明见对式其证明见对式(2.29)的证明。的证明。定理定理3.2说明，当两个集合之间相互独立时，它们说明，当两
34、个集合之间相互独立时，它们的的共熵最大共熵最大。3.3信源的冗余度信源的冗余度3.3.1最大信源熵最大信源熵56本讲稿第五十六页，共九十三页定理定理3.3对于初始信源对于初始信源X经过经过K重扩展的信源，若初重扩展的信源，若初始信源熵为始信源熵为H(X)，扩展后的信源熵为，扩展后的信源熵为H(XK)，有，有H(XK)KH(X)(3.33)当且仅当当且仅当K重符号序列消息的各个符号之间相互独重符号序列消息的各个符号之间相互独立时，上式取等号，此时得最大熵，为立时，上式取等号，此时得最大熵，为 H(XK)max=KH(X)(3.34)其证明同其证明同定理定理2.1的证明。的证明。定理定理3.3说明
35、，当说明，当K重扩展后信源的符号之间相互独重扩展后信源的符号之间相互独立时，其立时，其信源熵最大信源熵最大。3.3信源的冗余度信源的冗余度3.3.1最大信源熵最大信源熵57本讲稿第五十七页，共九十三页冗余度又称为冗余度又称为多余度多余度，是编码理论中的，是编码理论中的一个重要的概念。一个重要的概念。在信源编码中，人们总是在寻找在信源编码中，人们总是在寻找压缩信压缩信源冗余度源冗余度的方法来提高传输的有效性；的方法来提高传输的有效性；在信道编码中，人们又总是采取在信道编码中，人们又总是采取注入冗注入冗余度余度的方法来提高传输的可靠性。的方法来提高传输的可靠性。信源中存在着冗余度，信源中存在着冗余
36、度，冗余度可以用信冗余度可以用信源的熵值来表征源的熵值来表征，为此有如下的定义。，为此有如下的定义。3.3信源的冗余度信源的冗余度3.3.2信源的冗余度信源的冗余度58本讲稿第五十八页，共九十三页定义定义3.10设信源实际的熵为设信源实际的熵为H，该种信源可，该种信源可能的最大熵为能的最大熵为Hmax，则，则为信源的冗余度。为信源的冗余度。信源的冗余度实际上就是信源在发出消息时信源的冗余度实际上就是信源在发出消息时无用信息量所占的百分比无用信息量所占的百分比。3.3信源的冗余度信源的冗余度3.3.2信源的冗余度信源的冗余度59本讲稿第五十九页，共九十三页举例举例英文英文26个字母加空格共个字母
37、加空格共27个符号，假如完全等概，则得英文个符号，假如完全等概，则得英文的的最大熵为最大熵为Hmax=lb27 4.755比特比特/字母字母而根据表而根据表3.1，可计算这，可计算这27个符号的个符号的实际熵为实际熵为 H=0.1817lb20.18170.1073lb20.10730.00063lb20.00063 1比特比特/字母字母因此，该种信源的冗余度为因此，该种信源的冗余度为(4.7551)/4.755 79.0%3.3信源的冗余度信源的冗余度3.3.2信源的冗余度信源的冗余度60本讲稿第六十页，共九十三页不同的统计可以得到不同的实际熵不同的统计可以得到不同的实际熵。英文的冗余度是很
38、大的，因为语言本身有英文的冗余度是很大的，因为语言本身有很多固定的约束很多固定的约束，它，它对于信息传输是对于信息传输是“多余多余”。因此从信息传输的角度才把它定义为。因此从信息传输的角度才把它定义为“冗余冗余”。中文冗余度的统计比英文要复杂得多，中文的实际熵也比英文要难统计得多。中文冗余度的统计比英文要复杂得多，中文的实际熵也比英文要难统计得多。中文的最大熵是一个变量；中文的最大熵是一个变量；每一个单字都具有明确的意义，再由字组词，字词之间的相关性千变万化。每一个单字都具有明确的意义，再由字组词，字词之间的相关性千变万化。以以辞海辞海（上海，（上海，1989年版）收集的大约年版）收集的大约1
39、5000汉字为信源符号消息，汉字为信源符号消息，则则中文的最大信源熵为中文的最大信源熵为Hmax lb15000 13.9比特比特/汉字汉字3.3信源的冗余度信源的冗余度3.3.2信源的冗余度信源的冗余度61本讲稿第六十一页，共九十三页尚未找到给出中文实际熵和统计方法的尚未找到给出中文实际熵和统计方法的文献，但根据目前广泛使用的文本压缩文献，但根据目前广泛使用的文本压缩软件的压缩率来看，中文的实际熵应该软件的压缩率来看，中文的实际熵应该不会大于不会大于5比特比特/汉字，估计中文的冗余度汉字，估计中文的冗余度大约也会在大约也会在80%左右。左右。3.3信源的冗余度信源的冗余度3.3.2信源的冗余
40、度信源的冗余度62本讲稿第六十二页，共九十三页举例说明举例说明图图3.3给出了目前常用的几种语音编码的速率，假设图中三种编码给出了目前常用的几种语音编码的速率，假设图中三种编码方法方法PCM、ADPCM和和Vocoder代表三个信源，分别称为信代表三个信源，分别称为信源源A、B、C，其输出的码流均为二进制数字信号，码速率，其输出的码流均为二进制数字信号，码速率如图所示，若各种编码均没有造成语音信息的损失，而信如图所示，若各种编码均没有造成语音信息的损失，而信源源C输出的码流已基本达到输出的码流已基本达到1、0等概和完全随机，试求图中三等概和完全随机，试求图中三个信源的冗余度。个信源的冗余度。图
41、3.3 语音编码的几种速率3.3信源的冗余度信源的冗余度3.3.2信源的冗余度信源的冗余度63本讲稿第六十三页，共九十三页图中给出的图中给出的码速率码速率就是各信源的时间熵，因此使用式就是各信源的时间熵，因此使用式(3.35)时时均用时间熵均用时间熵。可认为三个信源的可认为三个信源的实际熵都是实际熵都是8kb/s，而三个信源的最大熵就是它，而三个信源的最大熵就是它们输出码序列的速率，即们输出码序列的速率，即64kb/s,32kb/s,8kb/s信源信源A冗余度为冗余度为RA=(648)/64=87.5%信源信源B冗余度为冗余度为RB=(328)/32=75%信源信源C冗余度为冗余度为RC=(8
42、8)/8=0即信源即信源C没有冗余，这时由于假设信源没有冗余，这时由于假设信源C的的输出已是该信源最大输出已是该信源最大熵熵。目前的语音编码器还做不到本例的假设条件，例如信源目前的语音编码器还做不到本例的假设条件，例如信源C中中仍有冗余度，因此仍有冗余度，因此各信源实际的冗余度可能更大各信源实际的冗余度可能更大。低速率的编码通常会带来语音信息的损失低速率的编码通常会带来语音信息的损失，且速率越低损失越，且速率越低损失越大，但这对于理解语音信息的冗余度没有影响。大，但这对于理解语音信息的冗余度没有影响。3.3信源的冗余度信源的冗余度3.3.2信源的冗余度信源的冗余度64本讲稿第六十四页，共九十三
43、页初始信源的冗余度通常是很大的，这为信源的压缩初始信源的冗余度通常是很大的，这为信源的压缩编码提供了可能编码提供了可能压缩编码的目标就是寻找某种编码方法，使得压缩编码的目标就是寻找某种编码方法，使得编码后编码后消息序列中的冗余度趋近于消息序列中的冗余度趋近于0如果将这种编码包含在信源中，也可以说是如果将这种编码包含在信源中，也可以说是寻找某寻找某种能够使信源冗余度趋近于种能够使信源冗余度趋近于0的编码方法的编码方法冗余度成为冗余度成为衡量信源编码效率的一个物理量衡量信源编码效率的一个物理量，冗，冗余度越低，编码效率就越高。余度越低，编码效率就越高。3.3信源的冗余度信源的冗余度3.3.2信源的
44、冗余度信源的冗余度65本讲稿第六十五页，共九十三页1.请请给给出出平平均均互互信信息息量量的的定定义义及及性性质质，说说说说疑疑义义度度、散散布布度度的的定定义义及及含含义义。张程张程2.请给出请给出熵的链接准则和信息链接准则。熵的链接准则和信息链接准则。证颖证颖3.请给出请给出n维随机变量的共熵与它们各自的熵之间的关系。维随机变量的共熵与它们各自的熵之间的关系。韩计海韩计海4.请简述数据处理定理和数据处理不等式。请简述数据处理定理和数据处理不等式。郭衍郭衍5.请给出几种信源的分类。请给出几种信源的分类。纵邦胜纵邦胜6.请说说用什么方法来描述自然语信源的关联性。请说说用什么方法来描述自然语信源
45、的关联性。绳红磊绳红磊7.请给出发出符号序列消息离散有记忆信源的熵请给出发出符号序列消息离散有记忆信源的熵荣俊兴荣俊兴8.请给出发出符号序列消息的马尔可夫信源的熵请给出发出符号序列消息的马尔可夫信源的熵王岩王岩9.请说说时间熵的定义、量纲请说说时间熵的定义、量纲曹喜曹喜10.请举例说明信源冗余度的定义。请举例说明信源冗余度的定义。唐岱唐岱第三次课（第三次课（2009年年3月月8日）日）上次课的回顾上次课的回顾66本讲稿第六十六页，共九十三页3.4信源符号序列分组定理信源符号序列分组定理设无记忆离散信源的信源空间设无记忆离散信源的信源空间为X：x1,x2,xi,xN P(X)：P1,P2,Pi,
46、PN 它的熵为它的熵为 假如将它进行假如将它进行K重扩展而得到重扩展而得到K重符号序列，用矢重符号序列，用矢量表示为量表示为 (3.36)则则这样的符号序列有这样的符号序列有N K个个。67本讲稿第六十七页，共九十三页3.4信源符号序列分组定理信源符号序列分组定理当当K的值很大时，根据大数定律，这个序列会的值很大时，根据大数定律，这个序列会以很高的概率以很高的概率出现以下情况出现以下情况：符号：符号x1约重复出现约重复出现KP1次，符号次，符号x2约重复出现约重复出现KP2次，次，符号，符号xN约重复出现约重复出现KPN次。次。这意味着当这意味着当K足够大时，将会以足够大时，将会以趋向于趋向于
47、1的概率的概率出现以下情况：出现以下情况：扩展后的很多序列扩展后的很多序列都具有相同的组成都具有相同的组成，因此也具有相同的概，因此也具有相同的概率。也就是说，当率。也就是说，当K足够大时，扩展后有相当多的符号序足够大时，扩展后有相当多的符号序列是等概的列是等概的。可以将具有上述结构的序列称为可以将具有上述结构的序列称为典型序列典型序列，而将其余的序列，而将其余的序列称为称为非典型序列非典型序列，如果典型序列的概率之和很大而非典型序列的概，如果典型序列的概率之和很大而非典型序列的概率之和很小，则率之和很小，则仅用典型序列来代表扩展信源在很多场合是可仅用典型序列来代表扩展信源在很多场合是可行的行
48、的。68本讲稿第六十八页，共九十三页既然所有的非典型序列的概率之和很小，对信源输出既然所有的非典型序列的概率之和很小，对信源输出来说，来说，忽略它们忽略它们而引入的误差可以小于任何给定的而引入的误差可以小于任何给定的值值将这一特性应用于将这一特性应用于信源的压缩编码信源的压缩编码中，这正是数据中，这正是数据压缩的本质压缩的本质信源符号序列分组定理说明了上述的信源符号序列分组定理说明了上述的分组是存在的分组是存在的，而且可以估算其典型序列的而且可以估算其典型序列的数目数目。下面给出信源符号序列分组定理及其证明。下面给出信源符号序列分组定理及其证明。3.4信源符号序列分组定理信源符号序列分组定理6
49、9本讲稿第六十九页，共九十三页(3.37)3.4信源符号序列分组定理信源符号序列分组定理70本讲稿第七十页，共九十三页证明证明设扩展后符号序列中取符号设扩展后符号序列中取符号xi值的次数为值的次数为ni (i=1,2,N)，由于信源是无记忆的，故有，由于信源是无记忆的，故有(3.38)两边取对数，有两边取对数，有(3.39)由于由于所以所以(3.40)3.4信源符号序列分组定理信源符号序列分组定理71本讲稿第七十一页，共九十三页ni/K=P(xi)+i(3.41)令令(3.42)3.4信源符号序列分组定理信源符号序列分组定理将式将式(3.41)代入代入(3.40)，有，有(3.43)在在NK个
50、可能的符号序列中，对于任意的个可能的符号序列中，对于任意的 0，将有，将有一部分一部分符号序列的符号序列的 max满足满足(3.44)72本讲稿第七十二页，共九十三页称满足式称满足式(3.45)条件的符号序列称为条件的符号序列称为典型序列（典型序列（TypicalSet），），将该种典型将该种典型序列的集合记作序列的集合记作G1，而称不满足式，而称不满足式(3.45)条件的符号序列称为条件的符号序列称为非典型序列非典型序列，将该种非典型序列的集合记作将该种非典型序列的集合记作G2。下面来估算下面来估算落入落入G1和和G2中的概率中的概率。对于集合对于集合G2，其中的符号序列不满足式，其中的符号