信息论与编码

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

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

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

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

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

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

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

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

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

10、书，都给定一个国际标准书号（ISBN），大大方便图书的销售、编目和收藏工作。,编码的应用的几个例子：,通讯系统模型,.,信息论的形成和发展,信息论是在长期通信工程的实践中，由通信技术与概率论、随机过程和数理统计相结合而逐步发展起来的一门科学。 奈魁斯特：在1924年研究影响电报传递速度的因素时,就察觉到信息传输速度和频带宽度有关系; 哈特莱(Hartley)：在1928年用概率的观点来分析信息传输问题; 仙农（Claude E.Shannon)：1948年发表通信的数学理论(A Mathematical Theory of Communication),为创立信息论作出了决定性的贡献;香农因此

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

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

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

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

15、和条件自信息量也满足非负和单调递减性。 关系 当X和Y独立时，,2.1单符号离散信源,.,互信息量(两个随机事件),2.1单符号离散信源,.,信源发出消息 的概率 称为先验概率，信宿收到 后推测信源发出 的概率称为后验概 率 。 定义 的后验概率与先验概率比值的对数为 对 的互信息量，用 表示，即 互信息量等于自信息量减去条件自信息量。 第三种表达方式：,2.1单符号离散信源,.,含义互信息I(xi;yj) = 自信息I(xi) - 条件自信息I(xi/yj) (1) I(xi)信宿收到yj之前，对信源发xi的不确定度 (2) I(xi|yj)信宿收到yj之后，对信源发xi的不确定度 (3)

16、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单符号离散信源,.,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)，

17、I(xi;yj)= 0 当xi代表“飞机正点起飞”时，I(xi|yj)I(xi)，I(xi;yj) 0,2.1单符号离散信源,.,条件互信息量(三个随机事件),联合集XYZ中,给定条件 下， 与 之间的互信息量，其定义式,互信息量,2.1单符号离散信源,.,平均自信息量(信源熵)-随机变量,单位 bit/(信源)符号,这个平均自信息量的表达式和统计物理学中热熵的表达式很相似。在统计物理学中，热熵是一个物理系统杂乱性（无序性）的度量。这在概念上也有相似之处。因而就借用“熵”这个词把平均自信息量H(X)称为“信源熵”。,通常研究单独一个事件或单独一个符号的信息量是不够的，往往需要研究整个事件集合或

18、符号序列(如信源)的平均的信息量(总体特征)，这就需要引入新的概念；定义自信息的数学期望为信源的平均信息量,2.1单符号离散信源,.,例：天气预报，有两个信源,则：,说明第二个信源的平均不确定性更大一些,信息熵具有以下三种物理含义： 1、表示信源输出前，信源的平均不确定性 2、表示信源输出后，每个符号所携带的平均信息量 3、反映了变量X的随机性。,2.1单符号离散信源,.,例：设某信源输出四个符号，其符号集合的概率分布为： 则其熵为：,2.1单符号离散信源,.,例：电视屏上约有 500 600= 3105个格点，按每点有10个不同的灰度等级考虑，则共能组成n=103x105个不同的画面。按等概

19、率1/103x105计算，平均每个画面可提供的信息量为,=31053.32 比特/画面,例：有一篇千字文章，假定每字可从万字表中任选，则共有不同的千字文N=100001000=104000篇。仍按等概率1/100001000计算，平均每篇千字文可提供的信息量为 H（X）log2N4103332=1.3104 比特千字文,“一个电视画面”平均提供的信息量远远超过“一篇千字文”提供的信息量。,2.1单符号离散信源,.,熵函数的数学特性,熵函数可以表示为：,二元熵：,性质1：非负性,H(X)0 由于0pi1,所以logpi0，logpi0，则总有H(X)0。,2.1单符号离散信源,.,性质2：对称性

20、,根据加法交换律可以证明，当变量交换顺序时熵函数的值不变。信源的熵只与概率空间的总体结构有关，而与个概率分量对应的状态顺序无关；,性质3：扩展性,这说明信源空间中增加某些概率很小的符号，虽然当发出这些符号时，提供很大的信息量，但由于其概率接近于0，在信源熵中占极小的比重，使信源熵保持不变。,2.1单符号离散信源,.,性质4：可加性,性质5：极值性,上式表明，对于具有n个符号的离散信源，只有在n个信源符号等可能出现的情况下，信源熵才能达到最大值，这也表明等概分布的信源的平均不确定性最大，这是一个很重要得结论，称为最大离散熵定理,例：对于一个二元信源 H(X)=H(1/2,1/2)=log2=1b

21、it,H(X)= -plog2p (1-p)log2(1-p)=H(p),2.1单符号离散信源,.,性质6：确定性,当信源X的信源空间X，P中。任一个概率分量等于1，根据完备空间特性，其它概率分量必为0，这时信源为一个确知信源，其熵为0。如果一个信源的输出符号几乎必然为某一状态，那么这个信源没有不确定性，信源输出符号后不提供任何信息量。,性质7：上凸性,是概率分布(p1,p2,pq)的严格上凸函数。,2.1单符号离散信源,.,设f(X)=f(x1,x2,xn)为一多元函数。若对于任意一个小于1的正数 （0= f(X1)+(1- )f(X2) 则称f(X)为定义域上的上凸函数。 若“=”不成立，

22、则为严格上凸函数 若“=”,则为下凸函数 若“”,则为严格下凸函数,2.1单符号离散信源,.,H（p）函数曲线如图所示。如果二元信源的输出符号是确定的，即p=1或q=1，则该信源不提供任何信息。反之，当二元信源符号0和1以等概率发生时，信源熵达到极大值，等于1比特信息量。,2.1单符号离散信源,.,信源熵是从整个信源的统计特性来考虑的，它是从平均意义上来表征信源的总体信息测度的。对于某特定的信源（概率空间给定），其信源熵是一个特定的值。不同的信源因统计特性不同，其熵也不同。信源熵用以表征信息源的平均不确定性，平均自信息量是消除信源不确定性时所需信息的量度，即收到一个信源符号，全部解除了这个符号

23、的不确定性。或者说获得这样大的信息量后，信源不确定性就被消除了。,2.1单符号离散信源,.,信源熵和平均自信息量两者在数值上相等，但含义不同。某一信源，不管它是否输出符号，只要这些符号具有某些概率特性，就必有信源的熵值；这熵值在总体平均上才有意义，因而是一个确定的值。而另一方面，信息量则只有当信源输出的符号被接收者收到后才有意义，信息量就是给予接收者的信息度量，该值本身可以是随机量，也可以与接收者的情况有关。,因此说信源熵是信源的平均不确定性的描述，一般情况下它并不等于平均获得的信息量。只是在无噪情况下，接收者才能正确无误地接收到信源所发出的信息，消除了信源熵H（X）值大小的平均不确定性，所以

24、获得的平均信息量就等于信源熵H（X）的值。在一般情况下获得的信息量是两熵之差，并不是信源熵本身。,2.1单符号离散信源,.,条件熵,思考：求条件熵时为什么要用联合概率加权？,条件熵是在联合符号集合XY上的条件自信息量的数学期望。在已知随机变量X的条件下，随机变量Y的条件熵定义为：,2.1单符号离散信源,.,条件概率,并且,当已知特定事件xi出现时，下一个出现的是yj 的不确定性为：,对集合Y中所有元素统计平均，其熵为：,上述熵值再对集合Y中的元素做统计平均，得条件熵：,同理可得：,.,条件熵H(X/Y)是一个确定值，表示信宿在收到Y后，信源X仍然存在的不确定度。这是信道干扰所造成的。有时称H(

25、X/Y)为信道疑义度，也称损失熵。 如果没有干扰，H(X/Y)=0,一般情括下H(X/Y)小于H(X)，说明经过信道传输，总能消除一些信源的不确定性，从而获得一些信息。 条件熵H(Y/X)也是一个确定值,表示信源发出X后，信宿仍然存在的不确定度。这是由于噪声引起的。也称为噪声熵。,2.1单符号离散信源,.,联合熵（共熵）,联合离散符号集合XY上的每个元素对 的联合自信息量的数学期望。,说明: 联合熵H（XY）表示X和Y同时发生的不确定度。,2.1单符号离散信源,.,加权熵（自学）,对香农熵引入主观因素效用权重系数(重量) 定义： 设信源X 则加权熵 Hw(X) 含义 消息xi 的权重wi对I(

26、xi)的加权平均 性质：略,2.1单符号离散信源,.,从通信系统角度看熵的意义,H(X)：表示信源边每个符号的平均信息量（信源熵）； H(Y)：表示信宿边每个符号的平均信息量（信宿熵）； H(X|Y):信道疑义度(含糊度)，表示在输出端接收到Y后，发送端X尚存的平均不确定性。这个对X尚存的不确定性是由于信道干扰引起的。 H(Y|X):噪声熵，表示在已知X后，对于输出Y尚存的平均不确定性； H(XY):表示整个信息传输系统的平均不确定性；,2.1单符号离散信源,.,各种熵的性质,联合熵H(XY)与熵H(X)及条件熵H(X/Y)之间存在下列关系: H(XY) H(X) H(Y/X ) H(XY)

27、H(Y) H(X/Y ),联合熵与信息熵的关系: H(XY) = H(X) H(Y),条件熵与信息熵的关系: H(Y|X) = H(Y) H(X|Y) = H(X),H(XY),H(X) H(Y) I(X; Y),2.1单符号离散信源,.,证明：,2.1单符号离散信源,.,互信息量和平均互信息量,互信息量表示先验的不确定性减去尚存的不确定性，这就是收信者获得的信息量； 互信息量可能为正数、负数、0； 对于无干扰信道，I(xi;yj) = I(xi)； 对于全损信道，I(xi;yj) = 0；,定义:,2.1单符号离散信源,.,为什么需要定义平均互信息量？ 互信息量 是定量地研究信息流通问题的重

28、要基础。但它只能定量地描述输入随机变量发出某个具体消息 ，输出变量出现某一个具体消息 时，流经信道的信息量；此外 还是随 和 变化而变化的随机变量。 互信息量不能从整体上作为信道中信息流通的测度。这种测度应该是从整体的角度出发，在平均意义上度量每通过一个符号流经信道的平均信息量。 定义互信息量 在联合概率空间 中的统计平均值为Y对X的平均互信息量，简称平均互信息，也称平均交互信息量或交互熵。,2.1单符号离散信源,.,平均互信息量 与其他熵的关系 I(X;Y) = H(X) - H(X|Y) 因为H(X),表示传输前信源的不确定性，而H(X/Y)表示收到一个符号后，对信源尚存的不确定性，所以二

29、者之差信道传递的信息量。 I(X;Y) = H(Y) - H(Y|X) I(X;Y)也表示输出端H(Y)的不确定性和已知X的条件下关于Y的不确定性之差，也等于发送前后关于Y的不确定性之差。 I(X;Y) = H(X) + H(Y) - H(X,Y) I(X;Y)确定通过信道的信息量的多少，因此称它为信道传输率或传信率。,2.1单符号离散信源,.,平均互信息量的性质 非负性：即I(X;Y) = 0 该性质表明，通过一个信道总能传递一些信息，最差的条件下，输入输出完全独立，不传递任何信息，互信息等于0，但决不会失去已知的信息。 极值性：即I(X;Y) = H(X) 一般来说，信道疑义度H(X|Y)

30、总是大于0，所以互信息总是小于信源的熵，只有当信道是无损信道时，信道疑义度等于0，互信息等于信源的熵。 对称性：即I(X;Y) = I(Y;X) I(Y;X)表示从X中提取关于的Y的信息量，实际上I(X,Y)和I(Y,X)只是观察者的立足点不同，对信道的输入X和输出Y的总体测度的两种表达形式,2.1单符号离散信源,.,I(X;Y)是二元函数:P(X)的上凸函数，P(Y|X)的下凸函数,平均互信息的凸状性,2.1单符号离散信源,.,定理2.1 对于固定的信道，平均互信息I(X;Y)是信源概率分布P(X)的上凸函数,这就是说，对于一定的信道转移概率分布P(Y|X)，总可以找到某一个先验概率分布的信

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

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

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

34、68), 2.6(P68), 2.7(P68), 2.10(P68),.,2.2多符号离散平稳信源,.,离散无记忆信源：发出的各个符号是相互独立的，发出的符号序列中的各个符号之间没有统计关联性，各个符号的出现概率是它自身的先验概率。 离散有记忆信源：所发出的各个符号的概率是有关联的。 发出单个符号的信源：是指信源每次只发出一个符号代表一个消息； 发出符号序列的信源：是指信源每次发出一组含二个以上符号的符号序列代表一个消息。 发出符号序列的有记忆信源：是指用信源发出的一个符号序列的整体概率（即联合概率）反映有记忆信源的特征。 发出符号序列的马尔可夫信源：是指某一个符号出现的概率只与前面一个或有限

35、个符号有关，而不依赖更前面的那些符号，这样的信源可以用信源发出符号序列内各个符号之间的条件概率来反映记忆特征。,2.2多符号离散平稳信源,.,2.2多符号离散平稳信源,离散无记忆信源 发出单个符号的无记忆信源（最简单的离散信源）,自信息量 信源熵,.,2.2多符号离散平稳信源,离散无记忆信源的扩展信源,实际信源输出的消息往往是时间上或空间上的一系列符号，如电报系统，序列中前后符号间一般是有统计依赖关系的。 离散无记忆二进制信源X的二次扩展信源 我们先讨论离散无记忆信源，此时，信源序列的前后符号之间是统计独立的. 如在二元系统中，我们可以把两个二元数字看成一组，会出现四种可能情况：00、01、1

36、0和11，我们可以把这四种情况看成一个新的信源称为二元无记忆信源的二次扩展信源，相应的，如果把N个二元数字看成一组，则新的信源称为二元无记忆信源的N次扩展信源。,.,则该信源的N次扩展信源为：,一般情况下，设一个离散无记忆信源为：,离散无记忆二进制信源X的三次扩展信源 离散无记忆信源X的N次扩展信源,2.2多符号离散平稳信源,.,根据信息熵的定义：,可以证明，对于离散无记忆的扩展信源,N次扩展信源的熵,2.2多符号离散平稳信源,注意： (1)单位:bit/sign,但含义不同 (2)N次扩展信源的熵等于各符号熵之和,.,例: 离散无记忆信源的N次扩展信源 离散无记忆信源为：X:a1,a2,a3

37、; P(X):1/4, 1/2, 1/4,2次扩展信源为：,:A1,A9,信源的9个符号为：,其概率关系为 :,2.2多符号离散平稳信源,.,计算可知,2.2多符号离散平稳信源,.,2.2多符号离散平稳信源,离散平稳信源,一般来说，信源的前后消息之间有前后依赖关系，可以用随机矢量描述：,信源在某一时刻发出什么样的值取决于两方面 1、这一时刻该变量的概率分布 2、这一时刻以前发出的消息 如一个人讲话 我们现在讨论平稳的随机序列，所谓平稳是指序列的统计性质与时间的推移无关（俩个任意时刻信源发出符号的概率分布完全相同）。信源所发符号序列的概率分布与时间的起点无关，这种信源我们称之为离散序列平稳信源。

38、,.,2.2多符号离散平稳信源,.,2.2多符号离散平稳信源,离散平稳信源的熵,最简单的平稳信源二维平稳信源，信源发出序列中只有前后两个符号间有依赖关系，我们可以对其二维扩展信源进行分析。 信源的概率空间:,假定X=X1X2 ,则可得到一个新的信源,.,2.2多符号离散平稳信源,根据信息熵的定义，可得： (1)联合熵,可以表征信源输出长度为2的符号的平均不确定性，或所含有的信息量。因此可以用 作为二维平稳信源的信息熵的近似值,(2)条件熵,则：,.,2.2多符号离散平稳信源,另外还可以得到：,只有信源统计独立时等号成立。 结论：二维离散平稳有记忆信源的熵小于等于二维平稳无记忆信源的熵。,可以证

39、明：,.,例 设某二维离散信源的原始信源的信源空间 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.5 bit/符号 条件熵： H(X2|X1)=1.4 bit/符号 可见： H(X2|X1)H(X) 二维信源的熵：H(X1X2)=H(X1)+H(X2|X1)=2.9 bit/消息 每个信

40、源符号提供的平均信息量为： H2(X1X2)=H(X1X2)/2=1.45 bit/符号。,2.2多符号离散平稳信源,.,2.2多符号离散平稳信源,.,对于离散平稳信源，当 时，具有以下性质： N给定时，平均符号熵 条件熵； 平均符号熵 随N增加是非递增的； 条件较多的熵必小于或等于条件较少的熵，而条件熵必小于等于无条件熵。,对于二维离散平稳信源，条件熵等于极限熵，因此条件熵就是二维离散平稳信源的真实熵。对于一般信源，求出极限熵是很困难的，然而，一般来说，取N不大时就可以得到与极限熵非常接近的条件熵和平均符号熵，因此可以用条件熵和平均符号熵来近似极限熵,2.2多符号离散平稳信源,.,课堂练习：

41、 分别写出I(xi),I(xiyj),I(xi|yj),I(xi;yj),H(X), H(Y),H(XY),H(X|Y),H(Y|X),I(X;Y)的表达式，并说 明其含义。,2.2多符号离散平稳信源,.,2.2多符号离散平稳信源,马尔可夫信源,在很多信源的输出序列中，符号之间的依赖关系是有限的，任何时刻信源符号发生的概率只与前边已经发出的若干个符号有关，而与更前面的符号无关。 为了描述这类信源除了信源符号集外还要引入状态集。这时，信源输出消息符号还与信源所处的状态有关。 若一个信源满足下面两个条件，则称为马尔可夫信源： （1）某一时刻信源输出的符号的概率只与当前所处的状态有关，而与以前的状态

42、无关； （2）信源的当前状态由当前输出符号和前一时刻信源状态唯一确定。,.,2.2多符号离散平稳信源,当信源在(m+1)时刻发出符号 时，我们可把sj看成另一种状态：,m时刻的状态,m+1时刻的状态,所谓“状态”，指与当前输出符号有关的前m个随机变量序列(X1X2Xm)的某一具体消息，用si表示，把这个具体消息看作是某个状态。,.,2.2多符号离散平稳信源,某一时刻信源输出的符号的概率只与当前所处的状态有关，而与以前的状态无关。或者说只与此前已输出的若干个符号有关。即,把此前已输出的符号视为状态,信源的当前状态由当前输出符号和前一时刻信源状态唯一确定。,该条件表明，若信源处于某一状态 ，当它发

43、出一个符号 后，所处的状态就变了，一定转移到另一状态。状态的转移依赖 于发出的信源符号，因此任何时刻信源处在什么状态完全由前一 时刻的状态和当前发出的符号决定。将信源输出符号的不确定性 问题变换为讨论信源状态转换问题。状态之间的一步转移概率为: p(sj|si),.,2.2多符号离散平稳信源,由上例可知，m阶马尔可夫信源符号集共有n个符号，则信源共有 个不同状态。信源在某一时刻时，必然处于某一种状态，等到下一个符号输出时，转移到另外一个状态。,从而得到马尔可夫信源的状态空间。,其状态转移图如下页。在状态转换图中，把信源的每一种状态用圆圈表示，用有向箭头表示信源发出某一符号后由一种状态到另一状态

44、的转移。,.,例：设有一二进制一阶马尔可夫信源，信源符号集为1,0， 条件概率定为：P(0|0)=0.25 P(0|1)=0.50 P(1|0)=0.75 P(1|1)=0.50 由于信源符号数q=2，因此二进制一阶信源仅有两个状态： S0=0,S1=1. 由条件概率求得信源的状态转移概率为： P(S1|S1)=0.25; P(S1|S2)=0.50; P(S2|S1)=0.75; P(S2|S2)=0.50.,2.2多符号离散平稳信源,.,例 设信源符号 Xx1, x2, x3 ，信源所处的状态Se1, e2, e3, e4, e5 。各状态之间的转移情况由下图给出。,2.2多符号离散平稳信

45、源,.,将图中信源在ei状态下发符号xk 的条件概率p(xk /ei)用矩阵表示,可以看出,.,2.2多符号离散平稳信源,M阶马尔可夫信源的平均信息量，即信源的极限熵,.,马尔可夫链的平稳分布 若齐次马尔可夫链对一切i,j存在不依赖于i的极限,则称其具有遍历性，p(si)称为平稳分布。,2.2多符号离散平稳信源,且满足,.,2.2多符号离散平稳信源,.,2.2多符号离散平稳信源,对于由二元信源X0,1得到的状态空间(s1,s2,s3,s4),容易验证 求出稳定状态下的p(sj) ，称为状态极限概率。 将一步转移概率代入上式得 p(s1) = 0.8 p(s1)+0.5 p(s3) p(s2)

46、= 0.2 p(s1)+0.5 p(s3) p(s3) = 0.5 p(s2)+0.2 p(s4) p(s4) = 0.5 p(s2)+0.8 p(s4),.,2.2多符号离散平稳信源,解方程组得 p(s1)= p(s4)=5/14 p(s2)= p(s3)=2/14 计算极限熵,.,2.2多符号离散平稳信源,信源的相关性和剩余度,平均符号熵随N增加是非递增的,也就是说信源输出符号间的相关程度越长，信源的实际熵越小，趋近于极限熵；若相关程度减小，信源实际熵增大。,当信源输出符号间彼此不存在依存关系，且为等概率分布时，信源实际熵趋于最大熵H0,为了衡量信源的相关程度，引入信源剩余度(冗余度)的概

47、念。,.,冗余度（多余度、剩余度）表示给定信源在实际发出消息时所包含的多余信息。冗余度来自两个方面： 一是信源符号间的相关性，由于信源输出符号间的依赖关系使得信源熵减小，这就是信源的相关性。相关程度越大，信源的实际熵越小，趋于极限熵H(X)；反之相关程度减小，信源实际熵就增大。 另一个方面是信源符号分布的不均匀性，当等概率分布时信源熵最大。而实际应用中大多是不均匀分布，使得实际熵减小。当信源输出符号间彼此不存在依赖关系且为等概率分布时，信源实际熵趋于最大H0(X)。,相对熵率 = H/H0 冗余度 R = 1 - ,2.2多符号离散平稳信源,.,自然语言的熵,（1）对于英文字母,（2）对于中文

48、,我们可以压缩剩余度来压缩信源，提高通信的可靠性。,2.2多符号离散平稳信源,.,正是因为原始的信息都有冗余，才有可能对信息进行压缩，以尽量减少冗余，提高每个符号携带的信息量；但另一方面，冗余信息可以提高信息的抗干扰能力，如果信息的某部分在传输中被损坏，则通过冗余有可能将其恢复。 (冗余小,有效) (冗余大,可靠) 中国 中华人民共和国 从提高信息传输效率的角度出发，总是希望减少剩余度（压缩），这是信源编码的作用；从提高信息抗干扰能力来看，总是希望增加或保留剩余度，这是信道编码的作用。,2.2多符号离散平稳信源,.,作业： 2.13(P69), 2.16(P69) , 2.17(P69),2.

49、2多符号离散平稳信源,.,2.3连续信源,连续信源的熵,连续信源是指输出在时间和取值上都连续的信源,属随机过程x(t)，以概率密度描述 平稳过程 统计特性与时间起点无关 遍历过程 集平均=时间平均的平稳过程,.,2.3连续信源,熵计算两种方法 法一 连续消息离散消息 再用离散信源方法计算 法二 连续消息抽样时间离散的连续消息 分析时先量化，再令0,.,分类 单变量信源无记忆信源 (与单符号离散源相似) 随机过程中取一个时间t1 多变量信源有记忆信源 (与多符号离散源相似) 随机过程中取多个时间ti 说明 对单变量信源，可研究：数学期望、方差 对两变量信源，可研究：自相关函数,2.3连续信源,.

50、,2.3连续信源,.,一、 单变量连续信源数学模型 R连续变量X的取值范围 二、 连续信源的熵 由法二得 ： (图2.3.1) 上式中第2项为 即连续信源熵值无穷大(取值可能性无限多) 舍第2项得定义(相对熵),2.3连续信源,.,二、 连续信源的熵 两个连续变量 联合熵 条件熵,2.3连续信源,.,2.3.2 几种特殊连续信源的熵和最大熵定理,一、均匀分布信源： Hc(X)= log2(b-a) 结论 熵值只与均匀分布间隔(b-a)有关， 若 b-a 1，则Hc(X)为负,2.3连续信源,.,二、高斯分布信源 结论 熵值 只与方差有关，与m无关。 三、指数分布信源 结论 熵值只与数学期望m有

51、关,2.3连续信源,.,四、最大熵定理 1. 限峰值功率的最大熵定理 均匀分布的连续信源具最大熵 2. 限平均功率的最大熵定理 高斯分布的连续信源具最大熵 3. 限均值的最大熵定理 指数分布的连续信源具最大熵 结论 连续信源的最大熵因条件而异 离散信源的最大熵出现于等概之时,2.3连续信源,.,(1) 连续熵可为负值（与离散熵不同） (2) 可加性 Hc(XY)=Hc(X)+Hc(Y/X)=Hc(Y)+Hc(X/Y) Hc(X1X2XN) = Hc(X1) + Hc(X2/X1) + Hc(X3/X1X2) + Hc(XN/X1X2XN-1),2.3连续信源,.,(3) 平均互信息的非负性 I

52、c(X;Y) = Hc(X) Hc(X/Y) Ic(Y;X) = Hc(Y) Hc(Y/X) 对称性 Ic(X;Y) = Ic(Y;X) 非负性 Ic(X;Y) 0 , Ic(Y;X) 0 条件熵不大于无条件熵 Hc(X/Y) Hc(X) Hc(Y/X) Hc(Y),2.3连续信源,.,(1) 信息变差Ip,q= Hcp(x),X Hcq(x),X (2.3.49) Hcp(x),X最大熵，对应分布p(x) Hcq(x),X实际熵：对应分布q(x) 说明 式(2.3.49)与 I0=H0 H相对应 且有：实际熵Hcq(x),X = Hcp(x),X Ip,q 最大熵最大的平均不确定度 实际熵测

53、定q(x)后还剩下的不定度 于是，获得的信息量Ip,q不确定度的减少量,2.3连续信源,.,(2) 熵功率 对零均值，平均功率(P)受限的信源， 高斯分布p(x)具最大值。(m = 0, P = 2) 对实际信源，分布为q(x), 也可写为 结论冗余度, 信息变差取决于限定功率与熵功率之比,2.3连续信源,.,2.4 离散无失真信源编码定理,信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。 信源编码理论是信息论的一个重要分支，其理

54、论基础是信源编码的两个定理。 无失真信源编码定理：是离散信源/数字信号编码的基础； 限失真信源编码定理：是连续信源/模拟信号编码的基础，如语音、图像等信号。 信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类。 离散信源编码：独立信源编码，可做到无失真编码； 连续信源编码：独立信源编码，只能做到限失真信源编码； 相关信源编码：非独立信源编码。,.,2.4 离散无失真信源编码定理,香农信息论三大定理 : 第一定理: 无失真信源编码定理 第二定理: 信道编码定理（包括离散和连续信道） 第三定理: 限失真信源编码定理.,.,2.4 离散无失真信源编码定理,信源编码 信源符号码符号，以适合信

55、道传输的一种映射(变换),.,定长编码定理：由L个符号组成的，平均符号熵为H(x)的平稳无记忆符号序列X，可用由K个码符号(每个有m种取值)组成的码序列作定长编码。对任意 0, 0 ，有： (1)正定理：只要 则当L 足够大时，译码差错必小于 (2) 逆定理：当 时译码差错必为有限值，且当L足够大时,译码几乎必定出错。,2.4 离散无失真信源编码定理,.,说明： (1)信息率(编码速率) R = (K/L)log2m bit/信源符号 log2m 每个码符号的最大熵(bit/码符号) Klog2m 每个码符号序列最大熵(bit/码序列) (K/L)log2m 编码后，平均每个信源符号所能载荷的

56、最 大信息量,2.4 离散无失真信源编码定理,.,(2)编码效率 H(X)编码前，平均每个信源符号包含的信息量 R编码后，平均每个信源符号所能传送的最大信息量 若在正定理中取等号：R = H(X) + ,于是,2.4 离散无失真信源编码定理,.,(3)正定理指出：当信息率 R 单符号熵H(X)时可做到几乎无失真译码，条件是L大。 只要 ,译码差错率必小于 信源序列自信息方差,2.4 离散无失真信源编码定理,.,(3) 逆定理指出： 若R比H(X) 小一个 时，译码差错未必超过 若R比H(X) 小两个 时，译码差错必定大于 L时必失真 (4)结论 (单符号)信源熵H(X)实为一个界限 当 RH(

57、X)时 无失真译码 当 RH(X) 时 有失真译码,(4)逆定理指出： 若R比H(X) 小一个 时，译码差错未必超过 若R比H(X) 小两个 时，译码差错必定大于 L时必失真 (5)结论 (单符号)信源熵H(X)实为一个界限 当 RH(X)时 无失真译码 当 RH(X)时 有失真译码,2.4 离散无失真信源编码定理,.,例2 给定信源模型：8种符号和概率 算得：H(X)=2.55 bit /信源符号， 2(X) =1.323 若要求：编码效率 =90%，由 得 =0.28 若要求: 译码差错率=10-6 , 则L太大 此外， 相对熵率不高,2.4 离散无失真信源编码定理,.,第三章 信道容量,

58、信息论与编码,主讲：苗立刚 基础楼318,计算机与通信工程学院 2014年3月,.,第三章 信道容量,3.1 单符号离散信道的数学模型（重点） 3.2 单符号离散信道的信道容量（重点） 3.3 多符号离散信道的信道容量（重点） 3.4 网络信息理论（自学） 3.5 连续信道（自学） 3.6 信道编码定理（重点）,本章主要讨论的问题：,.,3.1单符号离散信道的数学模型,单符号离散信道的数学模型及其分类,信道的数学模型,X 输入事件的集合, 概率空间为X P Y 输出事件的集合, 概率空间为Y P,.,信道的分类,1、根据信道用户的多少，分为： 单用户信道-输入、输出均只有一个 多用户信道-输入、输出有多个 2、根据输入输出信号的特点，分为： 离散信道-输入、输出随机变量均离散取值 连续信道-输入、输出随机变量均连续取值 半离散(连续)信道- 一为离散，另一为连续 3、根据输入、输出随机变量的个数 单符号信道-输入、输出均用随机变量表示 多符号信道-输入、输出用随机矢量表示,3.1单符号离散信道的数学模型,.,4、根据信道上有无噪声(干扰) ： 有噪(扰)信道 无噪(扰)信道 5、根据信道有无记