《信息论简述精.ppt》由会员分享，可在线阅读，更多相关《信息论简述精.ppt（97页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、信息论简述第1页，本讲稿共97页第第1章章 信息论基础信息论基础 内容提要信息论是应用近代概率统计方法研究信息传输、交换、存储和处理的一门学科，也是源于通信实践发展起来的一门新兴应用科学。本章首先引出信息的概念，简述信息传输系统模型的各个组成部分，进而讨论离散信源和离散信道的数学模型，简单介绍几种常见的离散信源和离散信道。第2页，本讲稿共97页 1948年香农在年香农在Bell System Technical Journal上发表了上发表了A Mathematical Theory of Communication。通信的基本问题是在彼时彼地精确地通信的基本问题是在彼时彼地精确地或近似地再现
2、此时此地发出的消息。或近似地再现此时此地发出的消息。第3页，本讲稿共97页1.1 1.1 信息的概念信息的概念物质、能量和信息是构成客观世界的三大要素。信息是物质和能量在空间和时间上分布的不均匀程度，或者说信息是关于事物运动的状态和规律。通信系统中形式上传输的是消息，实质上传输的是信息，消息中包含信息，消息是信息的载体。信息论信息论是研究信息的基本性质及度量方法，研究信息的获取、传输、存储和处理的一般规律的科学。第4页，本讲稿共97页l信息：信息是任何随机事件发生后所包含的内容（信息量特点）l消息：消息是信息的载体（互联网上的文字与图像）l信号：信号是消息的载体（调制原因）三者之间的关系三者之
3、间的关系:信息不等于消息，消息中包含信息，信息不等于消息，消息中包含信息，是信息的载体，信号携带消息，是消息的载体是信息的载体，信号携带消息，是消息的载体1.1 1.1 信息的概念信息的概念第5页，本讲稿共97页 20世世纪纪20年年代代奈奈奎奎斯斯特特（Nyquist，H）和和哈哈特特莱莱（Hartley，LVR）提出了信息的定义）提出了信息的定义 19241924年奈奎斯特解释了信号带宽和信息速率之间的关系年奈奎斯特解释了信号带宽和信息速率之间的关系 19281928哈哈特特莱莱最最早早研研究究了了通通信信系系统统传传输输信信息息的的能能力力，给给出出了了信信息息度量方法度量方法 1936
4、1936年年阿阿姆姆斯斯特特朗朗（ArmstrongArmstrong）提提出出了了增增大大带带宽宽可可以以使使抗抗干干扰扰能能力力加强加强 1941194119441944年年香香农农对对通通信信和和密密码码进进行行深深人人研研究究，用用概概率率论论的的方方法法研研究究通通信信系系统统，揭揭示示了了通通信信系系统统传传递递的的对对象象就就是是信信息息，并并对对信信息息给给以以科科学学的的定定量量描描述述，提提出出了了信信息息熵熵的的概概念念。指指出出通通信信系系统统的的中中心心问问题题是是在在噪噪声声下下如如何何有有效效而而可可靠靠地地传传送送信信息息以以及及实实现现这这一一目目标标的的主主
5、要要方方法法是是编编码等。香农因此成为信息论的奠基人。码等。香农因此成为信息论的奠基人。1.2 1.2 信息论与编码技术的发展简史信息论与编码技术的发展简史第6页，本讲稿共97页 5050年代信息论在学术界引起了巨大的反响年代信息论在学术界引起了巨大的反响 6060年年代代信信道道编编码码技技术术有有较较大大进进展展，使使它它成成为为信信息息论论的的又又一一重重要要分分支支；信信源源编编码码的的研研究究落落后后于于信信道道编编码码。香香农农 19591959年年的的文文章章(Coding(Coding theorems theorems for for a a discrete discret
6、e source source with with a a fidelity fidelity criterion)criterion)系系统统地地提提出出了了信信息息率率失失真真理理论论，它它是是数数据据压压缩缩的的数数学学基基础础，为各种信源编码的研究奠定了基础为各种信源编码的研究奠定了基础 到到7070年年代代，有有关关信信息息论论的的研研究究，从从点点与与点点间间的的单单用用户户通通信信推推广广到到多多用用户户系系统统的的研研究究。19721972年年盖盖弗弗（CaerCaer）发发表表了了有有关关广广播播信信道道的的研研究究，以以后后陆陆续续有有关关于于多多接接入入信信道道和和广广播
7、播信信道道模模型型的的研研究究，但但由由于于这这些些问问题题比比较较难难，到到目目前前为为止止，多多用用户户信信息息论论研研究究得得不不多多，还还有有许许多多尚尚待待解决的课题。解决的课题。第7页，本讲稿共97页对于信息论的研究，一般划分为三个不同的范畴：广义信息论，包括信息论在自然和社会中的新的应用，如模式识别、机器翻译、自学习自组织系统、心理学、生物学、经济学、社会学等一切与信息问题有关的领域。实用信息论，研究信息传输和处理问题，也就是狭义信息论方法在调制解调、编码译码以及检测理论等领域的应用。狭义信息论，即通信的数学理论，主要研究狭义信息的度量方法，研究各种信源、信道的描述和信源、信道的
8、编码定理。第8页，本讲稿共97页1.3 1.3 信息传输系统信息传输系统 通信的基本问题是在彼时彼地精确地或近似地再现此时此地发出的消息。各种通信系统，一般可概括为图1.1所示的统计模型：干干扰扰源源 信信道道信道译码器信道译码器信道编码器信道编码器信源译码器信源译码器信源编码器信源编码器信宿信宿信源信源等效信源等效信宿等效干扰信道图图1-1 信息传输系统模型信息传输系统模型 第9页，本讲稿共97页这个模型包括以下五个部分：3.信道信道 信道是信息传输和存储的媒介。4.译码器译码器 译码是编码的逆变换，分为信道译码和信源译码。5.信宿信宿 信宿是消息的接收者。2.编码器编码器 编码器是将消息变
9、成适合于信道传送的信号的设备。1.信源信源 信源是产生消息的源。编码器信源编码器，提高传输效率信道编码器，提高传输可靠性第10页，本讲稿共97页1.4 1.4 香农信息的定义香农信息的定义 三个基本概念l样本空间:l概率测度:l概率空间:对于离散情况下概率空间第11页，本讲稿共97页1.先验概率：表示选择符号作为消息的概率2.香农信息量(自信息量)：（图像）3.后验概率：表示接受端收到的消息为发送端收到的消息是4.互信息（收信者获得的信息量）：2.香农信息量：（图像）补充例题补充例题第12页，本讲稿共97页1.31.3 离散信源及其数学模型离散信源及其数学模型 信源是产生消息的源，根据X的不同
10、情况，信源可分为以下类型：根据信源的统计特性，离散信源又分为两种：离散信源离散信源 消息集X为离散集合。波形信源波形信源 时间连续的信源。连续信源连续信源 时间离散而空间连续的信源。无记忆信源无记忆信源 X的各时刻取值相互独立。有记忆信源有记忆信源 X的各时刻取值互相有关联。第13页，本讲稿共97页1.3.1 离散无记忆信源离散无记忆信源 离散无记忆信源离散无记忆信源(Discrete Memoryless Source，简记为DMS)输出的是单个符号的消息，不同时刻发出的符号之间彼此统计独立，而且符号集中的符号数目是有限的或可数的。离散无记忆信源的数学模型为离散型的概率空间，即：p(ai)：
11、信源输出符号消息ai的先验概率;满足：0 p(ai)1，1 i n 第14页，本讲稿共97页l联合自信息量联合自信息量:l联合熵联合熵 满足：0 p(aibj)1，1 i n,1jm,第15页，本讲稿共97页 2.1 单符号离散信源 四、互信息量和条件互信息量四、互信息量和条件互信息量 互信息量的概念互信息量的概念在通信系统中，发送端发出的信息经有噪信道后，在接收在通信系统中，发送端发出的信息经有噪信道后，在接收端收到的信息量的多少要用端收到的信息量的多少要用互信息量互信息量来描述。来描述。q设设X X为信源发出的离散消息集合；为信源发出的离散消息集合；Y Y为信宿收到的离散消为信宿收到的离散
12、消息集合；息集合；q信源发出的消息，经过有噪声的信道传递到信宿信源发出的消息，经过有噪声的信道传递到信宿；第16页，本讲稿共97页 其间信源其间信源X X和信宿和信宿Y Y的数学模型为：的数学模型为：在系统中，在系统中，q若信道是无噪的，收到信息若信道是无噪的，收到信息b bj j后，即可获得信息量后，即可获得信息量I(aI(aj j)。q若信道存在噪声，在接收端收到若信道存在噪声，在接收端收到b bj j后后重新估计重新估计信源发出的各信源发出的各个消息个消息p(ap(ai ibbj j)。我们称之为。我们称之为后验概率后验概率。0p(ai)1p(ai)=10p(bj)1p(bj)=1第17
13、页，本讲稿共97页因此，我们称：因此，我们称：n先验概率：信源发出消息先验概率：信源发出消息ai的概率的概率P(ai)。n后验概率：信宿收到消息后验概率：信宿收到消息bj后后,推测信源发出推测信源发出ai 的概的概率率，即条件概率即条件概率p(ai bj)。互信息量的定义互信息量的定义 ai的后验概率与先验概率之比的对数为的后验概率与先验概率之比的对数为bj对对ai的互信息量。的互信息量。用用I(ai;bj)表示。表示。互信息量等于自信息量减去条件自信息量互信息量等于自信息量减去条件自信息量第18页，本讲稿共97页v互信息有两方面的含义：互信息有两方面的含义：v表示事件表示事件bj出现前后关于
14、事件出现前后关于事件ai的不确定性减少的的不确定性减少的量；量；v事件事件bj出现以后信宿获得的关于事件出现以后信宿获得的关于事件ai的信息量。的信息量。v对互信息量的理解对互信息量的理解 观察者站在输出端观察者站在输出端v I(ai;bj)=logp(ai)logp(ai|bj)=I(ai)I(ai|bj)vI(ai)：在在 bj 一无所知的情况下一无所知的情况下 ai 存在的不确定度；存在的不确定度；vI(ai|bj)：收到收到 bj 后对后对 ai 仍然存在的不确定度；仍然存在的不确定度；vI(ai;bj)：收到收到 bj 前和收到前和收到 bj 后后不确定度被消除不确定度被消除的部分的
15、部分获得信息量获得信息量信道信道aibj第19页，本讲稿共97页观察者站在输入端观察者站在输入端qI(bj;ai)=logp(bj)logp(bj|ai)=I(bj)I(bj|ai)q 观察者得知输入端发出观察者得知输入端发出 ai 前、后对输出端出现前、后对输出端出现 bj 的不确定度的差。的不确定度的差。信道信道aibj第20页，本讲稿共97页v观察者站在通信系统总体立场上观察者站在通信系统总体立场上v互信息等于通信前后不确定度的差值互信息等于通信前后不确定度的差值n通信前：通信前：X和和Y之间没有任何关系，即之间没有任何关系，即X、Y统计独立。统计独立。即即 p(xi yj)=p(xi)
16、p(yj)，先验不确定度，先验不确定度n 通信后：通信后：p(xi yj)=p(xi)p(yj|xi)=p(yj)p(xi|yj)，后验，后验 不确定度不确定度第21页，本讲稿共97页 互信息量的性质互信息量的性质1)互信息的对称性互信息的对称性2)互信息可为零互信息可为零 物理含义：系统中干扰极大物理含义：系统中干扰极大3)互信息可为正值或负值互信息可为正值或负值4)任何两个事件之间的互信息不可能大于其中任一事任何两个事件之间的互信息不可能大于其中任一事件的自信息件的自信息信息量的丢失，不确定性增加第22页，本讲稿共97页 条件互信息量条件互信息量定义：定义：联合集联合集XYZ中，在给定中，
17、在给定ck的条件下的条件下ai与与bj之间的之间的互信息量定义为条件互信息量：互信息量定义为条件互信息量：在在XYZ联合集上，还有联合集上，还有ai与与bjck之间的互信息量之间的互信息量第23页，本讲稿共97页由前式可得：由前式可得：此外，还有：此外，还有：将上式两边相加有：将上式两边相加有：第24页，本讲稿共97页根据互易性有：根据互易性有：第25页，本讲稿共97页例：例：有一信源有一信源U包含包含8个消息个消息07，为了便于在二进制，为了便于在二进制信道上传送，将它们编为三位二进码，信源的先验信道上传送，将它们编为三位二进码，信源的先验概率及相应的代码如下：概率及相应的代码如下：试求：试
18、求：填上表格中的后三列填上表格中的后三列 x0与各消息的互信息量与各消息的互信息量 在收到（给定）在收到（给定）x0条件下，条件下，y1与各消息的互与各消息的互 信息量。信息量。在收到（给定）在收到（给定）x0y1条件下，条件下，z1与与U3消息的消息的互信息量互信息量.收到整个代码组收到整个代码组x0y1z1出现后提供的有关消出现后提供的有关消息息U3的互信息量。的互信息量。第26页，本讲稿共97页信源消息信源消息二进制代码二进制代码先验先验概率概率收到收到0后的后的后验后验概率概率收到收到01后的后的后验概率后验概率收到收到011后的后的后验概率后验概率0（U0）000（x0y0z0)1/
19、41（U1）001（x0y0z1)1/42（U2）010（x0y1z0)1/83（U3）011（x0y1z1)1/84（U4）100（x1y0z0)1/165（U5）101（x1y0z1)1/166（U6）110（x1y1z0)1/167（U7）111（x1y1z1)1/16第27页，本讲稿共97页解：解：收到第一个收到第一个0(x0)后后U0U7的后验概率：的后验概率：第28页，本讲稿共97页信源消息信源消息二进制代码二进制代码先验先验概率概率收到收到0后后的后验的后验概率概率收到收到01后后的后验概的后验概率率收到收到011后的后的后验概率后验概率0（U0）000（x0y0z0)1/41/
20、31（U1）001（x0y0z1)1/41/32（U2）010（x0y1z0)1/81/63（U3）011（x0y1z1)1/81/64（U4）100（x1y0z0)1/1605（U5）101（x1y0z1)1/1606（U6）110（x1y1z0)1/1607（U7）111（x1y1z1)1/160第29页，本讲稿共97页收到收到01后的后验概率：后的后验概率：收到收到011后的后验概率：后的后验概率：第30页，本讲稿共97页信源消息信源消息二进制代码二进制代码先验先验概率概率收到收到0后的后后的后验概率验概率收到收到01后后的后验概的后验概率率收到收到011后后的后验概的后验概率率0（U0
21、）000（x0y0z0)1/41/3001（U1）001（x0y0z1)1/41/3002（U2）010（x0y1z0)1/81/61/203（U3）011（x0y1z1)1/81/61/214（U4）100（x1y0z0)1/160005（U5）101（x1y0z1)1/160006（U6）110（x1y1z0)1/160007（U7）111（x1y1z1)1/16000第31页，本讲稿共97页 x0与各消息的互信息量与各消息的互信息量 在已收到（给定）在已收到（给定）x0条件下，条件下，y1与各消息的与各消息的 互信息量。互信息量。第32页，本讲稿共97页 在已收到（给定）在已收到（给定）
22、x0y1条件下，条件下，z1与与U3消息的互消息的互信息量信息量.收到整个代码组收到整个代码组x0y1z1出现后提供的有关消息出现后提供的有关消息U3的互信息量。的互信息量。第33页，本讲稿共97页物理含义我们还可以用下式求得代码组我们还可以用下式求得代码组x0y1z1出现后提供有关出现后提供有关U3的信息量：的信息量：011第34页，本讲稿共97页 2.1.5 平均互信息量平均互信息量 平均互信息量的定义平均互信息量的定义定义：互信息量定义：互信息量I（ai;bj)在联合概率空间在联合概率空间p(aibj)中的统计平均值为平均互信息量中的统计平均值为平均互信息量同理有：同理有：第35页，本讲
23、稿共97页 平均互信息量的物理意义平均互信息量的物理意义 平均互信息量可以定义为无条件熵与条件熵平均互信息量可以定义为无条件熵与条件熵的差：的差：H（X;Y)=H(X)H(X Y)=H(Y)H(Y X)=H(X)H(Y)H(XY)H(X)是信源集的符号熵，即发送端发出的平均信息量。H(XY)为信道干扰引起损失的平均信息量，即信道疑义度。所以该式表示为：接收到的平均信息量=发出的平均信息量信道损失的 信息量。第36页，本讲稿共97页H(X)+H(Y)表示在通信前系统的先验不确定性。H(XY)表示输入集符号经有噪信道传输到输出端，为系统的后验不确定性。所以该式表示为：接收到的平均信息量=系统的先验
24、不确定性系统的后验不确定性。H(Y)是输出集的符号熵，表示要确认Y所需的信息量H(YX)为噪声熵，表示发出X后要确认Y尚需增加的信息量所以该式表示为：接收到的平均信息量=确认Y所必需的平均信息量 发出X后要确认Y尚需增加的信息量。第37页，本讲稿共97页 平均互信息量的性质平均互信息量的性质 对称性对称性 I（X；Y）=I（Y；X）非负性非负性 I（X；Y）0 极值性极值性 I（X；Y）H（X）I（X；Y）H（Y）第38页，本讲稿共97页 凸函数性凸函数性q 平均互信息平均互信息I(X;Y)信道传递概率分布信道传递概率分布P(Y/X)的的U型凸型凸函数函数q 平均互信息平均互信息I(X;Y)是
25、信源概率分布是信源概率分布P(X)的的 型凸型凸函数函数 定理说明：对于一定的信道转移概率分布，总可定理说明：对于一定的信道转移概率分布，总可以找到某一个先验概率分布的信源以找到某一个先验概率分布的信源X，使平均互信息量，使平均互信息量达到相应的最大值达到相应的最大值Imax，这时称这个信源为该信道这时称这个信源为该信道的匹配信源。可以说不同的信道转移概率对应不同的匹配信源。可以说不同的信道转移概率对应不同的的Imax。第39页，本讲稿共97页 2.1 单符号离散信源例例1：已知：已知 联合概率分布如下，求：联合概率分布如下，求：H(XY)，H(X),H(Y),H(Y|X),H(X|Y)，I（
26、X;Y)。行矢之行矢之和为和为p(xi)列矢之和为列矢之和为p(yj)第40页，本讲稿共97页 2.1 单符号离散信源解：由边际分布得：解：由边际分布得：由联合分布可得：由联合分布可得：H(XY)=2.665 bit/符号符号I(X;Y)=H(X)+H(Y)H(XY)=1.257 bit/符号符号 H(X Y)=H(X)I（X;Y）=0.809 bit/符号符号 H(Y X)=H(Y)I（X;Y）=0.600 bit/符号符号H(X)=2.066 bit/符号符号H(Y)=1.856 bit/符号符号第41页，本讲稿共97页 2.1 单符号离散信源例例2：已知信源：已知信源 X=A,B,C,信
27、源信源 Y=D,E,F,G,其条件其条件概率分布和概率分布和X的概率分布如下表。的概率分布如下表。试求：联合熵，噪声熵，信道疑义度及平均互信试求：联合熵，噪声熵，信道疑义度及平均互信 息量。息量。P(Y|X)DEFGP(X)A1/41/41/41/41/2B3/101/51/53/101/3C1/61/21/61/61/6第42页，本讲稿共97页 2.1 单符号离散信源解：由解：由p(XY)=p(X)P(Y X)，即可由联合分布通过边际，即可由联合分布通过边际 分布即可求得分布即可求得p(Y)P(XY)DEFGA1/81/81/81/8B1/101/151/151/10C1/361/121/3
28、61/36P(Y)91/36033/12079/36091/360H(XY)=3.417 bit/符号；符号；H(X)=1.46 bit/符号；符号；H(Y)=1.997 bit/符号；符号；H(Y|X)=1.95 bit/符号；符号；H(X|Y)=H(XY)-H(Y)=1.42 bit/符号符号第43页，本讲稿共97页 2.1 单符号离散信源例例3：设有一个系统传送：设有一个系统传送10个数字个数字0，1，9，奇数在传送，奇数在传送时以时以0.5的概率错成另外的奇数，而其它数字总能正确接的概率错成另外的奇数，而其它数字总能正确接收。试求，收到一个数字平均得到的信息量。收。试求，收到一个数字平
29、均得到的信息量。解：设，解：设，10个发送的数字的概率分布为均匀分布，个发送的数字的概率分布为均匀分布，由已知得：由已知得：H(Y)=10 bit/符号符号第44页，本讲稿共97页 2.1 单符号离散信源第45页，本讲稿共97页1.3.2 离散无记忆的扩展信源离散无记忆的扩展信源 实际情况下，信源输出的消息往往不是单个符号，而是由许多不同时刻发出的符号所组成的符号序列。设序列由N个符号组成，若这N个符号取自同一符号集 a1,a2,an，并且先后发出的符号彼此间统计独立，我们将这样的信源称作离散无记忆的离散无记忆的N维扩展信维扩展信源源。其数学模型为N维概率空间：x为各种长为N的符号序列，x=x
30、1 x2 xN，xi a1,a2,ak，1 i N，序列集X=a1a1 a1,a1a1 a2,akak ak，共有kN种序列，x X序列的概率p(x)=p(x1x2 xN)=第46页，本讲稿共97页 2.2 多符号离散平稳信源q实际信源输出往往是符号序列，称为离散多实际信源输出往往是符号序列，称为离散多 符号信源。即符号信源。即 X=x1x2x3，其特点：，其特点：n消息序列中的每一位的出现都是随机的，即每一位都是随机消息序列中的每一位的出现都是随机的，即每一位都是随机变量变量/随机矢量。随机矢量。n消息序列中的前后符号通常是相互依赖的。消息序列中的前后符号通常是相互依赖的。n消息序列中的每一
31、位的出现有时是随时间变化的。消息序列中的每一位的出现有时是随时间变化的。q这种信源我们称之为这种信源我们称之为多符号离散信源多符号离散信源。q若随机矢量若随机矢量X中随机变量的各维联合概率分布与时间起点中随机变量的各维联合概率分布与时间起点无关则称随机矢量无关则称随机矢量X为为多符号离散平稳信源多符号离散平稳信源。第47页，本讲稿共97页n当离散平稳无记忆信源信源发出固定长度的消息序列时，则得当离散平稳无记忆信源信源发出固定长度的消息序列时，则得到原信源的到原信源的扩展信源扩展信源。n例如在电报系统中，若信源输出的是二个二元数字组成的符号例如在电报系统中，若信源输出的是二个二元数字组成的符号序
32、列，此时可认为是一个新的信源，它由四个符号（序列，此时可认为是一个新的信源，它由四个符号（00，01，10，11）组成，我们把该信源称为）组成，我们把该信源称为二元无记忆信源的二二元无记忆信源的二次扩展信源次扩展信源。n如果把如果把N个二元数字组成一组，则信源等效成一个具有个二元数字组成一组，则信源等效成一个具有2N个符号的新信源，把它称为个符号的新信源，把它称为二元无记信源的二元无记信源的N次扩展信源次扩展信源。第48页，本讲稿共97页n一般情况下，对一个离散无记忆信源一般情况下，对一个离散无记忆信源X，其样本空间为，其样本空间为x1,x2,xn，对它的输出，对它的输出消息序列消息序列，可用
33、一组组长度为，可用一组组长度为N的序列来表示它。这时，它等效成一个的序列来表示它。这时，它等效成一个新信源新信源。n新信源输出的新信源输出的符号符号是是N维离散维离散随机矢量随机矢量X=(X1，X2,XN)，其中每个分量，其中每个分量Xi(i1,2,N)都是随机变量，它们都取值都是随机变量，它们都取值于同一信源符号集，并且分量之间统计独立，则由随机矢量于同一信源符号集，并且分量之间统计独立，则由随机矢量X 组成的新信源称为组成的新信源称为离散无记忆信源离散无记忆信源X的的N次扩展信源。次扩展信源。第49页，本讲稿共97页2.2.12.2.1序列信息的熵序列信息的熵 离散无记忆信源离散无记忆信源
34、X取值于集合取值于集合 ，扩，扩展信源输出为一组组长度为展信源输出为一组组长度为N的消息序列，的消息序列，其中每个分量，其中每个分量Xi（i=1，2，N）都是随机变量，都取值于同一集合）都是随机变量，都取值于同一集合 ，且分量之间统计独立。，且分量之间统计独立。离散无记忆信源离散无记忆信源X的的N次扩展信源次扩展信源第50页，本讲稿共97页单符号离散信源X的数学模型：单符号离散信源X的N次扩展信源XN的数学模型：离散无记忆信源X的N次扩展信源的熵就是离散信源X的熵的N倍0p(ai)1第51页，本讲稿共97页例：有一离散平稳无记忆信源，求这个信源的二次扩展信源的熵。X2信源的元素a1a2a3a4
35、a5a6a7a8a9消息序列x1x1x1x2x1x3x2x1x2x2x2x3x3x1x3x2x3x3概率p(ai)1/41/81/81/81/161/161/81/161/16解：二次扩展信源：第52页，本讲稿共97页一、离散平稳信源的数学定义一、离散平稳信源的数学定义n在一般情况下在一般情况下，信源在，信源在 t=i 时刻将要发出什么样的符号决定于两方面：时刻将要发出什么样的符号决定于两方面：(1)信源在信源在 t=i 时刻随机变量时刻随机变量Xi 取值的概率分布取值的概率分布P(xi)。一般一般 P(xi)P(xj)(2)t=i 时刻以前信源发出的符号。时刻以前信源发出的符号。即与条件概率
36、即与条件概率P(xi/xi-1 xi-2)有关有关n对对平稳随机序列平稳随机序列，序列的统计性质与时间的推移无关，即信源发出，序列的统计性质与时间的推移无关，即信源发出符号序列的概率分布与时间起点无关。符号序列的概率分布与时间起点无关。2.2.2 2.2.2 离散平稳信源离散平稳信源 第53页，本讲稿共97页n平稳随机序列的数学定义如下：平稳随机序列的数学定义如下：n若当若当t=it=i，t=jt=j时时(i,j(i,j 是大于是大于1 1的任意整数的任意整数)，P(xP(xi i)=P(x)=P(xj j)=P(x)=P(x)，则序列是一维平稳的。具有这样性质的信源称为则序列是一维平稳的。具
37、有这样性质的信源称为一维平稳信源一维平稳信源。n除上述条件外，如果联合概率分布除上述条件外，如果联合概率分布P(xP(xi ix xi+1i+1)也与时间起点无关，即也与时间起点无关，即P(xP(xi ix xi+1i+1)=P(x)=P(xj jx xj+1j+1)(i,j)(i,j为任意整数且为任意整数且i i j)j)，则信源称为，则信源称为二维平稳信源二维平稳信源。它表示任何时刻信源发出二个符号的联合概率分布也完全相等。它表示任何时刻信源发出二个符号的联合概率分布也完全相等。n如果各维联合概率分布均与时间起点无关，那么，信源是完全平稳如果各维联合概率分布均与时间起点无关，那么，信源是完
38、全平稳的。这种各维联合概率分布均与时间起点无关的完全平稳信源称为的。这种各维联合概率分布均与时间起点无关的完全平稳信源称为离散平稳信源离散平稳信源。这时有：。这时有：P(xi)=P(xj)P(xi xi+1)=P(xj xj+1)P(xi xi+1 xi+N)=P(xj xj+1 xi+N)不同时刻，概率分布相同不同时刻，概率分布相同第54页，本讲稿共97页由于由于联合概率与条件概率联合概率与条件概率有以下关系：有以下关系：n结论：结论：对于平稳信源来说，其条件概率均与时间起点无关，只与关联长度对于平稳信源来说，其条件概率均与时间起点无关，只与关联长度N有关。有关。即平稳信源发出的平稳随机序列
39、前后的依赖关系与时间起点无关即平稳信源发出的平稳随机序列前后的依赖关系与时间起点无关。从从平稳性平稳性可得：可得：第55页，本讲稿共97页n对平稳信源对平稳信源如果如果某时刻发出什么符号只与前面发出的某时刻发出什么符号只与前面发出的N个个符号有关符号有关，那么，那么任何时刻任何时刻它们的依赖关系都是一样的。即：它们的依赖关系都是一样的。即：第56页，本讲稿共97页2.2.2 2.2.2 离散平稳信源的信源熵和极限熵离散平稳信源的信源熵和极限熵二维平稳有记忆信源：信源输出为一组组长度为2的消息序列，符号序列组内有统计关联性，且假设组与组之间是统计独立的。数学模型：得到一个新的离散无记忆信源集得到
40、一个新的离散无记忆信源集第57页，本讲稿共97页 两个有相互依赖关系的随机变量X1和X2所组成的随机矢量 的联合熵H(X),等于第一个随机变量的熵H(X1)与第一个随机变量X1已知的前提下，第二个随机变量X2的条件熵H(X2/X1)之和。当随机变量X1和X2相互统计独立时：当随机变量X1和X2取值于同一集合时：离散无记忆信源的二次扩展信源可看成是二维离散平稳信源的特例。注：第58页，本讲稿共97页例：设某二维离散信源的原始信源的信源模型：解：原始信源X的熵：中前后两个符号的条件概率如下：P(X2/X1)x1x2x3x17/92/90 x21/83/41/8x302/119/11条件熵：平均信息
41、量：信源的相关性使信息熵变小。信源的相关性使信息熵变小。第59页，本讲稿共97页1.离散平稳信源的信源熵：2.条件熵：条件熵随N的增加而单调不增3.平均符号熵：N给定，平均符号熵大于等于条件熵平均符号熵随N的增加而非递增的第60页，本讲稿共97页4.极限熵：对于离散平稳有记忆信源，当依赖关系为无限长时，平均符号熵和条件熵都非递增的一致趋于平稳有记忆信源的极限熵第61页，本讲稿共97页q在很多信源的输出序列中，符号之间的依赖关系是有限在很多信源的输出序列中，符号之间的依赖关系是有限的，任何时刻信源符号发生的概率只与前边已经发出的的，任何时刻信源符号发生的概率只与前边已经发出的若干个符号有关，而与
42、更前面的符号无关。若干个符号有关，而与更前面的符号无关。q为了描述这类信源除了信源符号集外还要引入状态集。为了描述这类信源除了信源符号集外还要引入状态集。这时，信源输出消息符号还与信源所处的状态有关。这时，信源输出消息符号还与信源所处的状态有关。要点：限制关联长度要点：限制关联长度 引入状态概念引入状态概念 马尔可夫信源马尔可夫信源:第62页，本讲稿共97页马尔可夫信源是一类有限长度记忆的非平稳离散信源。b：信源某l时刻所处的状态只由当前输出的符号和前一时刻信源所处的状态唯一决定2.2.4 2.2.4 马尔可夫信源马尔可夫信源一、定义：若信源输出的符号和所处的状态满足马尔可夫链的条件：a：某一
43、时刻信源输出的符号只与此刻信源所处的状态有关，而与以前的状态和输出的符号无关。若上述两条件与时刻L无关，则具有时齐性（齐次性），称为时齐马尔可夫信源。第63页，本讲稿共97页马尔可夫链的概念X1Xi+1X2XiXi+2SjXi-2Sj-1Xi-1Sj+1S2S1若信源随机状态序列服从马尔可夫链，若信源随机状态序列服从马尔可夫链，则称该信源为马尔可夫信源则称该信源为马尔可夫信源第64页，本讲稿共97页二、模型：（状态转移图）例：设信源符号 ，信源所处的状态 ，各状态之间的转移情况如图：第65页，本讲稿共97页马尔可夫信源的状态转移图马尔可夫信源的状态转移图 状态转移图状态转移图 发出的转移概率之
44、和为发出的转移概率之和为1 状态矩阵状态矩阵 行矢为行矢为1条件概率条件概率第66页，本讲稿共97页三、m阶马尔可夫信源 m阶马尔可夫信源，它在任何时刻l，符号发生的概率只与前面的m个符号有关，可以把这前面的m个符号看作信源在此l时刻所处的状态1、数学模型：当当m=1时，为时，为一阶马尔可夫信源一阶马尔可夫信源。第67页，本讲稿共97页2、m阶马氏信源熵注：（1）只有时齐遍历（各态历经）的马尔可夫信源，当时间足够长达到稳定以后才能等价成平稳有记忆信源。各态历经：定理：对于有限齐次马尔可夫链，若存在一个正整数l01，对于一切i，j=1，2，nm，都有 ,则对于每一个j都存在不依赖于i的极限则称这
45、种马尔可夫链是各态历经的。（2）此处联合概率 是时齐遍历的m阶马尔可夫信源达到稳定后的极限概率，与初始时刻符号概率分布不同第68页，本讲稿共97页对于对于m阶马尔可夫信源，阶马尔可夫信源，这表明这表明m阶马尔可夫信源的极限熵阶马尔可夫信源的极限熵H就等于就等于m阶条件熵。由阶条件熵。由条件熵的概念有：条件熵的概念有：时齐性时齐性限制关联长度限制关联长度时齐性时齐性定定义义式式马尔可夫信源的极限熵马尔可夫信源的极限熵:第69页，本讲稿共97页例：某二元二阶马尔可夫信源，信源符号 ，其状态空间共有nm=22=4个不同的状态 即各状态之间的转移情况如图：第70页，本讲稿共97页q有记忆信源的平均符号
46、熵有记忆信源的平均符号熵 m阶马尔科夫信源每发一个符号提供的平均信息量为阶马尔科夫信源每发一个符号提供的平均信息量为H，而，而m个为一组的有记忆信源每发一个符号提供的平个为一组的有记忆信源每发一个符号提供的平均信息量为均信息量为二者是不同的二者是不同的。第71页，本讲稿共97页 冗余度冗余度1n它表征信源信息率的多余程度，是描述信源客观统计特性的一个物理量。由广义Shannon不等式有：或：n可见对于有记忆信源，最小单个消息熵应为，即从理论上看，对有记忆信源只需传送即可。n但是这必需要掌握信源全部概率统计特性。这显然是不现实的。实际上，往往只能掌握有限的维，这时需传送n，那么与理论值相比，就多
47、传送了。第72页，本讲稿共97页冗余度冗余度2n为了定量描述信源有效性，可定义：信源效率：信源冗余度：（相对剩余）第73页，本讲稿共97页冗余度3n正由于信源存在着冗余度，即存在着不必要传送的信息，因此信源也就存在进一步压缩信息率的可能性。冗余度越大，压缩潜力也就越大。可见它是信源编码，数据压缩的前提与理论基础。第74页，本讲稿共97页 字母 字母 字母 空格ETOANIR0.20.1050.0720.06540.0630.0590.0550.054SHDLCF.UMP0.05020.0470.0350.0290.0230.0225 0.0210.0175Y.WGBVKXJ.QZ0.0120.
48、0110.01050.0080.0030.0020.0010.001冗余度冗余度4（举例：计算英文文字信源的冗余度）首先给出英文字母（含空格）出现概率如下：第75页，本讲稿共97页冗余度冗余度5（举例：计算英文文字信源的冗余度）n首先求得独立等概率情况，即n其次，计算独立不等概率情况，n再次，若仅考虑字母有一维相关性，求，n最后，利用统计推断方法求出，由于采用的逼近的方法和所取的样本的不同，推算值也有不同，这里采用Shannon的推断值。第76页，本讲稿共97页 由上述例子可看出：由上述例子可看出：n由于各个符号出现的概率不均匀由于各个符号出现的概率不均匀 所以：所以：H H1 1H H0 0
49、n随着序列增长，字母间的相关性越来越强随着序列增长，字母间的相关性越来越强:所以：所以：H H H H3 3H H2 2n正是因为信源符号中存在的这些统计不均匀性和相关性，正是因为信源符号中存在的这些统计不均匀性和相关性，才使得信源存在冗余度。才使得信源存在冗余度。n当英文字母的结构信息已预先充分获得时，可用合理当英文字母的结构信息已预先充分获得时，可用合理符号来表达英语，例如传送或存储这些符号，可大量符号来表达英语，例如传送或存储这些符号，可大量压缩，压缩，100100页的英语，大约只要页的英语，大约只要2929页就可以了。页就可以了。第77页，本讲稿共97页冗余度冗余度6这一结论说明，英文
50、信源，从理论上看71是多余成分。直观地说100页英文书，理论上看仅有29页是有效的，其余71页是多余的。正是由于这一多余量的存在，才有可能对英文信源进行压缩编码。第78页，本讲稿共97页冗余度冗余度7对于其它文字，也有不少人作了大量的统计工作，现简述如下：英文法文德文西班牙文中文（按8千汉字计算）第79页，本讲稿共97页问题问题1 1：冗余度产生的原因：冗余度产生的原因 n冗余度（多余度、剩余度）冗余度（多余度、剩余度）表示给定信源在实际发出消息时所包含表示给定信源在实际发出消息时所包含的多余信息。的多余信息。冗冗余余度度来来自自两两个个方方面面，一一是是信信源源符符号号间间的的相相关关性性，