信息论与编码1ppt课件

精选ppt,信息论与编码,主讲：苗立刚基础楼319,计算机与通信工程学院2016年3月,精选ppt,课程目标与安排,它是信息处理方向的一门重要的专业基础课，是后续课程的基础，如通讯原理、数字图像处理、语音信号处理等。介绍信息科学的基础理论和基本方法，课程将基于一个通讯系统的抽象数学模型进行展开，课程分为基础理论和编码理论两部分组成。本课程以概率论为基础，数学推导较多，学习时主要把注意力集中到概念的理解上，不过分追求数学细节的推导。注意基本概念的理解，不断加深概念的把握。学习时注意理解各个概念的“用处”，结合其他课程理解它的意义，而不要把它当作数学课来学习。,课程特点,精选ppt,学时：32考试方式：开卷考试成绩：平时成绩*20%+考试成绩*80%,课程目标与安排,精选ppt,第一章绪论第二章信源熵第三章信道容量第四章信息率失真函数第五章信源编码第六章信道编码第七章密码体制的安全性测度,课程内容安排,课程目标与安排,精选ppt,课程目标与安排,参考书,曲炜，朱诗兵，信息论基础及应用，清华大学出版社，2005信息论与编码，陈运、周亮、陈新，电子工业出版社，2007傅祖芸，信息论与编码，电子工业出版社，2004周荫清，信息论基础(第3版)，北京航空航天大学出版社，2006,有关的课程,高等数学，概率论，线性代数,精选ppt,第一章绪论,信息论基础,主讲：苗立刚基础楼318,计算机与通信工程学院2014年3月,精选ppt,第一章绪论,信息的有关概念通讯系统模型信息论的形成和发展历史,本章主要讨论的问题：,精选ppt,信息的有关概念,“信息”是信息论中最基本、最重要的概念，它是一个既抽象又复杂的概念，目前还没有一个统一的定义(百余种)；“信息”不同于消息在现代信息论形成之前，信息一直被看作是通信中消息的同义词，没有严格的数学含义；所谓消息，是用文字、符号、数据、语言、图片、图像等形式，把客观事物运动和主观思维活动的状态表达出来；消息是信息的载体；消息是表现形式，信息是实质。“信息”不同于情报情报往往是军事学、文献学方面的习惯用词，它的含义比“信息”窄的多，一般只限于特殊的领域，是一类特殊的信息；“情报”是人们对于某个特定对象所见、所闻、所理解产生的知识；,精选ppt,“信息”不同于知识知识是人们根据某种目的,从自然界收集得来的数据中整理、概括、提取得到的有价值的信息，是一种高层次的信息；知识是信息，但不等于信息的全体；“信息”不同于信号把消息变换成适合信道传输的物理量，就是信号；信号是承载消息的物理量；,信息的有关概念,精选ppt,信息的有关概念,信息的几种定义以信源为主的信息定义、以信道为主的信息定义和以信宿为主的信息定义。以信源为主的信息定义有：1)信息是事物之间的差异(Longo,1975)2)信息是有序性的度量(Wiener,1948)以信道为主的信息定义有：1)信息是通信传输的内容(Wiener,1950)2)信息是人与外界相互作用的过程中所交换的内容的名称(Wiener,1948)以信宿为主的信息定义有：1)信息是用来消除随机不定性的东西(Shannon,1948）2)信息是使概率分布发生变动的东西（Tribesetal,1971）,精选ppt,仙农从研究通信系统传输的实质出发，对信息做出了科学的定义；仙农注意到：收信者在收到消息之前是不知道消息的具体内容的。通信系统消息的传输对收信者来说，是一个从不知到知的过程，或者从知之甚少到知之甚多的过程，或是从不确定到部分确定或全部确定的过程。因此,对于收信者来说,通信过程是消除事物状态的不确定性的过程，不确定性的消除，就获得了信息，原先的不确定性消除的越多，获得的信息就越多；“信息”是事物运动状态或存在方式的不确定性的描述，这就是仙农关于信息的定义。,信息的有关概念,精选ppt,信息的度量,信息的度量（信息量）和不确定性消除的程度有关，消除了多少不确定性，就获得了多少信息量；不确定性就是随机性，可以用概率论和随机过程来测度不确定性的大小，出现概率小的事件，其不确定性大，反之，不确定性小；由以上两点可知：概率小信息量大，即信息量是概率的单调递减函数；此外，信息量应该具有可加性；,精选ppt,信息的度量,由于信息量与概率成反比，并且具有可加性，可以证明，信息量的计算式为其中pk是事件xk发生的概率，这也是仙农关于(自)信息量的度量(概率信息)，单位为bit,哈特莱早在20世纪20年代就提出用对数作为信息量的测度。哈特莱认为：消息和信息不同，多种多样、千姿百态的消息是信息的载体，消息究竟包含了多少信息，应该用消息出现的概率的对数来计算，从而他为信息度量找到了对数这一数学理论。,精选ppt,通讯系统模型,信源,编码器,信道,译码器,干扰源,通信系统基本模型,消息,信号,消息,信宿,噪声,信源：消息的来源，如文字、语音、图像等编码器：把消息变换成信号，如信源编码、纠错编码、调制器信道：传递信号的媒介，如电缆、光纤、无线电波等噪声：信道中的干扰，如加性干扰、乘性干扰译码器：把信道输出的信号反变换，解调器、纠错译码器、信源译码器信宿：信息的接受端，接收消息的人或物,精选ppt,通讯系统模型,信源：消息的来源编码器：把消息变换成信号信道：传递信号的媒介译码器：把信道输出的信号反变换信宿：信息的接受端噪声：信道中的干扰,信源编码器：把信源发出的消息变换成由二进制码元（或多进制码元）组成的代码组以提高通信系统传输消息的效率。信源编码可分为无失真信源编码和限失真信源编码。目的：提高信息传输的有效性信道编码器：在信源编码器输出的代码组上有目的地增加一些监督码元，使之具有检错或纠错的能力。目的：提高信息传输的可靠性密码学：研究如何隐蔽消息中的信息内容，使它在传输过程中不被窃听，提高通信系统的安全性。目的：提高信息的安全性,编码问题可分解为三类：信源编码、信道编码和密码,在实际问题中，上述三类编码应统一考虑来提高通信系统的性能。这些编码的目标往往是相互矛盾的。,精选ppt,电报常用的莫尔斯码就是按信息论的基本编码原则设计出来的；在一些商品上面有一张由粗细条纹组成的标签，从这张标签可以得知该商品的生产厂家、生产日期和价格等信息，这些标签是利用条形码设计出来的，非常方便，非常有用，应用越来越普遍；计算机的运算速度很高，要保证它几乎不出差错，相当于要求有100年的时间内不得有一秒钟的误差，这就需要利用纠错码来自动地及时地纠正所发生的错误；每出版一本书，都给定一个国际标准书号（ISBN），大大方便图书的销售、编目和收藏工作。,编码的应用的几个例子：,通讯系统模型,精选ppt,信息论的形成和发展,信息论是在长期通信工程的实践中，由通信技术与概率论、随机过程和数理统计相结合而逐步发展起来的一门科学。奈魁斯特：在1924年研究影响电报传递速度的因素时,就察觉到信息传输速度和频带宽度有关系;哈特莱(Hartley)：在1928年用概率的观点来分析信息传输问题;仙农（ClaudeE.Shannon)：1948年发表通信的数学理论(AMathematicalTheoryofCommunication),为创立信息论作出了决定性的贡献;香农因此成为信息论的奠基人。维纳(N.Wiener)等：为信息论的进一步发展和拓展作了大量工作;主要在通信的统计理论与滤波器理论方面。,精选ppt,第二章信源熵,信息论基础,主讲：苗立刚基础楼318,计算机与通信工程学院2014年3月,精选ppt,第二章信源熵,2.1单符号离散信源2.2多符号离散平稳信源2.3连续信源2.4离散无失真信源编码定理,本章主要讨论的问题：,精选ppt,2.1单符号离散信源,单符号离散信源的数学模型,单符号信源信源每次输出一个符号,用离散随机变量描述多符号信源信源每次输出多个符号(符号序列)，用离散随机矢量描述离散信源信源符号取值离散，包括单符号和多符号信源连续信源信源符号取值连续，用随机过程描述结论从概率、随机变量(过程)来研究信息信息对事物状态(存在方式)不确定性的描述,精选ppt,2.1单符号离散信源,单符号离散信源的数学模型,注意：大写字母X,Y,Z代表随机变量，小写字母代表随机事件。,精选ppt,概率复习,精选ppt,2.1单符号离散信源,由于信息量与概率成反比，并且具有可加性，自信息量的定义为：其中p(xi)是事件xi发生的概率，这也是仙农关于(自)信息量的度量(概率信息)计算信息量主要要注意有关事件发生概率的计算;性质：非负;单调递减；当p(xi)=0时,I(xi),不可能事件；当p(xi)=1时，I(xi)0，确定事件自信息量I(xi)的含义当事件xi发生以前，表示事件xi发生的不确定性；当事件xi发生以后，表示事件xi所提供的信息量；,自信息量（单个随机事件）,精选ppt,例1：从26个英文字母中，随即选取一个字母，则该事件的自信息量为I=-log2(1/26)=4.7比特例2：设m比特的二进制数中的每一个是等概率出现的(这样的数共有2m个)，则任何一个数出现的自信息为:I=-log2(1/2m)=m比特/符号,自信息量的单位自信息量的单位取决于对数的底；底为2，单位为“比特（bit）”；底为e，单位为“奈特（nat）”；底为10，单位为“哈特（hat）”；1nat=1.44bit,1hat=3.32bit；,2.1单符号离散信源,精选ppt,例3：设天气预报有两种消息，晴天和雨天，出现的概率分别为1/4和3/4，我们分别用来表示晴天，以来表示雨天，则我们的信源模型如下：,2.1单符号离散信源,精选ppt,联合自信息量(两个随机事件),二维联合集XY上的元素(xiyj)的联合自信息量定义为：含义X=xi，Y=yj同时发生时，带来的信息量特例若X、Y独立，则I(xiyj)=I(xi)+I(yj),2.1单符号离散信源,精选ppt,条件自信息量（两个随机事件）,二维联合集XY中，对事件xi和yj，事件xi在事件yj给定的条件下的条件信息量定义为：,联合自信息量和条件自信息量也满足非负和单调递减性。关系当X和Y独立时，,2.1单符号离散信源,精选ppt,互信息量(两个随机事件),2.1单符号离散信源,精选ppt,信源发出消息的概率称为先验概率，信宿收到后推测信源发出的概率称为后验概率。定义的后验概率与先验概率比值的对数为对的互信息量，用表示，即互信息量等于自信息量减去条件自信息量。第三种表达方式：,2.1单符号离散信源,精选ppt,含义互信息I(xi;yj)=自信息I(xi)-条件自信息I(xi/yj)(1)I(xi)信宿收到yj之前，对信源发xi的不确定度(2)I(xi|yj)信宿收到yj之后，对信源发xi的不确定度(3)I(xi;yj)收到yj而得到(关于xi)的互信息=不确定度的减少量性质(1)对称性I(xi;yj)=I(yj;xi)(2)X与Y独立时I(xi;yj)=0(3)I(xi;yj)可为正、负、0(4)I(xi;yj)=I(xi);I(xi;yj)=I(yj),2.1单符号离散信源,精选ppt,I(xi;yj)可为正、负、0的举例设yj代表“闪电”，则当xi代表“打雷”时，I(xi|yj)=0，I(xi;yj)=I(xi)0当xi代表“下雨”时，I(xi|yj)I(xi)，I(xi;yj)0当xi代表“雾天”时，I(xi|yj)=I(xi)，I(xi;yj)=0当xi代表“飞机正点起飞”时，I(xi|yj)I(xi)，I(xi;yj)0,2.1单符号离散信源,精选ppt,条件互信息量(三个随机事件),联合集XYZ中,给定条件下，与之间的互信息量，其定义式,互信息量,2.1单符号离散信源,精选ppt,平均自信息量(信源熵)-随机变量,单位bit/(信源)符号,这个平均自信息量的表达式和统计物理学中热熵的表达式很相似。在统计物理学中，热熵是一个物理系统杂乱性（无序性）的度量。这在概念上也有相似之处。因而就借用“熵”这个词把平均自信息量H(X)称为“信源熵”。,通常研究单独一个事件或单独一个符号的信息量是不够的，往往需要研究整个事件集合或符号序列(如信源)的平均的信息量(总体特征)，这就需要引入新的概念；定义自信息的数学期望为信源的平均信息量,2.1单符号离散信源,精选ppt,例：天气预报，有两个信源,则：,说明第二个信源的平均不确定性更大一些,信息熵具有以下三种物理含义：1、表示信源输出前，信源的平均不确定性2、表示信源输出后，每个符号所携带的平均信息量3、反映了变量X的随机性。,2.1单符号离散信源,精选ppt,例：设某信源输出四个符号，其符号集合的概率分布为：则其熵为：,2.1单符号离散信源,精选ppt,例：电视屏上约有500600=3105个格点，按每点有10个不同的灰度等级考虑，则共能组成n=103x105个不同的画面。按等概率1/103x105计算，平均每个画面可提供的信息量为,=31053.32比特/画面,例：有一篇千字文章，假定每字可从万字表中任选，则共有不同的千字文N=100001000=104000篇。仍按等概率1/100001000计算，平均每篇千字文可提供的信息量为H（X）log2N4103332=1.3104比特千字文,“一个电视画面”平均提供的信息量远远超过“一篇千字文”提供的信息量。,2.1单符号离散信源,精选ppt,熵函数的数学特性,熵函数可以表示为：,二元熵：,性质1：非负性,H(X)0由于0pi1,所以logpi0，logpi0，则总有H(X)0。,2.1单符号离散信源,精选ppt,性质2：对称性,根据加法交换律可以证明，当变量交换顺序时熵函数的值不变。信源的熵只与概率空间的总体结构有关，而与个概率分量对应的状态顺序无关；,性质3：扩展性,这说明信源空间中增加某些概率很小的符号，虽然当发出这些符号时，提供很大的信息量，但由于其概率接近于0，在信源熵中占极小的比重，使信源熵保持不变。,2.1单符号离散信源,精选ppt,性质4：可加性,性质5：极值性,上式表明，对于具有n个符号的离散信源，只有在n个信源符号等可能出现的情况下，信源熵才能达到最大值，这也表明等概分布的信源的平均不确定性最大，这是一个很重要得结论，称为最大离散熵定理,例：对于一个二元信源H(X)=H(1/2,1/2)=log2=1bit,H(X)=-plog2p(1-p)log2(1-p)=H(p),2.1单符号离散信源,精选ppt,性质6：确定性,当信源X的信源空间X，P中。任一个概率分量等于1，根据完备空间特性，其它概率分量必为0，这时信源为一个确知信源，其熵为0。如果一个信源的输出符号几乎必然为某一状态，那么这个信源没有不确定性，信源输出符号后不提供任何信息量。,性质7：上凸性,是概率分布(p1,p2,pq)的严格上凸函数。,2.1单符号离散信源,精选ppt,设f(X)=f(x1,x2,xn)为一多元函数。若对于任意一个小于1的正数（0=f(X1)+(1-)f(X2)则称f(X)为定义域上的上凸函数。若“=”不成立，则为严格上凸函数若“=”,则为下凸函数若“”,则为严格下凸函数,2.1单符号离散信源,精选ppt,H（p）函数曲线如图所示。如果二元信源的输出符号是确定的，即p=1或q=1，则该信源不提供任何信息。反之，当二元信源符号0和1以等概率发生时，信源熵达到极大值，等于1比特信息量。,2.1单符号离散信源,精选ppt,信源熵是从整个信源的统计特性来考虑的，它是从平均意义上来表征信源的总体信息测度的。对于某特定的信源（概率空间给定），其信源熵是一个特定的值。不同的信源因统计特性不同，其熵也不同。信源熵用以表征信息源的平均不确定性，平均自信息量是消除信源不确定性时所需信息的量度，即收到一个信源符号，全部解除了这个符号的不确定性。或者说获得这样大的信息量后，信源不确定性就被消除了。,2.1单符号离散信源,精选ppt,信源熵和平均自信息量两者在数值上相等，但含义不同。某一信源，不管它是否输出符号，只要这些符号具有某些概率特性，就必有信源的熵值；这熵值在总体平均上才有意义，因而是一个确定的值。而另一方面，信息量则只有当信源输出的符号被接收者收到后才有意义，信息量就是给予接收者的信息度量，该值本身可以是随机量，也可以与接收者的情况有关。,因此说信源熵是信源的平均不确定性的描述，一般情况下它并不等于平均获得的信息量。只是在无噪情况下，接收者才能正确无误地接收到信源所发出的信息，消除了信源熵H（X）值大小的平均不确定性，所以获得的平均信息量就等于信源熵H（X）的值。在一般情况下获得的信息量是两熵之差，并不是信源熵本身。,2.1单符号离散信源,精选ppt,条件熵,思考：求条件熵时为什么要用联合概率加权？,条件熵是在联合符号集合XY上的条件自信息量的数学期望。在已知随机变量X的条件下，随机变量Y的条件熵定义为：,2.1单符号离散信源,精选ppt,条件概率,并且,当已知特定事件xi出现时，下一个出现的是yj的不确定性为：,对集合Y中所有元素统计平均，其熵为：,上述熵值再对集合Y中的元素做统计平均，得条件熵：,同理可得：,精选ppt,条件熵H(X/Y)是一个确定值，表示信宿在收到Y后，信源X仍然存在的不确定度。这是信道干扰所造成的。有时称H(X/Y)为信道疑义度，也称损失熵。如果没有干扰，H(X/Y)=0,一般情括下H(X/Y)小于H(X)，说明经过信道传输，总能消除一些信源的不确定性，从而获得一些信息。条件熵H(Y/X)也是一个确定值,表示信源发出X后，信宿仍然存在的不确定度。这是由于噪声引起的。也称为噪声熵。,2.1单符号离散信源,精选ppt,联合熵（共熵）,联合离散符号集合XY上的每个元素对的联合自信息量的数学期望。,说明:联合熵H（XY）表示X和Y同时发生的不确定度。,2.1单符号离散信源,精选ppt,加权熵（自学）,对香农熵引入主观因素效用权重系数(重量)定义：设信源X则加权熵Hw(X)含义消息xi的权重wi对I(xi)的加权平均性质：略,2.1单符号离散信源,精选ppt,从通信系统角度看熵的意义,H(X)：表示信源边每个符号的平均信息量（信源熵）；H(Y)：表示信宿边每个符号的平均信息量（信宿熵）；H(X|Y):信道疑义度(含糊度)，表示在输出端接收到Y后，发送端X尚存的平均不确定性。这个对X尚存的不确定性是由于信道干扰引起的。H(Y|X):噪声熵，表示在已知X后，对于输出Y尚存的平均不确定性；H(XY):表示整个信息传输系统的平均不确定性；,2.1单符号离散信源,精选ppt,各种熵的性质,联合熵H(XY)与熵H(X)及条件熵H(X/Y)之间存在下列关系:H(XY)H(X)H(Y/X)H(XY)H(Y)H(X/Y),联合熵与信息熵的关系:H(XY)=H(X)H(Y),条件熵与信息熵的关系:H(Y|X)=H(Y)H(X|Y)=0该性质表明，通过一个信道总能传递一些信息，最差的条件下，输入输出完全独立，不传递任何信息，互信息等于0，但决不会失去已知的信息。极值性：即I(X;Y)=H(X)一般来说，信道疑义度H(X|Y)总是大于0，所以互信息总是小于信源的熵，只有当信道是无损信道时，信道疑义度等于0，互信息等于信源的熵。对称性：即I(X;Y)=I(Y;X)I(Y;X)表示从X中提取关于的Y的信息量，实际上I(X,Y)和I(Y,X)只是观察者的立足点不同，对信道的输入X和输出Y的总体测度的两种表达形式,2.1单符号离散信源,精选ppt,I(X;Y)是二元函数:P(X)的上凸函数，P(Y|X)的下凸函数,平均互信息的凸状性,2.1单符号离散信源,精选ppt,定理2.1对于固定的信道，平均互信息I(X;Y)是信源概率分布P(X)的上凸函数,这就是说，对于一定的信道转移概率分布P(Y|X)，总可以找到某一个先验概率分布的信源X，使平均交互信息量I(X;Y)达到相应的最大值Imax，这时称这个信源为该信道的匹配信源。可以说，不同的信道转移概率对应不同的Imax。,2.1单符号离散信源,精选ppt,例：对于二元对称信道,如果信源分布X=p,1-p，则,2.1单符号离散信源,精选ppt,2.1单符号离散信源,而：,所以：,当信道固定时，q为一个固定常数，平均互信息是信源分布的上凸函数，最大只为1-H(q)。图示曲线表明，对于固定信道，输入符号X的概率分布不同时，在接收端平均每个符号所获得的信息量就不同。当输入符号为等概率分布时，平均互信息量为最大值，接收每个符号所获得的信息量最大。信道容量的理论基础,精选ppt,定理2.2对于固定的信源，平均互信息I(X;Y)信道传递概率分布P(Y|X)的下凸函数,这就是说，对于一个已知先验概率为p的离散信源，总可以找到某一个转移概率分布的信道q，使平均互信息量达到相应的最小值Imin。,2.1单符号离散信源,精选ppt,例：对于二元对称信道,当信源固定后，p为一个固定常数，改变信道特性q可获得不同的平均互信息I(X;Y)。当q=1/2时，I(X;Y)=0,即在信道输出端获得的信息最小，这意味着信源的信息全部损失在信道中，这是一种最差的信道，其噪声最大。信息率失真理论的基础。,2.1单符号离散信源,精选ppt,对于无损信道，有I(X;Y)=H(X)=H(Y)=H(XY)H(X/Y)=H(Y/X)=0对于全损信道，有I(X;Y)=0H(X/Y)=H(X)；H(Y/X)=H(Y),2.1单符号离散信源,精选ppt,数据处理定理(自学)I(X;Z)I(Y;Z)I(X;Z)I(X;Y)意义信息不增原理每经一次处理，可能丢失一部分信息,2.1单符号离散信源,精选ppt,各类熵与集合图的类比,2.1单符号离散信源,精选ppt,信道中熵的信息流图,H(Y|X):噪声熵；H(X|Y):信道疑义度；它们都是由于噪声干扰的存在而存在的。信道中存在噪声干扰，是减低信道传信能力的基本原因。,2.1单符号离散信源,精选ppt,各种熵之间的关系,精选ppt,例,2.1单符号离散信源,精选ppt,精选ppt,精选ppt,作业：2.4(P68),2.6(P68),2.7(P68),2.10(P68),精选ppt,2.2多符号离散平稳信源,精选ppt,离散无记忆信源：发出的各个符号是相互独立的，发出的符号序列中的各个符号之间没有统计关联性，各个符号的出现概率是它自身的先验概率。离散有记忆信源：所发出的各个符号的概率是有关联的。发出单个符号的信源：是指信源每次只发出一个符号代表一个消息；发出符号序列的信源：是指信源每次发出一组含二个以上符号的符号序列代表一个消息。发出符号序列的有记忆信源：是指用信源发出的一个符号序列的整体概率（即联合概率）反映有记忆信源的特征。发出符号序列的马尔可夫信源：是指某一个符号出现的概率只与前面一个或有限个符号有关，而不依赖更前面的那些符号，这样的信源可以用信源发出符号序列内各个符号之间的条件概率来反映记忆特征。,2.2多符号离散平稳信源,精选ppt,2.2多符号离散平稳信源,离散无记忆信源发出单个符号的无记忆信源（最简单的离散信源）,自信息量信源熵,精选ppt,2.2多符号离散平稳信源,离散无记忆信源的扩展信源,实际信源输出的消息往往是时间上或空间上的一系列符号，如电报系统，序列中前后符号间一般是有统计依赖关系的。离散无记忆二进制信源X的二次扩展信源我们先讨论离散无记忆信源，此时，信源序列的前后符号之间是统计独立的.如在二元系统中，我们可以把两个二元数字看成一组，会出现四种可能情况：00、01、10和11，我们可以把这四种情况看成一个新的信源称为二元无记忆信源的二次扩展信源，相应的，如果把N个二元数字看成一组，则新的信源称为二元无记忆信源的N次扩展信源。,精选ppt,则该信源的N次扩展信源为：,一般情况下，设一个离散无记忆信源为：,离散无记忆二进制信源X的三次扩展信源离散无记忆信源X的N次扩展信源,2.2多符号离散平稳信源,精选ppt,根据信息熵的定义：,可以证明，对于离散无记忆的扩展信源,N次扩展信源的熵,2.2多符号离散平稳信源,注意：(1)单位:bit/sign,但含义不同(2)N次扩展信源的熵等于各符号熵之和,精选ppt,例:离散无记忆信源的N次扩展信源离散无记忆信源为：X:a1,a2,a3;P(X):1/4,1/2,1/4,2次扩展信源为：,:A1,A9,信源的9个符号为：,其概率关系为:,2.2多符号离散平稳信源,精选ppt,计算可知,2.2多符号离散平稳信源,精选ppt,2.2多符号离散平稳信源,离散平稳信源,一般来说，信源的前后消息之间有前后依赖关系，可以用随机矢量描述：,信源在某一时刻发出什么样的值取决于两方面1、这一时刻该变量的概率分布2、这一时刻以前发出的消息如一个人讲话我们现在讨论平稳的随机序列，所谓平稳是指序列的统计性质与时间的推移无关（俩个任意时刻信源发出符号的概率分布完全相同）。信源所发符号序列的概率分布与时间的起点无关，这种信源我们称之为离散序列平稳信源。,精选ppt,2.2多符号离散平稳信源,精选ppt,2.2多符号离散平稳信源,离散平稳信源的熵,最简单的平稳信源二维平稳信源，信源发出序列中只有前后两个符号间有依赖关系，我们可以对其二维扩展信源进行分析。信源的概率空间:,假定X=X1X2,则可得到一个新的信源,精选ppt,2.2多符号离散平稳信源,根据信息熵的定义，可得：(1)联合熵,可以表征信源输出长度为2的符号的平均不确定性，或所含有的信息量。因此可以用作为二维平稳信源的信息熵的近似值,(2)条件熵,则：,精选ppt,2.2多符号离散平稳信源,另外还可以得到：,只有信源统计独立时等号成立。结论：二维离散平稳有记忆信源的熵小于等于二维平稳无记忆信源的熵。,可以证明：,精选ppt,例设某二维离散信源的原始信源的信源空间X=x1,x2,x3;P(X)=1/4,1/4,1/2,一维条件概率为：p(x1|x1)=1/2;p(x2|x1)=1/2;p(x3|x1)=0;p(x1|x2)=1/8;p(x2|x2)=3/4;p(x3|x2)=1/8;p(x1|x3)=0;p(x2|x3)=1/4;p(x3|x3)=3/4;原始信源的熵为：H(X)=1.5bit/符号条件熵：H(X2|X1)=1.4bit/符号可见：H(X2|X1)0I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X)H(X)H(Y),思考：p(x)应该怎样取值？,a1a2a3,b1b2b3b4b5,精选ppt,3.2单符号离散信道的信道容量,确定信道：多对一（nm）,具有归并性的无噪信道,信道矩阵：每行只有一个元素“1”，其它全是0,损失熵H(X/Y)0噪声熵H(Y/X)=0I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(Y)H(X)H(Y),思考：p(x)应该怎样取值？,精选ppt,强对称离散信道(均匀信道),3.2单符号离散信道的信道容量,信道特点信道输入、输出均为n元每符号正确传输概率均为其他符号错误传输概率为p/(n-1)矩阵特点(1)nn阶对称阵(2)每行和为1,每列和为1,精选ppt,3.2单符号离散信道的信道容量,信道容量,可以看出，当输出等概分布时，即H(Y)=log2n时达到信道容量。,精选ppt,3.2单符号离散信道的信道容量,那么，在什么样的信源输入情况下，信道输出能等概分布呢？可以证明，输入等概分布时，离散对称信道的输出也为等概分布,结论对强对称信道，输入等概输出等概，可达到C,精选ppt,3.2单符号离散信道的信道容量,二进制对称信道(n=2),精选ppt,3.2单符号离散信道的信道容量,行可排列矩阵每行各元素都来自同一集合QQq1,q2,qm(排列可不同)列可排列矩阵每列各元素都来自同一集合PPp1,p2,pn(排列可不同)矩阵可排列矩阵的行、列皆可排列对称信道信道矩阵可排列,离散对称信道,(1)m=n时，Q、P为同一集合mn时，Q、P中，一个必为另一个的子集(2)输入等概输出等概,精选ppt,3.2单符号离散信道的信道容量,离散输入对称信道如果一个离散无记忆信道的信道矩阵中，每一行都是其他行的同一组元素的不同排列，则称此类信道为离散输入对称信道。,离散输出对称信道如果一个离散无记忆信道的信道矩阵中，每一列都是其他列的同一组元素的不同排列，则称此类信道为离散输出对称信道。,精选ppt,3.2单符号离散信道的信道容量,离散对称信道如果一个离散无记忆信道的信道矩阵中，每一行都是其他行的同一组元素的不同排列，并且每一列都是其他列的同一组元素的不同排列，则称此类信道为离散对称信道。,精选ppt,离散对称信道的信道容量定理：如果一个离散对称信道具有n个输入符号，m个输出符号，则当输入为等概率分布时，达到信道容量C。,3.2单符号离散信道的信道容量,对于行可排列情况，Hmi与i无关,可以看出，当输出等概分布时，即H(Y)=log2m时达到信道容量。由于对称信道的特点，输入等概率分布输出等概率分布。,精选ppt,准对称离散信道信道矩阵的行可排列，列不可排列但把该矩阵在水平方向上分割，则各子矩阵皆具可排列性例关键H(Y)最大(改变p(xi)时),3.2单符号离散信道的信道容量,思考：p(xi)应该怎样取值？P79,精选ppt,3.2单符号离散信道的信道容量,将H(Y)中的m项分解成s个子集M1,M2,Ms,各个子集分别有m1,m2,ms个元素(m1+m2+ms=m),则,则,精选ppt,3.2单符号离散信道的信道容量,由,故有,即,精选ppt,3.2单符号离散信道的信道容量,各个子矩阵具有可排列性,只要信源呈等概率分布，即可使第k个子集中的输出概率相等，即达到其均值。,相应的准对称信道的容量为,精选ppt,3.2单符号离散信道的信道容量,例,精选ppt,离散信道容量的一般计算方法P81,3.2单符号离散信道的信道容量,对于固定的信道，平均互信息I(X;Y)是信源概率分布p(xi)的上凸函数,所以极大值一定存在。I(X;Y)是n个变量p(ai)(i=1,2,n)的多元函数，并满足,所以可以用拉格朗日乘子法计算条件极值:,其中，为拉格朗日乘子,精选ppt,3.2单符号离散信道的信道容量,解方程组,可得一般信道容量C。由,I(X;Y)=H(Y)-H(Y|X),H(Y),H(Y|X),精选ppt,I(X;Y)最大值,3.2单符号离散信道的信道容量,令则,若m=n,则可求解,精选ppt,3.2单符号离散信道的信道容量,一般离散信道容量的求解步骤：,(1)(2)(3)(4),需要确认所有的，所求的C才存在。,精选ppt,3.2单符号离散信道的信道容量,例：,可列方程组：,精选ppt,解之得：,3.2单符号离散信道的信道容量,精选ppt,3.3多符号离散信道的信道容量,多符号离散信道的数学模型多符号离散信源X=X1X2Xk.XN在N个不同时刻分别通过单符号离散信道XP(Y/X)Y，在输出端出现Y=Y1Y2Yk.YN，形成一个新的信道，此即多符号离散信道。由于新信道相当于单符号离散信道在N个不同的时刻连续运用了N次，也称为单符号离散信道的N次扩展信道,基本概念,精选ppt,3.3多符号离散信道的信道容量,Xk取值:a1,a2,an,则X共有nN