第3章_离散信源

1、东南大学移动通信国家重点实验室1第三章离散信源第三章离散信源东南大学移动通信国家重点实验室2离散信源离散信源的分类及其描述的分类及其描述离散信源的离散信源的熵熵信源的信源的冗余度冗余度信源符号序列信源符号序列分组定理分组定理平稳离散平稳离散信源及其性质信源及其性质本章内容提要本章内容提要东南大学移动通信国家重点实验室3通信系统的任务是通信系统的任务是将信源的消息有效可将信源的消息有效可靠地传送到信宿靠地传送到信宿。信源消息是信源消息是多种多样多种多样的。的。本章将重点讨论信源的本章将重点讨论信源的数学模型数学模型以及以及如如何度量何度量信源消息中的信息。信源消息中的信息。第第3章离散信源章离散

2、信源东南大学移动通信国家重点实验室4 从从信源发出的消息在时间上和幅度上的分布信源发出的消息在时间上和幅度上的分布 分为离散信源和连续信源。分为离散信源和连续信源。 从信源消息是模拟的还是数字的从信源消息是模拟的还是数字的 分为模拟信源和数字信源；分为模拟信源和数字信源； 对数字信源还可分为二进制信源和多进制信源。对数字信源还可分为二进制信源和多进制信源。 对于离散信源对于离散信源，根据，根据符号的特点符号的特点以及符号间的以及符号间的关联性关联性 可分可分无记忆无记忆离散信源和离散信源和有记忆有记忆离散信源。离散信源。 对于对于前者前者，又可分为发出单个符号的无记忆离散信，又可分为发出单个符

3、号的无记忆离散信源和发出符号序列的无记忆离散信源；源和发出符号序列的无记忆离散信源； 对于对于后者后者，又可分为发出符号序列的有记忆离散信，又可分为发出符号序列的有记忆离散信源和发出符号序列的马尔可夫（源和发出符号序列的马尔可夫（Markov）信源。）信源。3.1 离散信源的分类及其描述离散信源的分类及其描述3.1.1信源的分类信源的分类东南大学移动通信国家重点实验室5从从描述信源消息的随机过程的平稳性角度描述信源消息的随机过程的平稳性角度 分为平稳信源和非平稳信源。分为平稳信源和非平稳信源。按按随机过程的类别随机过程的类别 分为高斯信源、马尔可夫信源等。分为高斯信源、马尔可夫信源等。根据根据

4、人们对信源消息的感知人们对信源消息的感知 分为数据信源、文本信源、语音信源、图像分为数据信源、文本信源、语音信源、图像信源等，其中文本信源和语音信源都是针对人信源等，其中文本信源和语音信源都是针对人类语言、文字、声乐等感知的，又通称为类语言、文字、声乐等感知的，又通称为自然自然语信源语信源。3.1 离散信源的分类及其描述离散信源的分类及其描述3.1.1信源的分类信源的分类东南大学移动通信国家重点实验室6信源的分类方法可以有多种，但信源的分类方法可以有多种，但本质上本质上主要基主要基于两方面的考虑：于两方面的考虑：一是信源消息一是信源消息取值的取值的集合以及消息取值集合以及消息取值时刻的时刻的集

5、合，由此可分为离散信源、连续信源或数字集合，由此可分为离散信源、连续信源或数字信源、模拟信源等；信源、模拟信源等；二是信源消息的二是信源消息的统计特性统计特性，由此可分为无记忆，由此可分为无记忆（Memoryless）信源、有记忆（）信源、有记忆（Memory）源、）源、平稳信源、非平稳信源、高斯信源、马尔可夫平稳信源、非平稳信源、高斯信源、马尔可夫信源等。信源等。3.1 离散信源的分类及其描述离散信源的分类及其描述3.1.1信源的分类信源的分类东南大学移动通信国家重点实验室7本章讨论本章讨论离散信源离散信源，包括，包括无记忆和有记忆两无记忆和有记忆两类类。 前者前者分为发出分为发出单个符号单

6、个符号的离散无记忆信的离散无记忆信源和发出源和发出符号序列符号序列的离散无记忆信源两种，的离散无记忆信源两种， 后者后者分为发出符号序列的分为发出符号序列的离散有记忆离散有记忆信信源和发出符号序列的源和发出符号序列的马尔可夫马尔可夫信源两种。信源两种。3.1 离散信源的分类及其描述离散信源的分类及其描述3.1.1信源的分类信源的分类东南大学移动通信国家重点实验室8离散无记忆信源发出的离散无记忆信源发出的各个消息符号是相互各个消息符号是相互独立的独立的 发出单个符号的离散无记忆信源：每次只发出发出单个符号的离散无记忆信源：每次只发出一个符号一个符号且每个符号且每个符号代表一个消息代表一个消息 发

7、出符号序列的离散无记忆信源：每次发出一发出符号序列的离散无记忆信源：每次发出一组组不少于两个不少于两个的符号序列来的符号序列来代表一个消息代表一个消息。3.1 离散信源的分类及其描述离散信源的分类及其描述3.1.1信源的分类信源的分类东南大学移动通信国家重点实验室9离散有记忆信源发出的各个消息符号是离散有记忆信源发出的各个消息符号是相互关联相互关联的的 发出符号序列的离散有记忆信源发出符号序列的离散有记忆信源关联性关联性可用其联合概率来表示可用其联合概率来表示发出符号序列的马尔可夫信源发出符号序列的马尔可夫信源 关联性可用其关联性可用其条件概率条件概率来表示来表示3.1 离散信源的分类及其描述

8、离散信源的分类及其描述3.1.1信源的分类信源的分类东南大学移动通信国家重点实验室10研究信源最主要的目的是研究信源最主要的目的是为信源编码服务为信源编码服务。信源编码的信源编码的目标目标是用尽可能少的是用尽可能少的码元符号码元符号或尽或尽可能低的可能低的数据速率数据速率来描述信源输出的消息。来描述信源输出的消息。怎样的信源编码才是好的或者说是怎样的信源编码才是好的或者说是有效的有效的?信源信源参数测量参数测量离散信源的离散信源的数学模型数学模型及其及其信息的度量信息的度量3.1 离散信源的分类及其描述离散信源的分类及其描述3.1.1信源的分类信源的分类东南大学移动通信国家重点实验室11可以简

9、单地将自然语信源定义为可以简单地将自然语信源定义为以人类的自然语以人类的自然语言作为输出消息的信源言作为输出消息的信源。自然语言又可以分为自然语言又可以分为书面书面语言和语言和声音声音语言两大类语言两大类 书面语言由一个个文字符号构成，是一种典型书面语言由一个个文字符号构成，是一种典型的离散信源的离散信源 也是信息论中首先讨论和研究最多的信源也是信息论中首先讨论和研究最多的信源 以英文和中文为例讨论书面语言以英文和中文为例讨论书面语言 声音语言的信源放在第声音语言的信源放在第6章讨论。章讨论。3.1 离散信源的分类及其描述离散信源的分类及其描述3.1.2自然语信源自然语信源东南大学移动通信国家

10、重点实验室12 英文信源英文信源 先将英文看成仅由先将英文看成仅由26个字母和空格个字母和空格构成，即构成，即暂不考虑暂不考虑标点符号及其他。标点符号及其他。 英文中英文中字母字母的组合构成单词，的组合构成单词，单词单词的组合构成句子，的组合构成句子，句子句子的组合构成段落和文章。的组合构成段落和文章。 在某一个统计集合中能得出其字母、单词、句子的分在某一个统计集合中能得出其字母、单词、句子的分布概率。布概率。 例如通过大量统计得到的例如通过大量统计得到的26个字母和空格的出现概率个字母和空格的出现概率如表如表3. 1所示。它构成了所示。它构成了英文字母和空格的信源空间英文字母和空格的信源空间

11、。 仅仅按照表中的出现概率随机构成的一串字母序列通仅仅按照表中的出现概率随机构成的一串字母序列通常并不能构成英文单词，。常并不能构成英文单词，。 其构成还有许多语法和修辞方面的其构成还有许多语法和修辞方面的制约制约，这种制约在，这种制约在数学关系上的反映就是其数学关系上的反映就是其关联性关联性。3.1 离散信源的分类及其描述离散信源的分类及其描述3.1.2自然语信源自然语信源东南大学移动通信国家重点实验室13表表3.1的一维概率分布是反映不出英文构成的关联性的。的一维概率分布是反映不出英文构成的关联性的。3.1 离散信源的分类及其描述离散信源的分类及其描述3.1.2自然语信源自然语信源东南大学

12、移动通信国家重点实验室14 中文信源中文信源，通常指，通常指汉字汉字 由字组词、由词组句、由句成文的由字组词、由词组句、由句成文的本质本质与英文一样与英文一样 中文与英文的中文与英文的重要区别重要区别是每个单字都有明确的意义，而是每个单字都有明确的意义，而且数量巨大且数量巨大 收入收入辞海辞海的汉字有的汉字有1.5万左右万左右 收入收入康熙字典康熙字典、汉语大字典汉语大字典分别超过了分别超过了4万万个和个和6万万个。个。 要给出汉字的信源空间，须对大量的汉字文献进行要给出汉字的信源空间，须对大量的汉字文献进行统计统计 新华社新华社曾对曾对2亿左右的汉字作了统计，得出了亿左右的汉字作了统计，得出

13、了1850个汉字个汉字的使用率为的使用率为98%的结论的结论 当被统计的数量当被统计的数量趋于无穷趋于无穷时，每个汉字的使用频率应该时，每个汉字的使用频率应该趋于平稳趋于平稳3.1 离散信源的分类及其描述离散信源的分类及其描述3.1.2自然语信源自然语信源东南大学移动通信国家重点实验室15汉字统计的汉字统计的成果成果已被总结成国家标准已被总结成国家标准例如：例如：GB2312-80、GB18030-2000等，等，给出了一级字库、二级字库和三级字库给出了一级字库、二级字库和三级字库由于文字的使用总是由于文字的使用总是与时俱进与时俱进的，这种统的，这种统计的工作必然一直是有意义的。计的工作必然一

14、直是有意义的。与英文类似，汉字同样必须考虑其与英文类似，汉字同样必须考虑其关联性关联性。3.1 离散信源的分类及其描述离散信源的分类及其描述3.1.2自然语信源自然语信源东南大学移动通信国家重点实验室16 可以用符号的可以用符号的联合概率或条件概率来描述自然语信源的关联合概率或条件概率来描述自然语信源的关联性联性。 对于英文，可以将包含对于英文，可以将包含K个字母的单词看成是具有个字母的单词看成是具有K个字母个字母的符号序列，或称为的符号序列，或称为K重符号序列重符号序列，将其作为一个整体消，将其作为一个整体消息，其息，其联合概率联合概率就已考虑了字母与字母间的关联性了。就已考虑了字母与字母间

15、的关联性了。 也可以把由汉字组成的也可以把由汉字组成的中文词汇作为符号序列中文词汇作为符号序列。 还可以将句子、段落甚至整篇文章还可以将句子、段落甚至整篇文章分别作为符号序列分别作为符号序列来考来考虑，用联合概率来描述。虑，用联合概率来描述。 有了符号或符号序列的信源空间，就可以度量它们出现时有了符号或符号序列的信源空间，就可以度量它们出现时所给出的信息量，并可以计算它们的所给出的信息量，并可以计算它们的信源熵信源熵。3.1 离散信源的分类及其描述离散信源的分类及其描述3.1.2自然语信源自然语信源东南大学移动通信国家重点实验室17但无论是符号概率还是符号序列的联合概率都但无论是符号概率还是符

16、号序列的联合概率都具有先验概率的性质，只能具有先验概率的性质，只能描述静态描述静态的情形，的情形，不能不能描述动态描述动态的过程。的过程。条件概率描述了符号间的记忆特性，但它同时条件概率描述了符号间的记忆特性，但它同时给出了符号间的给出了符号间的转移特性转移特性，故也称之为，故也称之为转移概转移概率率。 以用第一个字母为以用第一个字母为T来构成来构成3个字母的英文单词为例，第二个字母个字母的英文单词为例，第二个字母为为H的概率可以用条件概率的概率可以用条件概率 P(H|T)来表示，第三个字母为来表示，第三个字母为E的概率的概率可以用条件概率可以用条件概率P(E|TH)来表示，其他各种可能的组合

17、也都可用其来表示，其他各种可能的组合也都可用其条件概率来表示。条件概率来表示。用用转移概率转移概率来描述的信源是一种来描述的信源是一种典型的马尔可典型的马尔可夫信源夫信源。3.1 离散信源的分类及其描述离散信源的分类及其描述3.1.2自然语信源自然语信源东南大学移动通信国家重点实验室181. 马尔可夫过程和马尔可夫链的定义马尔可夫过程和马尔可夫链的定义 定义定义3.1 设设X(t)为一个随机过程，若对任意的为一个随机过程，若对任意的t1t2 tn时刻的随机变量时刻的随机变量X(t1)，X(t2)，X(tn)，有，有P( xn; tn | xn1, xn2, , x1; tn1, tn2, ,

18、t1)= P( xn; tn | xn1; tn1) (3.1)则称则称X(t)为为单纯马尔可夫过程单纯马尔可夫过程或或一阶马尔可一阶马尔可夫过程夫过程。 一阶马尔可夫过程在一阶马尔可夫过程在tn时刻的随机变量时刻的随机变量xn，仅仅和它前一时刻和它前一时刻tn-1的随机变量的随机变量xn-1有关有关。 3.1 离散信源的分类及其描述离散信源的分类及其描述3.1.3马尔可夫过程和马尔可夫链马尔可夫过程和马尔可夫链东南大学移动通信国家重点实验室19 定义定义3.2 设设X(t)为一个随机过程，若对任意的为一个随机过程，若对任意的t1t2tn k H(X2|X1) H(X2)2H(X)符号比特 /

19、 542.1)(lb)()(31iiiaPaPH X3.2 离散信源的熵离散信源的熵3.2.3发出符号序列消息离散有记忆信源的熵发出符号序列消息离散有记忆信源的熵符号比特 / 870. 0)|(lb)()|(313112ijijjiaaPaaPXXH东南大学移动通信国家重点实验室43上述结论说明上述结论说明符号间的关联性使信源输出的信符号间的关联性使信源输出的信息量减少息量减少根据根据2.4.1讨论的熵的链接准则讨论的熵的链接准则 对于对于2重扩展信源，有重扩展信源，有H(X2) =H(X)+H(X|X) 对于对于K重扩展信源，有重扩展信源，有(3.13) 且且 H(XK) KH(X)(3.1

20、4)对比对比2.4.1和和2.4.3中讨论的熵的链接准则和熵的中讨论的熵的链接准则和熵的界，界，K重扩展信源是多维随机变量的一种特例，重扩展信源是多维随机变量的一种特例，故故有时也称式有时也称式(3.13)为熵的链接公式为熵的链接公式。)|()|()()() 1( 个kKHHHHXXXXXXXX3.2 离散信源的熵离散信源的熵3.2.3发出符号序列消息离散有记忆信源的熵发出符号序列消息离散有记忆信源的熵东南大学移动通信国家重点实验室44马尔可夫信源在马尔可夫信源在发生状态转移时发出消息发生状态转移时发出消息。设当前状态为设当前状态为Ei，下一状态，下一状态Ej，则其，则其转移过程转移过程可表示

21、为可表示为 假设在这个转移中假设在这个转移中可能发出可能发出L个符号个符号，则有，则有L个个转移概率转移概率P1(Ej|Ei)，P2(Ej|Ei) ，PL (Ej|Ei) 。因此从状态因此从状态Ei转移到状态转移到状态Ej的总的转移概率为的总的转移概率为jEijPiEjEPiE )/()/( 缩写为：(3.15)3.2 离散信源的熵离散信源的熵3.2.4发出符号序列消息的马尔可夫信源的熵发出符号序列消息的马尔可夫信源的熵LlijlpijP1)|()|(东南大学移动通信国家重点实验室45设发一个符号有设发一个符号有J种转移，则信源由种转移，则信源由Ei状状态发出一个符号的熵为态发出一个符号的熵为

22、 (3.16)再假设当前状态共有再假设当前状态共有I 种可能，则有种可能，则有 (3.17) JiijPijPH)|(lb)|(IJJIIiijPijPijPijPiPHiPH)|(lb)()|(log)|()()(可见，可见，马尔可夫信源的熵为条件熵马尔可夫信源的熵为条件熵。3.2 离散信源的熵离散信源的熵3.2.4发出符号序列消息的马尔可夫信源的熵发出符号序列消息的马尔可夫信源的熵东南大学移动通信国家重点实验室46将式将式(2.9)重写如下：重写如下：可见，可见，马尔可夫信源的熵是一般条件熵的一个马尔可夫信源的熵是一般条件熵的一个特例特例。虽然马尔可夫信源发出的是符号序列消息，但虽然马尔可

23、夫信源发出的是符号序列消息，但上面推出的熵，是上面推出的熵，是平均每发出一个符号所给出平均每发出一个符号所给出的信息量的信息量，因此，因此其量纲仍为比特其量纲仍为比特/符号符号，故和，故和一般的条件熵在表达上完全相同。一般的条件熵在表达上完全相同。XYYX)|(lb)()|(yxPxyPH3.2 离散信源的熵离散信源的熵3.2.4发出符号序列消息的马尔可夫信源的熵发出符号序列消息的马尔可夫信源的熵东南大学移动通信国家重点实验室473.2 离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵应用中通常习惯于看应用中通常习惯于看单位时间里发出的平均信单位时间里发出的平均信息量

24、息量，由此得出，由此得出时间熵时间熵的概念。的概念。时间熵就是用单位时间来表示的熵时间熵就是用单位时间来表示的熵通常用通常用Ht表示，表示，单位时间的主量纲用秒（单位时间的主量纲用秒（s）表示，因此）表示，因此Ht的的主量纲为主量纲为比特每秒（比特每秒（b/s或或bps）也常用也常用kb/s、Mb/s、Gb/s、Tb/s（或（或kbps、Mbps、Gbps、Tbps）等，分别表示千比特每）等，分别表示千比特每秒、兆比特每秒、吉比特每秒秒、兆比特每秒、吉比特每秒。东南大学移动通信国家重点实验室481. 发出单个符号消息的离散无记忆信源的时间熵发出单个符号消息的离散无记忆信源的时间熵 首先定义首先

25、定义符号消息的平均长度符号消息的平均长度 定义定义3.9 若信源为具有若信源为具有N个单个符号消息的离个单个符号消息的离散信源，第散信源，第i个符号消息占有的时间为个符号消息占有的时间为bi秒，秒，对应的概率为对应的概率为Pi，i1，2，N，则称，则称bi的的统计平均值为该信源符号消息的统计平均值为该信源符号消息的平均时间长平均时间长度或平均长度度或平均长度，用，用 表示，表示，主量纲为秒主量纲为秒/符号符号。即即3.2 离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵bNiiibpb1秒/符号(3.18)东南大学移动通信国家重点实验室49对发出对发出单个符号消息单个

26、符号消息的离散无记忆信源，的离散无记忆信源，若其信源熵为若其信源熵为H(X)，则其时间熵为，则其时间熵为 )(bHHtXbn/13.2 离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵若信源每秒平均若信源每秒平均发发n个符号个符号， 即即 符号符号/秒秒 则则 Ht = nH(X) b/s(3.20)b/s(3.19)东南大学移动通信国家重点实验室502.发出符号序列消息的无记忆信源的时间熵发出符号序列消息的无记忆信源的时间熵设发出符号序列消息的无记忆信源是单个符号消息设发出符号序列消息的无记忆信源是单个符号消息的离散无记忆信源的的离散无记忆信源的K重扩展重扩展，K重

27、符号序列消息的重符号序列消息的平均长度用平均长度用 表示，则有表示，则有bHbKKHBHHKt/ )()(/ )(XXXNiiibpKbKB1(3.21)()(XXKHHK3.2 离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵由于由于信源无记忆信源无记忆，故有，故有B信源的时间熵为信源的时间熵为(3.22) b/s东南大学移动通信国家重点实验室51其其数值数值与发出单个符号消息的离散无记忆信源与发出单个符号消息的离散无记忆信源相同相同，但若该信源每秒平均发出，但若该信源每秒平均发出n个个K重符号序重符号序列列消息，则有消息，则有bKBn1/13.2 离散信源的熵离散

28、信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵因此因此 Ht = nKH(X) b/s (3.24)与式与式(3.20)比较，这种情况的时间熵比单个符比较，这种情况的时间熵比单个符号消息离散无记忆信源时号消息离散无记忆信源时大了大了K倍倍，这是由于，这是由于n个个K重符号序列重符号序列消息的缘故。消息的缘故。符号序列符号序列/秒秒(3.23)东南大学移动通信国家重点实验室523. 发出符号序列消息的有记忆信源的时间熵发出符号序列消息的有记忆信源的时间熵 消息之间的关联性消息之间的关联性体现在信源熵中而不体现在体现在信源熵中而不体现在平均长度中平均长度中 若其信源熵为若其信源熵为H(

29、XK)，符号序列消息的平均长，符号序列消息的平均长度为度为 ，则其时间熵依然应该是，则其时间熵依然应该是bKXHBXHHKKt/ )(/ )(3.2 离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵由于信源有记忆由于信源有记忆:)()(XKHXHK这时的时间熵同样不会大于无记忆情况。这时的时间熵同样不会大于无记忆情况。Bb/s (3.25)东南大学移动通信国家重点实验室53当然，可以当然，可以用熵的链接公式用熵的链接公式(3.13)来变换来变换H(XK )的形式的形式，而平均长度仍可用式，而平均长度仍可用式(3.18)来求。来求。这时，若该信源也是这时，若该信源也是每

30、秒平均发出每秒平均发出n个个K重符号序列消息重符号序列消息，即，即 符符号序列号序列/秒，则其时间熵又可表示为秒，则其时间熵又可表示为 Ht = n H(XK ) b/s(3.26)3.2 离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵bKBn/1/1东南大学移动通信国家重点实验室544. 发出符号序列消息的马尔可夫信源的时间熵发出符号序列消息的马尔可夫信源的时间熵 发出符号序列消息的马尔可夫信源的时间熵仍发出符号序列消息的马尔可夫信源的时间熵仍可用可用 来求。其信源熵来求。其信源熵H(X)已如式已如式(3.17)所示。所示。 下面讨论信源发出所有符号的平均长度下面

31、讨论信源发出所有符号的平均长度 。 假设从状态假设从状态Ei转移到状态转移到状态Ej时，信源发出符号时，信源发出符号为为 ，其长度为，其长度为 ，发出该符号的概率为，发出该符号的概率为 Pl (j/i) ，Ei状态的概率为状态的概率为P(i)，其余假设同前，其余假设同前从状态从状态Ei到状态到状态E j状态转移图如图状态转移图如图3.2所示，则其平均所示，则其平均长度为长度为 3.2 离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵bHHt/ )(Xb)(lija)(lijbIJLllijlbijpiPb1)()/()(秒秒/符号符号 (3.26)东南大学移动通信国家

32、重点实验室55图图3.2 马尔可夫信源状态马尔可夫信源状态Ei到状态到状态Ej的状态转移图的状态转移图 )/(1)1 ()1 (ijpbaijij Ei Ej )/()()(ijpballijlij )/()()(ijpbaLLijLij 3.2 离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵东南大学移动通信国家重点实验室56所以所以 b/s (3.27)3.2 离散信源的熵离散信源的熵3.2.5各种离散信源的时间熵各种离散信源的时间熵 JLlijbijlPIiPIJijPijPiPbHHt )()|()()|(lb)|()(/ )(X东南大学移动通信国家重点实验室

33、57讨论信源的最主要目的是为了讨论信源的最主要目的是为了得到高效率的信得到高效率的信源编码源编码。衡量信源编码效率的尺度衡量信源编码效率的尺度是什么呢？是什么呢？或者说能够使信源编码或者说能够使信源编码提高效率的根本原因提高效率的根本原因是是什么呢？什么呢？本节讨论的信源冗余度将回答这些问题。本节讨论的信源冗余度将回答这些问题。3.3 信源的冗余度信源的冗余度东南大学移动通信国家重点实验室58定理定理3.1 设信源设信源X中包含中包含M个不同符号，个不同符号，其信源熵为其信源熵为H(X)，有，有H(X) lb M(3.28)当且仅当当且仅当X中各个符号的概率全相等时，中各个符号的概率全相等时，

34、上式取等号，此时得到上式取等号，此时得到最大熵最大熵H(X) max = lbM (3.29)3.3.1最大信源熵最大信源熵3.3 信源的冗余度信源的冗余度东南大学移动通信国家重点实验室59这一定理亦称为这一定理亦称为最大信源熵定理最大信源熵定理，其证，其证明，需要引用如下关系：明，需要引用如下关系：ln 1 ( 0) (3.30)当且仅当当且仅当 = 1时，上式取等号。时，上式取等号。3.3.1最大信源熵最大信源熵3.3 信源的冗余度信源的冗余度东南大学移动通信国家重点实验室60 证明证明 H(X) lbM = = (3.31) 令令 = 1/MP(x)，因为，因为ln 1，( 0)，将其代

35、入式，将其代入式(3.31)并利用换底公式，有并利用换底公式，有即即 H(X) lbM当且仅当当且仅当 = 1/MP(x) = 1，即，即P(x) =1/M时等号成立。时等号成立。证毕。证毕。XXMxPxPxPlb)()(1lb)(X)(1lb)(xMPxP01/ln2)(11/ln2)(1（XXxPMxPMXH(X) lbM 3.3 信源的冗余度信源的冗余度3.3.1最大信源熵最大信源熵X1)(xP东南大学移动通信国家重点实验室61定理定理3.1说明说明:当一个信源中所有的符号消息为等概时，当一个信源中所有的符号消息为等概时，该信源的熵最大。该信源的熵最大。上一章式上一章式(2.29)和式和

36、式(2.36)已分别对二维和已分别对二维和n维随机变量的情况，证明了其共熵不大于维随机变量的情况，证明了其共熵不大于它们各自的熵之和。它们各自的熵之和。这里从最大熵的角度给出共熵和这里从最大熵的角度给出共熵和K重扩展重扩展信源最大熵的两个定理。信源最大熵的两个定理。3.3 信源的冗余度信源的冗余度3.3.1最大信源熵最大信源熵东南大学移动通信国家重点实验室62定理定理3.2 两个集合两个集合X、Y的共熵的共熵H(XY)与这两个与这两个集合的信源熵集合的信源熵H(X)、H(Y)之间存在关系之间存在关系 H(XY) H(X) + H(Y)当且仅当两个集合相互独立时，上式取等号，当且仅当两个集合相互

37、独立时，上式取等号，此时得最大熵此时得最大熵 H(XY)max = H(X) + H(Y)(3.32)其证明见对式其证明见对式(2.29)的证明。的证明。定理定理3.2说明，当两个集合之间相互独立时，它说明，当两个集合之间相互独立时，它们的们的共熵最大共熵最大。3.3 信源的冗余度信源的冗余度3.3.1最大信源熵最大信源熵东南大学移动通信国家重点实验室63定理定理3.3 对于初始信源对于初始信源X经过经过K重扩展的信源，重扩展的信源，若初始信源熵为若初始信源熵为H(X)，扩展后的信源熵为，扩展后的信源熵为H(XK )，有，有 H(XK ) KH(X) (3.33)当且仅当当且仅当K重符号序列消

38、息的各个符号之间相重符号序列消息的各个符号之间相互独立时，上式取等号，此时得最大熵，为互独立时，上式取等号，此时得最大熵，为 H(XK )max = KH(X) (3.34)其证明同其证明同定理定理2.1的证明。的证明。定理定理3.3说明，当说明，当K重扩展后信源的符号之间相重扩展后信源的符号之间相互独立时，其互独立时，其信源熵最大信源熵最大。3.3 信源的冗余度信源的冗余度3.3.1最大信源熵最大信源熵东南大学移动通信国家重点实验室64冗余度又称为冗余度又称为多余度多余度，是编码理论中的，是编码理论中的一个重要的概念。一个重要的概念。在信源编码中，人们总是在寻找在信源编码中，人们总是在寻找压

39、缩信压缩信源冗余度源冗余度的方法来提高传输的有效性；的方法来提高传输的有效性；在信道编码中，人们又总是采取在信道编码中，人们又总是采取注入冗注入冗余度余度的方法来提高传输的可靠性。的方法来提高传输的可靠性。信源中存在着冗余度，信源中存在着冗余度，冗余度可以用信冗余度可以用信源的熵值来表征源的熵值来表征，为此有如下的定义。，为此有如下的定义。3.3 信源的冗余度信源的冗余度3.3.2信源的冗余度信源的冗余度东南大学移动通信国家重点实验室65定义定义3.10 设信源实际的熵为设信源实际的熵为H，该种信源可，该种信源可能的最大熵为能的最大熵为Hmax，则，则为信源的冗余度。为信源的冗余度。信源的冗余

40、度实际上就是信源在发出消息时信源的冗余度实际上就是信源在发出消息时“无用信息量无用信息量”所占的所占的百分比百分比。%100maxmaxHHHR(3.35)3.3 信源的冗余度信源的冗余度3.3.2信源的冗余度信源的冗余度东南大学移动通信国家重点实验室66举例举例 英文英文26个字母加空格共个字母加空格共27个符号，假如完全等概，则个符号，假如完全等概，则得英文的得英文的最大熵为最大熵为Hmax = lb27 4.755 比特比特/字母字母 而根据表而根据表3.1，可计算这，可计算这27个符号的个符号的实际熵为实际熵为 H = 0.1817lb20.1817 0.1073lb20.1073 0

41、.00063lb20.00063 1 比特比特/字母字母 因此，该种信源的冗余度为因此，该种信源的冗余度为 (4.7551)/4.755 79.0 %100maxmaxHHHR3.3 信源的冗余度信源的冗余度3.3.2信源的冗余度信源的冗余度东南大学移动通信国家重点实验室67 不同的统计可以得到不同的实际熵不同的统计可以得到不同的实际熵。 英文的冗余度是很大的，因为语言本身有英文的冗余度是很大的，因为语言本身有很多固定的约束很多固定的约束，它，它对对于信息传输是于信息传输是“多余多余” 。因此从信息传输的角度才把它定义为。因此从信息传输的角度才把它定义为“冗余冗余” 。 中文冗余度的统计比英文

42、要复杂得多，中文的实际熵也比英文要中文冗余度的统计比英文要复杂得多，中文的实际熵也比英文要难统计得多。难统计得多。 中文的最大熵是一个变量；中文的最大熵是一个变量； 每一个单字都具有明确的意义，再由字组词，字词之间的相关性每一个单字都具有明确的意义，再由字组词，字词之间的相关性千变万化。千变万化。 以以辞海辞海（上海，（上海，1989年版）收集的大约年版）收集的大约15000汉字为信源符汉字为信源符号消息，则号消息，则中文的最大信源熵为中文的最大信源熵为Hmax lb15000 13.9 比特比特/汉字汉字3.3 信源的冗余度信源的冗余度3.3.2信源的冗余度信源的冗余度东南大学移动通信国家重

43、点实验室68尚未找到给出尚未找到给出中文实际熵和统计方法中文实际熵和统计方法的的文献，但根据目前广泛使用的文本压缩文献，但根据目前广泛使用的文本压缩软件的压缩率来看，中文的实际熵应该软件的压缩率来看，中文的实际熵应该不会大于不会大于5比特比特/汉字汉字，估计，估计中文的冗余中文的冗余度度大约也会在大约也会在80%左右。左右。3.3 信源的冗余度信源的冗余度3.3.2信源的冗余度信源的冗余度东南大学移动通信国家重点实验室69 举例说明举例说明图图3.3给出了目前常用的几种语音编码的速率，假设图给出了目前常用的几种语音编码的速率，假设图中三种编码方法中三种编码方法PCM、ADPCM和和Vocode

44、r代表三个信代表三个信源，分别称为信源源，分别称为信源A、B、C，其输出的码流均为二进，其输出的码流均为二进制数字信号，码速率如图所示，若各种编码制数字信号，码速率如图所示，若各种编码均没有均没有造造成语音信息的损失，而信源成语音信息的损失，而信源C输出的码流已基本达到输出的码流已基本达到1、0等概和完全随机等概和完全随机，试求图中三个信源的，试求图中三个信源的冗余度冗余度。语音语音 A 64 kb/s B 32 kb/s C 8 kb/s PCM ADPCM Vecoder 图图3.3 语音编码的几种速率语音编码的几种速率3.3 信源的冗余度信源的冗余度3.3.2信源的冗余度信源的冗余度东南

45、大学移动通信国家重点实验室70 图中给出的图中给出的码速率码速率就是各信源的时间熵，因此使用式就是各信源的时间熵，因此使用式(3.35)时时均用时间熵均用时间熵。 可认为三个信源的可认为三个信源的实际熵都是实际熵都是8 kb/s，而三个信源的最大，而三个信源的最大熵就是它们输出码序列的速率，即熵就是它们输出码序列的速率，即64 kb/s, 32 kb/s, 8 kb/s 信源信源A冗余度为冗余度为RA = (64 8 )/64 = 87.5% 信源信源B冗余度为冗余度为RB = (32 8)/32 = 75% 信源信源C冗余度为冗余度为RC = (8 8)/8 = 0即信源即信源C没有冗余，这

46、是由于假设信源没有冗余，这是由于假设信源C的的输出已是该信输出已是该信源最大熵源最大熵。 目前的语音编码器还做不到本例的假设条件，例如信源目前的语音编码器还做不到本例的假设条件，例如信源C中仍有冗余度，因此中仍有冗余度，因此各信源实际的冗余度可能更大各信源实际的冗余度可能更大。 低速率的编码通常会带来语音信息的损失低速率的编码通常会带来语音信息的损失，且速率越低，且速率越低损失越大，但这对于理解语音信息的冗余度没有影响。损失越大，但这对于理解语音信息的冗余度没有影响。3.3 信源的冗余度信源的冗余度3.3.2信源的冗余度信源的冗余度东南大学移动通信国家重点实验室71初始信源的冗余度通常是很大的

47、，这为信源的初始信源的冗余度通常是很大的，这为信源的压缩编码提供了可能压缩编码提供了可能压缩编码的目标就是寻找某种编码方法，使得压缩编码的目标就是寻找某种编码方法，使得编码后消息序列中的冗余度趋近于编码后消息序列中的冗余度趋近于0如果将这种编码包含在信源中，也可以说是如果将这种编码包含在信源中，也可以说是寻寻找某种能够使信源冗余度趋近于找某种能够使信源冗余度趋近于0的编码方法的编码方法冗余度成为冗余度成为衡量信源编码效率的一个物理量衡量信源编码效率的一个物理量，冗余度越低，编码效率就越高。冗余度越低，编码效率就越高。3.3 信源的冗余度信源的冗余度3.3.2信源的冗余度信源的冗余度东南大学移动

48、通信国家重点实验室723.4 信源符号序列分组定理信源符号序列分组定理 设无记忆离散信源的信源空间设无记忆离散信源的信源空间为X： x1, x2, , xi, , xN P(X)： P1, P2, ,Pi, , PN 它的熵为它的熵为NiiiPPH1lb)(X 假如将它进行假如将它进行K重扩展而得到重扩展而得到K重符号序列，重符号序列，用矢量表示为用矢量表示为 (3.36) 则则这样的符号序列有这样的符号序列有N K个个。 ikiixxx,21x东南大学移动通信国家重点实验室733.4 信源符号序列分组定理信源符号序列分组定理当当K的值很大时，根据大数定律，这个序列会的值很大时，根据大数定律，

49、这个序列会以很高的以很高的概率出现以下情况概率出现以下情况：符号：符号x1约重复出现约重复出现KP1次，符号次，符号x2约约重复出现重复出现KP2次，次，符号，符号xN约重复出现约重复出现KPN次。次。这意味着当这意味着当K足够大时，将会以足够大时，将会以趋向于趋向于1的概率的概率出现以出现以下情况：扩展后的很多序列下情况：扩展后的很多序列都具有相同的组成都具有相同的组成，因此也，因此也具有相同的概率。也就是说，当具有相同的概率。也就是说，当K足够大时，扩展后足够大时，扩展后有相当多的符号序列是等概的有相当多的符号序列是等概的。可以将具有上述结构的序列称为可以将具有上述结构的序列称为典型序列典

50、型序列，而将其余，而将其余的序列称为的序列称为非典型序列非典型序列，如果典型序列的概率之和很大，如果典型序列的概率之和很大而非典型序列的概率之和很小，则而非典型序列的概率之和很小，则仅用典型序列来代表仅用典型序列来代表扩展信源在很多场合是可行的扩展信源在很多场合是可行的。东南大学移动通信国家重点实验室74既然所有的非典型序列的概率之和很小，对信既然所有的非典型序列的概率之和很小，对信源输出来说，源输出来说，忽略它们忽略它们而引入的误差可以小于而引入的误差可以小于任何给定的值任何给定的值将这一特性应用于将这一特性应用于信源的压缩编码信源的压缩编码中，这正是中，这正是数据压缩的本质数据压缩的本质信

51、源符号序列分组定理说明了上述的信源符号序列分组定理说明了上述的分组是存分组是存在的在的，而且可以估算其典型序列的，而且可以估算其典型序列的数目数目。下面给出信源符号序列分组定理及其证明。下面给出信源符号序列分组定理及其证明。3.4 信源符号序列分组定理信源符号序列分组定理东南大学移动通信国家重点实验室75(3.37)3.4 信源符号序列分组定理信源符号序列分组定理1)()(lb1XxHPKP东南大学移动通信国家重点实验室76 证明证明 设扩展后符号序列中取符号设扩展后符号序列中取符号xi值的次数为值的次数为ni ( i =1, 2, , N)，由于信源是无记忆的，故有，由于信源是无记忆的，故有

52、(3.38) 两边取对数，有两边取对数，有(3.39) 由于由于 所以所以 (3.40) KiniixPP1x3.4 信源符号序列分组定理信源符号序列分组定理KiiixPnP1)(lb)(lbxNiiixPxPH1)(lb)()(X)(lb)()()(lb11iiKiixPxPKnHPKXx东南大学移动通信国家重点实验室77ni /K=P(xi)+ i (3.41)令令 (3.42)|maxmaxii3.4 信源符号序列分组定理信源符号序列分组定理将式将式(3.41)代入代入(3.40)，有，有(3.43) 在在NK个可能的符号序列中，对于任意的个可能的符号序列中，对于任意的 0，将有，将有一

53、部分一部分符号序列的符号序列的 max满足满足)(lb/1maxiKixP(3.44)| )()(lb1|XxHPK| )(lb|1iKiixP)(lb1maxiKixP东南大学移动通信国家重点实验室78 称满足式称满足式(3.45)条件的符号序列称为条件的符号序列称为典型序列（典型序列（Typical Set），），将将该种典型序列的集合记作该种典型序列的集合记作G1，而称不满足式，而称不满足式(3.45)条件的符号序条件的符号序列称为列称为非典型序列非典型序列，将该种非典型序列的集合记作，将该种非典型序列的集合记作G2。 下面来估算下面来估算落入落入G1 和和G2中的概率中的概率。 对于集

54、合对于集合G2，其中的符号序列不满足式，其中的符号序列不满足式(3.44)，即，即至少存在一个至少存在一个值值l，使使max)(/lixPKn3.4 信源符号序列分组定理信源符号序列分组定理则这些符号序列即能满足则这些符号序列即能满足)45. 3(| )()(lb1|XxHPK(3.46)东南大学移动通信国家重点实验室79 如果把发生式如果把发生式(3.46)的事件记为的事件记为El，则对于，则对于G2中所有序列，中所有序列，有有(3.47) 但根据但根据大数定律大数定律，当，当K足够大时，对于任意足够大时，对于任意l 值总可以有值总可以有一个整数一个整数K0，使当，使当K K0时，对任意的时

55、，对任意的 0，有，有(3.48) 即即nl /K依概率收敛到依概率收敛到P(xl)。这样，就得到。这样，就得到G2组组中符号序中符号序列的概率之和小于列的概率之和小于 ，即，即)(max)()(11lllEPKEPEPlKlKlKxPKnPEPill/| )(/|max3.4 信源符号序列分组定理信源符号序列分组定理)(1lKlEP (3.49)东南大学移动通信国家重点实验室80所以所以G1中中符号序列概率之和大于符号序列概率之和大于1 ，此结论，此结论即为式即为式(3.37)。由于。由于 、 都是任意给定的，故都是任意给定的，故亦可以亦可以取取 = ，定理依然成立。，定理依然成立。证毕。证

56、毕。定理定理3.4被称为被称为信源符号序列分组定理信源符号序列分组定理，也有的，也有的文献称之为文献称之为渐进均分特性渐进均分特性。3.4 信源符号序列分组定理信源符号序列分组定理东南大学移动通信国家重点实验室81 下面估计下面估计G1集合中典型符号序列的数目集合中典型符号序列的数目。 根据式根据式(3.37)，有，有(3.50)式中的对数以式中的对数以2为底，则为底，则x在在G1集合中的概率集合中的概率P(x)的范的范围为围为 (3.51) 设设G1内典型符号序列的数目为内典型符号序列的数目为NG, 则则 (3.52) )(min2)(xHKPx 2)(2)()(xHKxHKP x1)()(

57、1minGGxxPPN3.4 信源符号序列分组定理信源符号序列分组定理)()(lb1XxHPK因此因此(3.53)(G2xHKN(3.54) 上限上限东南大学移动通信国家重点实验室82 任意一个符号序列任意一个符号序列不在不在G1内必在内必在G2内内，因此，因此(3.55)而而 (3.56)(max2)(xHKP x1)(1GxP1)()(maxGGxxPPN3.4 信源符号序列分组定理信源符号序列分组定理由式由式(3.51)知知(3.57)所以所以)(G2)1 (xHKN)(G)(22)1 (xHKxHKN由于由于 、 很小，故有很小，故有)(G2xKHN(3.58 下限下限)(3.59)(

58、3.60)东南大学移动通信国家重点实验室83信源符号序列分组定理说明，对信源符号序列分组定理说明，对于于K重扩展重扩展信源，信源，只考虑典型符只考虑典型符号序列对信源特性带来的损失可号序列对信源特性带来的损失可以低到可被忽略的程度以低到可被忽略的程度，这给出，这给出了信源压缩编码的理论依据。了信源压缩编码的理论依据。3.4 信源符号序列分组定理信源符号序列分组定理东南大学移动通信国家重点实验室84从描述信源消息随机过程的从描述信源消息随机过程的平稳性平稳性角度角度，信源可以分为，信源可以分为平稳平稳信源和信源和非非平稳平稳信源信源很多实际的信源在很多实际的信源在较短的一段时间较短的一段时间内都

59、可以用平稳信源来描述内都可以用平稳信源来描述研究平稳信源是研究非平稳信源的研究平稳信源是研究非平稳信源的基础，故本节讨论基础，故本节讨论平稳离散信源及平稳离散信源及其性质其性质3.5 平稳离散信源及其性质平稳离散信源及其性质东南大学移动通信国家重点实验室85 定义定义3.10 若一个离散信源发出的符号序列若一个离散信源发出的符号序列()，其出现概率与另一符号序列，其出现概率与另一符号序列()的出现概率相等，那么这个离散的出现概率相等，那么这个离散信源称为平稳离散信源。信源称为平稳离散信源。 定义定义3.10说明，对于平稳离散信源，若说明，对于平稳离散信源，若改变符号序列的起改变符号序列的起始位

60、置始位置，其概率的描述不变。，其概率的描述不变。 由该定义还可以看出，平稳离散信源的定义对应的随机由该定义还可以看出，平稳离散信源的定义对应的随机过程是过程是严平稳严平稳的。的。 下面通过讨论平稳离散信源的熵来研究它的一些性质。下面通过讨论平稳离散信源的熵来研究它的一些性质。Kxxx,21Kjjjxxx,213.5 平稳离散信源及其性质平稳离散信源及其性质东南大学移动通信国家重点实验室86（1）平稳离散信源的极限熵）平稳离散信源的极限熵 K重有记忆离散信源每发一个符号提供的平均信息量重有记忆离散信源每发一个符号提供的平均信息量。 由于信源不断发出符号，在由于信源不断发出符号，在时间域时间域上总