信息论与编码(第三版).ppt

信息论与编码信息论与编码计算器1简简 介介 是一门应用概率论、随机过程、数理统计和是一门应用概率论、随机过程、数理统计和近代代数的方法，来研究信息传输、提取和处近代代数的方法，来研究信息传输、提取和处理中一般规律的学科。理中一般规律的学科。奠基人：美国数学家香农（）奠基人：美国数学家香农（）19481948年年“通信的数学理论通信的数学理论”2简简 介介l信息论的基本问题信息论的基本问题信息的度量信息的度量l无失真信源编码定理无失真信源编码定理香农第一定理香农第一定理l信道编码定理信道编码定理香农第二定理香农第二定理l信源编码、信道编码信源编码、信道编码3绪绪 论论第第1 1章章41.1 1.1 信息的概念信息的概念 5情报：情报：是人们对于某个特定对象所见、所闻、所是人们对于某个特定对象所见、所闻、所理解而产生的知识。理解而产生的知识。知识：知识：一种具有普遍和概括性质的高层次的信息一种具有普遍和概括性质的高层次的信息 ，以实践为基础，通过抽象思维，对客观事物规，以实践为基础，通过抽象思维，对客观事物规律性的概括。律性的概括。消息：消息：用文字、符号、语音、图像等能够被人们用文字、符号、语音、图像等能够被人们感觉器官所感知的形式，把客观物质运动和主观感觉器官所感知的形式，把客观物质运动和主观思维活动的状态表达出来。思维活动的状态表达出来。几个常见概念几个常见概念6香农信息的度量香农信息的度量（1 1）样本空间）样本空间 某事物各种可能出现的不同状态。某事物各种可能出现的不同状态。（2 2）概率测度）概率测度 对每一个可能选择的消息指定一个概率。对每一个可能选择的消息指定一个概率。（3 3）概率空间）概率空间 l先验概率先验概率p p(x xi i)：选择符号选择符号x xi i作为消息的概率。作为消息的概率。样本空间概率测度7l例：例：气象预报气象预报 甲甲乙乙l“甲地晴甲地晴”比比“乙地晴乙地晴”的不确定性小。的不确定性小。l某一事物状态出现的概率越小，其不确定性越大。某一事物状态出现的概率越小，其不确定性越大。某一事物状态出现的概率接近于某一事物状态出现的概率接近于1,1,即预料中肯定会即预料中肯定会出现的事件，那它的不确定性就接近于零。出现的事件，那它的不确定性就接近于零。8 对对x xi i的不确定性可表示为先验概率的不确定性可表示为先验概率p(xp(xi i)的倒数的某一函数。的倒数的某一函数。（4 4）自信息）自信息（5 5）互信息）互信息 先验的不确定性减去尚存的不确定性。先验的不确定性减去尚存的不确定性。后验概率后验概率p p(a ai i|b bj j)：接收端收到消息接收端收到消息b bj j后而后而发送端发的是发送端发的是a ai i的概率。的概率。9信息的特征信息的特征信息是信息是物质存在的普遍属性物质存在的普遍属性，信息和能量、物质规定了，信息和能量、物质规定了事物的事物的功能和性能功能和性能；接收者在收到信息之前，对它的内容是不知道的，所以，接收者在收到信息之前，对它的内容是不知道的，所以，信息是信息是新知识、新内容新知识、新内容；它使认识主体对某一事物的未；它使认识主体对某一事物的未知性或不确定性减少的有用知识；知性或不确定性减少的有用知识；信息的存在具有信息的存在具有普遍性、无限性、动态性、时效性普遍性、无限性、动态性、时效性和和相相对独立性对独立性；信息可以产生，也可以消失，同时信息可以被信息可以产生，也可以消失，同时信息可以被传递、转传递、转换、扩散、复制、贮存、分割换、扩散、复制、贮存、分割，具有，具有可共享性可共享性；信息是信息是可以量度可以量度的，信息量有多少的差别。的，信息量有多少的差别。101.2 1.2 信息论研究的信息论研究的对象、目的和内容对象、目的和内容11研究对象：通信系统模型研究对象：通信系统模型信信道道信信源源信源编码信源编码加密加密信信道道编编码码干干 扰扰 源源信信宿宿信源解码信源解码解密解密信信道道解解码码加密密钥解密密钥12l信源：信源：发送消息的源发送消息的源l离散信源离散信源l模拟信源模拟信源信源是信息论的主要研究对象之一信源是信息论的主要研究对象之一.我们我们不探讨信不探讨信源的内部结构和机理源的内部结构和机理，而关注，而关注信源的输出。信源的输出。重点重点讨论其讨论其描述方法及性质描述方法及性质。l信宿：信宿：信息归宿之意，亦即收信者或用户，信息归宿之意，亦即收信者或用户，是信息传送的终点或目的地。是信息传送的终点或目的地。l信道：信道：传输信息的传输信息的物理媒介物理媒介。信源、信道、信宿信源、信道、信宿13l信源编码器信源编码器l通过信源编码可以压缩信源的冗余度通过信源编码可以压缩信源的冗余度,以提高通以提高通信系统传输消息的效率。信系统传输消息的效率。l信源编码器分为两类信源编码器分为两类l无失真信源编码无失真信源编码：适用于离散信源或数字信号；：适用于离散信源或数字信号；l限失真信源编码限失真信源编码：用于连续信源或模拟信号：用于连续信源或模拟信号,如如语音、图像等信号的数字处理。语音、图像等信号的数字处理。信源编码器与译码器信源编码器与译码器l信源编码器的主要指标信源编码器的主要指标l是它的是它的编码效率编码效率。一般来说，效率越高，编译码。一般来说，效率越高，编译码器的代价也将越大。器的代价也将越大。l信源译码器信源译码器l把信道译码器的输出变换成信宿所需的消息形式，把信道译码器的输出变换成信宿所需的消息形式，相当于相当于信源编码器的逆过程信源编码器的逆过程。14信道编码器与译码器信道编码器与译码器l信道编码信道编码l主要作用是提高信息传送的主要作用是提高信息传送的可靠性可靠性。l信道编码器的作用信道编码器的作用l在信源编码器输出的代码组上有目的地增加一些监督在信源编码器输出的代码组上有目的地增加一些监督码元码元,使之具有检错或纠错的能力。使之具有检错或纠错的能力。l信道编码的主要方法信道编码的主要方法l增大码率或频带增大码率或频带,即增大所需的信道容量。这恰与信源即增大所需的信道容量。这恰与信源编码相反。编码相反。l信道译码器的作用信道译码器的作用l具有检错或纠错的功能具有检错或纠错的功能,它能将落在其检错或纠错范围它能将落在其检错或纠错范围内的错传码元检出或纠正内的错传码元检出或纠正,以提高传输消息的可靠性。以提高传输消息的可靠性。151.3 1.3 信息论的形成和发展信息论的形成和发展16 信信息息论论是是在在长长期期的的通通信信工工程程实实践践和和理理论论研研究究的基础上发展起来的。的基础上发展起来的。简简 史史l现代信息论现代信息论是从是从2020世纪世纪2020年代年代奈奎斯特奈奎斯特和和哈特莱哈特莱的工作开始的：的工作开始的：l19241924年奈奎斯特年奈奎斯特(Nyquist)(Nyquist)的的“影响电报速率因影响电报速率因素的确定素的确定”。l19281928年哈特莱年哈特莱(Hartley)(Hartley)的的“信息传输信息传输”一文研一文研究了通信系统传输信息的能力，并给出了信息度究了通信系统传输信息的能力，并给出了信息度量方法。量方法。信息论的形成信息论的形成17l19461946年年柯切尔尼柯夫柯切尔尼柯夫的学位论文的学位论文“起伏噪声下的潜在抗干起伏噪声下的潜在抗干扰理论扰理论”，根据最小错误概率准则和最小均方误差准则研根据最小错误概率准则和最小均方误差准则研究了离散和连续信道的最佳接收问题。究了离散和连续信道的最佳接收问题。l19481948年年香农香农的权威性长文的权威性长文“通信的数学理论通信的数学理论”，讨论了信讨论了信源和信道特性，源和信道特性，19491949年香农年香农“噪声中的通信噪声中的通信”，两论文奠两论文奠定了现代信息论的理论基础。定了现代信息论的理论基础。l此后，在基本理论和实际应用方面，信息论都得到了巨大此后，在基本理论和实际应用方面，信息论都得到了巨大的发展。的发展。18第第2 2章章 离散信源及其信息测度离散信源及其信息测度 2.1 2.1 信源的数学模型及分类信源的数学模型及分类2.2 2.2 离散信源的信息熵离散信源的信息熵2.3 2.3 信息熵的基本性质信息熵的基本性质2.5 2.5 离散无记忆的扩展信源离散无记忆的扩展信源2.6 2.6 离散平稳信源离散平稳信源2.7 2.7 马尔可夫信源马尔可夫信源2.8 2.8 信源剩余度与自然语言的熵信源剩余度与自然语言的熵19信源信源 产生产生消息消息或或消息序列消息序列的源。的源。消息消息携带信息，携带信息，是信息的具体形式。是信息的具体形式。描述方法描述方法 通信过程中，信源发出何种消息是通信过程中，信源发出何种消息是不确定不确定的、的、是是随机的。随机的。因此，信源可用因此，信源可用随机变量、随机矢量随机变量、随机矢量或或随机随机过程过程（或（或样本空间样本空间及其及其概率测度概率测度）来描述。）来描述。不同的信源根据其输出消息的不同的不同的信源根据其输出消息的不同的随机性随机性质质进行分类。进行分类。2.1 2.1 信源的数学模型及分类信源的数学模型及分类201 1、随机变量描述的信源（单符号）、随机变量描述的信源（单符号）l特点：特点：输出单符号消息。符号集的取值输出单符号消息。符号集的取值A:A:aa1 1,a,a2 2,a,aq q 是是有限的有限的或或可数的可数的,可用可用离散型随机变量离散型随机变量X X描述。描述。l数学模型：数学模型：设每个信源符号设每个信源符号a ai i出现的出现的(先验先验)概率概率p(p(a ai i)(i=1,2,q)(i=1,2,q)满足：满足：概率空间概率空间能表征离散信源的能表征离散信源的统计特性统计特性，因此也称概率空，因此也称概率空间为间为信源空间信源空间。1 1）离散信源）离散信源211 1）平稳信源）平稳信源l特点特点:信源输出的消息由一信源输出的消息由一符号序列符号序列所组成。所组成。可用可用N N维随机矢量维随机矢量 X X(X(X1 1,X,X2 2,X,XN N)描述，且描述，且随机矢量随机矢量X X的各维概率分布都与时间起点无关的各维概率分布都与时间起点无关 。l离散平稳信源：离散平稳信源：每个随机变量每个随机变量X X X Xi i(i(i1,2,N)1,2,N)是取值是取值离散的随机变量。离散的随机变量。l连续平稳信源：连续平稳信源：每个随机变量每个随机变量X X X Xi i(i(i1,2,N)1,2,N)是取值是取值连续的随机变量。连续的随机变量。2 2、随机矢量描述的信源、随机矢量描述的信源222 2）离散无记忆平稳信源）离散无记忆平稳信源l离散平稳信源的离散平稳信源的特例，特例，信源发出的符号都信源发出的符号都相互统计独立，相互统计独立，即各随机变即各随机变量量X Xi i (i1,2,N)之间统计独立。之间统计独立。l性质：性质：l独立独立P(X)=P(XP(X)=P(X1 1,X,X2 2,X,XN N)=P)=P1 1(X(X1 1)P)P2 2(X(X2 2)P)PN N(X(XN N)l平稳平稳PP1 1(X(Xi i)=P)=P2 2(X(Xi i)=P)=PN N(X(Xi i)=P(X)=P(Xi i)（下标下标1-N1-N为时间标志为时间标志）N N维随机维随机矢量矢量的一个取值，的一个取值，i i(a(ai1i1 a ai2i2aaiNiN)P(aP(aikik)是符号集是符号集A A的一维的一维概率分布概率分布若各随机变量若各随机变量X Xi取值同样符号集取值同样符号集A:A:a a1 1,a,a2 2,a,aq q，则则23信源信源X X的各输出的各输出X Xi i间统计独立、且取值同一符号集间统计独立、且取值同一符号集A A。该信源。该信源输出的输出的N N维维随机矢量随机矢量X X为为离散无记忆信源离散无记忆信源X X的的N N次扩展信源。次扩展信源。此扩展信源取值为符号集此扩展信源取值为符号集 i i(a(ai1i1a ai2i2aaiNiN),),其中其中(i(i1 1,i,i2 2,i,iN N=1,2=1,2 ,q),q)，其其数学模型数学模型是是X X信源空间的信源空间的N N重空间：重空间：3 3）离散无记忆信源的）离散无记忆信源的N N次扩展信源次扩展信源 若若X为为离散无记忆信源：离散无记忆信源：244 4）有记忆信源）有记忆信源 信源在不同时刻发出的信源在不同时刻发出的符号之间是相互依赖的，符号之间是相互依赖的，即信源输出即信源输出的的随机序列随机序列X X中，各随机变量中，各随机变量Xi之间相互依赖。之间相互依赖。须使用随机矢量的须使用随机矢量的联合概率分布联合概率分布和和条件概率分布条件概率分布来说明它来说明它们之间的关联关系。们之间的关联关系。例：汉字组成的中文序列中，只有根据中文的语法、习惯用例：汉字组成的中文序列中，只有根据中文的语法、习惯用语、修辞制约和表达实际意义的制约所构成的中文序列才是有语、修辞制约和表达实际意义的制约所构成的中文序列才是有意义的中文句子或文章。所以，在汉字序列中前后文字的出现意义的中文句子或文章。所以，在汉字序列中前后文字的出现是有依赖的，是彼此相关的。是有依赖的，是彼此相关的。255 5）m m阶马尔可夫信源（非平稳信源）阶马尔可夫信源（非平稳信源）不同时刻发出的符号间的依赖关系不同时刻发出的符号间的依赖关系 记忆信源的记忆长度为记忆信源的记忆长度为m+1时，称这种有记忆信源为时，称这种有记忆信源为m阶阶马尔可夫信源。马尔可夫信源。若上述条件概率与时间起点若上述条件概率与时间起点 i 无关，信源输出的符无关，信源输出的符号序列可看成为时齐马尔可夫链，则此信源称为号序列可看成为时齐马尔可夫链，则此信源称为时齐马时齐马尔可夫信源。尔可夫信源。262.2 2.2 离散信源的信息熵离散信源的信息熵 基本的离散信源：基本的离散信源：输出输出单符号单符号消息，且这些消息间两两互不相容。用消息，且这些消息间两两互不相容。用一维随机变量一维随机变量X来描述信源的输出，其数学模型可抽象为来描述信源的输出，其数学模型可抽象为:问题：问题：问题：问题：这样的信源能输出多少信息这样的信源能输出多少信息这样的信源能输出多少信息这样的信源能输出多少信息?每个消息的出现携带多少信息量每个消息的出现携带多少信息量每个消息的出现携带多少信息量每个消息的出现携带多少信息量?27信息的度量信息的度量l要点：要点：l信息的度量（信息量）和信息的度量（信息量）和不确定性消除不确定性消除的程度有关，的程度有关，消除的不消除的不确定性获得的信息量；确定性获得的信息量；l不确定性就是随机性，可以用概率论和随机过程来测度；不确定性就是随机性，可以用概率论和随机过程来测度；l推论：推论：l概率小概率小 信息量大，即信息量是信息量大，即信息量是概率的单调递减函数；概率的单调递减函数；l信息量应该具有信息量应该具有可加性；可加性；l信息量的计算公式为（香农（自）信息量的度量）：信息量的计算公式为（香农（自）信息量的度量）：282.1.1 2.1.1 自信息自信息 设离散信源设离散信源X的概率空间为：的概率空间为：I(aI(ai i)代表两种代表两种含义：含义：（1）当事件当事件ai发生以前，表示事件发生以前，表示事件ai发生的发生的不确定性不确定性（2）当事件）当事件ai发生以后，表示事件发生以后，表示事件ai所提供的所提供的信息量信息量自信息量：自信息量：事件事件ai发生所含有的信息量发生所含有的信息量29度量单位度量单位l计算自信息量时要注意有关事件发生概率的计算；计算自信息量时要注意有关事件发生概率的计算；l自信息量的自信息量的单位单位取决于对数的底；取决于对数的底；l底为底为2 2，单位为，单位为“比特比特（bit,binary unit）”；l底为底为e e，单位为，单位为“奈特奈特（nat,nature unit）”；l底为底为1010，单位为，单位为“哈特哈特（hat,Hartley）”；l根据换底公式得：根据换底公式得：n一般计算都采用以一般计算都采用以“2”2”为底的对数，为了书写简洁，常把为底的对数，为了书写简洁，常把底数底数“2”2”略去不写略去不写1 nat=1.44bit,1 hat=3.32 bit1 nat=1.44bit,1 hat=3.32 bit；30收信者收信者收到某消息收到某消息获得的信息量获得的信息量 不确定性减少的量不确定性减少的量 (收到此消息前关于某事件的不确定性收到此消息前关于某事件的不确定性)-(-(收到此消息后关于某事件的不确定性收到此消息后关于某事件的不确定性)通信的实质？通信的实质？即：传递信息，消除不确定性。即：传递信息，消除不确定性。即：传递信息，消除不确定性。即：传递信息，消除不确定性。312.2.2 2.2.2 信息熵信息熵l对对一一个个信信源源发发出出不不同同消消息息所所含含有有的的信信息息量量也也不不同同。所所以以自自信信息息I(aI(ai i)是是一一个个随随机机变变量量，不不能能用用它它来来作作为为整整个个信信源源的信息测度。的信息测度。l信息熵：信息熵：自信息的数学期望，自信息的数学期望，平均自信息量平均自信息量H Hr r(X)(X)：r r进制单位进制单位/符号符号32熵的含义熵的含义l熵是熵是从整个集合的统计特性从整个集合的统计特性来考虑的，它从平均意来考虑的，它从平均意义上来表征信源的总体特征。义上来表征信源的总体特征。l信源输出前，信源输出前，熵熵H(X)H(X)表示信源的表示信源的平均不确定性；平均不确定性；l信源输出后，信源输出后，熵熵H(X)H(X)表示每个消息的表示每个消息的平均信息量；平均信息量；l信息熵信息熵H(X)H(X)表征了变量表征了变量X X的的随机性。随机性。33 信息熵是信息熵是信源概率空间信源概率空间的一种特殊函数。这个函数的取的一种特殊函数。这个函数的取值大小，与信源的值大小，与信源的符号数符号数及其及其概率分布概率分布有关。有关。用用概概率矢量率矢量P P来表示来表示概概率分布率分布P P(x x)：3.3 3.3 信息熵的基本性质信息熵的基本性质 则信息熵则信息熵H(X)H(X)是概率矢量是概率矢量P P或它的分量或它的分量p p1 1，p p2 2，p pq q的的q-1q-1元函数元函数(独立变量只有独立变量只有q-1q-1元元)。则。则 H(X)H(X)可写成：可写成：34熵函数的向量形式熵函数的向量形式lH(P)H(P)是概率矢量是概率矢量P P的函数，称为的函数，称为熵函数熵函数。l我们用下述表示方法：我们用下述表示方法：l用用H(x)H(x)表示以离散随机变量表示以离散随机变量x x描述的描述的信源的信息熵信源的信息熵；l用用H(P)H(P)或或H(pH(p1 1,p,p2 2,p,pq q)表示表示概率矢量概率矢量为为P=(pP=(p1 1,p,p2 2,p,pq q)的的q q个符号信源的信息熵个符号信源的信息熵。l若当若当 q=2 q=2 时，因为时，因为 p p1 1+p+p2 2=1,=1,所以将两个符号的熵函数所以将两个符号的熵函数写成写成H(pH(p1 1)或或H(pH(p2 2)。l熵函数熵函数H(P)H(P)是一种特殊函数，具有以下性质。是一种特殊函数，具有以下性质。35熵函数性质熵函数性质1 1、对称性：、对称性：H(P)H(P)的取值与分量的取值与分量 p p1 1,p,p2 2,p,pq q的顺序无关。的顺序无关。l说明：说明：H(P)=H(P)=p pi i log log p pi i 中的和式满足中的和式满足交换率交换率；熵只与随机变量的熵只与随机变量的总体统计特性总体统计特性有关。有关。例子：例子：362 2、确定性：、确定性：H(1,0)=H(1,0,0)=H(1,0,0,0)=0H(1,0)=H(1,0,0)=H(1,0,0,0)=0l说明说明：从总体来看，信源虽然有不同的输出符号，但：从总体来看，信源虽然有不同的输出符号，但它只有一个符号几乎必然出现，而其它符号则是几乎它只有一个符号几乎必然出现，而其它符号则是几乎不可能出现，那么，这个信源是一个确知信源，其熵不可能出现，那么，这个信源是一个确知信源，其熵为零。为零。分析：分析：若若P Pi i=1,P=1,Pi ilogPlogPi i=0=0；其他；其他P Pj j趋于趋于0 0，P Pj jlogPlogPj j 趋于趋于0 0。由罗。由罗比塔法则：比塔法则：因此因此373 3、非负性：、非负性：H(P)H(P)0 0l说明：说明：l随机变量随机变量X X的概率分布满足的概率分布满足0 0p pi i1 1，对数函数的底大，对数函数的底大于于1 1时，时，log(plog(pi i)0 0，-p-pi ilog(plog(pi i)0 0，即得的熵为正，即得的熵为正值。只有当随机变量是一确知量时熵才等于零。值。只有当随机变量是一确知量时熵才等于零。l这种非负性合适于离散信源的熵，对连续信源来说这一这种非负性合适于离散信源的熵，对连续信源来说这一性质并不存在（基于性质并不存在（基于差熵、相对熵差熵、相对熵概念）。概念）。v非负性体现信息是非负的。非负性体现信息是非负的。非负性体现信息是非负的。非负性体现信息是非负的。384 4、扩展性、扩展性l说明：说明：信源的信源的符号数增多符号数增多时，若这些取值对应的概率时，若这些取值对应的概率很小很小(接近于零接近于零)，则信源的熵不变。，则信源的熵不变。所以，上式成立。所以，上式成立。因为因为趋于趋于0 0395 5、可加性、可加性 统计独立信源统计独立信源X X和和Y Y的的联合信源联合信源XYXY的熵的熵等于信源等于信源X X和和Y Y各自的熵之和：各自的熵之和：H(XY)=H(X)+H(Y)H(XY)=H(X)+H(Y)即：即：另外：可加性是熵函数的一个重要特性，正因具有可加性，另外：可加性是熵函数的一个重要特性，正因具有可加性，才能保证熵函数的形式是唯一的。才能保证熵函数的形式是唯一的。信源信源XYXY的符号的符号联合概率联合概率40证明：证明：=1=141例如，例如，甲信源为甲信源为它们的它们的联合信源联合信源是是可计算得可计算得联合信源的联合熵：联合信源的联合熵：H(Z)=H(XY)=log(nm)=log m+log n=H(X)+H(Y)H(Z)=H(XY)=log(nm)=log m+log n=H(X)+H(Y)乙信源为乙信源为426 6、强可加性、强可加性 两个互相关联的信源两个互相关联的信源X X和和Y Y的的联合信源联合信源XYXY的熵等于信源的熵等于信源X X的熵加上在的熵加上在X X已知条件下信源已知条件下信源Y Y的条件熵。的条件熵。H H（XYXY）=H=H（X X）+H+H（Y|XY|X）l证明：证明：设设X X、Y Y的概率分布为的概率分布为 X X、Y Y之间存在关联，用之间存在关联，用条件概率条件概率描述：描述：同时，同时，联合信源联合信源XYXY的各个符号，由的各个符号，由X X、Y Y信源中的符号构成，信源中的符号构成，每个联合符号的每个联合符号的联合概率联合概率为：为：43显然显然则则联合概率联合概率44=1条件熵条件熵条件熵条件熵45l条件熵：条件熵：H H（Y|XY|X）表示信源）表示信源 X X 输出一符号的条件下，输出一符号的条件下，信源信源Y Y再再输出一符号输出一符号所能提供的所能提供的平均信息量。平均信息量。也即：也即：由前面的推导，可得：由前面的推导，可得：467 7、递增性、递增性 若原信源若原信源 X X 中中有一个符号分割成了有一个符号分割成了m m个元素个元素(符号符号)，这，这m m个元素的个元素的概率之和概率之和等于原元素的概率，而其他等于原元素的概率，而其他符号的概率不变，则符号的概率不变，则新信源的熵增加。新信源的熵增加。熵的增加量熵的增加量等于由分割而产生的不确定性量。等于由分割而产生的不确定性量。47#（选讲）#证明证明:可以从可以从熵的定义熵的定义或或强可加性强可加性得出：得出：48因为因为而当而当inin时时p pijij=0=0，所以，所以即得：即得：49递增性的推广递增性的推广l它表示它表示n n个元素的信源熵可以递推成个元素的信源熵可以递推成(n-1)(n-1)个二元信源个二元信源的熵函数的加权和。这样，可使的熵函数的加权和。这样，可使多元信源的熵函数的多元信源的熵函数的计算简化成计算若干个二元信源的熵函数。计算简化成计算若干个二元信源的熵函数。因此，熵因此，熵函数的递增性又可称为递推性。函数的递增性又可称为递推性。50#（选讲）#例例：运用熵函数的递增性（的推广），计算熵函数运用熵函数的递增性（的推广），计算熵函数H(1/3H(1/3，1/31/3，1/61/6，1/6)1/6)的数值。的数值。518 8、极值性、极值性 在离散信源情况下，信源各符号等概率分布时，熵在离散信源情况下，信源各符号等概率分布时，熵值达到最大。值达到最大。等概率分布信源的平均不确定性为最大。这是一个等概率分布信源的平均不确定性为最大。这是一个重要结论，称为重要结论，称为最大离散熵定理。最大离散熵定理。证明：证明：因为对数函数是因为对数函数是型凸函数，型凸函数，满足满足詹森不等式詹森不等式 Elog Y Elog Y log EYlog EY，令，令矢量矢量Y=1/PY=1/P即（即（y yi i=1/=1/p pi i），则有：），则有：=152特例：特例：二进制离散信源。二进制离散信源。该信源符号只有二个，设为该信源符号只有二个，设为“0”0”和和“1”1”。符号输出。符号输出的概率分别为的概率分别为“”和和“1-1-”，即信源的概率空间为：，即信源的概率空间为：H(X)=-H(X)=-loglog (1-1-)log()log(1-1-)=H()=H()即信息熵即信息熵H(x)H(x)是是 的函数。的函数。取值于取值于00，11区间，可画出熵区间，可画出熵函数函数H(H()的曲线来，如右图所的曲线来，如右图所示。示。53 熵函数熵函数H(P)H(P)是概率矢量是概率矢量P P(p(p1 1，p p2 2，p pq q)的的严格严格型凸函数型凸函数(或称或称上凸函数上凸函数)。（因为（因为H(P)H(P)是由具有是由具有严格上凸性严格上凸性的的对数函数对数函数-xlogx-xlogx（二阶导（二阶导数数0 0）的线性组合。）的线性组合。）即：对任意概率矢量即：对任意概率矢量 P P1 1(p(p1 1,p,p2 2,p,pq q)和和 P P2 2 (p(p1 1,p,p2 2,p,pq q)，和任意的和任意的 0 0 1 1，有：，有：HH P P1 1+(1-+(1-)P)P2 2 H(PH(P1 1)+(1-)+(1-)H(P)H(P2 2)因为熵函数具有上凸性，所以熵函数具有因为熵函数具有上凸性，所以熵函数具有极值，极值，其其最大最大值存在。值存在。9 9、上凸性、上凸性54扩展信源的由来：扩展信源的由来：当离散无记忆信源信源发出当离散无记忆信源信源发出固定长度固定长度的的消息序列消息序列时，则得时，则得到到原信源原信源的的扩展信源扩展信源。例如：例如：在电报系统中，若信源输出的是二个符号组成的符号序列，在电报系统中，若信源输出的是二个符号组成的符号序列，此时可认为是一个此时可认为是一个新的信源新的信源，它由四个符号（，它由四个符号（0000，0101，1010，1111）组成，我们把该信源称为）组成，我们把该信源称为二元无记忆信源的二次扩展信源二元无记忆信源的二次扩展信源。更进一步，如果把更进一步，如果把N N个二元符号组成一组，则信源等效成个二元符号组成一组，则信源等效成一个具有一个具有2 2N N个符号的新信源，把它称为个符号的新信源，把它称为二元无记信源的二元无记信源的N N次扩次扩展信源展信源。2.4 2.4 离散无记忆的扩展信源离散无记忆的扩展信源55概念：概念：一般地，对一个一般地，对一个离散无记忆信源离散无记忆信源X X，其样本空间为，其样本空间为aa1 1,a,a2 2,a,aq q ，对它的输出，对它的输出消息序列，消息序列，可用一组可用一组组长度为组长度为N N的序列的序列来表示它。这时，它来表示它。这时，它等效等效成一个成一个新信源。新信源。新信源新信源输出的输出的符号符号是是N N维离散维离散随机矢量随机矢量X=(XX=(X1 1，X X2 2 ,X,XN N)，其中每个分量其中每个分量X Xi i(i(i1,2,N)1,2,N)都是随机变量，它们都都是随机变量，它们都取值于取值于同一信源符号集同一信源符号集，并且分量之间统计独立，则由，并且分量之间统计独立，则由随机随机矢量矢量X X组成的新信源称为组成的新信源称为离散无记忆信源离散无记忆信源X X的的N N次扩展信源。次扩展信源。56单符号离散无记忆信源单符号离散无记忆信源X X的数学模型：的数学模型：lN N次扩展信源次扩展信源与与单符号离散信源单符号离散信源比较，其输出不是单个符号，而是一比较，其输出不是单个符号，而是一串串N N个相互独立的符号序列：个相互独立的符号序列：X X(X(X1 1,X,X2 2,X,XN N)，联合分布密度联合分布密度 P(X)=P(XP(X)=P(X1 1X X2 2XXN N)它们把它们把 X X 等效为一个新信源等效为一个新信源-X X的的N N次扩展信源。次扩展信源。N N次扩展次扩展N N次扩展信源次扩展信源N N次扩展信源的数学模型次扩展信源的数学模型57N N次扩展信源数学模型表示为：次扩展信源数学模型表示为：因为是无记忆的因为是无记忆的(彼此统计独立彼此统计独立)则：则：58性质：性质：离散平稳无记忆离散平稳无记忆N N次扩展信源的次扩展信源的熵熵 H(XH(XN N)=NH(X)=NH(X)其中其中：同理计算式中其余各项，得到：同理计算式中其余各项，得到：H(XH(XN N)=H(X)+H(X)+H(X)=N H(X)=H(X)+H(X)+H(X)=N H(X)证明：证明：分解为分解为N N重求和重求和59一、概念一、概念 在一般情况下在一般情况下，信源在，信源在 t=i 时刻将要发出什么样的符号决定于时刻将要发出什么样的符号决定于两方面：两方面：(1)信源在信源在 t=i 时刻，随机变量时刻，随机变量Xi 取值的取值的概率分布概率分布P(xi)。一般一般 P(xi)P(xj)(2)t=i 时刻时刻以前信源发出的符号以前信源发出的符号。即与即与条件概率条件概率P(xi|xi-1 xi-2)有关有关l平稳随机序列：平稳随机序列：其其统计性质与时间的推移无关统计性质与时间的推移无关，即信源发，即信源发出出符号序列符号序列的概率分布与时间起点无关。的概率分布与时间起点无关。2.5 离散平稳信源 60l一维平稳信源一维平稳信源：若当若当t=i，t=j时时(i,j 是大于是大于1的任意整数的任意整数)，信源输出的随，信源输出的随机序列满足机序列满足一维一维概率分布概率分布时间起点无关时间起点无关条件条件 P(xi)=P(xj)=P(x)l二维平稳信源二维平稳信源：除满足上述一维平稳信源条件外，如果除满足上述一维平稳信源条件外，如果联合概率分布联合概率分布P(xixi+1)也与时间起点无关，即也与时间起点无关，即 P(xixi+1)=P(xjxj+1)(i,j为任意整数且为任意整数且i j)它表示它表示任何时刻，任何时刻，信源信源先后发出二个符号先后发出二个符号的联合概率分的联合概率分布也完全相等。布也完全相等。61l完全平稳信源：完全平稳信源：如果如果各维联合概率分布各维联合概率分布均与均与时间起点时间起点无关，那么信源是完全平稳无关，那么信源是完全平稳的（的（N为任意正整数）。为任意正整数）。由于联合概率与条件概率有以下关系：62平稳信源的特点：平稳信源的特点：l对于平稳信源发出的随机序列，其前后符号依赖的对于平稳信源发出的随机序列，其前后符号依赖的条件概率条件概率均与均与时时间起点间起点无关，只与无关，只与关联长度关联长度N有关。有关。l如果如果某时刻发出什么符号只与前面发出的某时刻发出什么符号只与前面发出的N个符号有关个符号有关，那么由平，那么由平稳性，则稳性，则任何时刻任何时刻它们的依赖关系都是一样的。它们的依赖关系都是一样的。则由前面两个关系，可推知各维则由前面两个关系，可推知各维条件概率条件概率也满足也满足时间起点无关性：时间起点无关性：63三、离散平稳信源的极限熵三、离散平稳信源的极限熵l对于一般平稳有记忆信源，设其概率空间为：对于一般平稳有记忆信源，设其概率空间为：发出的符号序列为发出的符号序列为发出的符号序列为发出的符号序列为(X(X1 1，X X2 2，X XN N，)，假设信源符号之假设信源符号之假设信源符号之假设信源符号之间的间的间的间的依赖长度依赖长度依赖长度依赖长度为为为为N N，且，且，且，且各维概率分布各维概率分布各维概率分布各维概率分布为：为：为：为：简记为简记为64且满足完备集条件，各维概率密度之和皆为且满足完备集条件，各维概率密度之和皆为且满足完备集条件，各维概率密度之和皆为且满足完备集条件，各维概率密度之和皆为1 1：65 已知已知联合概率分布联合概率分布，可得离散平稳信源的一系列，可得离散平稳信源的一系列联合熵联合熵：N N长的信源符号序列中长的信源符号序列中长的信源符号序列中长的信源符号序列中平均每符号携带平均每符号携带平均每符号携带平均每符号携带的信息量为：的信息量为：的信息量为：的信息量为：平均符号熵平均符号熵平均符号熵平均符号熵:信息度量信息度量1平均符号平均符号熵熵66 另一方面，因信源符号之间的另一方面，因信源符号之间的另一方面，因信源符号之间的另一方面，因信源符号之间的依赖关系长度依赖关系长度依赖关系长度依赖关系长度为为为为N,N,所以可以求出已知前面所以可以求出已知前面所以可以求出已知前面所以可以求出已知前面N-1N-1个符号时，后面出现一个符号的个符号时，后面出现一个符号的个符号时，后面出现一个符号的个符号时，后面出现一个符号的平均不确定性平均不确定性平均不确定性平均不确定性。条件熵条件熵条件熵条件熵:若已知前面若已知前面若已知前面若已知前面N N一一1 1个符号，后面出现一个符号的平均不个符号，后面出现一个符号的平均不个符号，后面出现一个符号的平均不个符号，后面出现一个符号的平均不确定性（确定性（确定性（确定性（平均信息量平均信息量平均信息量平均信息量），即得），即得），即得），即得一系列一系列一系列一系列的的的的条件熵条件熵条件熵条件熵：信息度量信息度量2条件熵条件熵67 对离散平稳信源，若对离散平稳信源，若H1(X)，则有：，则有：1)条件熵、平均符号熵都随序列长度条件熵、平均符号熵都随序列长度N的增加是的增加是非递增的非递增的；2)对于任意序列长度对于任意序列长度N，平均符号熵，平均符号熵不小于不小于条件熵；条件熵；3)极限熵极限熵 H 存在，并且等于存在，并且等于序列长度序列长度N无穷大无穷大时的平均符号熵或条时的平均符号熵或条件熵。件熵。对于一般平稳信源，求对于一般平稳信源，求 H 相当困难（相当困难（N取无穷大）。但取无穷大）。但N不很大时有：不很大时有：H HN(X)或或 H H(XN|X1X2XN-1)。离散平稳信源性质总结离散平稳信源性质总结近似计算近似计算68 对对离散二维平稳信源，离散二维平稳信源，一维和二维概率分布确定，且与时间一维和二维概率分布确定，且与时间推移无关。推移无关。对于这样的二维平稳信源，二符号之间的条件概率反映了前对于这样的二维平稳信源，二符号之间的条件概率反映了前面输出某一个符号、后面再输出某一个符号的概率，其输出符号面输出某一个符号、后面再输出某一个符号的概率，其输出符号序列中依赖关系是有限的，所以有：序列中依赖关系是有限的，所以有：u特例