信息论与编码ppt.ppt

1、a,1,信息论与编码,主讲：苗立刚 基础楼319,计算机与通信工程学院 2016年3月,a,2,课程目标与安排,它是信息处理方向的一门重要的专业基础课，是后续课程的基础，如通讯原理、数字图像处理、语音信号处理等。 介绍信息科学的基础理论和基本方法，课程将基于一个通讯系统的抽象数学模型进行展开，课程分为基础理论和编码理论两部分组成。 本课程以概率论为基础，数学推导较多，学习时主要把注意力集中到概念的理解上，不过分追求数学细节的推导。 注意基本概念的理解，不断加深概念的把握。学习时注意理解各个概念的“用处”，结合其他课程理解它的意义，而不要把它当作数学课来学习。,课程特点,a,3,学 时：32 考

2、试方式：开卷 考试成绩：平时成绩*20% + 考试成绩*80%,课程目标与安排,a,4,第一章 绪论 第二章 信源熵 第三章 信道容量 第四章 信息率失真函数 第五章 信源编码 第六章 信道编码 第七章 密码体制的安全性测度,课程内容安排,课程目标与安排,a,5,课程目标与安排,参考书,曲炜，朱诗兵，信息论基础及应用，清华大学出版社，2005 信息论与编码，陈运、周亮、陈新，电子工业出版社，2007 傅祖芸，信息论与编码，电子工业出版社，2004 周荫清，信息论基础(第3版)，北京航空航天大学出版社，2006,有关的课程,高等数学，概率论，线性代数,a,6,第一章 绪论,信息论基础,主讲：苗立

3、刚 基础楼318,计算机与通信工程学院 2014年3月,a,7,第一章 绪论,信息的有关概念 通讯系统模型 信息论的形成和发展历史,本章主要讨论的问题：,a,8,信息的有关概念,“信息”是信息论中最基本、最重要的概念，它是一个既抽象又复杂的概念，目前还没有一个统一的定义(百余种)； “信息”不同于消息 在现代信息论形成之前，信息一直被看作是通信中消息的同义词，没有严格的数学含义； 所谓消息，是用文字、符号、数据、语言、图片、图像等形式，把客观事物运动和主观思维活动的状态表达出来； 消息是信息的载体；消息是表现形式，信息是实质。 “信息”不同于情报 情报往往是军事学、文献学方面的习惯用词，它的含

4、义比“信息”窄的多，一般只限于特殊的领域，是一类特殊的信息； “情报”是人们对于某个特定对象所见、所闻、所理解产生的知识；,a,9,“信息”不同于知识 知识是人们根据某种目的,从自然界收集得来的数据中整理、概括、提取得到的有价值的信息，是一种高层次的信息； 知识是信息，但不等于信息的全体； “信息”不同于信号 把消息变换成适合信道传输的物理量，就是信号；信号是承载消息的物理量；,信息的有关概念,a,10,信息的有关概念,信息的几种定义 以信源为主的信息定义、以信道为主的信息定义和以信宿为主的信息定义。 以信源为主的信息定义有： 1)信息是事物之间的差异(Longo,1975) 2)信息是有序性

5、的度量(Wiener,1948) 以信道为主的信息定义有： 1)信息是通信传输的内容(Wiener,1950) 2)信息是人与外界相互作用的过程中所交换的内容的名称(Wiener,1948) 以信宿为主的信息定义有： 1)信息是用来消除随机不定性的东西 (Shannon,1948） 2)信息是使概率分布发生变动的东西 （Tribes etal, 1971）,a,11,仙农从研究通信系统传输的实质出发，对信息做出了科学的定义； 仙农注意到：收信者在收到消息之前是不知道消息的具体内容的。通信系统消息的传输对收信者来说，是一个从不知到知的过程，或者从知之甚少到知之甚多的过程，或是从不确定到部分确定或

6、全部确定的过程。 因此, 对于收信者来说, 通信过程是消除事物状态的不确定性的过程，不确定性的消除，就获得了信息，原先的不确定性消除的越多，获得的信息就越多； “信息”是事物运动状态或存在方式的不确定性的描述，这就是仙农关于信息的定义。,信息的有关概念,a,12,信息的度量,信息的度量（信息量）和不确定性消除的程度有关，消除了多少不确定性，就获得了多少信息量； 不确定性就是随机性，可以用概率论和随机过程来测度不确定性的大小，出现概率小的事件，其不确定性大，反之，不确定性小； 由以上两点可知：概率小 信息量大，即信息量是概率的单调递减函数； 此外，信息量应该具有可加性；,a,13,信息的度量,由

7、于信息量与概率成反比，并且具有可加性，可以证明，信息量的计算式为 其中pk是事件xk发生的概率，这也是仙农关于(自)信息量的度量(概率信息)，单位为bit,哈特莱早在20世纪20年代就提出用对数作为信息量的测度。哈特莱认为：消息和信息不同，多种多样、千姿百态的消息是信息的载体，消息究竟包含了多少信息，应该用消息出现的概率的对数来计算，从而他为信息度量找到了对数这一数学理论。,a,14,通讯系统模型,信源,编码器,信道,译码器,干扰源,通信系统基本模型,消息,信号,消息,信宿,噪声,信源：消息的来源，如文字、语音、图像等 编码器：把消息变换成信号，如信源编码、纠错编码、调制器 信道：传递信号的媒

8、介，如电缆、光纤、无线电波等 噪声：信道中的干扰，如加性干扰、乘性干扰 译码器：把信道输出的信号反变换，解调器、纠错译码器、信源译码器 信宿：信息的接受端，接收消息的人或物,a,15,通讯系统模型,信源：消息的来源 编码器：把消息变换成信号 信道：传递信号的媒介 译码器：把信道输出的信号反变换 信宿：信息的接受端 噪声：信道中的干扰,信源编码器：把信源发出的消息变换成由二进制码元（或多进制码元）组成的代码组以提高通信系统传输消息的效率。信源编码可分为无失真信源编码和限失真信源编码。目的：提高信息传输的有效性 信道编码器：在信源编码器输出的代码组上有目的地增加一些监督码元，使之具有检错或纠错的能

9、力。 目的：提高信息传输的可靠性 密码学：研究如何隐蔽消息中的信息内容，使它在传输过程中不被窃听，提高通信系统的安全性。 目的：提高信息的安全性,编码问题可分解为三类：信源编码、信道编码和密码,在实际问题中，上述三类编码应统一考虑来提高通信系统的性能。这些编码的目标往往是相互矛盾的。,a,16,电报常用的莫尔斯码就是按信息论的基本编码原则设计出来的； 在一些商品上面有一张由粗细条纹组成的标签，从这张标签可以得知该商品的生产厂家、生产日期和价格等信息，这些标签是利用条形码设计出来的，非常方便，非常有用，应用越来越普遍； 计算机的运算速度很高，要保证它几乎不出差错，相当于要求有100年的时间内不得

10、有一秒钟的误差，这就需要利用纠错码来自动地及时地纠正所发生的错误； 每出版一本书，都给定一个国际标准书号（ISBN），大大方便图书的销售、编目和收藏工作。,编码的应用的几个例子：,通讯系统模型,a,17,信息论的形成和发展,信息论是在长期通信工程的实践中，由通信技术与概率论、随机过程和数理统计相结合而逐步发展起来的一门科学。 奈魁斯特：在1924年研究影响电报传递速度的因素时,就察觉到信息传输速度和频带宽度有关系; 哈特莱(Hartley)：在1928年用概率的观点来分析信息传输问题; 仙农（Claude E.Shannon)：1948年发表通信的数学理论(A Mathematical The

11、ory of Communication),为创立信息论作出了决定性的贡献;香农因此成为信息论的奠基人。 维纳(N. Wiener)等：为信息论的进一步发展和拓展作了大量工作;主要在通信的统计理论与滤波器理论方面。,a,18,第二章 信源熵,信息论基础,主讲：苗立刚 基础楼318,计算机与通信工程学院 2014年3月,a,19,第二章 信源熵,2.1 单符号离散信源 2.2 多符号离散平稳信源 2.3 连续信源 2.4 离散无失真信源编码定理,本章主要讨论的问题：,a,20,2.1单符号离散信源,单符号离散信源的数学模型,单符号信源信源每次输出一个符号,用离散随机变量描述 多符号信源信源每次输

12、出多个符号(符号序列)，用离散随 机矢量描述 离散信源信源符号取值离散，包括单符号和多符号信源 连续信源信源符号取值连续，用随机过程描述 结论 从概率、随机变量(过程)来研究信息 信息对事物状态(存在方式)不确定性的描述,a,21,2.1单符号离散信源,单符号离散信源的数学模型,注意：大写字母X,Y,Z代表随机变量，小写字母代 表随机事件。,a,22,概率复习,a,23,2.1单符号离散信源,由于信息量与概率成反比，并且具有可加性，自信息量的定义为： 其中p(xi)是事件xi发生的概率，这也是仙农关于(自)信息量的度量(概率信息) 计算信息量主要要注意有关事件发生概率的计算; 性质：非负;单调

13、递减；当p(xi) =0时,I(xi) ,不可能事件；当p(xi)=1时， I(xi)0 ，确定事件 自信息量 I(xi) 的含义 当事件xi发生以前，表示事件xi发生的不确定性； 当事件xi发生以后，表示事件xi所提供的信息量；,自信息量（单个随机事件）,a,24,例1：从26个英文字母中，随即选取一个字母，则该事件的自信息量为 I = -log2(1/26) = 4.7 比特 例2：设m比特的二进制数中的每一个是等概率出现的(这样的数共有2m个)，则任何一个数出现的自信息为: I = -log2(1/ 2m) = m 比特/符号,自信息量的单位 自信息量的单位取决于对数的底； 底为2，单位

14、为“比特（bit）”； 底为e，单位为“奈特（nat）”； 底为10，单位为“哈特（hat）”； 1 nat = 1.44bit , 1 hat = 3.32 bit；,2.1单符号离散信源,a,25,例3：设天气预报有两种消息，晴天和雨天，出现的概率分别为1/4和3/4，我们分别用 来表示晴天，以 来表示雨天，则我们的信源模型如下：,2.1单符号离散信源,a,26,联合自信息量(两个随机事件),二维联合集XY上的元素(xiyj)的联合自信息量定义为： 含义 X=xi，Y=yj 同时发生时，带来的信息量 特例 若X、Y 独立，则I(xiyj) = I(xi) + I(yj),2.1单符号离散信

15、源,a,27,条件自信息量（两个随机事件）,二维联合集XY中，对事件xi和yj，事件xi在事件yj给定的条件下的条件信息量定义为：,联合自信息量和条件自信息量也满足非负和单调递减性。 关系 当X和Y独立时，,2.1单符号离散信源,a,28,互信息量(两个随机事件),2.1单符号离散信源,a,29,信源发出消息 的概率 称为先验概率，信宿收到 后推测信源发出 的概率称为后验概 率 。 定义 的后验概率与先验概率比值的对数为 对 的互信息量，用 表示，即 互信息量等于自信息量减去条件自信息量。 第三种表达方式：,2.1单符号离散信源,a,30,含义互信息I(xi;yj) = 自信息I(xi) -

16、条件自信息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单符号离散信源,a,31,I(xi;yj) 可为正、负、0的举例 设yj代表“闪电”，则 当xi代表“打雷”时，I(xi|yj) =

17、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单符号离散信源,a,32,条件互信息量(三个随机事件),联合集XYZ中,给定条件 下， 与 之间的互信息量，其定义式,互信息量,2.1单符号离散信源,a,33,平均自信息量(信源熵)-随机变量,单位 bit/(信源)符号,这个平均自信息量的表达式和统计物理学中热熵的表达式很相似。在统计物理学中，热熵是一个物理系统杂乱性（

18、无序性）的度量。这在概念上也有相似之处。因而就借用“熵”这个词把平均自信息量H(X)称为“信源熵”。,通常研究单独一个事件或单独一个符号的信息量是不够的，往往需要研究整个事件集合或符号序列(如信源)的平均的信息量(总体特征)，这就需要引入新的概念；定义自信息的数学期望为信源的平均信息量,2.1单符号离散信源,a,34,例：天气预报，有两个信源,则：,说明第二个信源的平均不确定性更大一些,信息熵具有以下三种物理含义： 1、表示信源输出前，信源的平均不确定性 2、表示信源输出后，每个符号所携带的平均信息量 3、反映了变量X的随机性。,2.1单符号离散信源,a,35,例：设某信源输出四个符号，其符号

19、集合的概率分布为： 则其熵为：,2.1单符号离散信源,a,36,例：电视屏上约有 500 600= 3105个格点，按每点有10个不同的灰度等级考虑，则共能组成n=103x105个不同的画面。按等概率1/103x105计算，平均每个画面可提供的信息量为,=31053.32 比特/画面,例：有一篇千字文章，假定每字可从万字表中任选，则共有不同的千字文N=100001000=104000篇。仍按等概率1/100001000计算，平均每篇千字文可提供的信息量为 H（X）log2N4103332=1.3104 比特千字文,“一个电视画面”平均提供的信息量远远超过“一篇千字文”提供的信息量。,2.1单符

20、号离散信源,a,37,熵函数的数学特性,熵函数可以表示为：,二元熵：,性质1：非负性,H(X)0 由于0pi1,所以logpi0，logpi0，则总有H(X)0。,2.1单符号离散信源,a,38,性质2：对称性,根据加法交换律可以证明，当变量交换顺序时熵函数的值不变。信源的熵只与概率空间的总体结构有关，而与个概率分量对应的状态顺序无关；,性质3：扩展性,这说明信源空间中增加某些概率很小的符号，虽然当发出这些符号时，提供很大的信息量，但由于其概率接近于0，在信源熵中占极小的比重，使信源熵保持不变。,2.1单符号离散信源,a,39,性质4：可加性,性质5：极值性,上式表明，对于具有n个符号的离散信

21、源，只有在n个信源符号等可能出现的情况下，信源熵才能达到最大值，这也表明等概分布的信源的平均不确定性最大，这是一个很重要得结论，称为最大离散熵定理,例：对于一个二元信源 H(X)=H(1/2,1/2)=log2=1bit,H(X)= -plog2p (1-p)log2(1-p)=H(p),2.1单符号离散信源,a,40,性质6：确定性,当信源X的信源空间X，P中。任一个概率分量等于1，根据完备空间特性，其它概率分量必为0，这时信源为一个确知信源，其熵为0。如果一个信源的输出符号几乎必然为某一状态，那么这个信源没有不确定性，信源输出符号后不提供任何信息量。,性质7：上凸性,是概率分布(p1,p2

22、,pq)的严格上凸函数。,2.1单符号离散信源,a,41,设f(X)=f(x1,x2,xn)为一多元函数。若对于任意一个小于1的正数 （0= f(X1)+(1- )f(X2) 则称f(X)为定义域上的上凸函数。 若“=”不成立，则为严格上凸函数 若“=”,则为下凸函数 若“”,则为严格下凸函数,2.1单符号离散信源,a,42,H（p）函数曲线如图所示。如果二元信源的输出符号是确定的，即p=1或q=1，则该信源不提供任何信息。反之，当二元信源符号0和1以等概率发生时，信源熵达到极大值，等于1比特信息量。,2.1单符号离散信源,a,43,信源熵是从整个信源的统计特性来考虑的，它是从平均意义上来表征

23、信源的总体信息测度的。对于某特定的信源（概率空间给定），其信源熵是一个特定的值。不同的信源因统计特性不同，其熵也不同。信源熵用以表征信息源的平均不确定性，平均自信息量是消除信源不确定性时所需信息的量度，即收到一个信源符号，全部解除了这个符号的不确定性。或者说获得这样大的信息量后，信源不确定性就被消除了。,2.1单符号离散信源,a,44,信源熵和平均自信息量两者在数值上相等，但含义不同。某一信源，不管它是否输出符号，只要这些符号具有某些概率特性，就必有信源的熵值；这熵值在总体平均上才有意义，因而是一个确定的值。而另一方面，信息量则只有当信源输出的符号被接收者收到后才有意义，信息量就是给予接收者的

24、信息度量，该值本身可以是随机量，也可以与接收者的情况有关。,因此说信源熵是信源的平均不确定性的描述，一般情况下它并不等于平均获得的信息量。只是在无噪情况下，接收者才能正确无误地接收到信源所发出的信息，消除了信源熵H（X）值大小的平均不确定性，所以获得的平均信息量就等于信源熵H（X）的值。在一般情况下获得的信息量是两熵之差，并不是信源熵本身。,2.1单符号离散信源,a,45,条件熵,思考：求条件熵时为什么要用联合概率加权？,条件熵是在联合符号集合XY上的条件自信息量的数学期望。在已知随机变量X的条件下，随机变量Y的条件熵定义为：,2.1单符号离散信源,a,46,条件概率,并且,当已知特定事件xi

25、出现时，下一个出现的是yj 的不确定性为：,对集合Y中所有元素统计平均，其熵为：,上述熵值再对集合Y中的元素做统计平均，得条件熵：,同理可得：,a,47,条件熵H(X/Y)是一个确定值，表示信宿在收到Y后，信源X仍然存在的不确定度。这是信道干扰所造成的。有时称H(X/Y)为信道疑义度，也称损失熵。 如果没有干扰，H(X/Y)=0,一般情括下H(X/Y)小于H(X)，说明经过信道传输，总能消除一些信源的不确定性，从而获得一些信息。 条件熵H(Y/X)也是一个确定值,表示信源发出X后，信宿仍然存在的不确定度。这是由于噪声引起的。也称为噪声熵。,2.1单符号离散信源,a,48,联合熵（共熵）,联合离

26、散符号集合XY上的每个元素对 的联合自信息量的数学期望。,说明: 联合熵H（XY）表示X和Y同时发生的不确定度。,2.1单符号离散信源,a,49,加权熵（自学）,对香农熵引入主观因素效用权重系数(重量) 定义： 设信源X 则加权熵 Hw(X) 含义 消息xi 的权重wi对I(xi)的加权平均 性质：略,2.1单符号离散信源,a,50,从通信系统角度看熵的意义,H(X)：表示信源边每个符号的平均信息量（信源熵）； H(Y)：表示信宿边每个符号的平均信息量（信宿熵）； H(X|Y):信道疑义度(含糊度)，表示在输出端接收到Y后，发送端X尚存的平均不确定性。这个对X尚存的不确定性是由于信道干扰引起的

27、。 H(Y|X):噪声熵，表示在已知X后，对于输出Y尚存的平均不确定性； H(XY):表示整个信息传输系统的平均不确定性；,2.1单符号离散信源,a,51,各种熵的性质,联合熵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)

28、 = 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单符号离散信源,a,57,I(X;Y)是二元函数:P(X)的上凸函数，P(Y|X)的下凸函数,平均互信息的凸状性,2.1单符号离散信源,a,58,定理2.1 对于固定的信道，平均互信息I(X;Y)是信源概率分布P(X)的上凸函数,这就是说，对于一定的信

29、道转移概率分布P(Y|X)，总可以找到某一个先验概率分布的信源X，使平均交互信息量I(X;Y)达到相应的最大值Imax，这时称这个信源为该信道的匹配信源。可以说，不同的信道转移概率对应不同的Imax。,2.1单符号离散信源,a,59,例：对于二元对称信道,如果信源分布X=p,1-p，则,2.1单符号离散信源,a,60,2.1单符号离散信源,而：,所以：,当信道固定时，q为一个固定常数，平均互信息是信源分布的上凸函数，最大只为1-H(q)。图示曲线表明，对于固定信道，输入符号X的概率分布不同时，在接收端平均每个符号所获得的信息量就不同。当输入符号为等概率分布时，平均互信息量为最大值，接收每个符号

30、所获得的信息量最大。信道容量的理论基础,a,61,定理2.2 对于固定的信源，平均互信息I(X;Y)信道传递概率分布P(Y|X)的下凸函数,这就是说，对于一个已知先验概率为p的离散信源，总可以找到某一个转移概率分布的信道q，使平均互信息量达到相应的最小值Imin。,2.1单符号离散信源,a,62,例：对于二元对称信道,当信源固定后，p为一个固定常数，改变信道特性q可获得不同的平均互信息I(X;Y)。当q=1/2时，I(X;Y)=0,即在信道输出端获得的信息最小，这意味着信源的信息全部损失在信道中，这是一种最差的信道，其噪声最大。信息率失真理论的基础。,2.1单符号离散信源,a,63,对于无损信

31、道，有 I(X;Y) = H(X) = H(Y) = H(XY) H(X/Y)=H(Y/X)=0 对于全损信道，有 I(X; Y) = 0 H(X/Y)=H(X)； H(Y/X)=H(Y),2.1单符号离散信源,a,64,数据处理定理(自学) I(X;Z) I(Y;Z) I(X;Z) I(X;Y) 意义 信息不增原理 每经一次处理，可能丢失一部分信息,2.1单符号离散信源,a,65,各类熵与集合图的类比,2.1单符号离散信源,a,66,信道中熵的信息流图,H(Y|X) :噪声熵； H(X|Y) :信道疑义度； 它们都是由于噪声干扰的存在而存在的。信道中存在噪声干扰，是减低信道传信能力的基本原因

32、。,2.1单符号离散信源,a,67,各种熵之间的关系,a,68,例,2.1单符号离散信源,a,69,a,70,a,71,作业： 2.4(P68), 2.6(P68), 2.7(P68), 2.10(P68),a,72,2.2多符号离散平稳信源,a,73,离散无记忆信源：发出的各个符号是相互独立的，发出的符号序列中的各个符号之间没有统计关联性，各个符号的出现概率是它自身的先验概率。 离散有记忆信源：所发出的各个符号的概率是有关联的。 发出单个符号的信源：是指信源每次只发出一个符号代表一个消息； 发出符号序列的信源：是指信源每次发出一组含二个以上符号的符号序列代表一个消息。 发出符号序列的有记忆信

33、源：是指用信源发出的一个符号序列的整体概率（即联合概率）反映有记忆信源的特征。 发出符号序列的马尔可夫信源：是指某一个符号出现的概率只与前面一个或有限个符号有关，而不依赖更前面的那些符号，这样的信源可以用信源发出符号序列内各个符号之间的条件概率来反映记忆特征。,2.2多符号离散平稳信源,a,74,2.2多符号离散平稳信源,离散无记忆信源 发出单个符号的无记忆信源（最简单的离散信源）,自信息量 信源熵,a,75,2.2多符号离散平稳信源,离散无记忆信源的扩展信源,实际信源输出的消息往往是时间上或空间上的一系列符号，如电报系统，序列中前后符号间一般是有统计依赖关系的。 离散无记忆二进制信源X的二次

34、扩展信源 我们先讨论离散无记忆信源，此时，信源序列的前后符号之间是统计独立的. 如在二元系统中，我们可以把两个二元数字看成一组，会出现四种可能情况：00、01、10和11，我们可以把这四种情况看成一个新的信源称为二元无记忆信源的二次扩展信源，相应的，如果把N个二元数字看成一组，则新的信源称为二元无记忆信源的N次扩展信源。,a,76,则该信源的N次扩展信源为：,一般情况下，设一个离散无记忆信源为：,离散无记忆二进制信源X的三次扩展信源 离散无记忆信源X的N次扩展信源,2.2多符号离散平稳信源,a,77,根据信息熵的定义：,可以证明，对于离散无记忆的扩展信源,N次扩展信源的熵,2.2多符号离散平稳

35、信源,注意： (1)单位:bit/sign,但含义不同 (2)N次扩展信源的熵等于各符号熵之和,a,78,例: 离散无记忆信源的N次扩展信源 离散无记忆信源为：X:a1,a2,a3; P(X):1/4, 1/2, 1/4,2次扩展信源为：,:A1,A9,信源的9个符号为：,其概率关系为 :,2.2多符号离散平稳信源,a,79,计算可知,2.2多符号离散平稳信源,a,80,2.2多符号离散平稳信源,离散平稳信源,一般来说，信源的前后消息之间有前后依赖关系，可以用随机矢量描述：,信源在某一时刻发出什么样的值取决于两方面 1、这一时刻该变量的概率分布 2、这一时刻以前发出的消息 如一个人讲话 我们现

36、在讨论平稳的随机序列，所谓平稳是指序列的统计性质与时间的推移无关（俩个任意时刻信源发出符号的概率分布完全相同）。信源所发符号序列的概率分布与时间的起点无关，这种信源我们称之为离散序列平稳信源。,a,81,2.2多符号离散平稳信源,a,82,2.2多符号离散平稳信源,离散平稳信源的熵,最简单的平稳信源二维平稳信源，信源发出序列中只有前后两个符号间有依赖关系，我们可以对其二维扩展信源进行分析。 信源的概率空间:,假定X=X1X2 ,则可得到一个新的信源,a,83,2.2多符号离散平稳信源,根据信息熵的定义，可得： (1)联合熵,可以表征信源输出长度为2的符号的平均不确定性，或所含有的信息量。因此可

37、以用 作为二维平稳信源的信息熵的近似值,(2)条件熵,则：,a,84,2.2多符号离散平稳信源,另外还可以得到：,只有信源统计独立时等号成立。 结论：二维离散平稳有记忆信源的熵小于等于二维平稳无记忆信源的熵。,可以证明：,a,85,例 设某二维离散信源的原始信源的信源空间 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;

38、原始信源的熵为： H(X)=1.5 bit/符号 条件熵： H(X2|X1)=1.4 bit/符号 可见： H(X2|X1)0 I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X) H(X)H(Y),思考：p(x)应该怎样取值？,a1 a2 a3,b1 b2 b3 b4 b5,a,142,3.2单符号离散信道的信道容量,确定信道：多对一（nm）,具有归并性的无噪信道,信道矩阵：每行只有一个元素“1”，其它全是0,损失熵 H(X/Y) 0 噪声熵 H(Y/X) = 0 I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(Y) H(X) H(Y),思考：p(x)应该

39、怎样取值？,a,143,强对称离散信道(均匀信道),3.2单符号离散信道的信道容量,信道特点 信道输入、输出均为n元 每符号正确传输概率均为 其他符号错误传输概率为p/(n-1) 矩阵特点 (1)nn阶对称阵 (2)每行和为1,每列和为1,a,144,3.2单符号离散信道的信道容量,信道容量,可以看出，当输出等概分布时，即H(Y)=log2n时达到信道容量。,a,145,3.2单符号离散信道的信道容量,那么，在什么样的信源输入情况下，信道输出能等概分布呢？可以证明，输入等概分布时，离散对称信道的输出也为等概分布,结论对强对称信道，输入等概输出等概，可达到C,a,146,3.2单符号离散信道的信

40、道容量,二进制对称信道(n=2),a,147,3.2单符号离散信道的信道容量,行可排列矩阵每行各元素都来自同一集合Q Qq1,q2,qm(排列可不同) 列可排列矩阵每列各元素都来自同一集合P Pp1,p2,pn(排列可不同) 矩阵可排列矩阵的行、列皆可排列 对称信道信道矩阵可排列,离散对称信道,(1)m=n 时，Q、P为同一集合 mn时，Q、P中，一个必为另一个的子集 (2)输入等概输出等概,a,148,3.2单符号离散信道的信道容量,离散输入对称信道 如果一个离散无记忆信道的信道矩阵中，每一行都是其他行的同一组元素的不同排列，则称此类信道为离散输入对称信道。,离散输出对称信道 如果一个离散无

41、记忆信道的信道矩阵中，每一列都是其他列的同一组元素的不同排列，则称此类信道为离散输出对称信道。,a,149,3.2单符号离散信道的信道容量,离散对称信道 如果一个离散无记忆信道的信道矩阵中，每一行都是其他行的同一组元素的不同排列，并且每一列都是其他列的同一组元素的不同排列，则称此类信道为离散对称信道。,a,150,离散对称信道的信道容量 定理：如果一个离散对称信道具有n个输入符号，m个输出符 号，则当输入为等概率分布时，达到信道容量C。,3.2单符号离散信道的信道容量,对于行可排列情况，Hmi与i 无关,可以看出，当输出等概分布时，即H(Y)=log2m时达到信道容量。 由于对称信道的特点，输入等概率分布输出等概率分布。,a,151,准对称离散信道 信道矩阵的行可排列，列不可排列 但把该矩阵在水平方向上分割， 则各子矩阵皆具可排列性 例 关键H(Y)最大(改变p(xi)时),3