信息论复习资料傅祖芸版本省公共课一等奖全国赛课获奖课件.pptx

信息论与编码信息论与编码计算器1第1页简简 介介 是一门应用概率论、随机过程、数理统计和是一门应用概率论、随机过程、数理统计和近代代数方法，来研究信息传输、提取和处理近代代数方法，来研究信息传输、提取和处理中普通规律学科。中普通规律学科。奠基人：美国数学家香农（奠基人：美国数学家香农（C.E.ShannonC.E.Shannon）19481948年年“通信数学理论通信数学理论”2第2页简简 介介l信息论基本问题信息论基本问题信息度量信息度量l无失真信源编码定理无失真信源编码定理香农第一定理香农第一定理l信道编码定理信道编码定理香农第二定理香农第二定理l信源编码、信道编码信源编码、信道编码3第3页绪绪 论论第第1 1章章4第4页1.1 1.1 信息概念信息概念 5第5页情报：情报：是人们对于某个特定对象所见、所闻、所是人们对于某个特定对象所见、所闻、所了解而产生知识。了解而产生知识。知识：知识：一个含有普遍和概括性质高层次信息一个含有普遍和概括性质高层次信息 ，以实践为基础，经过抽象思维，对客观事物规律以实践为基础，经过抽象思维，对客观事物规律性概括。性概括。消息：消息：用文字、符号、语音、图像等能够被人们用文字、符号、语音、图像等能够被人们感觉器官所感知形式，把客观物质运动和主观思感觉器官所感知形式，把客观物质运动和主观思维活动状态表示出来。维活动状态表示出来。几个常见概念几个常见概念6第6页香农信息度量香农信息度量（1 1）样本空间）样本空间 某事物各种可能出现不一样状态。某事物各种可能出现不一样状态。（2 2）概率测度）概率测度 对每一个可能选择消息指定一个概率。对每一个可能选择消息指定一个概率。（3 3）概率空间）概率空间 l先验概率先验概率p p(x xi i)：选择符号选择符号x xi i作为消息概率。作为消息概率。样本空间概率测度7第7页l例：例：气象预报气象预报 甲甲乙乙l“甲地晴甲地晴”比比“乙地晴乙地晴”不确定性小。不确定性小。l某一事物状态出现概率越小，其不确定性越大。某某一事物状态出现概率越小，其不确定性越大。某一事物状态出现概率靠近于一事物状态出现概率靠近于1,1,即预料中必定会出现即预料中必定会出现事件，那它不确定性就靠近于零。事件，那它不确定性就靠近于零。8第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第9页信息特征信息特征信息是信息是物质存在普遍属性物质存在普遍属性，信息和能量、物质要求了事，信息和能量、物质要求了事物物功效和性能功效和性能；接收者在收到信息之前，对它内容是不知道，所以，信接收者在收到信息之前，对它内容是不知道，所以，信息是息是新知识、新内容新知识、新内容；它使认识主体对某一事物未知性；它使认识主体对某一事物未知性或不确定性降低有用知识；或不确定性降低有用知识；信息存在含有信息存在含有普遍性、无限性、动态性、时效性普遍性、无限性、动态性、时效性和和相对相对独立性独立性；信息能够产生，也能够消失，同时信息能够被信息能够产生，也能够消失，同时信息能够被传递、转传递、转换、扩散、复制、贮存、分割换、扩散、复制、贮存、分割，含有，含有可共享性可共享性；信息是信息是能够量度能够量度，信息量有多少差异。，信息量有多少差异。10第10页1.2 1.2 信息论研究对信息论研究对象、目标和内容象、目标和内容11第11页研究对象：通信系统模型研究对象：通信系统模型信信道道信信源源信源编码信源编码加密加密信信道道编编码码干干 扰扰 源源信信宿宿信源解码信源解码解密解密信信道道解解码码加密密钥解密密钥12第12页l信源：信源：发送消息源发送消息源l离散信源离散信源l模拟信源模拟信源信源是信息论主要研究对象之一信源是信息论主要研究对象之一.我们我们不探讨信源不探讨信源内部结构和机理内部结构和机理，而关注，而关注信源输出。信源输出。重点讨论其重点讨论其描述方法及性质描述方法及性质。l信宿：信宿：信息归宿之意，亦即收信者或用户，信息归宿之意，亦即收信者或用户，是信息传送终点或目标地。是信息传送终点或目标地。l信道：信道：传输信息传输信息物理媒介物理媒介。信源、信道、信宿信源、信道、信宿13第13页l信源编码器信源编码器l经过信源编码能够压缩信源冗余度经过信源编码能够压缩信源冗余度,以提升通信以提升通信系统传输消息效率。系统传输消息效率。l信源编码器分为两类信源编码器分为两类l无失真信源编码无失真信源编码：适合用于离散信源或数字信号；：适合用于离散信源或数字信号；l限失真信源编码限失真信源编码：用于连续信源或模拟信号：用于连续信源或模拟信号,如如语音、图像等信号数字处理。语音、图像等信号数字处理。信源编码器与译码器信源编码器与译码器l信源编码器主要指标信源编码器主要指标l是它是它编码效率编码效率。普通来说，效率越高，编译码器。普通来说，效率越高，编译码器代价也将越大。代价也将越大。l信源译码器信源译码器l把信道译码器输出变换成信宿所需消息形式，相把信道译码器输出变换成信宿所需消息形式，相当于当于信源编码器逆过程信源编码器逆过程。14第14页信道编码器与译码器信道编码器与译码器l信道编码信道编码l主要作用是提升信息传送主要作用是提升信息传送可靠性可靠性。l信道编码器作用信道编码器作用l在信源编码器输出代码组上有目标地增加一些监督码在信源编码器输出代码组上有目标地增加一些监督码元元,使之含有检错或纠错能力。使之含有检错或纠错能力。l信道编码主要方法信道编码主要方法l增大码率或频带增大码率或频带,即增大所需信道容量。这恰与信源编即增大所需信道容量。这恰与信源编码相反。码相反。l信道译码器作用信道译码器作用l含有检错或纠错功效含有检错或纠错功效,它能将落在其检错或纠错范围内它能将落在其检错或纠错范围内错传码元检出或纠正错传码元检出或纠正,以提升传输消息可靠性。以提升传输消息可靠性。15第15页1.3 1.3 信息论形成和发展信息论形成和发展16第16页l 信息论是在长久通信工程实践和理论研究基础上发展起来。l简 史l当代信息论是从20世纪代奈奎斯特和哈特莱工作开始：l1924年奈奎斯特(Nyquist)“影响电报速率原因确实定”。l1928年哈特莱(Hartley)“信息传输”一文研究了通信系统传输信息能力，并给出了信息度量方法。信息论形成信息论形成17第17页l19461946年年柯切尔尼柯夫柯切尔尼柯夫学位论文学位论文“起伏噪声下潜在抗干扰理起伏噪声下潜在抗干扰理论论”，依据最小错误概率准则和最小均方误差准则研究了依据最小错误概率准则和最小均方误差准则研究了离散和连续信道最正确接收问题。离散和连续信道最正确接收问题。l19481948年年香农香农权威性长文权威性长文“通信数学理论通信数学理论”，讨论了信源和讨论了信源和信道特征，信道特征，19491949年香农年香农“噪声中通信噪声中通信”，两论文奠定了当两论文奠定了当代信息论理论基础。代信息论理论基础。l今后，在基本理论和实际应用方面，信息论都得到了巨大今后，在基本理论和实际应用方面，信息论都得到了巨大发展。发展。18第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第19页信源信源 产生产生消息消息或或消息序列消息序列源。源。消息消息携带信息，是携带信息，是信息详细形式。信息详细形式。描述方法描述方法 通信过程中，信源发出何种消息是通信过程中，信源发出何种消息是不确定不确定、是是随机。随机。所以，信源可用所以，信源可用随机变量、随机矢量随机变量、随机矢量或或随机随机过程过程（或（或样本空间样本空间及其及其概率测度概率测度）来描述。）来描述。不一样信源依据其输出消息不一样不一样信源依据其输出消息不一样随机性质随机性质进行分类。进行分类。2.1 2.1 信源数学模型及分类信源数学模型及分类20第20页1 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）离散信源）离散信源21第21页1 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、随机矢量描述信源、随机矢量描述信源22第22页2 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第23页信源信源X X各输出各输出X Xi i间统计独立、且取值同一符号集间统计独立、且取值同一符号集A A。该信源。该信源输出输出N N维维随机矢量随机矢量X X为为离散无记忆信源离散无记忆信源X XN 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为为离散无记忆信源：离散无记忆信源：24第24页4 4）有记忆信源）有记忆信源 信源在不一样时刻发出信源在不一样时刻发出符号之间是相互依赖，符号之间是相互依赖，即信源输出即信源输出随随机序列机序列X X中，各随机变量中，各随机变量Xi之间相互依赖。之间相互依赖。须使用随机矢量须使用随机矢量联合概率分布联合概率分布和和条件概率分布条件概率分布来说明它们来说明它们之间关联关系。之间关联关系。例：汉字组成汉字序列中，只有依据汉字语法、习惯用语、例：汉字组成汉字序列中，只有依据汉字语法、习惯用语、修辞制约和表示实际意义制约所组成汉字序列才是有意义汉字修辞制约和表示实际意义制约所组成汉字序列才是有意义汉字句子或文章。所以，在汉字序列中前后文字出现是有依赖，是句子或文章。所以，在汉字序列中前后文字出现是有依赖，是彼此相关。彼此相关。25第25页5 5）m m阶马尔可夫信源（非平稳信源）阶马尔可夫信源（非平稳信源）不一样时刻发出符号间依赖关系不一样时刻发出符号间依赖关系 记忆信源记忆长度为记忆信源记忆长度为m+1时，称这种有记忆信源为时，称这种有记忆信源为m阶马阶马尔可夫信源。尔可夫信源。若上述条件概率与时间起点若上述条件概率与时间起点 i 无关，信源输出符号无关，信源输出符号序列可看成为时齐马尔可夫链，则此信源称为序列可看成为时齐马尔可夫链，则此信源称为时齐马尔时齐马尔可夫信源。可夫信源。26第26页2.2 2.2 离散信源信息熵离散信源信息熵 基本离散信源：基本离散信源：输出输出单符号单符号消息，且这些消息间两两互不相容。用消息，且这些消息间两两互不相容。用一维随机变量一维随机变量X来描述信源输出，其数学模型可抽象为来描述信源输出，其数学模型可抽象为:问题：问题：问题：问题：这么信源能输出多少信息这么信源能输出多少信息这么信源能输出多少信息这么信源能输出多少信息?每个消息出现携带多少信息量每个消息出现携带多少信息量每个消息出现携带多少信息量每个消息出现携带多少信息量?27第27页信息度量信息度量l关键点：关键点：l信息度量（信息量）和信息度量（信息量）和不确定性消除不确定性消除程度相关，程度相关，消除不确定性消除不确定性取得信息量；取得信息量；l不确定性就是随机性，能够用概率论和随机过程来测度；不确定性就是随机性，能够用概率论和随机过程来测度；l推论：推论：l概率小概率小 信息量大，即信息量是信息量大，即信息量是概率单调递减函数；概率单调递减函数；l信息量应该含有信息量应该含有可加性；可加性；l信息量计算公式为（香农（自）信息量度量）：信息量计算公式为（香农（自）信息量度量）：28第28页2.1.1 2.1.1 自信息自信息 设离散信源设离散信源X概率空间为：概率空间为：I(aI(ai i)代表两种代表两种含义：含义：（1）当事件当事件ai发生以前，表示事件发生以前，表示事件ai发生发生不确定性不确定性（2）当事件）当事件ai发生以后，表示事件发生以后，表示事件ai所提供所提供信息量信息量自信息量：自信息量：事件事件ai发生所含有信息量发生所含有信息量29第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第30页收信者收信者收到某消息收到某消息取得信息量取得信息量 不确定性降低量不确定性降低量 (收到此消息前关于某事件不确定性收到此消息前关于某事件不确定性)-(-(收到此消息后关于某事件不确定性收到此消息后关于某事件不确定性)通信实质？通信实质？即：传递信息，消除不确定性。即：传递信息，消除不确定性。即：传递信息，消除不确定性。即：传递信息，消除不确定性。31第31页2.2.2 2.2.2 信息熵信息熵l对对一一个个信信源源发发出出不不一一样样消消息息所所含含有有信信息息量量也也不不一一样样。所所以以自自信信息息I(aI(ai i)是是一一个个随随机机变变量量，不不能能用用它它来来作作为为整整个个信信源源信息测度。信息测度。l信息熵：信息熵：自信息数学期望，自信息数学期望，平均自信息量平均自信息量H Hr r(X)(X)：r r进制单位进制单位/符号符号32第32页熵含义熵含义l熵是熵是从整个集合统计特征从整个集合统计特征来考虑，它从平均意义上来考虑，它从平均意义上来表征信源总体特征。来表征信源总体特征。l信源输出前，信源输出前，熵熵H(X)H(X)表示信源表示信源平均不确定性；平均不确定性；l信源输出后，信源输出后，熵熵H(X)H(X)表示每个消息表示每个消息平均信息量；平均信息量；l信息熵信息熵H(X)H(X)表征了变量表征了变量X X随机性。随机性。33第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 qq-1q-1元函元函数数(独立变量只有独立变量只有q-1q-1元元)。则。则 H(X)H(X)可写成：可写成：34第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第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 中和式满足中和式满足交换率交换率；熵只与随机变量熵只与随机变量总体统计特征总体统计特征相关。相关。例子：例子：36第36页2 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。由罗。由罗比塔法则：比塔法则：所以所以37第37页3 3、非负性：、非负性：H(P)H(P)0 0l说明：说明：l随机变量随机变量X X概率分充满足概率分充满足0 0p pi i1 1，对数函数底大于，对数函数底大于1 1时，时，loglog(p(pi i)0 0，-p-pi ilog(plog(pi i)0 0，即得熵为正值。只有当随，即得熵为正值。只有当随机变量是一确知量时熵才等于零。机变量是一确知量时熵才等于零。l这种非负性适当于离散信源熵，对连续信源来说这一性这种非负性适当于离散信源熵，对连续信源来说这一性质并不存在（基于质并不存在（基于差熵、相对熵差熵、相对熵概念）。概念）。v非负性表达信息是非负。非负性表达信息是非负。非负性表达信息是非负。非负性表达信息是非负。38第38页4 4、扩展性、扩展性l说明：说明：信源信源符号数增多符号数增多时，若这些取值对应概率很小时，若这些取值对应概率很小(靠近于零靠近于零)，则信源熵不变。，则信源熵不变。所以，上式成立。所以，上式成立。因为因为趋于趋于0 039第39页5 5、可加性、可加性 统计独立信源统计独立信源X X和和Y Y联合信源联合信源XYXY熵熵等于信源等于信源X X和和Y Y各各自熵之和：自熵之和：H(XY)=H(X)+H(Y)H(XY)=H(X)+H(Y)即：即：另外：可加性是熵函数一个主要特征，正因含有可加性，另外：可加性是熵函数一个主要特征，正因含有可加性，才能确保熵函数形式是唯一。才能确保熵函数形式是唯一。信源信源XYXY符号符号联合概率联合概率40第40页证实：证实：=1=141第41页比如，比如，甲信源为甲信源为它们它们联合信源联合信源是是可计算得可计算得联合信源联合熵：联合信源联合熵：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)乙信源为乙信源为42第42页6 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第43页显然显然则则联合概率联合概率44第44页=1条件熵条件熵条件熵条件熵45第45页l条件熵：条件熵：H H（Y|XY|X）表示信源）表示信源 X X 输出一符号条件下，信输出一符号条件下，信源源Y Y再再输出一符号输出一符号所能提供所能提供平均信息量。平均信息量。也即：也即：由前面推导，可得：由前面推导，可得：46第46页7 7、递增性、递增性 若原信源若原信源 X X 中中有一个符号分割成了有一个符号分割成了m m个元素个元素(符号符号)，这，这m m个元素个元素概率之和概率之和等于原元素概率，而其它符号等于原元素概率，而其它符号概率不变，则概率不变，则新信源熵增加。新信源熵增加。熵增加量熵增加量等于由分割而产生不确定性量。等于由分割而产生不确定性量。47第47页#（选讲）#证实证实:能够从能够从熵定义熵定义或或强可加性强可加性得出：得出：48第48页因为因为而当而当inin时时p pijij=0=0，所以，所以即得：即得：49第49页递增性推广递增性推广l它表示它表示n n个元素信源熵能够递推成个元素信源熵能够递推成(n-1)(n-1)个二元信源熵个二元信源熵函数加权和。这么，可使函数加权和。这么，可使多元信源熵函数计算简化成多元信源熵函数计算简化成计算若干个二元信源熵函数。计算若干个二元信源熵函数。所以，熵函数递增性又所以，熵函数递增性又可称为递推性。可称为递推性。50第50页#（选讲）#例例：利用熵函数递增性（推广），计算熵函数利用熵函数递增性（推广），计算熵函数H(1/3H(1/3，1/31/3，1/61/6，1/6)1/6)数值。数值。51第51页8 8、极值性、极值性 在离散信源情况下，信源各符号等概率分布时，熵在离散信源情况下，信源各符号等概率分布时，熵值到达最大。值到达最大。等概率分布信源平均不确定性为最大。这是一个主等概率分布信源平均不确定性为最大。这是一个主要结论，称为要结论，称为最大离散熵定理。最大离散熵定理。证实：证实：因为对数函数是因为对数函数是型凸函数，型凸函数，满足满足詹森不等式詹森不等式 Elog Y Elog Y log EYlog EY，令，令矢量矢量Y=1/PY=1/P即（即（y yi i=1/=1/p pi i），则有：），则有：=152第52页特例：特例：二进制离散信源。二进制离散信源。该信源符号只有二个，设为该信源符号只有二个，设为“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第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第54页扩展信源由来：扩展信源由来：当离散无记忆信源信源发出当离散无记忆信源信源发出固定长度固定长度消息序列消息序列时，则得到时，则得到原信源原信源扩展信源扩展信源。比如：比如：在电报系统中，若信源输出是二个符号组成符号序列，此在电报系统中，若信源输出是二个符号组成符号序列，此时可认为是一个时可认为是一个新信源新信源，它由四个符号（，它由四个符号（0000，0101，1010，1111）组）组成，我们把该信源称为成，我们把该信源称为二元无记忆信源二次扩展信源二元无记忆信源二次扩展信源。更深入，假如把更深入，假如把N N个二元符号组成一组，则信源等效成一个二元符号组成一组，则信源等效成一个含有个含有2 2N N个符号新信源，把它称为个符号新信源，把它称为二元无记信源二元无记信源N N次扩展信源次扩展信源。2.4 2.4 离散无记忆扩展信源离散无记忆扩展信源55第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 XN N次扩展信源。次扩展信源。56第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 XN N次扩展信源。次扩展信源。N N次扩展次扩展N N次扩展信源次扩展信源N N次扩展信源数学模型次扩展信源数学模型57第57页N N次扩展信源数学模型表示为：次扩展信源数学模型表示为：因为是无记忆因为是无记忆(彼此统计独立彼此统计独立)则：则：58第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第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 离散平稳信源 60第60页l一维平稳信源一维平稳信源：若当若当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)它表示它表示任何时刻，任何时刻，信源信源先后发出二个符号先后发出二个符号联合概率分布联合概率分布也完全相等。也完全相等。61第61页l完全平稳信源：完全平稳信源：假如假如各维联合概率分布各维联合概率分布均与均与时间起点时间起点无关，那么信源是完全平稳无关，那么信源是完全平稳（N为任意正整数）。为任意正整数）。因为联合概率与条件概率有以下关系：62第62页平稳信源特点：平稳信源特点：l对于平稳信源发出随机序列，其前后符号依赖对于平稳信源发出随机序列，其前后符号依赖条件概率条件概率均与均与时间起时间起点点无关，只与无关，只与关联长度关联长度N相关。相关。l假如假如某时刻发出什么符号只与前面发出某时刻发出什么符号只与前面发出N个符号相关个符号相关，那么由平稳，那么由平稳性，则性，则任何时刻任何时刻它们依赖关系都是一样。它们依赖关系都是一样。则由前面两个关系，可推知各维则由前面两个关系，可推知各维条件概率条件概率也满足也满足时间起点无关性：时间起点无关性：63第63页三、离散平稳信源极限熵三、离散平稳信源极限熵l对于普通平稳有记忆信源，设其概率空间为：对于普通平稳有记忆信源，设其概率空间为：发出符号序列为发出符号序列为发出符号序列为发出符号序列为(X(X1 1，X X2 2，X XN N，)，假设信源符号之间假设信源符号之间假设信源符号之间假设信源符号之间依赖长度依赖长度依赖长度依赖长度为为为为N N，且，且，且，且各维概率分布各维概率分布各维概率分布各维概率分布为：为：为：为：简记为简记为64第64页且满足完备集条件，各维概率密度之和皆为且满足完备集条件，各维概率密度之和皆为且满足完备集条件，各维概率密度之和皆为且满足完备集条件，各维概率密度之和皆为1 1：65第65页 已知已知联合概率分布联合概率分布，可得离散平稳信源一系列，可得离散平稳信源一系列联合熵联合熵：N N长信源符号序列中长信源符号序列中长信源符号序列中长信源符号序列中平均每符号携带平均每符号携带平均每符号携带平均每符号携带信息量为：信息量为：信息量为：信息量为：平均符号熵平均符号熵平均符号熵平均符号熵:信息度量信息度量1平均符号平均符号熵熵66第66页 其次，因信源符号之间依赖关系长度为N,所以可以求出已知前面N-1个符号时，后面出现一个符号平均不确定性。条件熵:若已知前面N一1个符号，后面出现一个符号平均不确定性（平均信息量），即得一系列条件熵：信息度量信息度量2条件熵条件熵67第67页 对离散平稳信源，若对离散平稳信源，若H1(X)，则有：，则有：1)条件熵、平均符号熵都随序列长度条件熵、平均符号熵都随序列长度N增加是增加是非递增非递增；2)对于任意序列长度对于任意序列长度N，平均符号熵，平均符号熵大于大于条件熵；条件熵；3)极限熵极限熵 H 存在，而且等于存在，而且等于序列长度序列长度N无穷大无穷大时平均符号熵或条件时平均符号熵或条件熵。熵。对于普通平稳信源，求对于普通平稳信源，求 H 相当困难（相当困难（N取无穷大）。但取无穷大）。但N不很大时有：不很大时有：H HN(X)或或 H H(XN|X1X2XN-1)。离散平稳信源性质总结离散平稳信源性质总结近似计算近似计算68第68页 对对离散二维平稳信源，离散二维平稳信源，一维和二维概率分布确定，且与时间一维和二维概率分布确定，且与时间推移无关。推移无关。对于这么二维平稳信源，二符号之间条件概率反应了前面输对于这么二维平稳信源，二符号之间条件概率反应了前面输出某一个符号、后面再输出某一个符号概率，其输出符号序列中出某一个符号、后面再输出某一个符号概率，其输出符号序列中依赖关系是有限，所以有：依赖关系是有限，所以有：u特例分析：离散二维平稳信源特例分析：离散二维平稳信源69第69页联合概率满足完备性联合概率满足完备性边缘分布概率边缘分布概率另外，可从联合概率得到另外，可从联合概率得到边缘分布概率边缘分布概率：则则条件熵条件熵表示为：表示为：70第70页此时：此时：l可见：可见：离散二维平稳信源离散二维平稳信源极限熵极限熵，等于条件熵，等于条件熵 H(XH(X2 2|X|X1 1)。N-2维边缘概率维边缘概率71第71页推广：推广：普通情况，假如平稳信源记忆长度有限，也即某时刻输出什普通情况，假如平稳信源记忆长度有限，也即某时刻输出什么符号么符号只与前面只与前面m个符号个符号相关。相关。此时，则可用此时，则可用有限记忆长度有限记忆长度条件熵条件熵来测度离散平稳信源来测度离散平稳信源极限熵极限熵：72第72页第第3 3章章 离散信道及其信道容量离散信道及其信道容量 第一节第一节 信道数学模型及分类信道数学模型及分类第二节第二节 平均互信息平均互信息第三节第三节 平均互信息特征平均互信息特征第四节第四节 信道容量及其计算方法信道容量及其计算方法 第五节第五节 离散无记忆扩展信道及其信道容量离散无记忆扩展信道及其信道容量第六节第六节 信源与信道匹配信源与信道匹配73第73页u信道任务：信道任务：以以信号方式信号方式传输信息和存放信息。传输信息和存放信息。u研究内容：研究内容：信道中能够传送或存放最大信息量，即信道容量。信道中能够传送或存放最大信息量，即信道容量。74第74页3.1 信道数学模型和分类 数字通信系统普通模型数字通信系统普通模型75第75页二、离散信道数学模型 条件概率条件概率 P(y|x)P(y|x)描述了输入信号和输出信号之间统计依赖描述了