《信息论与编码ppt》由会员分享，可在线阅读，更多相关《信息论与编码ppt（294页珍藏版）》请在金锄头文库上搜索。
1、信息论与编码主讲：苗立刚主讲：苗立刚基础楼基础楼319 计算机与通信工程学院计算机与通信工程学院2016年年3月月2021/5/231课程目标与安排 它是信息处理方向的一门重要的专业基础课，是后续课程它是信息处理方向的一门重要的专业基础课，是后续课程的基础，如通讯原理、数字图像处理、语音信号处理等。的基础，如通讯原理、数字图像处理、语音信号处理等。 介绍信息科学的基础理论和基本方法，课程将基于一个介绍信息科学的基础理论和基本方法，课程将基于一个通通讯系统的抽象数学模型讯系统的抽象数学模型进行展开，课程分为基础理论和编码进行展开，课程分为基础理论和编码理论两部分组成。理论两部分组成。 本课程以本
2、课程以概率论概率论为基础，数学推导较多，学习时主要把注为基础，数学推导较多，学习时主要把注意力集中到概念的理解上，不过分追求数学细节的推导。意力集中到概念的理解上，不过分追求数学细节的推导。 注意注意基本概念基本概念的理解，不断加深概念的把握。学习时注意的理解，不断加深概念的把握。学习时注意理解各个概念的理解各个概念的“用处用处”，结合其他课程理解它的意义，而，结合其他课程理解它的意义，而不要把它当作数学课来学习。不要把它当作数学课来学习。n 课程特点课程特点2021/5/232学学 时：时：3232 考试方式：开卷考试方式：开卷考试成绩：平时成绩考试成绩：平时成绩* *20% + 20% +
3、 考试成绩考试成绩* *80%80%课程目标与安排2021/5/233第一章第一章 绪论绪论第二章第二章 信源熵信源熵第三章第三章 信道容量信道容量第四章第四章 信息率失真函数信息率失真函数第五章第五章 信源编码信源编码第六章第六章 信道编码信道编码第七章第七章 密码体制的安全性测度密码体制的安全性测度n 课程内容安排课程内容安排课程目标与安排2021/5/234课程目标与安排n 参考书参考书曲炜，朱诗兵，信息论基础及应用，清华大学出版社，曲炜，朱诗兵，信息论基础及应用，清华大学出版社，20052005信息论与编码，陈运、周亮、陈新，电子工业出版社，信息论与编码，陈运、周亮、陈新，电子工业出版
4、社，20072007傅祖芸，信息论与编码，电子工业出版社，傅祖芸，信息论与编码，电子工业出版社，20042004周荫清，信息论基础周荫清，信息论基础( (第第3 3版版) )，北京航空航天大学出版，北京航空航天大学出版社，社，20062006n 有关的课程有关的课程 高等数学，概率论，线性代数高等数学，概率论，线性代数2021/5/235第一章第一章 绪论绪论信息论基础主讲：苗立刚主讲：苗立刚基础楼基础楼318 计算机与通信工程学院计算机与通信工程学院2014年年3月月2021/5/236第一章 绪论 信息的有关概念信息的有关概念 通讯系统模型通讯系统模型 信息论的形成和发展历史信息论的形成和
5、发展历史 n 本章主要讨论的问题：本章主要讨论的问题：2021/5/237信息的有关概念“信息信息”是信息论中最基本、最重要的概念，它是一个既抽是信息论中最基本、最重要的概念，它是一个既抽象又复杂的概念，目前还没有一个统一的定义象又复杂的概念，目前还没有一个统一的定义( (百余种百余种) )；“信息信息”不同于消息不同于消息在现代信息论形成之前，信息一直被看作是通信中消息的在现代信息论形成之前，信息一直被看作是通信中消息的同义词，没有严格的数学含义；同义词，没有严格的数学含义；所谓消息，是用文字、符号、数据、语言、图片、图像等所谓消息，是用文字、符号、数据、语言、图片、图像等形式，把客观事物运
6、动和主观思维活动的状态表达出来；形式，把客观事物运动和主观思维活动的状态表达出来； 消息是信息的载体；消息是表现形式，信息是实质。消息是信息的载体；消息是表现形式，信息是实质。“信息信息”不同于情报不同于情报情报往往是军事学、文献学方面的习惯用词，它的含义比情报往往是军事学、文献学方面的习惯用词，它的含义比“信息信息”窄的多，一般只限于特殊的领域，是一类特殊的窄的多，一般只限于特殊的领域，是一类特殊的信息；信息；“情报情报”是人们对于某个特定对象所见、所闻、所理解产是人们对于某个特定对象所见、所闻、所理解产生的知识；生的知识；2021/5/238“信息信息”不同于知识不同于知识知识是人们根据某
7、种目的知识是人们根据某种目的, ,从自然界收集得来的数据中从自然界收集得来的数据中整理、概括、提取得到的有价值的信息，是一种高层次整理、概括、提取得到的有价值的信息，是一种高层次的信息；的信息；知识是信息，但不等于信息的全体；知识是信息，但不等于信息的全体；“信息信息”不同于信号不同于信号把消息变换成适合信道传输的物理量，就是信号；信号把消息变换成适合信道传输的物理量，就是信号；信号是承载消息的物理量；是承载消息的物理量；信息的有关概念2021/5/239信息的有关概念信息的几种定义信息的几种定义 以信源为主的信息定义、以信道为主的信息定义和以信宿以信源为主的信息定义、以信道为主的信息定义和以
8、信宿为主的信息定义。为主的信息定义。以信源为主的信息定义有：以信源为主的信息定义有： 1) 1)信息是事物之间的差异信息是事物之间的差异(Longo,1975)(Longo,1975) 2) 2)信息是有序性的度量信息是有序性的度量(Wiener,1948)(Wiener,1948)以信道为主的信息定义有：以信道为主的信息定义有： 1) 1)信息是通信传输的内容信息是通信传输的内容(Wiener,1950)(Wiener,1950) 2) 2)信息是人与外界相互作用的过程中所交换的内容的名称信息是人与外界相互作用的过程中所交换的内容的名称(Wiener,1948)(Wiener,1948)以信
9、宿为主的信息定义有：以信宿为主的信息定义有： 1)1)信息是用来消除随机不定性的东西信息是用来消除随机不定性的东西 (Shannon,1948(Shannon,1948） 2) 2)信息是使概率分布发生变动的东西信息是使概率分布发生变动的东西 （Tribes etal, 1971Tribes etal, 1971）2021/5/2310 仙农从研究通信系统传输的实质出发，对信息做出了仙农从研究通信系统传输的实质出发，对信息做出了科学的定义；科学的定义；仙农注意到：收信者在收到消息之前是不知道消息的具体仙农注意到：收信者在收到消息之前是不知道消息的具体内容的。通信系统消息的传输对收信者来说，是一
10、个从不内容的。通信系统消息的传输对收信者来说，是一个从不知到知的过程，或者从知之甚少到知之甚多的过程，或是知到知的过程，或者从知之甚少到知之甚多的过程，或是从不确定到部分确定或全部确定的过程。从不确定到部分确定或全部确定的过程。因此因此, , 对于收信者来说对于收信者来说, , 通信过程是消除事物状态的不确通信过程是消除事物状态的不确定性的过程，不确定性的消除，就获得了信息，原先的不定性的过程，不确定性的消除，就获得了信息，原先的不确定性消除的越多，获得的信息就越多；确定性消除的越多，获得的信息就越多；“信息信息”是事物运动状态或存在方式的不确定性的描述，是事物运动状态或存在方式的不确定性的描
11、述，这就是仙农关于信息的定义。这就是仙农关于信息的定义。信息的有关概念2021/5/2311信息的度量信息的度量（信息量）和不确定性消除的程度有关，消除了信息的度量（信息量）和不确定性消除的程度有关，消除了多少不确定性，就获得了多少信息量；多少不确定性，就获得了多少信息量；不确定性就是随机性，可以用概率论和随机过程来测度不确不确定性就是随机性，可以用概率论和随机过程来测度不确定性的大小，出现概率小的事件，其不确定性大，反之，不定性的大小，出现概率小的事件，其不确定性大，反之，不确定性小；确定性小；由以上两点可知：由以上两点可知：概率小概率小 信息量大信息量大，即信息量是概率的单，即信息量是概率
12、的单调递减函数；调递减函数；此外，信息量应该具有可加性；此外，信息量应该具有可加性；2021/5/2312信息的度量由于信息量与概率成反比，并且具有可加性，可以证明，由于信息量与概率成反比，并且具有可加性，可以证明，信息量的计算式为信息量的计算式为 其中其中p pk k是事件是事件x xk k发生的概率，这也是仙农关于发生的概率，这也是仙农关于( (自自) )信息信息量的度量量的度量( (概率信息概率信息) )，单位为，单位为bitbit 哈特莱早在哈特莱早在2020世纪世纪2020年代就提出用对数作为信息年代就提出用对数作为信息量的测度。哈特莱认为：消息和信息不同，多种多样、量的测度。哈特莱
13、认为：消息和信息不同，多种多样、千姿百态的消息是信息的载体，消息究竟包含了多少千姿百态的消息是信息的载体，消息究竟包含了多少信息，应该用消息出现的概率的对数来计算，从而他信息，应该用消息出现的概率的对数来计算，从而他为信息度量找到了对数这一数学理论。为信息度量找到了对数这一数学理论。 2021/5/2313通讯系统模型信源信源编码器编码器信道信道译码器译码器干扰源干扰源通信系统基本模型通信系统基本模型消息消息信号信号消息消息信宿信宿噪声噪声信源：消息的来源，如文字、语音、图像等信源：消息的来源，如文字、语音、图像等编码器：把消息变换成信号，如信源编码、纠错编码、调制器编码器：把消息变换成信号，
14、如信源编码、纠错编码、调制器信道：传递信号的媒介，如电缆、光纤、无线电波等信道：传递信号的媒介，如电缆、光纤、无线电波等噪声：信道中的干扰，如加性干扰、乘性干扰噪声：信道中的干扰，如加性干扰、乘性干扰译码器：把信道输出的信号反变换，解调器、纠错译码器、信译码器：把信道输出的信号反变换，解调器、纠错译码器、信源译码器源译码器信宿：信息的接受端，接收消息的人或物信宿：信息的接受端，接收消息的人或物2021/5/2314通讯系统模型信源：消息的来源信源：消息的来源编码器：把消息变换成信号编码器：把消息变换成信号信道：传递信号的媒介信道：传递信号的媒介译码器：把信道输出的信号反变换译码器：把信道输出的
15、信号反变换信宿：信息的接受端信宿：信息的接受端噪声：信道中的干扰噪声：信道中的干扰信源编码器：把信源发出的消息变换成由二进制码元（或信源编码器：把信源发出的消息变换成由二进制码元（或多进制码元）组成的代码组以提高通信系统传输消息的效多进制码元）组成的代码组以提高通信系统传输消息的效率。信源编码可分为无失真信源编码和限失真信源编码。率。信源编码可分为无失真信源编码和限失真信源编码。目的：提高信息传输的有效性目的：提高信息传输的有效性信道编码器：在信源编码器输出的代码组上有目的地增加信道编码器：在信源编码器输出的代码组上有目的地增加一些监督码元，使之具有检错或纠错的能力。一些监督码元，使之具有检错
16、或纠错的能力。 目的：提高信息传输的可靠性目的：提高信息传输的可靠性密码学：研究如何隐蔽消息中的信息内容，使它在传输过密码学：研究如何隐蔽消息中的信息内容，使它在传输过程中不被窃听，提高通信系统的安全性。程中不被窃听，提高通信系统的安全性。 目的：提高信息的安全性目的：提高信息的安全性编码问题可分解为三类：信源编码、信道编码和密码编码问题可分解为三类：信源编码、信道编码和密码编码问题可分解为三类：信源编码、信道编码和密码编码问题可分解为三类：信源编码、信道编码和密码 在实际问题中，上述三类编码应统一考虑来提高通信在实际问题中，上述三类编码应统一考虑来提高通信系统的性能。这些编码的目标往往是相互
17、矛盾的。系统的性能。这些编码的目标往往是相互矛盾的。2021/5/2315电报常用的莫尔斯码就是按信息论的基本编码原则设计出电报常用的莫尔斯码就是按信息论的基本编码原则设计出来的；来的；在一些商品上面有一张由粗细条纹组成的标签，从这张标在一些商品上面有一张由粗细条纹组成的标签，从这张标签可以得知该商品的生产厂家、生产日期和价格等信息，签可以得知该商品的生产厂家、生产日期和价格等信息，这些标签是利用条形码设计出来的，非常方便，非常有用，这些标签是利用条形码设计出来的，非常方便，非常有用，应用越来越普遍；应用越来越普遍；计算机的运算速度很高，要保证它几乎不出差错，相当于计算机的运算速度很高，要保证
18、它几乎不出差错，相当于要求有要求有100100年的时间内不得有一秒钟的误差，这就需要利年的时间内不得有一秒钟的误差，这就需要利用纠错码来自动地及时地纠正所发生的错误；用纠错码来自动地及时地纠正所发生的错误；每出版一本书，都给定一个国际标准书号（每出版一本书，都给定一个国际标准书号（ISBNISBN），大大），大大方便图书的销售、编目和收藏工作。方便图书的销售、编目和收藏工作。编码的应用的几个例子：编码的应用的几个例子：编码的应用的几个例子：编码的应用的几个例子：通讯系统模型2021/5/2316 信息论的形成和发展信息论是在长期信息论是在长期通信工程通信工程的实践中，由通信技术与概率论、的实践
19、中，由通信技术与概率论、随机过程和数理统计相结合而逐步发展起来的一门科学。随机过程和数理统计相结合而逐步发展起来的一门科学。奈魁斯特：在奈魁斯特：在19241924年研究影响电报传递速度的因素时年研究影响电报传递速度的因素时, ,就察觉就察觉到信息传输速度和频带宽度有关系到信息传输速度和频带宽度有关系; ;哈特莱哈特莱(Hartley)(Hartley)：在：在19281928年用年用概率概率的观点来分析信息传输问的观点来分析信息传输问题题; ;仙农（仙农（Claude E.Shannon)Claude E.Shannon)：19481948年发表年发表通信的数学理论通信的数学理论(A Mat
20、hematical Theory of Communication),(A Mathematical Theory of Communication),为创立信息论为创立信息论作出了决定性的贡献作出了决定性的贡献; ;香农因此成为信息论的奠基人。香农因此成为信息论的奠基人。维纳维纳(N. Wiener)(N. Wiener)等：为信息论的进一步发展和拓展作了大量等：为信息论的进一步发展和拓展作了大量工作工作; ;主要在通信的统计理论与滤波器理论方面。主要在通信的统计理论与滤波器理论方面。2021/5/2317第二章第二章 信源熵信源熵信息论基础信息论基础主讲：苗立刚主讲：苗立刚基础楼基础楼31
21、8 计算机与通信工程学院计算机与通信工程学院2014年年3月月2021/5/2318第二章第二章 信源熵信源熵2.1 单符号离散信源单符号离散信源2.2 多符号离散平稳信源多符号离散平稳信源2.3 连续信源连续信源2.4 离散无失真信源编码定理离散无失真信源编码定理 n 本章主要讨论的问题：本章主要讨论的问题：2021/5/23192.12.1单符号离散信源单符号离散信源n 单符号离散信源的数学模型单符号离散信源的数学模型 单符号信源单符号信源信源每次输出一个符号信源每次输出一个符号, ,用用离散随机变量离散随机变量描述描述 多符号信源多符号信源信源每次输出多个符号信源每次输出多个符号( (符
22、号序列符号序列) )，用，用离散随离散随 机矢量机矢量描述描述 离散信源离散信源信源符号取值离散，包括单符号和多符号信源信源符号取值离散，包括单符号和多符号信源 连续信源连续信源信源符号取值连续，用随机过程描述信源符号取值连续，用随机过程描述 结论结论 从概率、随机变量从概率、随机变量( (过程过程) )来研究信息来研究信息 信息信息对事物状态对事物状态( (存在方式存在方式) )不确定性的描述不确定性的描述2021/5/23202.12.1单符号离散信源单符号离散信源n 单符号离散信源的数学模型单符号离散信源的数学模型注意：大写字母注意：大写字母X,Y,ZX,Y,Z代表随机变量，小写字母代代
23、表随机变量，小写字母代 表随机事件。表随机事件。2021/5/2321概概率率复复习习2021/5/23222.12.1单符号离散信源单符号离散信源 由于信息量与概率成反比，并且具有可加性，自信息量由于信息量与概率成反比，并且具有可加性，自信息量的定义为：的定义为： 其中其中p(xp(xi)i)是事件是事件x xi i发生的概率，这也是仙农关于发生的概率，这也是仙农关于( (自自) )信信息量的度量息量的度量( (概率信息概率信息) )计算信息量主要要注意有关事件发生概率的计算计算信息量主要要注意有关事件发生概率的计算; ;性质：性质：非负非负; ;单调递减；单调递减；当当p(xp(xi i)
24、 =0) =0时时,I(x,I(xi i) ,) ,不可能事件；当不可能事件；当p(xp(xi i)=1)=1时，时， I(xI(xi i)0 )0 ，确定事件，确定事件自信息量自信息量 I(xI(xi i) ) 的含义的含义当事件当事件x xi i发生以前，表示事件发生以前，表示事件x xi i发生的不确定性；发生的不确定性；当事件当事件x xi i发生以后，表示事件发生以后，表示事件x xi i所提供的信息量；所提供的信息量；n自信息量（单个随机事件）自信息量（单个随机事件）2021/5/2323 例例1 1：从：从2626个英文字母中，随即选取一个字母，则该事件的自个英文字母中，随即选取
25、一个字母，则该事件的自信息量为信息量为 I = -logI = -log2 2(1/26) = 4.7 (1/26) = 4.7 比特比特 例例2 2：设：设m m比特的二进制数中的每一个是等概率出现的比特的二进制数中的每一个是等概率出现的( (这样的这样的数共有数共有2 2m m个个) )，则任何一个数出现的自信息为，则任何一个数出现的自信息为: : I = -logI = -log2 2(1/ 2(1/ 2m m) = m ) = m 比特比特/ /符号符号自信息量的单位自信息量的单位自信息量的单位取决于对数的底；自信息量的单位取决于对数的底；底为底为2 2，单位为，单位为“比特（比特（b
26、itbit）”；底为底为e e，单位为单位为“奈特（奈特（natnat）”；底为底为1010，单位为，单位为“哈特（哈特（hathat）”；1 nat = 1.44bit , 1 hat = 3.32 bit1 nat = 1.44bit , 1 hat = 3.32 bit；2.12.1单符号离散信源单符号离散信源2021/5/2324例例3 3：设天气预报有两种消息，晴天和雨天，出现的概率分：设天气预报有两种消息，晴天和雨天，出现的概率分别为别为1/41/4和和3/43/4，我们分别用，我们分别用 来表示晴天，以来表示晴天，以 来表示来表示雨天，则我们的信源模型如下：雨天，则我们的信源模型
27、如下： 2.12.1单符号离散信源单符号离散信源2021/5/2325n 联合自信息量联合自信息量( (两个随机事件两个随机事件) )二维联合集二维联合集XYXY上的元素上的元素(x(xi iy yj j) )的联合自信息量定义为：的联合自信息量定义为： 含义含义 X=x X=xi i，Y=yY=yj j 同时发生同时发生时，带来的信息量时，带来的信息量 特例特例 若若X X、Y Y 独立，则独立，则I(xI(xi iy yj j) = I(x) = I(xi i) + I(y) + I(yj j) )2.12.1单符号离散信源单符号离散信源2021/5/2326n 条件自信息量（两个随机事件
28、）条件自信息量（两个随机事件） 二维联合集二维联合集XYXY中，对事件中，对事件x xi i和和y yj j，事件，事件x xi i在事件在事件y yj j给定的给定的条件下的条件信息量定义为：条件下的条件信息量定义为：联合自信息量和条件自信息量也满足非负和单调递减性。联合自信息量和条件自信息量也满足非负和单调递减性。关系关系当当X X和和Y Y独立时，独立时，2.12.1单符号离散信源单符号离散信源2021/5/2327n 互信息量互信息量( (两个随机事件两个随机事件) )信道信道信源信源X X信宿信宿Y Y2.12.1单符号离散信源单符号离散信源2021/5/2328信源发出消息信源发出
29、消息 的概率的概率 称为称为先验概率先验概率，信，信宿收到宿收到 后推测信源发出后推测信源发出 的概率称为的概率称为后验概后验概 率率 。定义定义 的后验概率与的后验概率与先验概先验概率率比值比值的对数为的对数为 对对 的的互信息量互信息量，用，用 表示，即表示，即互信息量等于自信息量减去条件自信息量。互信息量等于自信息量减去条件自信息量。第三种表达方式：第三种表达方式：2.12.1单符号离散信源单符号离散信源2021/5/2329 含义含义 互信息互信息I(xI(xi i;y;yj j) = ) = 自信息自信息I(xI(xi i) - ) - 条件自信息条件自信息I(xI(xi i/y/y
30、j j) ) (1) (1) I(xI(xi i) )信宿收到信宿收到y yj j之前，对信源发之前，对信源发x xi i的不确定度的不确定度(2) I(x(2) I(xi i|y|yj j) )信宿收到信宿收到y yj j之后，对信源发之后，对信源发x xi i的不确定度的不确定度(3) I(x(3) I(xi i;y;yj j) )收到收到y yj j而得到而得到( (关于关于x xi i ) )的互信息的互信息 = =不确定度的减少量不确定度的减少量 性质性质 (1) (1) 对称性对称性I(xI(xi i ;y;yj j) = I(y) = I(yj j ;x;xi i) ) (2)
31、X(2) X与与Y Y独立时独立时I(xI(xi i ;y;yj j) = 0) = 0 (3) I(x(3) I(xi i;y;yj j) ) 可为正、负、可为正、负、0 0 (4) I(x (4) I(xi i;y;yj j)=I(x)=I(xi i); I(x); I(xi i;y;yj j)=I(y)=I(yj j) )2.12.1单符号离散信源单符号离散信源2021/5/2330I(xI(xi i;y;yj j) ) 可为正、负、可为正、负、0 0的举例的举例设设y yj j代表代表“闪电闪电”，则，则当当x xi i代表代表“打雷打雷”时，时，I(xI(xi i|y|yj j) =
32、 0) = 0，I(xI(xi i;y;yj j) = I(x) = I(xi i) )0 0 当当x xi i代表代表“下雨下雨”时，时，I(xI(xi i|y|yj j) ) I(xI(xi i) )，I(xI(xi i;y;yj j) )0 0当当x xi i代表代表“雾天雾天”时，时，I(xI(xi i|y|yj j) = I(x) = I(xi i) )，I(xI(xi i;y;yj j)= 0)= 0当当x xi i代表代表“飞机正点起飞飞机正点起飞”时，时，I(xI(xi i|y|yj j) )I(xI(xi i) )，I(xI(xi i;y;yj j) ) 0 0 2.12.1
33、单符号离散信源单符号离散信源2021/5/2331n 条件互信息量条件互信息量( (三个随机事件三个随机事件) ) 联合集联合集XYZXYZ中中, ,给定条件给定条件 下，下， 与与 之间的互信息量，之间的互信息量，其定义式其定义式互信息量互信息量2.12.1单符号离散信源单符号离散信源2021/5/2332n 平均自信息量平均自信息量( (信源熵信源熵)-)-随机变量随机变量 单位单位 bit/( bit/(信源信源) )符号符号 这个平均自信息量的表达式和统计物理学中热熵的表达式这个平均自信息量的表达式和统计物理学中热熵的表达式很相似。在统计物理学中，热熵是一个物理系统杂乱性（无序很相似。
34、在统计物理学中，热熵是一个物理系统杂乱性（无序性）的度量。这在概念上也有相似之处。因而就借用性）的度量。这在概念上也有相似之处。因而就借用“熵熵”这这个词把平均自信息量个词把平均自信息量H(X)H(X)称为称为“信源熵信源熵”。 通常研究单独一个事件或单独一个符号的信息量是不够的，通常研究单独一个事件或单独一个符号的信息量是不够的，往往需要研究整个事件集合或符号序列往往需要研究整个事件集合或符号序列( (如信源如信源) )的平均的信息的平均的信息量量( (总体特征总体特征) )，这就需要引入新的概念；定义自信息的数学期，这就需要引入新的概念；定义自信息的数学期望为信源的平均信息量望为信源的平均
35、信息量2.12.1单符号离散信源单符号离散信源2021/5/2333例：天气预报，有两个信源例：天气预报，有两个信源则：则：说明第二个信源的平均不确定性更大一些说明第二个信源的平均不确定性更大一些信息熵具有以下三种物理含义：信息熵具有以下三种物理含义：1 1、表示信源输出前，信源的平均不确定性、表示信源输出前，信源的平均不确定性2 2、表示信源输出后，每个符号所携带的平均信息量、表示信源输出后，每个符号所携带的平均信息量3 3、反映了变量、反映了变量X X的随机性的随机性。2.12.1单符号离散信源单符号离散信源2021/5/2334例：设某信源输出四个符号，其符号集合的概率分布为：例：设某信
36、源输出四个符号，其符号集合的概率分布为： 则其熵为：则其熵为：2.12.1单符号离散信源单符号离散信源2021/5/2335例：电视屏上约有例：电视屏上约有 500 600= 310500 600= 3105 5个格点，按每点有个格点，按每点有1010个个不同的灰度等级考虑，则共能组成不同的灰度等级考虑，则共能组成n=10n=103x103x105 5个不同的画面。按等个不同的画面。按等概率概率1/101/103x103x105 5计算，平均每个画面可提供的信息量为计算，平均每个画面可提供的信息量为 =310=3105 53.32 3.32 比特比特/ /画面画面 例：有一篇千字文章，假定每字
37、可从万字表中任选，则共有不同例：有一篇千字文章，假定每字可从万字表中任选，则共有不同的千字文的千字文N=10000N=1000010001000=10=1040004000篇。仍按等概率篇。仍按等概率1/100001/1000010001000计算，平计算，平均每篇千字文可提供的信息量为均每篇千字文可提供的信息量为 H H（X X）loglog2 2N N4104103 33332=1.31032=1.3104 4 比特千字文比特千字文“一个电视画面一个电视画面”平均提供的信息量远远超过平均提供的信息量远远超过“一篇千字文一篇千字文”提供的信息量。提供的信息量。 2.12.1单符号离散信源单符
38、号离散信源2021/5/2336n熵函数的数学特性熵函数的数学特性熵函数可以表示为：熵函数可以表示为：二元熵：二元熵：性质性质1 1：非负性：非负性H(X)0H(X)0由于由于0p0pi i1,1,所以所以logplogpi i00，logplogpi i00，则总有，则总有H(X)0H(X)0。2.12.1单符号离散信源单符号离散信源2021/5/2337性质性质2 2：对称性：对称性 根据加法交换律可以证明，当变量交换顺序时熵函数根据加法交换律可以证明，当变量交换顺序时熵函数的值不变。信源的熵只与概率空间的总体结构有关，而与的值不变。信源的熵只与概率空间的总体结构有关，而与个概率分量对应的
39、状态顺序无关；个概率分量对应的状态顺序无关；性质性质3 3：扩展性：扩展性 这说明信源空间中增加某些概率很小的符号，虽然当发这说明信源空间中增加某些概率很小的符号，虽然当发出这些符号时，提供很大的信息量，但由于其概率接近于出这些符号时，提供很大的信息量，但由于其概率接近于0 0，在信源熵中占极小的比重，使信源熵保持不变。，在信源熵中占极小的比重，使信源熵保持不变。 2.12.1单符号离散信源单符号离散信源2021/5/2338性质性质4 4：可加性：可加性 性质性质5 5：极值性：极值性 上式表明，对于具有上式表明，对于具有n n个符号的离散信源，只有在个符号的离散信源，只有在n n个个信源符
40、号等可能出现的情况下，信源熵才能达到最大值，这信源符号等可能出现的情况下，信源熵才能达到最大值，这也表明等概分布的信源的平均不确定性最大，这是一个很重也表明等概分布的信源的平均不确定性最大，这是一个很重要得结论，称为要得结论，称为最大离散熵定理最大离散熵定理例：对于一个二元信源例：对于一个二元信源 H(X)=H(1/2,1/2)=log2=1bitH(X)=H(1/2,1/2)=log2=1bitH(X)= -plog2p (1-p)log2(1-p)=H(p)2.12.1单符号离散信源单符号离散信源2021/5/2339性质性质6 6：确定性：确定性 当信源当信源X X的信源空间的信源空间X
41、X，PP中。任一个概率分量等于中。任一个概率分量等于1 1，根据完备空间特性，其它概率分量必为根据完备空间特性，其它概率分量必为0 0，这时信源为一个，这时信源为一个确知信源，其熵为确知信源，其熵为0 0。如果一个信源的输出符号几乎必然为。如果一个信源的输出符号几乎必然为某一状态，那么这个信源没有不确定性，信源输出符号后不某一状态，那么这个信源没有不确定性，信源输出符号后不提供任何信息量。提供任何信息量。性质性质7 7：上凸性：上凸性 是概率分布是概率分布(p(p1 1,p,p2 2, ,p,pq q) )的严格上凸函数。的严格上凸函数。2.12.1单符号离散信源单符号离散信源2021/5/2
42、340 设设f(X)=f(xf(X)=f(x1 1,x,x2 2, ,x,xn n) )为一多元函数。若对于任意一个小为一多元函数。若对于任意一个小于于1 1的正数的正数 （0 10 = f(X= f(X1 1)+(1- )f(X)+(1- )f(X2 2) )则称则称f(X)f(X)为定义域上的上凸函数。为定义域上的上凸函数。若若“= =”不成立，则为严格上凸函数不成立，则为严格上凸函数若若“=”, ,则为下凸函数则为下凸函数若若“ ”, ,则为严格下凸函数则为严格下凸函数2.12.1单符号离散信源单符号离散信源2021/5/23410 0.2 0.4 0.6 0.8 110.80.60.4
43、0.2pH(p)H H（p p）函数曲线如图所示。如果二元信源的输出符号是确定的，）函数曲线如图所示。如果二元信源的输出符号是确定的，即即p=1p=1或或q=1q=1，则该信源不提供任何信息。反之，当二元信源符号，则该信源不提供任何信息。反之，当二元信源符号0 0和和1 1以等概率发生时，信源熵达到极大值，等于以等概率发生时，信源熵达到极大值，等于1 1比特信息量。比特信息量。2.12.1单符号离散信源单符号离散信源2021/5/2342 信信源源熵熵是是从从整整个个信信源源的的统统计计特特性性来来考考虑虑的的，它它是是从从平平均均意意义义上上来来表表征征信信源源的的总总体体信信息息测测度度的
44、的。对对于于某某特特定定的的信信源源（概概率率空空间间给给定定），其其信信源源熵熵是是一一个个特特定定的的值值。不不同同的的信信源源因因统统计计特特性性不不同同，其其熵熵也也不不同同。信信源源熵熵用用以以表表征征信信息息源源的的平平均均不不确确定定性性，平平均均自自信信息息量量是是消消除除信信源源不不确确定定性性时时所所需需信信息息的的量量度度，即即收收到到一一个个信信源源符符号号，全全部部解解除除了了这这个个符符号号的的不不确确定定性性。或或者者说说获获得得这样大的信息量后，信源不确定性就被消除了。这样大的信息量后，信源不确定性就被消除了。 2.12.1单符号离散信源单符号离散信源2021/
45、5/2343 信源熵信源熵和和平均自信息量平均自信息量两者在数值上相等，但两者在数值上相等，但含义含义不同。某不同。某一信源，不管它是否输出符号，只要这些符号具有某些概率特性，一信源，不管它是否输出符号，只要这些符号具有某些概率特性，就必有信源的熵值；这熵值在总体平均上才有意义，因而是一个就必有信源的熵值；这熵值在总体平均上才有意义，因而是一个确定的值确定的值。而另一方面，信息量则只有当信源输出的符号被接收。而另一方面，信息量则只有当信源输出的符号被接收者收到后才有意义，信息量就是给予接收者的信息度量，该值本者收到后才有意义，信息量就是给予接收者的信息度量，该值本身可以是身可以是随机量随机量，
46、也可以与接收者的情况有关。，也可以与接收者的情况有关。 因此说因此说信源熵是信源的平均不确定性信源熵是信源的平均不确定性的描述，一般情况下它的描述，一般情况下它并不等于平均获得的信息量。只是在无噪情况下，接收者才能正并不等于平均获得的信息量。只是在无噪情况下，接收者才能正确无误地接收到信源所发出的信息，消除了信源熵确无误地接收到信源所发出的信息，消除了信源熵H H（X X）值大小）值大小的平均不确定性，所以获得的平均信息量就等于信源熵的平均不确定性，所以获得的平均信息量就等于信源熵H H（X X）的）的值。在一般情况下获得的信息量是两熵之差，并不是信源熵本身。值。在一般情况下获得的信息量是两熵
47、之差，并不是信源熵本身。2.12.1单符号离散信源单符号离散信源2021/5/2344n条件熵条件熵思考：求条思考：求条件熵时为什件熵时为什么要用联合么要用联合概率加权？概率加权？条件熵是在联合符号集合条件熵是在联合符号集合XYXY上的上的条件自信息量条件自信息量的数学期望。的数学期望。在已知随机变量在已知随机变量X X的条件下，随机变量的条件下，随机变量Y Y的条件熵定义为：的条件熵定义为：2.12.1单符号离散信源单符号离散信源2021/5/2345条件概率条件概率并且并且当已知特定事件当已知特定事件xi出现时，下一个出现的是出现时，下一个出现的是yj 的不确的不确定性为：定性为：对集合对
48、集合Y Y中所有元素统计平均，其熵为：中所有元素统计平均，其熵为：上述熵值再对集合上述熵值再对集合Y Y中的元素做统计平均，得条件中的元素做统计平均，得条件熵熵：同理可得：同理可得：2021/5/2346条件熵条件熵H(X/Y)H(X/Y)是一个确定值，表示信宿在收到是一个确定值，表示信宿在收到Y Y后，信后，信源源X X仍然存在的不确定度。这是信道干扰所造成的。有时仍然存在的不确定度。这是信道干扰所造成的。有时称称H(X/Y)H(X/Y)为为信道疑义度信道疑义度，也称，也称损失熵损失熵。如果没有干扰，如果没有干扰，H(X/Y)=0,H(X/Y)=0,一般情括下一般情括下H(X/Y)H(X/Y
49、)小于小于H(X)H(X)，说明经过信道传输，总能消除一些信源的不确定性，从，说明经过信道传输，总能消除一些信源的不确定性，从而获得一些信息。而获得一些信息。条件熵条件熵H(Y/X)H(Y/X)也是一个确定值也是一个确定值, ,表示信源发出表示信源发出X X后，信后，信宿仍然存在的不确定度。这是由于噪声引起的。也称为宿仍然存在的不确定度。这是由于噪声引起的。也称为噪噪声熵声熵。2.12.1单符号离散信源单符号离散信源2021/5/2347n联合熵（共熵）联合熵（共熵） 联合离散符号集合联合离散符号集合XYXY上的每个元素对上的每个元素对 的联合自信息的联合自信息量的数学期望。量的数学期望。说明
50、说明: : 联合熵联合熵H H（XYXY）表示）表示X X和和Y Y同时发生的不确定度。同时发生的不确定度。2.12.1单符号离散信源单符号离散信源2021/5/2348n加权熵（自学）加权熵（自学）对香农熵引入主观因素对香农熵引入主观因素效用权重系数效用权重系数( (重量重量) )定义：定义： 设信源设信源X 则加权熵则加权熵 HwHw( (X) ) 含义含义 消息消息xi xi 的权重的权重wiwi对对I(xi)I(xi)的加权平均的加权平均性质：略性质：略2.12.1单符号离散信源单符号离散信源2021/5/2349从通信系统角度看熵的意义从通信系统角度看熵的意义H(X)H(X)：表示信
51、源边每个符号的平均信息量（信源熵）；表示信源边每个符号的平均信息量（信源熵）；H(Y)H(Y)：表示信宿边每个符号的平均信息量（信宿熵）；表示信宿边每个符号的平均信息量（信宿熵）；H(X|Y):H(X|Y):信道疑义度信道疑义度( (含糊度含糊度) )，表示在输出端接收到，表示在输出端接收到Y Y后，后，发送端发送端X X尚存的平均不确定性。这个对尚存的平均不确定性。这个对X X尚存的不确定性是尚存的不确定性是由于信道干扰引起的。由于信道干扰引起的。H(Y|X):H(Y|X):噪声熵，表示在已知噪声熵，表示在已知X X后，对于输出后，对于输出Y Y尚存的平均尚存的平均不确定性；不确定性；H(X
52、Y):H(XY):表示整个信息传输系统的平均不确定性；表示整个信息传输系统的平均不确定性；2.12.1单符号离散信源单符号离散信源2021/5/2350n各种熵的性质各种熵的性质 联合熵联合熵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) = 0I(X;Y) = 0 该性质表明，通过一个信道总能该性质表
53、明，通过一个信道总能传递一些信息，最差的条件下，输入输出完全独立，不传递传递一些信息，最差的条件下，输入输出完全独立，不传递任何信息，互信息等于任何信息，互信息等于0 0，但决不会失去已知的信息。，但决不会失去已知的信息。极值性：即极值性：即I(X;Y) = H(X)I(X;Y) = H(X) 一般来说，信道疑义度一般来说，信道疑义度H(X|Y)H(X|Y)总是大于总是大于0 0，所以互信息总是小于信源的熵，只有当信道是，所以互信息总是小于信源的熵，只有当信道是无损信道时，信道疑义度等于无损信道时，信道疑义度等于0 0，互信息等于信源的熵。，互信息等于信源的熵。对称性：即对称性：即I(X;Y)
54、 = I(Y;X)I(X;Y) = I(Y;X) I(Y;X) I(Y;X)表示从表示从X X中提取关于的中提取关于的Y Y的信息量，实际上的信息量，实际上I(X,Y)I(X,Y)和和I(Y,X)I(Y,X)只是观察者的立足点不同，只是观察者的立足点不同，对信道的输入对信道的输入X X和输出和输出Y Y的总体测度的两种表达形式的总体测度的两种表达形式 2.12.1单符号离散信源单符号离散信源2021/5/2356 I(X;Y) I(X;Y)是二元函数是二元函数:P(X):P(X)的上凸函数，的上凸函数，P(Y|X)P(Y|X)的下凸的下凸函数函数 平均互信息的凸状性平均互信息的凸状性2.12.
55、1单符号离散信源单符号离散信源2021/5/2357 定理定理2.1 2.1 对于固定的信道，平均互信息对于固定的信道，平均互信息I(X;Y)I(X;Y)是信源是信源概率分布概率分布P(X)P(X)的上凸函数的上凸函数 这就是说，对于一定的信道转移概率分布这就是说，对于一定的信道转移概率分布P(Y|X)P(Y|X)，总可，总可以找到某一个先验概率分布的信源以找到某一个先验概率分布的信源X X，使平均交互信息量，使平均交互信息量I(X;Y)I(X;Y)达到相应的最大值达到相应的最大值I Imaxmax，这时称这个信源为，这时称这个信源为该信道的匹该信道的匹配信源配信源。可以说，不同的信道转移概率
56、对应不同的。可以说，不同的信道转移概率对应不同的I Imaxmax。信宿信宿信道信道信源信源 通信系统的简化模型通信系统的简化模型噪声噪声2.12.1单符号离散信源单符号离散信源2021/5/2358例：对于二元对称信道例：对于二元对称信道如果信源分布如果信源分布X=p,1-pX=p,1-p，则，则 2.12.1单符号离散信源单符号离散信源qq10YX2021/5/23592.12.1单符号离散信源单符号离散信源而：而：所以：所以： 当当信信道道固固定定时时，q q为为一一个个固固定定常常数数，平平均均互互信信息息是是信信源源分分布布的的上上凸凸函函数数，最最大大只只为为1-H(q)1-H(q
57、)。图图示示曲曲线线表表明明，对对于于固固定定信信道道，输输入入符符号号X X的的概概率率分分布布不不同同时时，在在接接收收端端平平均均每每个个符符号号所所获获得得的的信信息息量量就就不不同同。当当输输入入符符号号为为等等概概率率分分布布时时，平平均均互互信信息息量量为为最最大大值值，接收每个符号所获得的信息量最大。接收每个符号所获得的信息量最大。信道容量的理论基础信道容量的理论基础1-H(q)0 0.5 1 pI(X;Y)2021/5/2360定理定理2.2 2.2 对于固定的信源，平均互信息对于固定的信源，平均互信息I(X;Y)I(X;Y)信道传递信道传递概率分布概率分布P(Y|X)P(Y
58、|X)的下凸函数的下凸函数 这就是说，对于一个已知先验概率为这就是说，对于一个已知先验概率为p p的离散信源，总可以的离散信源，总可以找到某一个转移概率分布的信道找到某一个转移概率分布的信道q q，使平均互信息量达到相应的，使平均互信息量达到相应的最小值最小值I Iminmin。信宿信宿信道信道信源信源 通信系统的简化模型通信系统的简化模型噪声噪声2.12.1单符号离散信源单符号离散信源2021/5/2361例：对于二元对称信道例：对于二元对称信道 当信源固定后，当信源固定后，p p为一个固定常数，改变信道特性为一个固定常数，改变信道特性q q可获得不可获得不同的平均互信息同的平均互信息I(X
59、;Y)I(X;Y)。当。当q=1/2q=1/2时，时，I(X;Y)=0,I(X;Y)=0,即在信道输出端即在信道输出端获得的信息最小，这意味着信源的信息全部损失在信道中，这是获得的信息最小，这意味着信源的信息全部损失在信道中，这是一种最差的信道，其噪声最大。一种最差的信道，其噪声最大。信息率失真理论的基础。信息率失真理论的基础。2.12.1单符号离散信源单符号离散信源qq10YX0 0.5 1 qH(p)I(X;Y)2021/5/2362对于无损信道，有对于无损信道，有I(X;Y) = H(X) = H(Y) = H(XY) I(X;Y) = H(X) = H(Y) = H(XY) H(X/Y
60、)=H(Y/X)=0H(X/Y)=H(Y/X)=0对于全损信道，有对于全损信道，有I(X; Y) = 0 I(X; Y) = 0 H(X/Y)=H(X)H(X/Y)=H(X)； H(Y/X)=H(Y) H(Y/X)=H(Y)2.12.1单符号离散信源单符号离散信源2021/5/2363n 数据处理定理数据处理定理( (自学自学) ) I(X;Z) I(Y;Z)I(X;Z) I(Y;Z) I(X;Z) I(X;Y) I(X;Z) I(X;Y) 意义意义 信息不增原理信息不增原理 每经一次处理，可能丢失一部分信息每经一次处理，可能丢失一部分信息P(Y/X)P(Z/Y)XYZ2.12.1单符号离散信
61、源单符号离散信源2021/5/2364H(X)H(Y)H(X|Y)H(Y|X)I(X;Y)H(XY)ABABABABA B各类熵与集合图的类比各类熵与集合图的类比2.12.1单符号离散信源单符号离散信源2021/5/2365信道中熵的信息流图信道中熵的信息流图H(Y|X) :H(Y|X) :噪声熵；噪声熵；H(X|Y) :H(X|Y) :信道疑义度；信道疑义度；它们都是由于噪声干扰的存在而存在的。信道中存在噪声它们都是由于噪声干扰的存在而存在的。信道中存在噪声干扰，是减低信道传信能力的基本原因。干扰，是减低信道传信能力的基本原因。H(X)H(Y)I(X;Y)H(X|Y)H(Y|X)2.12.1
62、单符号离散信源单符号离散信源2021/5/2366各种熵之间的关系各种熵之间的关系2021/5/2367例例2.12.1单符号离散信源单符号离散信源2021/5/23682021/5/23692021/5/2370n 作业：作业：2.4(P68), 2.6(P68), 2.7(P68), 2.10(P68)2021/5/23712.22.2多符号离散平稳信源多符号离散平稳信源2021/5/2372离离散散无无记记忆忆信信源源：发发出出的的各各个个符符号号是是相相互互独独立立的的，发发出出的的符符号号序序列列中中的的各各个个符符号号之之间间没没有有统统计计关关联联性性，各各个个符符号号的的出出现
63、现概率是它自身的先验概率。概率是它自身的先验概率。 离散有记忆信源：离散有记忆信源：所发出的各个符号的概率是有关联的。所发出的各个符号的概率是有关联的。发发出出单单个个符符号号的的信信源源：是是指指信信源源每每次次只只发发出出一一个个符符号号代代表表一一个消息；个消息；发发出出符符号号序序列列的的信信源源：是是指指信信源源每每次次发发出出一一组组含含二二个个以以上上符符号的符号序列代表一个消息号的符号序列代表一个消息。 发发出出符符号号序序列列的的有有记记忆忆信信源源：是是指指用用信信源源发发出出的的一一个个符符号号序序列的整体概率（即列的整体概率（即联合概率联合概率）反映有记忆信源的特征。）
64、反映有记忆信源的特征。 发发出出符符号号序序列列的的马马尔尔可可夫夫信信源源：是是指指某某一一个个符符号号出出现现的的概概率率只只与与前前面面一一个个或或有有限限个个符符号号有有关关，而而不不依依赖赖更更前前面面的的那那些些符符号号，这这样样的的信信源源可可以以用用信信源源发发出出符符号号序序列列内内各各个个符符号号之之间间的的条件概率条件概率来反映记忆特征。来反映记忆特征。2.22.2多符号离散平稳信源多符号离散平稳信源2021/5/23732.22.2多符号离散平稳信源多符号离散平稳信源n 离散无记忆信源离散无记忆信源 发出单个符号的无记忆信源（最简单的离散信源）发出单个符号的无记忆信源（
65、最简单的离散信源）自信息量自信息量信源熵信源熵2021/5/23742.22.2多符号离散平稳信源多符号离散平稳信源n 离散无记忆信源的扩展信源离散无记忆信源的扩展信源 实际信源输出的消息往往是时间上或空间上的一系列符号，实际信源输出的消息往往是时间上或空间上的一系列符号，如电报系统，序列中前后符号间一般是有统计依赖关系的。如电报系统，序列中前后符号间一般是有统计依赖关系的。离散无记忆二进制信源离散无记忆二进制信源X的二次扩展信源的二次扩展信源 我们先讨论离散无记忆信源，此时，信源序列的前后符号我们先讨论离散无记忆信源，此时，信源序列的前后符号之间是统计独立的之间是统计独立的. . 如在二元系
66、统中，我们可以把两个二元数字看成一组，会如在二元系统中，我们可以把两个二元数字看成一组，会出现四种可能情况：出现四种可能情况：0000、0101、1010和和1111，我们可以把这四种情况，我们可以把这四种情况看成一个新的信源称为看成一个新的信源称为二元无记忆信源的二次扩展信源二元无记忆信源的二次扩展信源，相应，相应的，如果把的，如果把N N个二元数字看成一组，则新的信源称为个二元数字看成一组，则新的信源称为二元无记二元无记忆信源的忆信源的N N次扩展信源次扩展信源。2021/5/2375则该信源的则该信源的N N次扩展信源为：次扩展信源为：一般情况下，设一个离散无记忆信源为：一般情况下，设一
67、个离散无记忆信源为：离散无记忆二进制信源离散无记忆二进制信源X X的三次扩展信源的三次扩展信源离散无记忆信源离散无记忆信源X X的的N N次扩展信源次扩展信源2.22.2多符号离散平稳信源多符号离散平稳信源2021/5/2376根据信息熵的定义：根据信息熵的定义：可以证明，对于离散无记忆的扩展信源可以证明，对于离散无记忆的扩展信源 N N次次扩展信源的熵扩展信源的熵2.22.2多符号离散平稳信源多符号离散平稳信源注意：注意：(1)(1)单位单位:bit/sign,:bit/sign,但含义不同但含义不同(2)N(2)N次次扩展信源的熵等于各符号熵之和扩展信源的熵等于各符号熵之和2021/5/2
68、377例例: : 离散无记忆信源的离散无记忆信源的N N次扩展信源次扩展信源离散无记忆信源为：离散无记忆信源为：X:aX:a1 1,a,a2 2,a,a3 3; P(X):1/4, 1/2, 1/4; P(X):1/4, 1/2, 1/42 2次扩展信源为：次扩展信源为：:A:A1 1, ,A,A9 9 信源的信源的9 9个符号为：个符号为：A A1 1=a=a1 1a a1 1A A2 2=a=a1 1a a2 2A A3 3=a=a1 1a a3 3A A4 4=a=a2 2a a1 1A A5 5=a=a2 2a a2 2A A6 6=a=a2 2a a3 3A A7 7=a=a3 3a
69、 a1 1A A8 8=a=a3 3a a2 2A A9 9=a=a3 3a a3 3其概率关系为其概率关系为 : :A A1 1A A2 2A3A3A A4 4A A5 5A A6 6A A7 7A A8 8A A9 91/161/16 1/81/81/161/16 1/81/81/41/41/81/81/161/16 1/81/81/161/162.22.2多符号离散平稳信源多符号离散平稳信源2021/5/2378计算可知计算可知2.22.2多符号离散平稳信源多符号离散平稳信源2021/5/23792.22.2多符号离散平稳信源多符号离散平稳信源n 离散平稳信源离散平稳信源 一般来说，信源
70、的前后消息之间有前后依赖关系，可以一般来说，信源的前后消息之间有前后依赖关系，可以用随机矢量描述：用随机矢量描述：信源在某一时刻发出什么样的值取决于两方面信源在某一时刻发出什么样的值取决于两方面1 1、这一时刻该变量的概率分布、这一时刻该变量的概率分布2 2、这一时刻以前发出的消息、这一时刻以前发出的消息 如一个人讲话如一个人讲话 我们现在讨论我们现在讨论平稳的平稳的随机序列，随机序列，所谓平稳是指序列的统所谓平稳是指序列的统计性质与时间的推移无关计性质与时间的推移无关（俩个任意时刻信源发出符号的（俩个任意时刻信源发出符号的概率分布完全相同）。概率分布完全相同）。信源所发符号序列的信源所发符号
71、序列的概率分布与时概率分布与时间的起点无关间的起点无关，这种信源我们称之为，这种信源我们称之为离散序列平稳信源离散序列平稳信源。2021/5/23802.22.2多符号离散平稳信源多符号离散平稳信源2021/5/23812.22.2多符号离散平稳信源多符号离散平稳信源n 离散平稳信源的熵离散平稳信源的熵 最简单的平稳信源最简单的平稳信源二维平稳信源，信源发出序二维平稳信源，信源发出序列中只有前后两个符号间有依赖关系，我们可以对其二列中只有前后两个符号间有依赖关系，我们可以对其二维扩展信源进行分析。维扩展信源进行分析。信源的概率空间信源的概率空间: :假定假定X=X1X2 , ,则可得到一个新的
72、信源则可得到一个新的信源2021/5/23822.22.2多符号离散平稳信源多符号离散平稳信源根据信息熵的定义，可得：根据信息熵的定义，可得：(1)(1)联合熵联合熵 可以表征信源输出长度为可以表征信源输出长度为2 2的符号的平均不确定性，或所的符号的平均不确定性，或所含有的信息量。因此可以用含有的信息量。因此可以用 作为二维平稳信源的作为二维平稳信源的信息熵的近似值信息熵的近似值(2)(2)条件熵条件熵则：则：2021/5/23832.22.2多符号离散平稳信源多符号离散平稳信源另外还可以得到：另外还可以得到：只有信源统计独立时等号成立。只有信源统计独立时等号成立。结论：二维离散平稳有记忆信
73、源的熵小于等于二结论：二维离散平稳有记忆信源的熵小于等于二维平稳无记忆信源的熵。维平稳无记忆信源的熵。可以证明：可以证明：2021/5/2384 例例 设某二维离散信源的原始信源的信源空间设某二维离散信源的原始信源的信源空间X=x1,x2,x3; P(X)=1/4, 1/4, 1/2, 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|x1)=1/2; p(x2|x1)=1/2; p(x3|x1)=0;p(x1|x2)=1/8; p(x2|x2)=3/4; p(
74、x3|x2)=1/8;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;p(x1|x3)=0; p(x2|x3)=1/4; p(x3|x3)=3/4;原始信源的熵为：原始信源的熵为： H(X)=1.5 bit/H(X)=1.5 bit/符号符号条件熵：条件熵： H(X2|X1)=1.4 bit/H(X2|X1)=1.4 bit/符号符号可见：可见： H(X2|X1)H(X)H(X2|X1)H(X)二维信源的熵：二维信源的熵：H(X1X2)=H(X1)+H(X2|X1)=2.9 bit/
75、H(X1X2)=H(X1)+H(X2|X1)=2.9 bit/消息消息每个信源符号提供的平均信息量为：每个信源符号提供的平均信息量为：H H2 2(X1X2)=H(X1X2)/2=1.45 bit/(X1X2)=H(X1X2)/2=1.45 bit/符号。符号。2.22.2多符号离散平稳信源多符号离散平稳信源2021/5/23852.22.2多符号离散平稳信源多符号离散平稳信源2021/5/2386对于离散平稳信源，当对于离散平稳信源，当 时，具有以下性质：时，具有以下性质：N N给定时，平均符号熵给定时，平均符号熵 条件熵；条件熵； 平均符号熵平均符号熵 随随N N增加是非递增的；增加是非递
76、增的；条件较多的熵必小于或等于条件较少的熵，而条件熵必小条件较多的熵必小于或等于条件较少的熵，而条件熵必小于等于无条件熵。于等于无条件熵。 对于二维离散平稳信源，条件熵等于极限熵，因此条件熵对于二维离散平稳信源，条件熵等于极限熵，因此条件熵就是二维离散平稳信源的真实熵。就是二维离散平稳信源的真实熵。对于一般信源，求出极限熵对于一般信源，求出极限熵是很困难的是很困难的，然而，一般来说，取，然而，一般来说，取N N不大时就可以得到与极限不大时就可以得到与极限熵非常接近的条件熵和平均符号熵，因此可以用熵非常接近的条件熵和平均符号熵，因此可以用条件熵条件熵和和平均平均符号熵符号熵来近似极限熵来近似极限
77、熵2.22.2多符号离散平稳信源多符号离散平稳信源2021/5/2387课堂练习：课堂练习： 分别写出分别写出I(xI(xi i),I(x),I(xi iy yj j),I(x),I(xi i|y|yj j),I(x),I(xi i;y;yj j),H(X),),H(X),H(Y),H(XY),H(X|Y),H(Y|X),I(X;Y)H(Y),H(XY),H(X|Y),H(Y|X),I(X;Y)的表达式，并说的表达式，并说明其含义。明其含义。2.22.2多符号离散平稳信源多符号离散平稳信源2021/5/23882.22.2多符号离散平稳信源多符号离散平稳信源n 马尔可夫信源马尔可夫信源 在很多
78、信源的输出序列中，符号之间的依赖关系是有限的，在很多信源的输出序列中，符号之间的依赖关系是有限的，任何时刻信源符号发生的概率只与任何时刻信源符号发生的概率只与前边已经发出的若干个符号前边已经发出的若干个符号有关有关，而，而与更前面的符号无关与更前面的符号无关。 为了描述这类信源除了为了描述这类信源除了信源符号集信源符号集外还要引入外还要引入状态集状态集。这。这时，信源输出消息符号还与信源所处的状态有关。时，信源输出消息符号还与信源所处的状态有关。 若一个信源满足下面两个条件，则称为若一个信源满足下面两个条件，则称为马尔可夫信源马尔可夫信源： （1 1）某一时刻信源输出的符号的概率只与当前所处的
79、）某一时刻信源输出的符号的概率只与当前所处的状态状态有关，而与以前的状态无关；有关，而与以前的状态无关； （2 2）信源的）信源的当前当前状态状态由当前输出符号和前一时刻信源由当前输出符号和前一时刻信源状态状态唯一确定。唯一确定。2021/5/23892.22.2多符号离散平稳信源多符号离散平稳信源当信源在当信源在(m+1)(m+1)时刻发出符号时刻发出符号 时，我们可把时，我们可把sj看成另一种看成另一种状态：状态：m m时刻的状态时刻的状态m+1m+1时刻的状态时刻的状态 所谓所谓“状态状态”，指与当前输出符号有关的前，指与当前输出符号有关的前m m个随机变量序列个随机变量序列( (X1X
80、2Xm)的某一具体消息，用的某一具体消息，用si表示，把这个具体消息看作是某表示，把这个具体消息看作是某个状态。个状态。2021/5/2390,X1, X2, ,Xm-1, Xm, Xm+1, sisj2.22.2多符号离散平稳信源多符号离散平稳信源 某一时刻信源输出的符号的概率只与某一时刻信源输出的符号的概率只与当前所处的状态当前所处的状态有关，而有关，而与以前的状态无关。或者说只与与以前的状态无关。或者说只与此前已输出的若干个符号有关此前已输出的若干个符号有关。即。即把此前已输出的符号把此前已输出的符号视为状态视为状态 信源的当前状态由当前输出符号和前一时刻信源状态唯一确定信源的当前状态由
81、当前输出符号和前一时刻信源状态唯一确定。 该条件表明，若信源处于某一状态该条件表明，若信源处于某一状态 ，当它发出一个符号，当它发出一个符号后，所处的状态就变了，一定转移到另一状态。状态的转移依赖后，所处的状态就变了，一定转移到另一状态。状态的转移依赖于发出的信源符号，因此任何时刻信源处在什么状态完全由前一于发出的信源符号，因此任何时刻信源处在什么状态完全由前一时刻的状态和当前发出的符号决定。将信源输出符号的不确定性时刻的状态和当前发出的符号决定。将信源输出符号的不确定性问题变换为讨论信源状态转换问题。状态之间的一步转移概率为问题变换为讨论信源状态转换问题。状态之间的一步转移概率为: : p(
82、sj|si)2021/5/23912.22.2多符号离散平稳信源多符号离散平稳信源 由上例可知，由上例可知，m m阶马尔可夫信源符号集共有阶马尔可夫信源符号集共有n n个符号，则信个符号，则信源共有源共有 个不同状态。信源在某一时刻时，必然处于某一种个不同状态。信源在某一时刻时，必然处于某一种状态，等到下一个符号输出时，转移到另外一个状态。状态，等到下一个符号输出时，转移到另外一个状态。 从而得到马尔可夫信源的状态空间。从而得到马尔可夫信源的状态空间。 其其状态转移图状态转移图如下页。在状态转换图中，把信如下页。在状态转换图中，把信源的每一种状态用圆圈表示，用有向箭头表示信源源的每一种状态用圆
83、圈表示，用有向箭头表示信源发出某一符号后由一种状态到另一状态的转移。发出某一符号后由一种状态到另一状态的转移。2021/5/2392例：设有一二进制一阶马尔可夫信源，信源符号集为例：设有一二进制一阶马尔可夫信源，信源符号集为1,01,0， 条件概率定为：条件概率定为：P(0|0)=0.25P(0|0)=0.25 P(0|1)=0.50 P(0|1)=0.50 P(1|0)=0.75 P(1|0)=0.75 P(1|1)=0.50 P(1|1)=0.50 由于信源符号数由于信源符号数q=2q=2，因此二进制一阶信源仅有两个状态：，因此二进制一阶信源仅有两个状态：S S0 0=0,S=0,S1 1
84、=1.=1. 由条件概率求得信源的状态由条件概率求得信源的状态转移概率转移概率为：为： P(S P(S1 1|S|S1 1)=0.25; P(S)=0.25; P(S1 1|S|S2 2)=0.50; )=0.50; P(S P(S2 2|S|S1 1)=0.75; P(S)=0.75; P(S2 2|S|S2 2)=0.50.)=0.50. 2.22.2多符号离散平稳信源多符号离散平稳信源2021/5/2393 例例 设信源符号设信源符号 Xx1, x2, x3 ，信源所处的状态，信源所处的状态Se1, e2, e3, e4, e5 。各状态之间的转移情况由下。各状态之间的转移情况由下图给出
85、。图给出。2.22.2多符号离散平稳信源多符号离散平稳信源2021/5/2394将图中信源在将图中信源在ei状态下发符号状态下发符号xk 的条件概率的条件概率p(xk /ei)用矩阵表示用矩阵表示可以看出可以看出2021/5/23952.22.2多符号离散平稳信源多符号离散平稳信源 M M阶马尔可夫信源的平均信息量，即信源的极限熵阶马尔可夫信源的平均信息量，即信源的极限熵2021/5/2396马尔可夫链的平稳分布马尔可夫链的平稳分布若齐次马尔可夫链对一切若齐次马尔可夫链对一切i,ji,j存在不依赖于存在不依赖于i i的极限的极限 则称其具有遍历性，则称其具有遍历性，p(si i) )称称为平稳
86、分布。为平稳分布。2.22.2多符号离散平稳信源多符号离散平稳信源且满足且满足2021/5/23972.22.2多符号离散平稳信源多符号离散平稳信源2021/5/23982.22.2多符号离散平稳信源多符号离散平稳信源对于由二元信源对于由二元信源X0,1得到的状态空间得到的状态空间(s1,s2,s3,s4), ,容易验证容易验证求出稳定状态下的求出稳定状态下的p( (s sj j) ) ，称为，称为状态极限概率状态极限概率。将一步转移概率代入上式得将一步转移概率代入上式得 p(s1) = 0.8 p(s1)+0.5 p(s3) p(s2) = 0.2 p(s1)+0.5 p(s3) p(s3)
87、 = 0.5 p(s2)+0.2 p(s4) p(s4) = 0.5 p(s2)+0.8 p(s4)2021/5/23992.22.2多符号离散平稳信源多符号离散平稳信源解方程组得解方程组得 p(s1)= p(s4)=5/14 p(s2)= p(s3)=2/14计算极限熵计算极限熵2021/5/231002.22.2多符号离散平稳信源多符号离散平稳信源n 信源的相关性和剩余度信源的相关性和剩余度 平均符号熵随平均符号熵随N N增加是非递增的增加是非递增的, ,也就是说信源输出符号间也就是说信源输出符号间的相关程度越长，信源的实际熵越小，趋近于极限熵；若相关的相关程度越长，信源的实际熵越小，趋近
88、于极限熵；若相关程度减小，信源实际熵增大。程度减小，信源实际熵增大。 当信源输出符号间彼此不存在依存关系，且为等概率分布当信源输出符号间彼此不存在依存关系，且为等概率分布时，信源实际熵趋于最大熵时，信源实际熵趋于最大熵H0 为了衡量信源的相关程度，引入信源剩余度为了衡量信源的相关程度，引入信源剩余度(冗余度冗余度)的概念。的概念。2021/5/23101 冗余度（多余度、剩余度）表示给定信源在实际发出消冗余度（多余度、剩余度）表示给定信源在实际发出消息时所包含的多余信息。冗余度来自两个方面：息时所包含的多余信息。冗余度来自两个方面： 一是信源符号间的相关性，由于信源输出符号间的依赖一是信源符号
89、间的相关性，由于信源输出符号间的依赖关系使得信源熵减小，这就是信源的相关性。相关程度越大，关系使得信源熵减小，这就是信源的相关性。相关程度越大，信源的实际熵越小，趋于极限熵信源的实际熵越小，趋于极限熵H H (X)(X)；反之相关程度减小，；反之相关程度减小，信源实际熵就增大。信源实际熵就增大。 另一个方面是信源符号分布的不均匀性，当等概率分布另一个方面是信源符号分布的不均匀性，当等概率分布时信源熵最大。而实际应用中大多是不均匀分布，使得实际时信源熵最大。而实际应用中大多是不均匀分布，使得实际熵减小。当信源输出符号间彼此不存在依赖关系且为等概率熵减小。当信源输出符号间彼此不存在依赖关系且为等概
90、率分布时，信源实际熵趋于最大分布时，信源实际熵趋于最大H H0 0(X)(X)。 相对熵率相对熵率 = H/H0 冗余度冗余度 R = 1 - 2.22.2多符号离散平稳信源多符号离散平稳信源2021/5/23102自然语言的熵自然语言的熵（1 1）对于英文字母）对于英文字母（2 2）对于中文）对于中文我们可以压缩剩余度来压缩信源，提高通信的可靠性。我们可以压缩剩余度来压缩信源，提高通信的可靠性。2.22.2多符号离散平稳信源多符号离散平稳信源2021/5/23103正是因为原始的信息都有冗余，才有可能对信息进行压缩，正是因为原始的信息都有冗余，才有可能对信息进行压缩，以尽量减少冗余，提高每个
91、符号携带的信息量；但另一方面，以尽量减少冗余，提高每个符号携带的信息量；但另一方面，冗余信息可以提高信息的抗干扰能力，如果信息的某部分在冗余信息可以提高信息的抗干扰能力，如果信息的某部分在传输中被损坏，则通过冗余有可能将其恢复。传输中被损坏，则通过冗余有可能将其恢复。 ( (冗余小冗余小, ,有效有效) ) ( (冗余大冗余大, ,可靠可靠) ) 中国中国 中华人民共和国中华人民共和国从提高信息传输效率的角度出发，总是希望减少剩余度（压从提高信息传输效率的角度出发，总是希望减少剩余度（压缩），这是信源编码的作用；从提高信息抗干扰能力来看，缩），这是信源编码的作用；从提高信息抗干扰能力来看，总是
92、希望增加或保留剩余度，这是信道编码的作用。总是希望增加或保留剩余度，这是信道编码的作用。2.22.2多符号离散平稳信源多符号离散平稳信源2021/5/23104n 作业：作业： 2.13(P69), 2.16(P69) , 2.17(P69)2.22.2多符号离散平稳信源多符号离散平稳信源2021/5/231052.32.3连续信源连续信源n 连续信源的熵连续信源的熵连续信源是指输出在时间和取值上都连续的信源连续信源是指输出在时间和取值上都连续的信源属随机过程属随机过程x(t)x(t)，以概率密度描述，以概率密度描述平稳过程平稳过程 统计特性与时间起点无关统计特性与时间起点无关遍历过程遍历过程
93、 集平均集平均= =时间平均的平稳过程时间平均的平稳过程2021/5/231062.32.3连续信源连续信源 熵计算两种方法熵计算两种方法 法一法一 连续消息连续消息离散消息离散消息 再用离散信源方法计算再用离散信源方法计算 法二法二 连续消息抽样连续消息抽样时间离散的连续消息时间离散的连续消息 分析时先量化，再令分析时先量化，再令0 02021/5/23107 分类分类 单变量信源单变量信源无记忆信源无记忆信源 ( (与单符号离散源相似与单符号离散源相似) ) 随机过程中取一个时间随机过程中取一个时间t t1 1 多变量信源多变量信源有记忆信源有记忆信源 ( (与多符号离散源相似与多符号离散
94、源相似) ) 随机过程中取多个时间随机过程中取多个时间t ti i 说明说明 对单变量信源，可研究：数学期望、方差对单变量信源，可研究：数学期望、方差 对两变量信源，可研究：自相关函数对两变量信源，可研究：自相关函数2.32.3连续信源连续信源2021/5/231082.32.3连续信源连续信源2021/5/23109一、一、 单变量连续信源数学模型单变量连续信源数学模型 RR连续变量连续变量X X的取值范围的取值范围二、二、 连续信源的熵连续信源的熵由法二得由法二得 ：( (图图2.3.1)2.3.1) 上式中第上式中第2 2项为项为 即连续信源熵值无穷大即连续信源熵值无穷大( (取值可能性
95、无限多取值可能性无限多) )舍第舍第2 2项得定义项得定义( (相对熵相对熵) )2.32.3连续信源连续信源2021/5/23110二、二、 连续信源的熵连续信源的熵 两个连续变量两个连续变量 联合熵联合熵条件熵条件熵2.32.3连续信源连续信源2021/5/231112.3.2 2.3.2 几种特殊连续信源的熵和最大熵定理几种特殊连续信源的熵和最大熵定理一、均匀分布信源：一、均匀分布信源： H Hc c( (X X)= log)= log2 2( (b b- -a a) ) 结论结论 熵值只与均匀分布间隔熵值只与均匀分布间隔( (b b- -a a) )有关，有关， 若若 b b- -a
96、a 1 R 单符号熵单符号熵H(X)H(X)时可做到几乎无失时可做到几乎无失真译码，条件是真译码，条件是L L大。大。 只要只要 , ,译码差错率必小于译码差错率必小于 信源序列自信息方差信源序列自信息方差2.42.4 离散无失真信源编码定理离散无失真信源编码定理2021/5/23125(3) 逆定理指出：逆定理指出：若若R比比H(X) 小一个小一个 时，译码差错未必超过时，译码差错未必超过 若若R比比H(X) 小两个小两个 时，译码差错必定大于时，译码差错必定大于 L时必失真时必失真(4)结论结论(单符号单符号)信源熵信源熵H(X)实为一个界限实为一个界限 当当 RH(X)时时 无失真译码无
97、失真译码当当 RH(X) 时时 有失真译码有失真译码(4)(4)逆定理指出：逆定理指出：若若R比比H( (X) ) 小一个小一个 时，译码差错未必超过时，译码差错未必超过 若若R比比H( (X) ) 小两个小两个 时，译码差错必定大于时，译码差错必定大于 L时必失真时必失真(5)(5)结论结论( (单符号单符号) )信源熵信源熵H( (X) )实为一个界限实为一个界限 当当 RH( (X) )时时 无失真译码无失真译码 当当 RH( (X) )时时 有失真译码有失真译码2.42.4 离散无失真信源编码定理离散无失真信源编码定理2021/5/23126 例例2 2 给定信源模型：给定信源模型：8
98、 8种符号和概率种符号和概率 算得：算得：H(X)=2.55 bit /2.55 bit /信源符号，信源符号， 2(X) =1.323 =1.323若要求：编码效率若要求：编码效率 =90%=90%，由，由 得得 =0.28=0.28若要求若要求: : 译码差错率译码差错率=10=10-6-6 , , 则则L太大太大 此外，此外， 相对熵率不高相对熵率不高2.42.4 离散无失真信源编码定理离散无失真信源编码定理2021/5/23127第三章第三章 信道容量信道容量信息论与编码信息论与编码主讲：苗立刚主讲：苗立刚基础楼基础楼318 计算机与通信工程学院计算机与通信工程学院2014年年3月月2
99、021/5/23128第三章第三章 信道容量信道容量3.1 单符号离散信道的数学模型（重点）单符号离散信道的数学模型（重点）3.2 单符号离散信道的信道容量（重点）单符号离散信道的信道容量（重点）3.3 多符号离散信道的信道容量（重点）多符号离散信道的信道容量（重点）3.4 网络信息理论（自学）网络信息理论（自学）3.5 连续信道（自学）连续信道（自学）3.6 信道编码定理（重点）信道编码定理（重点）n 本章主要讨论的问题：本章主要讨论的问题：2021/5/231293.13.1单符号离散信道的数学模型单符号离散信道的数学模型n 单符号离散信道的数学模型及其分类单符号离散信道的数学模型及其分类
100、 信道的数学模型信道的数学模型 P(Y/X)XYX X 输入事件的集合输入事件的集合, , 概率空间为概率空间为X PX PY Y 输出事件的集合输出事件的集合, , 概率空间为概率空间为Y PY P信宿信宿信道信道信源信源 通信系统的简化模型通信系统的简化模型噪声噪声2021/5/23130 信道的分类信道的分类 1 1、根据信道用户的多少，分为：、根据信道用户的多少，分为：单用户信道单用户信道-输入、输出均只有一个输入、输出均只有一个多用户信道多用户信道-输入、输出有多个输入、输出有多个2 2、根据输入输出信号的特点，分为：、根据输入输出信号的特点，分为：离散信道离散信道-输入、输出随机变
101、量均离散取值输入、输出随机变量均离散取值连续信道连续信道-输入、输出随机变量均连续取值输入、输出随机变量均连续取值半离散半离散( (连续连续) )信道信道- - 一为离散，另一为连续一为离散，另一为连续3、根据输入、输出随机变量的个数、根据输入、输出随机变量的个数单符号信道单符号信道-输入、输出均用输入、输出均用随机变量随机变量表示表示多符号信道多符号信道-输入、输出用输入、输出用随机矢量随机矢量表示表示3.13.1单符号离散信道的数学模型单符号离散信道的数学模型2021/5/231314 4、根据信道上有无噪声、根据信道上有无噪声( (干扰干扰) ) ：有噪有噪( (扰扰) )信道信道无噪无
102、噪( (扰扰) )信道信道5 5、根据信道有无记忆特性、根据信道有无记忆特性无记忆信道无记忆信道-输出仅与当前输入有关，与先前输入无关输出仅与当前输入有关，与先前输入无关有记忆信道有记忆信道-输出不仅与当前输入有关，还与先前输入有输出不仅与当前输入有关，还与先前输入有关关3.13.1单符号离散信道的数学模型单符号离散信道的数学模型2021/5/23132 离散信道的数学模型离散信道的数学模型n 信道容量的定义信道容量的定义设离散信道的输入空间为设离散信道的输入空间为输出空间为输出空间为概率分布为概率分布为概率分布为概率分布为3.23.2单符号离散信道的信道容量单符号离散信道的信道容量并有条件概
103、率并有条件概率条件概率被称为条件概率被称为信道的传递概率或转移概率信道的传递概率或转移概率。 X Y2021/5/23133将所有转移概率以矩阵方式列出，得：将所有转移概率以矩阵方式列出，得：其中其中该矩阵完全描述了信道在干扰作用下的统计特性，称该矩阵完全描述了信道在干扰作用下的统计特性，称为为信道矩阵信道矩阵(n行行m列列)。3.23.2单符号离散信道的信道容量单符号离散信道的信道容量2021/5/23134反信道矩阵（反信道矩阵（m行行n列）列）其中其中3.23.2单符号离散信道的信道容量单符号离散信道的信道容量2021/5/231353.23.2单符号离散信道的信道容量单符号离散信道的信
104、道容量（1 1）联合概率）联合概率其中其中称为称为前向概率前向概率，描述信道的噪声特性，描述信道的噪声特性称为称为后向概率后向概率，有时也把有时也把 称为称为先验概率先验概率 称为称为后验概率后验概率（2 2）输出符号的概率）输出符号的概率（3 3）后验概率）后验概率表明输出端收到任一符号，必定是输入端某一符号输入所致表明输出端收到任一符号，必定是输入端某一符号输入所致 离散信道中的概率关系离散信道中的概率关系2021/5/231363.23.2单符号离散信道的信道容量单符号离散信道的信道容量n 信道容量的定义信道容量的定义含义：含义：给定信道时，对应各种信源分布，求取的最大平均互信息；给定信
105、道时，对应各种信源分布，求取的最大平均互信息；给定信道时，理论上能传输的最大信息量，表征信道传送信息给定信道时，理论上能传输的最大信息量，表征信道传送信息的最大能力；的最大能力； 信道容量定义为平均互信息的最大值：信道容量定义为平均互信息的最大值： 平均互信息平均互信息I(X;Y)I(X;Y)是信源分布是信源分布p(x)p(x)的上凸函数，是信道传的上凸函数，是信道传递概率递概率p(y|x)p(y|x)的下凸函数。对于一个固定的信道，总存在一种的下凸函数。对于一个固定的信道，总存在一种信源，使传输每个符号平均获得的信息量信源，使传输每个符号平均获得的信息量I(X;Y)I(X;Y)最大。最大。
106、信道容量信道容量C C只与信道的统计特性只与信道的统计特性p(y|x)p(y|x)有关，而与信源的分有关，而与信源的分布布p(x)p(x)无关。它是信道的特征参数，反应的是信道的最大的信无关。它是信道的特征参数，反应的是信道的最大的信息传输能力。息传输能力。2021/5/23137信息传输速率信息传输速率Rt:Rt: 单位时间内平均传输的信息量单位时间内平均传输的信息量信息传输率信息传输率R:R: 信道中平均每个符号所能传送的信息量。由于信道中平均每个符号所能传送的信息量。由于平均互信息平均互信息I(X;Y)I(X;Y)的含义是接收到符号的含义是接收到符号Y Y后，平均每个符号获得后，平均每个
107、符号获得的关于的关于X X的信息量，因此信道信息传输率就是平均互信息。的信息量，因此信道信息传输率就是平均互信息。最大信息传输速率最大信息传输速率Ct:Ct: 单位时间内平均传输的最大信息量单位时间内平均传输的最大信息量3.23.2单符号离散信道的信道容量单符号离散信道的信道容量2021/5/23138例：对于二元对称信道例：对于二元对称信道如果信源分布如果信源分布X=p,1-pX=p,1-p，则，则 qq10YX3.23.2单符号离散信道的信道容量单符号离散信道的信道容量1-H(q)0 0.5 1 pI(X;Y)信道容量为：信道容量为： 2021/5/231393.23.2单符号离散信道的信
108、道容量单符号离散信道的信道容量 无损确定信道：无损确定信道：一对一一对一（n=mn=m）信道矩阵信道矩阵：单位阵：单位阵损失熵损失熵 H(X/Y) = 0 H(X/Y) = 0 噪声熵噪声熵 H(Y/X) = 0H(Y/X) = 0I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X) H(X) = H(X) = H(Y)H(Y)n 离散离散无噪无噪信道：信道：输出输出Y Y和输入和输入X X有确定关系（广义）有确定关系（广义）a1a2a3 anb1b2b3 bn 2021/5/231403.23.2单符号离散信道的信道容量单符
109、号离散信道的信道容量 无损信道：无损信道：一对多一对多（n nm m）具有扩展性的无噪信道具有扩展性的无噪信道信道矩阵信道矩阵：每列只有一个非：每列只有一个非0 0元素，不元素，不全是全是0 0、1 1信道疑义度（损失熵）信道疑义度（损失熵） H(X/Y)=0H(X/Y)=0噪声熵噪声熵 H(Y/X)0H(Y/X)0I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X)I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X) H(X) H(X)H(Y) H(Y) 思考：思考：p(x)p(x)应该应该怎样取值？怎样取值？a1a2a3b1b2b3b4 b52021/5
110、/231413.23.2单符号离散信道的信道容量单符号离散信道的信道容量 确定信道：确定信道：多对一多对一（nmnm）具有归并性的无噪信道具有归并性的无噪信道信道矩阵信道矩阵：每行只有一个元素：每行只有一个元素“1 1”，其它全是其它全是0 0损失熵损失熵 H(X/Y) 0H(X/Y) 0噪声熵噪声熵 H(Y/X) = 0H(Y/X) = 0I(X;Y)=H(X)-H(X|Y)=H(Y)-I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(Y)H(Y|X)=H(Y) H(X) H(X) H(Y)H(Y)思考：思考：p(x)p(x)应该应该怎样取值？怎样取值？b1b2b3a1a2a
111、3a4 a52021/5/23142n 强对称离散信道强对称离散信道( (均匀信道均匀信道) )3.23.2单符号离散信道的信道容量单符号离散信道的信道容量信道特点信道特点 信道输入、输出均为信道输入、输出均为n n元元 每符号正确传输概率均为每符号正确传输概率均为 其他符号错误传输概率为其他符号错误传输概率为p/(n-1)p/(n-1)矩阵特点矩阵特点 (1)nn(1)nn阶对称阵阶对称阵 (2)(2)每行和为每行和为1,1,每列和为每列和为1 12021/5/231433.23.2单符号离散信道的信道容量单符号离散信道的信道容量 信道容量信道容量 可以看出，当输出等概分布时，即可以看出，当
112、输出等概分布时，即H(Y)=logH(Y)=log2 2n n时时达到信道容量。达到信道容量。2021/5/231443.23.2单符号离散信道的信道容量单符号离散信道的信道容量 那么，在什么样的信源输入情况下，信道输出能等那么，在什么样的信源输入情况下，信道输出能等概分布呢？可以证明，输入等概分布时，离散对称信道概分布呢？可以证明，输入等概分布时，离散对称信道的输出也为等概分布的输出也为等概分布 结论结论 对强对称信道，对强对称信道，输入等概输入等概输出等概输出等概，可达到可达到C C2021/5/231453.23.2单符号离散信道的信道容量单符号离散信道的信道容量二进制对称信道二进制对称
113、信道(n=2)(n=2)0 0.5 1 p1C2021/5/231463.23.2单符号离散信道的信道容量单符号离散信道的信道容量行可排列行可排列矩阵每行各元素都来自同一集合矩阵每行各元素都来自同一集合Q Qq1,q2,qm( (排列可不同排列可不同) ) 列可排列列可排列矩阵每列各元素都来自同一集合矩阵每列各元素都来自同一集合P Pp1,p2,pn( (排列可不同排列可不同) ) 矩阵可排列矩阵可排列矩阵的行、列皆可排列矩阵的行、列皆可排列对称信道对称信道信道矩阵可排列信道矩阵可排列n 离散对称信道离散对称信道 (1)(1)m=n 时，时，Q、P为同一集合为同一集合 mn时，时，Q、P中，一
114、个必为另一个的子集中，一个必为另一个的子集 (2)(2)输入等概输入等概输出等概输出等概2021/5/231473.23.2单符号离散信道的信道容量单符号离散信道的信道容量 离散输入对称信道离散输入对称信道 如果一个离散无记忆信道的信道矩阵中，每一行都是其他如果一个离散无记忆信道的信道矩阵中，每一行都是其他行的同一组元素的不同排列，则称此类信道为离散输入对称信行的同一组元素的不同排列，则称此类信道为离散输入对称信道。道。 离散输出对称信道离散输出对称信道 如果一个离散无记忆信道的信道矩阵中，每一列都是其他如果一个离散无记忆信道的信道矩阵中，每一列都是其他列的同一组元素的不同排列，则称此类信道为
115、离散输出对称信列的同一组元素的不同排列，则称此类信道为离散输出对称信道。道。2021/5/231483.23.2单符号离散信道的信道容量单符号离散信道的信道容量 离散对称信道离散对称信道 如果一个离散无记忆信道的信道矩阵中，每一行都是其他如果一个离散无记忆信道的信道矩阵中，每一行都是其他行的同一组元素的不同排列，并且每一列都是其他列的同一组行的同一组元素的不同排列，并且每一列都是其他列的同一组元素的不同排列，则称此类信道为离散对称信道。元素的不同排列，则称此类信道为离散对称信道。2021/5/23149 离散对称信道的信道容量离散对称信道的信道容量 定理：如果一个定理：如果一个离散对称信道离散
116、对称信道具有具有n n个输入符号，个输入符号，m m个输出符个输出符 号，则当输入为等概率分布时，达到信道容量号，则当输入为等概率分布时，达到信道容量C C。3.23.2单符号离散信道的信道容量单符号离散信道的信道容量对于行可排列情况，对于行可排列情况，Hmi与与i 无关无关可以看出，当输出等概分布时，即可以看出，当输出等概分布时，即H(Y)=logH(Y)=log2 2m m时达到信道容量。时达到信道容量。由于对称信道的特点，输入等概率分布由于对称信道的特点，输入等概率分布输出等概率分布。输出等概率分布。2021/5/23150n准对称离散信道准对称离散信道 信道矩阵的行可排列，列不可排列信
117、道矩阵的行可排列，列不可排列但把该矩阵在水平方向上分割，但把该矩阵在水平方向上分割， 则各子矩阵皆具可排列性则各子矩阵皆具可排列性 例例 关键关键 H(Y)最大最大( (改变改变p(xi)时时) )3.23.2单符号离散信道的信道容量单符号离散信道的信道容量思考：思考：p(xi)应该应该怎样取值？怎样取值？P79P792021/5/231513.23.2单符号离散信道的信道容量单符号离散信道的信道容量 将将H(Y)H(Y)中的中的m m项分解成项分解成s s个子集个子集M M1 1,M,M2 2,M,Ms s, ,各个子集分别有各个子集分别有m m1 1,m,m2 2,m,ms s个元素个元素
118、(m(m1 1+m+m2 2+m+ms s=m),=m),则则则则2021/5/231523.23.2单符号离散信道的信道容量单符号离散信道的信道容量由由故有故有即即2021/5/231533.23.2单符号离散信道的信道容量单符号离散信道的信道容量 各个子矩阵具有可排列性各个子矩阵具有可排列性, ,只要信源呈等概率分布，即可只要信源呈等概率分布，即可使第使第k k个子集中的输出概率相等，即达到其均值。个子集中的输出概率相等，即达到其均值。 相应的准对称信道的容量为相应的准对称信道的容量为2021/5/231543.23.2单符号离散信道的信道容量单符号离散信道的信道容量 例例 2021/5/
119、23155n 离散信道容量的一般计算方法离散信道容量的一般计算方法P81P813.23.2单符号离散信道的信道容量单符号离散信道的信道容量 对于固定的信道，平均互信息对于固定的信道，平均互信息I(X;Y)是信源概率分布是信源概率分布p(xi)的的上凸函数上凸函数, ,所以极大值一定存在。所以极大值一定存在。 I(X;Y)是是n个变量个变量p(ai)(i=1,2,n)的多元函数，并满足的多元函数，并满足 所以可以用拉格朗日乘子法计算条件极值所以可以用拉格朗日乘子法计算条件极值: :其中，其中， 为拉格朗日乘子为拉格朗日乘子2021/5/231563.23.2单符号离散信道的信道容量单符号离散信道
120、的信道容量解方程组解方程组可得一般信道容量可得一般信道容量C。由由I(X;Y) = H(Y) - H(Y|X)H(Y)H(Y|X)2021/5/23157I(X;Y)最大值最大值3.23.2单符号离散信道的信道容量单符号离散信道的信道容量令令则则若若m=n,则可求解则可求解2021/5/231583.23.2单符号离散信道的信道容量单符号离散信道的信道容量一般离散信道容量的求解步骤：一般离散信道容量的求解步骤：(1)(2)(3) (4)需要确认所有的需要确认所有的 ，所求的，所求的C才存在。才存在。2021/5/231593.23.2单符号离散信道的信道容量单符号离散信道的信道容量例：例：可列
121、方程组：可列方程组：2021/5/23160解之得：解之得：3.23.2单符号离散信道的信道容量单符号离散信道的信道容量2021/5/231613.33.3多符号离散信道的信道容量多符号离散信道的信道容量n 多符号离散信道的数学模型多符号离散信道的数学模型 多符号离散信源多符号离散信源X=X1X2 Xk .XN在在N个不同时刻分别个不同时刻分别通过单符号离散信道通过单符号离散信道 X P(Y/X) Y，在输出端出现在输出端出现Y=Y1Y2 Yk .YN，形成一个新的信道，此即，形成一个新的信道，此即多符号离散信道。多符号离散信道。由于新由于新信道相当于单符号离散信道在信道相当于单符号离散信道在
122、N N个不同的时刻连续运用了个不同的时刻连续运用了N N次，次，也称为也称为单符号离散信道的单符号离散信道的N次扩展信道次扩展信道 基本概念基本概念2021/5/231623.33.3多符号离散信道的信道容量多符号离散信道的信道容量Xk取值取值: a1,a2,an, 则则X共有共有nN种种 , i=1nNYk取值取值: b1,b2,bm, 则则Y共有共有mN种种 , j=1mNP(Y/X)或或p(bj/ai)X=X1X2 Xk .XNY=Y1Y2 Yk .YN 多符号离散信道的数学模型多符号离散信道的数学模型2021/5/23163 信道矩阵信道矩阵3.33.3多符号离散信道的信道容量多符号离
123、散信道的信道容量每行元素之和等于每行元素之和等于1 12021/5/231643.33.3多符号离散信道的信道容量多符号离散信道的信道容量n 离散无记忆扩展信道的信道容量离散无记忆扩展信道的信道容量X=X1X2 Xk .XNY=Y1Y2 Yk .YN P(Y1/X1)P(Y1/X1)P(Y1/X1)X1 Y1X2 Y2XN YN 把把多符号离散信道多符号离散信道理解成理解成单符号离散信道单符号离散信道在每一个单位时间在每一个单位时间传递一个随机变量的时候，需要考虑传递一个随机变量的时候，需要考虑k时刻的输出变量时刻的输出变量Yk与时刻与时刻k之前的输入变量之前的输入变量X1X2Xk-1和输出变
124、量和输出变量Y1Y2Yk-1之间有无依赖关系。之间有无依赖关系。单符号离散信道的单符号离散信道的N次扩展信道的数学模型次扩展信道的数学模型2021/5/23165 若若多符号离散信道多符号离散信道的转移概率满足的转移概率满足 则称之为则称之为离散无记忆信道的离散无记忆信道的N次扩展信道次扩展信道 解释解释 扩展信道的转移概率扩展信道的转移概率 = =各时刻单符号信道转移概率的连乘各时刻单符号信道转移概率的连乘 无记忆性无记忆性k时刻输出时刻输出Yk只与只与k 时刻输入时刻输入Xk有关有关, 与与k时刻之前输入时刻之前输入X1X2 Xk-1无关无关 无预感性无预感性k时刻之前输出时刻之前输出Y1
125、Y2 Yk-1只与只与k时刻之前输时刻之前输 入入X1X2 Xk-1有关有关，与与Xk无关无关结论结论 离散无记忆离散无记忆N次扩展信道次扩展信道无记忆，无预感无记忆，无预感3.33.3多符号离散信道的信道容量多符号离散信道的信道容量2021/5/231663.33.3多符号离散信道的信道容量多符号离散信道的信道容量互信息和信道容量互信息和信道容量离散无记忆离散无记忆N次扩展信道两端的平均互信息次扩展信道两端的平均互信息I(X;Y)=H(Y) - H(Y|X) 由于信道无记忆由于信道无记忆 当第当第k个随机变量个随机变量Xk单独通过单符号离散信道时，在输出端单独通过单符号离散信道时，在输出端得
126、到的关于得到的关于Xk的平均互信息量的平均互信息量2021/5/23167相减可得相减可得3.33.3多符号离散信道的信道容量多符号离散信道的信道容量 离散无记忆信道的离散无记忆信道的N N次扩展信道的平均互信息，不大于次扩展信道的平均互信息，不大于N N个随个随机变量机变量X1X2XN单独通过信道单独通过信道X P(Y|X) YX P(Y|X) Y的平均互信息之和。的平均互信息之和。 当且仅当信源当且仅当信源X= =X1X2XN无记忆无记忆, ,或信源或信源X是离散无记忆信是离散无记忆信源源X的的N次扩展信源时，等号成立。次扩展信源时，等号成立。 原因：原因： 离散无记忆信道的离散无记忆信道
127、的N次扩展信道，当输入端的次扩展信道，当输入端的N个输入随机个输入随机变量统计独立时，信道的总平均互信息等于这变量统计独立时，信道的总平均互信息等于这N个变量单独通过个变量单独通过信道的平均互信息之和。信道的平均互信息之和。2021/5/231683.33.3多符号离散信道的信道容量多符号离散信道的信道容量 对于离散无记忆信源的对于离散无记忆信源的N N次扩展信源次扩展信源 通过同一个离散无记忆信道信道通过同一个离散无记忆信道信道 X P(Y|X) Y 在信道输出端，随机变量序列在信道输出端，随机变量序列Y= =Y1Y2YN中的随机变量中的随机变量Yk 离散无记忆信道的离散无记忆信道的N N次
128、扩展信道，如果信源也是离散无记忆次扩展信道，如果信源也是离散无记忆信源的信源的N N次扩展信源，则信道总的平均互信息量是单符号离散无次扩展信源，则信道总的平均互信息量是单符号离散无记忆信道的平均互信息量的记忆信道的平均互信息量的N N倍。倍。2021/5/231693.33.3多符号离散信道的信道容量多符号离散信道的信道容量n独立并联信道独立并联信道含义含义 信道输入序列的各随机变量取值于不同符号集信道输入序列的各随机变量取值于不同符号集 信道输出序列的各随机变量亦取值于不同符号集信道输出序列的各随机变量亦取值于不同符号集 也称为独立并列信道、独立平行信道或积信道也称为独立并列信道、独立平行信
129、道或积信道信道容量信道容量当当N个输入随机变量之间统计独立，并且每个输入随机变量个输入随机变量之间统计独立，并且每个输入随机变量Xk的概率分布为达到各自信道容量的概率分布为达到各自信道容量Ck的最佳分布时，的最佳分布时，CN达到最大值达到最大值N个独立并联信道的信道容量等于个独立并联信道的信道容量等于各个信道容量之和各个信道容量之和2021/5/231703.63.6信道编码定理信道编码定理n信道编码定理信道编码定理 对离散平稳无记忆信道，其信道容量为对离散平稳无记忆信道，其信道容量为C，输入序列长度，输入序列长度为为L。只要实际信息率。只要实际信息率RC，就必可找到一种编码，当，就必可找到一
130、种编码，当L L足够足够长时，译码差错概率长时，译码差错概率Pe C，则对任何编码，则对任何编码，Pe必大于零。必大于零。 说明说明 前者为正定理，后者为逆定理前者为正定理，后者为逆定理给出了信息传输率的极限给出了信息传输率的极限 只要只要RC，必为有失真传输，必为有失真传输存在性定理存在性定理2021/5/23171作业：作业：3.1 (P99); 3.2 (P99)；3.11 (P100);3.14 (P101);3.15 (p101);3.33.3多符号离散信道的信道容量多符号离散信道的信道容量2021/5/23172第四章第四章 信息率失真函数信息率失真函数信息论基础信息论基础主讲：苗
131、立刚主讲：苗立刚基础楼基础楼318 计算机与通信工程学院计算机与通信工程学院2014年年3月月2021/5/231734.14.1 基本概念基本概念n 基本概念基本概念 在实际生活中，人们不一定要求完全无失真的恢复消息，在实际生活中，人们不一定要求完全无失真的恢复消息，也就是允许有一定的失真。如语音、图像。也就是允许有一定的失真。如语音、图像。 那么在允许一定程度失真的条件下，能够把信源信息压缩那么在允许一定程度失真的条件下，能够把信源信息压缩到什么程度，也就是，允许一定程度失真的条件下，如何能快到什么程度，也就是，允许一定程度失真的条件下，如何能快速的传输信息，这就是信息率失真理论所要讨论的
132、问题。速的传输信息，这就是信息率失真理论所要讨论的问题。 信道编码定理：信道编码定理：若若 R C，则传输总要产生失真。，则传输总要产生失真。 无失真信源编码定理：无失真信源编码定理： 要做到几乎无失真信源编码，要做到几乎无失真信源编码，R必须大于信源熵。故有必须大于信源熵。故有H(X)RC 失真失真2021/5/23174 信息率失真理论信息率失真理论香农于香农于1959年在年在保真度准则下的保真度准则下的离散信源编码定理离散信源编码定理中提出。定义了信息率失真函数中提出。定义了信息率失真函数R(D),明明确提出：在允许一定失真度确提出：在允许一定失真度D的情况下，信源输出的信息率的情况下，
133、信源输出的信息率可压缩到可压缩到R(D)值。值。 信息率失真理论是量化、数模转换、频带压缩和数据压信息率失真理论是量化、数模转换、频带压缩和数据压缩的理论基础。缩的理论基础。 I(X;Y)P(X)、P(Y/X)的二元函数的二元函数 固定固定P(Y/X) ，改变，改变P(X)得得I(X;Y)最大值最大值(上凸函数上凸函数) 信道容量信道容量 固定固定P(X)，改变，改变P(Y/X) 得得I(X;Y)最小值最小值(下凸函数下凸函数) 率失真函数率失真函数 信息率失真理论信息率失真理论4.1 基本概念基本概念2021/5/23175 若固定若固定P(X)，改变，改变P(Y/X) 得得I(X;Y)最小
134、值。最小值。 当当p(bj|ai)=p(bj) 时，即时，即X和和Y相互统计独立，该最小值等相互统计独立，该最小值等于零。这样求得的极小值就没有任何意义，因为信道不能传于零。这样求得的极小值就没有任何意义，因为信道不能传递任何信息，或者信源的信息全部损失掉了。递任何信息，或者信源的信息全部损失掉了。 如果限定一个失真度，则在失真度一定的情况下如果限定一个失真度，则在失真度一定的情况下(小于信小于信源熵源熵)，求信息率的极小值就具有非常重要的意义，它需要的，求信息率的极小值就具有非常重要的意义，它需要的信道资源最小。信道资源最小。 信息率失真函数信息率失真函数4.1 基本概念基本概念信息率失真信
135、息率失真允许失真允许失真所需信息率所需信息率2021/5/23176n 失真函数与平均失真度失真函数与平均失真度 失真函数失真函数信源信源信源信源编码编码信道信道编码编码信道信道信道信道译码译码信源信源译码译码信宿信宿干扰干扰 根据信道编码定理，我们可以把根据信道编码定理，我们可以把信道编码信道编码、信道信道和和信道解信道解码码等价成是一个没有任何干扰的广义信道，这样收信者收到消等价成是一个没有任何干扰的广义信道，这样收信者收到消息后，所产生的失真只是由信源编码带来的。我们也可以把信息后，所产生的失真只是由信源编码带来的。我们也可以把信源编码和信源译码等价成一个信道。源编码和信源译码等价成一个
136、信道。4.1 基本概念基本概念2021/5/23177设离散无记忆信源为设离散无记忆信源为 其概率分布为其概率分布为 对于每一对对于每一对( (ai, ,bj) )，我们指定一个非负的函数，我们指定一个非负的函数称为单个符号的称为单个符号的失真度失真度（或称（或称失真函数失真函数）接收端变量为接收端变量为 4.1 基本概念基本概念 其概率分布为其概率分布为 信道矩阵为信道矩阵为 2021/5/23178 失真函数用来表征信源发出一个符号失真函数用来表征信源发出一个符号 ，而在接收端再，而在接收端再现成符号现成符号 所引起的误差或失真。所引起的误差或失真。d越小表示失真越小，等越小表示失真越小，
137、等于于0 0表示没有失真。表示没有失真。 可以将所有的失真函数排列成矩阵的形式：可以将所有的失真函数排列成矩阵的形式：我们称它为我们称它为失真矩阵失真矩阵。n行行m列列4.1 基本概念基本概念2021/5/23179例：设信源符号序列例：设信源符号序列X=0,1X=0,1，接收端收到的符号序列为，接收端收到的符号序列为Y=0,1,2,Y=0,1,2,规定失真函数为：规定失真函数为：失真矩阵为：失真矩阵为：01012yjxi0.50010.514.1 基本概念基本概念2021/5/23180(1)失真矩阵为：失真矩阵为：若若a=1,=1,则为汉明失真函数则为汉明失真函数对所有不同的对所有不同的i
138、和和j引起引起的误差都一样，所以的误差都一样，所以定义失真度为常数定义失真度为常数a。4.1 基本概念基本概念2021/5/231814.1 基本概念基本概念(2) d(ai,bj) = (bjai)2 平方误差失真函数平方误差失真函数 失真矩阵称为平方误差失真矩阵。较大幅度的失真要比较失真矩阵称为平方误差失真矩阵。较大幅度的失真要比较小幅度的失真引起的错误更为严重，严重程度用平方表示。小幅度的失真引起的错误更为严重，严重程度用平方表示。说明说明: :最常用的失真函数最常用的失真函数 均方失真函数：均方失真函数： d(ai,bj)=(ai-bj)2 绝对失真函数：绝对失真函数： d(ai,bj
139、)=|ai-bj| 相对失真函数：相对失真函数： d(ai,bj)=|ai-bj|/|ai| 误码失真函数：误码失真函数： d(ai,bj)= 2021/5/23182(2)(2)最常用的失真函数及其适用性最常用的失真函数及其适用性 均均方方失失真真函函数数, ,绝绝对对失失真真函函数数, , 相相对对失失真真函函数数适适用用于于连连续续信信源源; ; 误码失真函数适用于离散信源。误码失真函数适用于离散信源。(3)(3)失真函数困难性比较失真函数困难性比较 均均方方失失真真和和绝绝对对失失真真只只与与(a(ai i-b-bj j) )有有关关，而而不不是是分分别别与与a ai i及及b bj
140、j有有关关，在在数数学学处处理理上上比比较较方方便便；相相对对失失真真与与主主观观特特性性比比较较匹匹配配，因因为为主主观观感感觉觉往往往往与与客客观观量量的的对对数数成成正正比比，但但在在数数学学处处理中就要困难得多。理中就要困难得多。 4.1 基本概念基本概念2021/5/23183 平均失真度平均失真度 失真函数的数学期望，平均意义上表示信道每传递一个符失真函数的数学期望，平均意义上表示信道每传递一个符号所引起的失真的大小。号所引起的失真的大小。4.1 基本概念基本概念 说明说明 由于由于xi和和yj都是随机变量，所以失真函数都是随机变量，所以失真函数d(xi,yj)也是随机变量，也是随
141、机变量，只能用它的数学期望或统计平均值，因此将失真函数的数学期望只能用它的数学期望或统计平均值，因此将失真函数的数学期望称为称为平均失真平均失真。是在平均意义上，对系统失真的总体描述是在平均意义上，对系统失真的总体描述是信源统计特性是信源统计特性p(xi)的函数的函数 是信道统计特性是信道统计特性p(yj| xi)的函数的函数 是规定失真度是规定失真度d(xi, yj)的函数的函数 若保持若保持p(xi)、d(xi, yj)不变，则平均失真度就是信道特性不变，则平均失真度就是信道特性p(yj|xi)的函数，的函数，是传输过程所产生的失真的总体度量。是传输过程所产生的失真的总体度量。2021/5
142、/231844.1 基本概念基本概念 保真度准则保真度准则 如果规定平均失真度如果规定平均失真度 不能超过某一限定的值不能超过某一限定的值D，即，即 则则D就是允许失真的上界就是允许失真的上界 在满足保真度准则前提下，求信息率最小值，即为信息率在满足保真度准则前提下，求信息率最小值，即为信息率失真函数。失真函数。2021/5/23185 离散无记忆信道的离散无记忆信道的N次扩展信道次扩展信道 输入序列输入序列XN=X1X2XN N位位, ,每位每位n种种, ,共有共有nN种序列种序列 输出序列输出序列 YN=Y1Y2YN N位位, ,每位每位m种种, ,共有共有mN种序列种序列(1)(1)输入
143、序列输入序列 和输出序列和输出序列 之间的失真函数之间的失真函数(2)(2)N次离散无记忆扩展信源和扩展信道的平均失真度次离散无记忆扩展信源和扩展信道的平均失真度是单是单符号时的符号时的N倍倍保真度准则保真度准则4.1 基本概念基本概念2021/5/23186例：设离散矢量信源例：设离散矢量信源N=3,N=3,输出矢量序列为输出矢量序列为X=XX=X1 1X X2 2X X3 3, ,其中其中X Xi i,i=1,2,3,i=1,2,3的取值为的取值为0,10,1；经信道传输后的输出为；经信道传输后的输出为Y=YY=Y1 1Y Y2 2Y Y3 3，其中其中Y Yi i,i=1,2,3,i=1
144、,2,3的取值为的取值为0,10,1。定义失真函数为：。定义失真函数为：失真函数为：失真函数为：4.1 基本概念基本概念2021/5/23187n 信息率失真函数信息率失真函数D D允许信道允许信道( (试验信道试验信道) ) 若平均失真度若平均失真度 不大于我们所允许的失真不大于我们所允许的失真D D，我们称此，我们称此为为保真度准则保真度准则。 凡满足保真度准则的这些试验信道称为凡满足保真度准则的这些试验信道称为D D允许信道（允许信道（D D允许允许的试验信道）的试验信道）。把所有。把所有D D允许信道组成一个集合，用符号允许信道组成一个集合，用符号 表示。表示。离散无记忆信源的离散无记
145、忆信源的N N次扩展信源和离散无记忆信道的次扩展信源和离散无记忆信道的N N次扩展信道：次扩展信道： 如果信息传输率如果信息传输率R大于信道容量大于信道容量C, ,就应该对信源压缩，使就应该对信源压缩，使其压缩后的信息率其压缩后的信息率R小于信道容量小于信道容量C，但要保证压缩引入的失，但要保证压缩引入的失真不超过预先规定的限度。真不超过预先规定的限度。4.1 基本概念基本概念2021/5/23188信息率失真函数的定义信息率失真函数的定义 当信源和失真函数给定后，我们总希望在满足保真度准当信源和失真函数给定后，我们总希望在满足保真度准则下寻找平均互信息的最小值，也就是在则下寻找平均互信息的最
146、小值，也就是在 中找一个信道，中找一个信道，使平均互信息取极小值。这个最小值就是在使平均互信息取极小值。这个最小值就是在 的条件下，的条件下，信源必须传输的最小平均信息量。信源必须传输的最小平均信息量。 改变试验信道求平均互信息的最小值，实质上是选择一种改变试验信道求平均互信息的最小值，实质上是选择一种编码方式使信息传输率为最小。编码方式使信息传输率为最小。R(D)是假定信源给定的情况是假定信源给定的情况下，在用户可以容忍的失真度内，再现信源消息所必须获得的下，在用户可以容忍的失真度内，再现信源消息所必须获得的最小平均互信息量。它反映的是信源的可压缩程度。最小平均互信息量。它反映的是信源的可压
147、缩程度。 试验信道的范围：只有能够满足保真度准则的那些信道。试验信道的范围：只有能够满足保真度准则的那些信道。从而使从而使I(X,Y)的最小值具有实用意义。的最小值具有实用意义。4.1 基本概念基本概念2021/5/23189 对于离散无记忆信源的对于离散无记忆信源的N次扩展信源和离散无记忆信道的次扩展信源和离散无记忆信道的N次扩展信道，其信息率失真函数为次扩展信道，其信息率失真函数为: : 满足满足 的的N维试验信道集合中，寻找某个信道维试验信道集合中，寻找某个信道使平均互信息取得最小值。使平均互信息取得最小值。 由于信源和信道的无记忆性，容易证明：由于信源和信道的无记忆性，容易证明： RN
148、(D) =NR(D)4.1 基本概念基本概念2021/5/23190三、率失真函数与信道容量的比较三、率失真函数与信道容量的比较率失真函数与信道容量的比较率失真函数与信道容量的比较4.1 基本概念基本概念2021/5/23191 信息率失真函数信息率失真函数R( (D) )的性质的性质1) 1) R( (D) )的定义域和值域的定义域和值域 D为为允许平均失真度允许平均失真度，也就是平均失真度，也就是平均失真度 的上限值。的上限值。D的的选择必须根据信源的统计特性选择必须根据信源的统计特性P(X)和失真函数和失真函数d(ai, bj)，在，在平均平均失真度失真度 的可能取值范围内，合理地选择某
149、一值作为允许的平的可能取值范围内，合理地选择某一值作为允许的平均失真度。均失真度。是失真函数的数学期望，为非负函数，其下限为是失真函数的数学期望，为非负函数，其下限为0。D的下限也必然为的下限也必然为0，这就是不允许任何失真的情况。，这就是不允许任何失真的情况。 信源的最小平均失真度信源的最小平均失真度 只有当失真矩阵中每行至少有一个为只有当失真矩阵中每行至少有一个为0 0时，允许失真度时，允许失真度D取取得最小值，即得最小值，即Dmin=0=0。R(0)=H(X)，即信息率至少为信源的信息熵。，即信息率至少为信源的信息熵。4.1 基本概念基本概念2021/5/23192 因为因为D越大，越大
150、，R( (D) )越小，最小为越小，最小为0 0，当，当D再大时，再大时，R( (D) )也只也只能为能为0 0。因此，。因此，Dmax是满足是满足R( (D)=0)=0的所有平均失真度的所有平均失真度D中最小值。中最小值。 令试验信道特性令试验信道特性p(bj|ai)=p(bj)(i=1,2,n),则则X和和Y相互独立，相互独立，等效于通信中断，必有等效于通信中断，必有I(X,Y)=0, ,即即R(D)=0。 对满足对满足p(bj|ai)=p(bj)的所有试验信道，的所有试验信道，计算平均失真度，其最小值即为计算平均失真度，其最小值即为Dmax0 D* Dmax DR(D)H(X)R(D*)
151、令令则则4.1 基本概念基本概念2021/5/23193 例例 离散二元信源离散二元信源 ，求，求Dmaxx1(1/3)x2(2/3)y1 y2xi dij yj0011 例例 离散二元信源离散二元信源 ，求求Dmax4.1 基本概念基本概念2021/5/23194率失真函数率失真函数R(D)的定义域为的定义域为(Dmin, Dmax)。一般情况下。一般情况下: (1)(1)Dmin=0, R(Dmin) = H(X)； (2) (2)当当DDmax时，时，R(D)=0； (3)(3)当当DminDR(D) 02) 2) R( (D) )对允许平均失真的下凸性对允许平均失真的下凸性 对任一对任
152、一01和任意平均失真度和任意平均失真度D, ,D Dmax，有有3) 3) R( (D) )函数的单调递减性和连续性函数的单调递减性和连续性4.1 基本概念基本概念2021/5/23195结论结论: : 1. R(D)是非负函数；是非负函数； 定义域定义域0Dmax , , 值域值域0H(X) 2. R(D)是单调不增、下凸的连续函数是单调不增、下凸的连续函数 3.意义意义: :对规定的失真对规定的失真D*，可算得，可算得R( (D*) )，于是，于是 (1) R(D*)是理论极限是理论极限 为满足为满足DD*，实际，实际RR(D*) (2) 压缩比极限压缩比极限K=H(X)/R(D*)0 D
153、* Dmax DR(D)H(X)R(D*)4.1 基本概念基本概念2021/5/23196n 离散信源信息率失真函数的参量表达式离散信源信息率失真函数的参量表达式 对于固定的信源对于固定的信源p( (ai) )和失真函数和失真函数d( (ai, ,bj) )，在满足保真度准，在满足保真度准则的条件则的条件 下，在试验信道下，在试验信道PD中选择中选择p(bj|ai)，使得平均互，使得平均互信息信息I(X;Y)取得最小值。取得最小值。并且并且和和4.24.2离散信源的信息率失真函数离散信源的信息率失真函数自然对数自然对数可采用拉格朗日乘子法，构造一个新的目标函数进行求解。可采用拉格朗日乘子法，构
154、造一个新的目标函数进行求解。2021/5/231974.24.2离散信源的信息率失真函数离散信源的信息率失真函数其中，其中，S和和 为拉格朗日乘子。为拉格朗日乘子。 对对p(bj|ai)求偏导数，并令导数为零，即求偏导数，并令导数为零，即2021/5/23198两边除以两边除以p(ai), 并令并令4.24.2离散信源的信息率失真函数离散信源的信息率失真函数2021/5/231994.24.2离散信源的信息率失真函数离散信源的信息率失真函数两边对两边对j求和求和两边乘以两边乘以p(ai),再对再对i求和求和或或可求解出以可求解出以S为参为参量的量的p(bj)和和p(bj|ai)2021/5/2
155、32004.24.2离散信源的信息率失真函数离散信源的信息率失真函数可得以可得以S为参量的平均失真函数为参量的平均失真函数以以S为参量的信息率失真函数为参量的信息率失真函数选择使选择使p(bj)非负非负的所有的所有S,得到的得到的D和和R值，可以得到值，可以得到R(D)曲线曲线.2021/5/232014.24.2离散信源的信息率失真函数离散信源的信息率失真函数 具体方法具体方法 (1) 选择使选择使p(bj)非零、非负的非零、非负的S值，由值，由(4.2.12)得得 i(2) 再再由由(4.2.14)、 (4.2.15)解得解得D(S)、R(S)(3) 可得可得RD曲线上一点，并得曲线上一点
156、，并得RD曲线曲线(4) S(D)=dR(D)/dD RD曲线斜率曲线斜率2021/5/23202两边对两边对S为求导为求导4.24.2离散信源的信息率失真函数离散信源的信息率失真函数2021/5/23203两边乘以两边乘以p(bj)并对并对j求和，可得求和，可得4.24.2离散信源的信息率失真函数离散信源的信息率失真函数由于由于可得可得S就是就是R(D)函数的斜率函数的斜率2021/5/23204S(D) D曲线性质曲线性质由于由于R(D)的严格递减和下凸性，斜率为的严格递减和下凸性，斜率为负负S(D)0单调递增单调递增 dS(D)/dD0Smin- ，D=0处处R(D)的斜率的斜率当当DD
157、max时，时， Smax多为某一负值，最多为某一负值，最大值为大值为0。然后在。然后在Dmax点处，点处，S曲线突跳曲线突跳到零。到零。 4.24.2离散信源的信息率失真函数离散信源的信息率失真函数R(D)S(D)Dmax D2021/5/232054.24.2离散信源的信息率失真函数离散信源的信息率失真函数n 二元及等概率离散信源的信息率失真函数二元及等概率离散信源的信息率失真函数输出符号集输出符号集Y: 0,1, 计算信息率失真函数计算信息率失真函数R(D)设二元信源设二元信源对称失真矩阵对称失真矩阵(1) 求求Dmax 2021/5/23206(2) 计算计算S和和Smax4.24.2离
158、散信源的信息率失真函数离散信源的信息率失真函数由由P115错误错误P108错误错误2021/5/232074.24.2离散信源的信息率失真函数离散信源的信息率失真函数由于由于2021/5/232084.24.2离散信源的信息率失真函数离散信源的信息率失真函数由于由于2021/5/232094.24.2离散信源的信息率失真函数离散信源的信息率失真函数2021/5/23210由由可得可得令令 ，可得，可得显式表显式表达式达式2021/5/23211由由信源熵信源熵 因容忍一定的失真度而可以压缩的信息率因容忍一定的失真度而可以压缩的信息率(3) 计算计算R(D)4.24.2离散信源的信息率失真函数离
159、散信源的信息率失真函数2021/5/232124.24.2离散信源的信息率失真函数离散信源的信息率失真函数(4) R(D)曲线和曲线和S(D)曲线曲线( =1) 1) =1，即即d(xi, yj)为误码个数，为误码个数， 其数学期望为误码率其数学期望为误码率 D允许的误码率，于是允许的误码率，于是 2) R(D)D曲线还与曲线还与p有关有关 p=1/2时，若时，若D=0.5，则，则R=0 p=1/4时，若时，若D=0.25，则，则R=00 0.25 0.5 DR(D)P=1/2S(D)p=1/4A3) 等概时等概时R(D)曲线在最上，面曲线在最上，面对相同的对相同的D，等概时，等概时R(D)最
160、大最大4) S(D)曲线只有一条，但定义域不同曲线只有一条，但定义域不同 p=1/2时，时，S(D)定义域：定义域：D=00.5， 连续，连续， Smax=0 p=1/4时，时，S(D)定义域：定义域：D = 00.25，在，在0.25处断开处断开2021/5/23213对于二元信源呈等概率分布时对于二元信源呈等概率分布时4.24.2离散信源的信息率失真函数离散信源的信息率失真函数2021/5/23214对于对于n元信源呈等概率分布时元信源呈等概率分布时4.24.2离散信源的信息率失真函数离散信源的信息率失真函数2021/5/232154.24.2离散信源的信息率失真函数离散信源的信息率失真函
161、数信源熵信源熵 因容忍一定的失真度而可能压缩的信息率因容忍一定的失真度而可能压缩的信息率2021/5/232164.24.2离散信源的信息率失真函数离散信源的信息率失真函数n 信息率失真函数与信息价值信息率失真函数与信息价值香农信息论的信息量香农信息论的信息量客观客观信息量的重要性因人而异信息量的重要性因人而异主观主观把平均失真理解为平均损失，便可衡量价值把平均失真理解为平均损失，便可衡量价值一、例一、例某工厂某工厂生产：合格品生产：合格品x1，p(x1)=0.99 废废 品品x2，p(x2)=0.01检验：合格品检验：合格品y1，合格品报废，合格品报废损失损失1 1元元 废废 品品y2，废品
162、出厂，废品出厂损失损失100100元元建模型建模型检验不正确引起的损失检验不正确引起的损失信道传输失真信道传输失真信源信源信道信道X X( (生产生产) )( (检验检验) )Y Y2021/5/232171.产品未经检验全部出厂产品未经检验全部出厂p(y1/x1) = p(y1/x2) = 1 p(y2/x1) = p(y2/x2) = 0 结论结论 产品未经检验全部出厂引起损失产品未经检验全部出厂引起损失1 1元元信源信源信道信道X(生产生产)(检验检验)Y4.24.2离散信源的信息率失真函数离散信源的信息率失真函数2021/5/232182.产品未经检验全部报废产品未经检验全部报废p(y
163、1/x1) = p(y1/x2) = 0 p(y2/x1) = p(y2/x2) = 1 结论结论 产品未经检验全部报废引起损失产品未经检验全部报废引起损失0.990.99元元出厂一个废品比报废出厂一个废品比报废9999个合格品的损失大个合格品的损失大根据根据Dmax定义，定义， Dmax = 0.99若允许损失为若允许损失为0.990.99元，则无需检验，把产品报废即可元，则无需检验，把产品报废即可信源信源信道信道X(生产生产)(检验检验)Y4.24.2离散信源的信息率失真函数离散信源的信息率失真函数2021/5/232193. 检验完全正确检验完全正确p(y1/x1) = p(y2/x2)
164、 = 1 p(y2/x1) = p(y1/x2) = 0 结论结论 为达无错检验，需要为达无错检验，需要0.081bit信息量信息量 0.081bit信息量避免了信息量避免了0.99元的损失元的损失 每每bit价值价值 = 0.99/0.081=12.2元元/bit信源信源信道信道X(生产生产)(检验检验)Y4.24.2离散信源的信息率失真函数离散信源的信息率失真函数2021/5/232204. 检验有一定误差检验有一定误差( (设错判概率为设错判概率为0.1) 0.1) p(y1/x1) = p(y2/x2) = 0.9 p(y2/x1) = p(y1/x2) = 0.1 结论结论1 1 比
165、最大损失比最大损失(0.99(0.99元元) )减少了减少了0.7910.791元，元， 原因是检验获得了信息量原因是检验获得了信息量I(X;Y)p(x1)0.99p(x2)0.01p(y1)p(y2)0.90.90.10.14.24.2离散信源的信息率失真函数离散信源的信息率失真函数2021/5/23221结论结论1每每bit价值价值=0.791/0.025=31.6元元/bitp(x1)0.99p(x2)0.01p(y1)p(y2)0.90.90.10.14.24.2离散信源的信息率失真函数离散信源的信息率失真函数每每bit价值价值=0.791/0.025=31.6元元/bit2021/5
166、/23222 结论结论2 2 有误差检验的信息价值比无误差检验的高！有误差检验的信息价值比无误差检验的高！可画出信息可画出信息(R) 损失损失(D)曲线曲线反之，反之， D(R) 信息率为信息率为R时的平均损失时的平均损失0 0.199 0.99 D(元元)R(D)(bit)H(X)0.0810.025Dmax4.24.2离散信源的信息率失真函数离散信源的信息率失真函数检验完全正确检验完全正确产品未经检验全部报废产品未经检验全部报废检验有一定误差检验有一定误差2021/5/232234.24.2离散信源的信息率失真函数离散信源的信息率失真函数n 信息价值信息价值1. 价值价值V = Dmax
167、D(R) 曲线上某点与曲线上某点与Dmax间纵轴距，表明损失减少量间纵轴距，表明损失减少量2. 价值率价值率每每bitbit信息提供的损失减少量信息提供的损失减少量 性质性质 SR(D)曲线斜率曲线斜率表明，表明， RV 概念：提供的信息量越大概念：提供的信息量越大, ,价值越大价值越大, ,损失越小损失越小0R(bit)H(X)0.0810.025Dmax0.990.199D(R)2021/5/23224 上例上例 1) 不检验，全部报废不检验，全部报废 D = Dmax=0.99 元情况元情况2) 无错检验无错检验 D = 0，R=H(X)=0.081bit情况情况 此时此时, , V =
168、 Dmax 0 = 0.99 元元 v = V/R = 12.2 元元/bit3) 有错检验有错检验 D = 0.199元，元，R=0.025bit情况情况此时此时, , V = Dmax D = 0.791 元元 v = V/R = 31.6 元元/bit0R(bit)H(X)0.0810.025Dmax0.990.199D(R)4.24.2离散信源的信息率失真函数离散信源的信息率失真函数2021/5/23225n 限失真信源编码定理限失真信源编码定理 设有一离散、平稳、无记忆信源，其率失真函数为设有一离散、平稳、无记忆信源，其率失真函数为R(D)。则对任意选定的则对任意选定的D0，当传信率
169、，当传信率RR(D)时，只要信源序列长度时，只要信源序列长度L足够长，必存在一种编码方式足够长，必存在一种编码方式C，使译码后的失真使译码后的失真 并且当并且当L时，时， 0 反之反之, , 若若RR(D) 则必可设计一种编码方式则必可设计一种编码方式, ,满足满足 若系统若系统R R(D) 则无法满足则无法满足 要求要求2. 逆定理逆定理 若已规定满足失真度准则若已规定满足失真度准则 , 则对所有设计均有则对所有设计均有RR(D) 3. R 单符号熵单符号熵H( (X) )时可做到几乎无失真译码，条时可做到几乎无失真译码，条件是件是L比较比较大。大。 只要只要 , ,译码差错率必小于译码差错
170、率必小于 信源序列信源序列自信息方差自信息方差2021/5/23244(4)(4)逆定理指出：逆定理指出：若若R比比H( (X) ) 小一个小一个 时，译码差错未必超过时，译码差错未必超过 若若R比比H( (X) ) 小两个小两个 时，译码差错必定大于时，译码差错必定大于 L时必失真时必失真(5)(5)结论结论( (单符号单符号) )信源熵信源熵H( (X) )实为一个界限实为一个界限 当当 RH( (X) )时时 无失真译码无失真译码 当当 RH( (X) )时时 有失真译码有失真译码5.35.3定长码定长码2021/5/23245 例例 给定信源模型：给定信源模型：8 8种符号和概率种符号
171、和概率算得：算得：H(X)=2.55 bit /信源符号，信源符号， 2(X) =1.323 若要求：编码效率若要求：编码效率 =90%，由，由 得得 =0.28 若要求若要求: : 译码差错率译码差错率=10-6 , , 则则L太大太大 此外，此外， 编码效率不高编码效率不高 变长编码变长编码5.35.3定长码定长码2021/5/23246n 变长码的分类和主要编码方法变长码的分类和主要编码方法5.45.4变长码变长码信源符号信源符号出现概率出现概率码码1码码2码码3码码4s1s2s3s41/21/41/81/80110011010000111010010001010010001 码码1 1
172、是一个奇异码，不是唯一可译码；码是一个奇异码，不是唯一可译码；码2 2是非奇异码，也是非奇异码，也不是唯一可译码，因为收到一串序列无法唯一译出对应的原符不是唯一可译码，因为收到一串序列无法唯一译出对应的原符号序列，如号序列，如0100001000，即可译作，即可译作s4s3s1,s4s3s1,也可译作也可译作s4s1s3,s1s2s3s4s1s3,s1s2s3或或s1s2s1s1s1s2s1s1；码；码3 3和码和码4 4都是唯一可译的。都是唯一可译的。 但码但码3 3和码和码4 4也不太一样，码也不太一样，码4 4称作逗点码，只要收到称作逗点码，只要收到1 1，就，就可以立即作出译码；而码可
173、以立即作出译码；而码3 3不同，当收到一个或几个码字时，必不同，当收到一个或几个码字时，必须参考后面的码才能作出判断。须参考后面的码才能作出判断。 2021/5/232475.45.4变长码变长码所有的码所有的码非奇异码非奇异码唯一可译码唯一可译码即时码即时码各种码之间的关系各种码之间的关系码码定长码定长码变长码变长码码码非分组码非分组码分组码分组码奇异码奇异码非奇异码非奇异码非唯一可译码非唯一可译码唯一可译码唯一可译码非即时码非即时码即时码即时码奇异码奇异码信源符号码字并非一一对应信源符号码字并非一一对应, ,译码将一对多译码将一对多非唯一可译码非唯一可译码一码字是其他码字的组合一码字是其他
174、码字的组合非即时码，又名延长码非即时码，又名延长码一码字是其他码字的延长一码字是其他码字的延长即时码，又名异前置码即时码，又名异前置码收到一个完整码字后，可立即译出收到一个完整码字后，可立即译出2021/5/23248树图法构造即时码树图法构造即时码( (异前置码异前置码) ) (1) (1) 码树画法码树画法( (m进制进制) )从树根出发，画从树根出发，画m条树枝，树枝端点称为一级节点，有条树枝，树枝端点称为一级节点，有m个；从个；从第一级节点出发，再画第一级节点出发，再画m条树枝，得第二级节点，有条树枝，得第二级节点，有m2个；第个；第n n级节点，共有级节点，共有mn个。个。 串联的树
175、枝成为联枝。从树根出发到每一个终节点的联枝串联的树枝成为联枝。从树根出发到每一个终节点的联枝代表一个码字。代表一个码字。5.45.4变长码变长码满树满树非满树，全树非满树，全树非全树非全树树根树根终节点终节点中间节点中间节点2021/5/23249满树满树 每个码字的联枝数均相同时每个码字的联枝数均相同时( (定长码定长码) )非满树非满树 当码字的联枝数不同时当码字的联枝数不同时( (变长码变长码) ) 全树全树 每个中间节点的后续分支数均为每个中间节点的后续分支数均为m 非全树非全树 有些中间节点的后续分支数不足有些中间节点的后续分支数不足m5.45.4变长码变长码满树满树非全树非全树树根
176、树根终节点终节点中间节点中间节点非满树，全树非满树，全树即时码即时码,异前置码异前置码每个码字都被安排在终节点上每个码字都被安排在终节点上命题：命题：一个一个唯一可译码唯一可译码成为成为即时码即时码的的充分必要条件充分必要条件是其中任何是其中任何一个码字都不是其他码字的前缀。一个码字都不是其他码字的前缀。2021/5/23250(2)(2)克拉夫特不等式克拉夫特不等式 m元长度为元长度为ki的即时码存在的充要条件的即时码存在的充要条件 n信源符号数，信源符号数，m码元个数，码元个数，ki第第i个码字长度个码字长度 证明略证明略 5.45.4变长码变长码2021/5/23251编码后的码字为：编
177、码后的码字为：码长为：码长为：设信源设信源码平均长度码平均长度(1)平均码长平均码长平均每个信源符号所需的码长平均每个信源符号所需的码长(2)信息率信息率编码后，平均每个信源符号能载荷的最大信息量编码后，平均每个信源符号能载荷的最大信息量(3)(信道信道)信息传输率信息传输率编码后编码后, , 平均每个码符号载荷的平均每个码符号载荷的(信源信源)信息量信息量5.45.4变长码变长码2021/5/232525.45.4变长码变长码 单符号变长编码定理单符号变长编码定理 若一离散无记忆信源的符号熵为若一离散无记忆信源的符号熵为H( (X) )，对信源符号以，对信源符号以m进制进制码元作变长编码，则
178、必定存在一种无失真编码方法，其码字平均码元作变长编码，则必定存在一种无失真编码方法，其码字平均码长满足码长满足 意义意义 给出了平均码长的上给出了平均码长的上, ,下限。可在编码前先估算下限。可在编码前先估算下限给出了信源压缩的极限。达到下限的编码下限给出了信源压缩的极限。达到下限的编码熵编码熵编码最佳编码应是最佳编码应是与信源熵与信源熵H( (X) )相匹配的编码相匹配的编码2021/5/232535.45.4变长码变长码 离散平稳无记忆序列变长编码定理离散平稳无记忆序列变长编码定理 对于离散平稳无记忆信源，当信源输出长度为对于离散平稳无记忆信源，当信源输出长度为L L的消息序列时的消息序列
179、时 代表平均码序列长度。代表平均码序列长度。 已知信源平均输出信息率为已知信源平均输出信息率为 故有故有若一离散平稳无记忆序列信源的平均符号熵为若一离散平稳无记忆序列信源的平均符号熵为H( (X) )，则必存在一，则必存在一种无失真编码方法，使信息率种无失真编码方法，使信息率R满足：满足：H(X)R H(X) + 2021/5/232545.45.4变长码变长码 对信源进行变长编码一般所要求的信源符号长度对信源进行变长编码一般所要求的信源符号长度L比定长编比定长编码小得多。编码效率的下界为码小得多。编码效率的下界为例如：二元编码，例如：二元编码，m=2，log2m=1。如果。如果H( (X)=
180、2.5525,)=2.5525,若要求若要求 ，则，则 L=1/0.2836=3.5261L=1/0.2836=3.5261只要只要4 4个符号一起编码，即可满足对编码的效率要求。个符号一起编码，即可满足对编码的效率要求。2021/5/232555.45.4变长码变长码 香农编码方法香农编码方法n 变长码的编码方法：变长码的编码方法：根据概率分布，赋予不同的码长根据概率分布，赋予不同的码长设信源设信源若对若对ai编一个长度为编一个长度为ki的码字，使的码字，使规定规定 为整数时，上式取等号；非整为整数时，上式取等号；非整数时，数时，ki取取比它大一些的最接近整数，则满足上式的比它大一些的最接近
181、整数，则满足上式的ki必存在。必存在。异前置码异前置码2021/5/232565.45.4变长码变长码二进制香农编码步骤为：二进制香农编码步骤为：1. 将信源符号按概率排序：将信源符号按概率排序：p(a1)p(a2)p(an)；2. 计算第计算第i个码字个码字( (之前之前) )的累加概率的累加概率pa(xj)3. 确定第确定第i个码字的码长个码字的码长ki( (整数整数) )：- -log2p(xi)ki1-log2p(xi)4.4.将累加概率将累加概率pa(xj)变为二进制数，并取其小数点后变为二进制数，并取其小数点后ki位，即为位，即为ai的编码的编码 说明说明 j j=1=1时，时，
182、pa(a1) = p(a0) =0j j=2=2时，时， pa(a2) = p(a1) + p(a0) = p(a1) ) j j=3=3时，时， pa(a3) = p(a2) + p(a1)因而因而pa(aj)表示：表示：aj之前之前( (不含不含aj) )的各概率之和的各概率之和2021/5/232575.45.4变长码变长码例例: : 有一单符号离散无记忆信源有一单符号离散无记忆信源对该信源编二进制香农码。其编码过程如下表所示。对该信源编二进制香农码。其编码过程如下表所示。0001100101110111110大概率用短码大概率用短码2021/5/23258计算出给定信源香农码的平均码长
183、计算出给定信源香农码的平均码长若对上述信源采用等长编码，要做到无失真译码，每个符号至若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用少要用3 3个比特表示。相比较，香农编码对信源进行了压缩。个比特表示。相比较，香农编码对信源进行了压缩。由离散无记忆信源熵定义，可计算出：由离散无记忆信源熵定义，可计算出：对上述信源采用香农编码的信息编码速率为对上述信源采用香农编码的信息编码速率为编码效率为信源熵和信息率之比。则编码效率为信源熵和信息率之比。则 可以看出，编码效率并不是很高。可以看出，编码效率并不是很高。5.45.4变长码变长码2021/5/232595.45.4变长码变长码 Fano
184、Fano编码方法编码方法费诺编码也是一种常见的信源编码方法。费诺编码也是一种常见的信源编码方法。编码步骤如下：编码步骤如下：(1)(1)将概率按从大到小的顺序排列，令将概率按从大到小的顺序排列，令 p(a1) p(a2) p(an)(2)(2)按编码进制数将概率分组，使每组概率尽可能接近或相等。按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编如编二进制码就分成两组，编m m进制码就分成进制码就分成m m组。组。(3)(3)给每一组分配一位码元。给每一组分配一位码元。(4)(4)将每一分组再按同样原则划分，重复步骤将每一分组再按同样原则划分，重复步骤2 2和和3 3
185、，直至概率，直至概率不再可分为止。不再可分为止。2021/5/23260例例 设有一单符号离散信源设有一单符号离散信源对该信源编二进制费诺码。编码过程如下表。对该信源编二进制费诺码。编码过程如下表。5.45.4变长码变长码二进制费诺编码二进制费诺编码信源符号信源符号概率概率编码编码码字码字码长码长x10.250002x20.2501012x30.200102x40.1501103x50.10011104x60.05111111114大概率用短码大概率用短码2021/5/23261该信源的熵为该信源的熵为平均码长为平均码长为编码效率为编码效率为 本例中费诺编码有较高的编码效率。费诺码比较适合于本
186、例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近每次分组概率都很接近的信源。特别是对每次的信源。特别是对每次分组概率都相分组概率都相等等的信源进行编码时，可达到理想的编码效率。的信源进行编码时，可达到理想的编码效率。5.45.4变长码变长码2021/5/23262题中码字还可用码树来表示，如图所示。题中码字还可用码树来表示，如图所示。5.45.4变长码变长码2021/5/232635.45.4变长码变长码例例 设有一单符号离散信源设有一单符号离散信源对该信源编二进制费诺码。对该信源编二进制费诺码。2021/5/232645.45.4变长码变长码平均码长平均码长 编码效率编码效
187、率信源熵信源熵 H(X)=2.75 bit/sign 每次两分组的概率正好相等每次两分组的概率正好相等2021/5/23265(1) (1) 将信源符号按概率从大到小的顺序排列，令将信源符号按概率从大到小的顺序排列，令 p(a1) p(a2) p(an)(2) (2) 给两个概率最小的信源符号给两个概率最小的信源符号p( (an-1) )和和p( (an) )各分配一个码位各分配一个码位“0 0”和和“1 1”，将这两个信源符号合并成一个新符号，并用这，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含两个最小的概率之和作为新符号的概率，结果得到一个
188、只包含( (q1) )个信源符号的新信源。称为个信源符号的新信源。称为信源的第一次缩减信源信源的第一次缩减信源，用，用S1表示。表示。(3)(3)将缩减信源将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤的符号仍按概率从大到小顺序排列，重复步骤2 2，得到只含，得到只含( (q2) )个符号的缩减信源个符号的缩减信源S2。(4)(4)重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为两个符号的概率之和必为1 1。然后从最后一级缩减信源开始，依。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应
189、的码字。编码路径向前返回，就得到各信源符号所对应的码字。5.45.4变长码变长码 Huffman Huffman编码步骤编码步骤2021/5/23266例例 设单符号离散无记忆信源如下，要求对信源编二进制霍夫曼码设单符号离散无记忆信源如下，要求对信源编二进制霍夫曼码 在图中在图中读取码字的读取码字的时候，一定时候，一定要从后向前要从后向前读，此时编读，此时编出来的码字出来的码字才是唯一可才是唯一可译码。若从译码。若从前向后读取前向后读取码字，则码码字，则码字不是唯一字不是唯一可译码。可译码。2021/5/23267 将上图左右颠倒过来重画一下，即可得到二进制哈夫曼码将上图左右颠倒过来重画一下，
190、即可得到二进制哈夫曼码的码树。的码树。5.45.4变长码变长码100101101010100000000010000112021/5/232685.45.4变长码变长码信源熵为：信源熵为：平均码长为平均码长为编码效率为编码效率为若采用定长编码，码长若采用定长编码，码长K=3K=3，则编码效率，则编码效率可见哈夫曼的编码效率提高了可见哈夫曼的编码效率提高了12.7%12.7%。2021/5/23269注意：注意：哈夫曼的编法并不惟一哈夫曼的编法并不惟一。每次对缩减信源两个概率最小的符号分配每次对缩减信源两个概率最小的符号分配“0 0”和和“1 1”码码元是任意的，所以可得到不同的码字。不同的码元
191、分配，元是任意的，所以可得到不同的码字。不同的码元分配，得到的具体码字不同，但码长不变，平均码长也不变，所得到的具体码字不同，但码长不变，平均码长也不变，所以没有本质区别；以没有本质区别；缩减信源时，若合并后的新符号概率与其他符号概率相等，缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，从编码方法上来说，这几个符号的次序可任意排列，编出这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同的码都是正确的，但得到的码字不相同。5.45.4变长码变长码例：例：单符号离散无记忆信源单符号离散无记忆信源 用两种不同的方法对其编二进制哈夫曼码。用两种不同的方法对其编二进
192、制哈夫曼码。2021/5/232705.45.4变长码变长码方法一：合并后的新符号排在其它相同概率符号的后面。方法一：合并后的新符号排在其它相同概率符号的后面。2021/5/232715.45.4变长码变长码 这两种编码哪一种这两种编码哪一种更好呢，我们来计算更好呢，我们来计算一下二者的码长。一下二者的码长。方法二：合并后的新符号排在其它相同概率符号的前面。方法二：合并后的新符号排在其它相同概率符号的前面。2021/5/23272两种编码的平均码长是一样的，都是两种编码的平均码长是一样的，都是2.22.2，那一种更好呢，那一种更好呢，我们可以计算一下平均码长的方差。我们可以计算一下平均码长的方
193、差。定义码字长度的方差定义码字长度的方差2 2：5.45.4变长码变长码2021/5/23273 可见：第二种编码方法的码长方差要小许多。意味着第二种可见：第二种编码方法的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码长。编码方法的码长变化较小，比较接近于平均码长。第一种方法编出的第一种方法编出的5 5个码字有个码字有4 4种不同的码长；种不同的码长；第二种方法编出的码长只有两种不同的码长；第二种方法编出的码长只有两种不同的码长；显然，显然，第二种编码方法更简单、更容易实现，所以更好第二种编码方法更简单、更容易实现，所以更好。结论：结论：在哈夫曼编码过程中，对缩减信源符
194、号按概率由大到小在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。得到充分利用。5.45.4变长码变长码2021/5/232745.45.4变长码变长码m进制哈夫曼编码进制哈夫曼编码1.编码步骤编码步骤同二进制，但需注意两点同二进制，但需注意两点 (1)(1)每次取最小的每次取最小的m个概率个概率, ,分别赋以分别赋以0,1,0,1, ,m-1-1； (2)(2)为使平均码长最
195、短，当对应的码树为非全树时，为使平均码长最短，当对应的码树为非全树时， 第一次采用小于第一次采用小于m个概率个概率，此后每次均用，此后每次均用m个概率个概率2.非全树时的编码非全树时的编码 (1)(1)全树全树 码树中码树中, ,每个中间节点的后续枝数必为每个中间节点的后续枝数必为m (2) (2)非全树非全树码树中码树中, ,有些中间节点的后续枝数不足有些中间节点的后续枝数不足m三进制三进制满树满树（等长码）（等长码）三进制全树三进制全树（少一根即（少一根即为非全树）为非全树）2021/5/23275(3)(3)m进制的全树的终端节点数进制的全树的终端节点数( (即时码个数即时码个数) )
196、m + k(m-1), k = 0,1,2,. ( (每从一个节点分出每从一个节点分出m枝枝, , 就增加就增加m-1-1个终端个终端) )(4)(4)当当n m+k(m-1)时时, ,令令 s = m+k(m-1)-n, , s(m-1)-1)为构成全树所缺少的码字为构成全树所缺少的码字( (分支分支) )数数(5)(5)非全树时的哈夫曼编码非全树时的哈夫曼编码 第一次取最小概率时，只取第一次取最小概率时，只取 m-s 个个, , 分别赋以分别赋以0,1,2,m-s-1。此后每次都取。此后每次都取m个个5.45.4变长码变长码三进制全树三进制全树（少一根即（少一根即为非全树）为非全树）202
197、1/5/23276(1)分析分析 n=8, m=3, m + k(m-1)=3+2k, 取取k = 3，得得s=1.于是于是m-s=2，即第一次取两个概率即第一次取两个概率(2)编码编码0.090.220.381.00120121 x5 0.0722 x6 0.06200 x7 0.05201 x8 0.0411 x3 0.112 x4 0.110 x2 0.18 0 x1 0.4001201202002011222101121例例 设单符号离散无记忆信源如下，要求对信源编三进制霍夫曼码设单符号离散无记忆信源如下，要求对信源编三进制霍夫曼码2021/5/23277(3)说明说明平均码长平均码长
198、信息率信息率R=2.678bit/=2.678bit/信源符号信源符号编码效率编码效率 = = H( (X)/)/R=2.552/2.678=98.98%=2.552/2.678=98.98%由树图可见，第一次取由树图可见，第一次取m-s个概率的影响是：个概率的影响是： 长码不全，因而平均码长短长码不全，因而平均码长短5.45.4变长码变长码2021/5/23278n总结总结香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了
199、对信源的压缩；从而实现了对信源的压缩；香农码有系统的、唯一的编码方法，但在很多情况下编码效香农码有系统的、唯一的编码方法，但在很多情况下编码效率不是很高；率不是很高；费诺码和哈夫曼码的编码方法都不唯一；费诺码和哈夫曼码的编码方法都不唯一；费诺码比较适合于对分组概率相等或接近的信源编码；费诺码比较适合于对分组概率相等或接近的信源编码；哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码费诺码。局限性局限性均均需予知概率分布需予知概率
200、分布，主要用于无记忆信源，主要用于无记忆信源5.45.4变长码变长码2021/5/23279作业：作业：5.1 (P166); 5.2(P166); 5.3(P166); 5.4(P166)其中，其中，5.3的三进制的三进制huffman编码不要求编码不要求5.4只做只做(1)(2)(3)5.45.4变长码变长码2021/5/23280RLCRLCRun-Length CodeRun-Length Code无失真编码，适用于二元相关信源无失真编码，适用于二元相关信源二元二元0 0游程后为游程后为1 1，反之亦然，反之亦然相关相关有长有长0 0、长、长1 1基本概念基本概念游程游程数字序列中，连
201、续出现的同种符号的统称。数字序列中，连续出现的同种符号的统称。 “0 0”游程，游程，“1 1”游程游程游程长度游程长度连续出现的同种符号的长度连续出现的同种符号的长度( (连码个数连码个数) )游程游程( (长度长度) )序列序列由游程长度构成的序列由游程长度构成的序列游程长度编码游程长度编码对游程长度序列进行编码。可用交替出现的对游程长度序列进行编码。可用交替出现的“0 0”游程和游程和“1 1”游程的长度，来表示任意二元序列。游程的长度，来表示任意二元序列。n 游程编码游程编码5.55.5游程编码游程编码2021/5/23281 例例 二元信源二元信源 0 0 0 1 0 1 1 1 0
202、 0 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 0 1 原序列原序列( (二元二元) ) 3 1 1 3 2 1 3 1 3 1 1 3 2 1 3 1 游程序列游程序列 说明说明(1)(1)可逆：由游程序列恢复出原来的二元序列可逆：由游程序列恢复出原来的二元序列(2)(2)规定：从规定：从“0 0”游程开始游程开始( (此后交替此后交替) )(3)(3)游程序列为游程序列为多元序列多元序列，此后可用哈夫曼编码等编码，此后可用哈夫曼编码等编码(4)(4)原则上亦可用于原则上亦可用于m元序列元序列( (如灰度图像如灰度图像) )，对应，对应m种游程，但需种游程，但需
203、增设标志位，因而减小了压缩比。对多元序列进行游程变换得增设标志位，因而减小了压缩比。对多元序列进行游程变换得意义不大。意义不大。(5)(5)若二元序列的概率特性已知，由于二元序列与游程变换序列的若二元序列的概率特性已知，由于二元序列与游程变换序列的一一对应性，可计算出游程序列的概率特性。一一对应性，可计算出游程序列的概率特性。5.55.5游程编码游程编码2021/5/232825.55.5游程编码游程编码设二元序列为独立序列，令设二元序列为独立序列，令“0”和和“1”的概率分别为的概率分别为p0和和p1，长度为，长度为i的的“0”游程记为游程记为 ，则，则0游程长度概率为游程长度概率为同理可得
204、同理可得“1”游程长度游程长度 1 0 0 0 1 L(0)-1个个2021/5/23283可构造两个信源：可构造两个信源： “0”游程长度信源和游程长度信源和“1”游程长度信源游程长度信源5.55.5游程编码游程编码由由 ，可得，可得2021/5/232845.55.5游程编码游程编码H(p0)为原二元序列的熵为原二元序列的熵2021/5/232855.55.5游程编码游程编码“0”游程序列的平均游程长度游程序列的平均游程长度“1”游程序列的熵和平均游程长度游程序列的熵和平均游程长度“0”游程序列的熵与游程序列的熵与“1”游程序列的熵之和除以它们的平均游程游程序列的熵之和除以它们的平均游程长
205、度之和，即为对应元二元序列的熵长度之和，即为对应元二元序列的熵H(X)。游程变换后符号熵没。游程变换后符号熵没有发生变化。有发生变化。2021/5/23286游程长度序列的截断处理游程长度序列的截断处理 游程长度可由游程长度可由1，要建立游程长度和码子之间的一一对，要建立游程长度和码子之间的一一对应的码表比较困难，即使能够建立码表，也没有任何意义。应的码表比较困难，即使能够建立码表，也没有任何意义。( (霍霍夫曼编码需严格对应概率夫曼编码需严格对应概率) ) 在实际应用中，常对长码采用截断处理的方法。设游程长在实际应用中，常对长码采用截断处理的方法。设游程长度为度为2n，所有大于，所有大于2n
206、者，都按照者，都按照2n处理，采用霍夫曼编码方法。处理，采用霍夫曼编码方法。 游程长度游程长度2n，只有一个码字，只有一个码字C，为了区分这些序列，可在，为了区分这些序列，可在C之后再加一个之后再加一个n位的自然码，代表余数。位的自然码，代表余数。 游程长度游程长度=2n ，用，用C0000表示表示(n个个)； 游程长度游程长度=2n+1 ，用，用C0001表示表示(n个个)； 游程长度游程长度=2n+1-1 ，用，用C1111表示表示(n个个)； 游程长度游程长度=2n+1 ，用，用C0000 C0000表示表示(n个个)； 游程长度游程长度=2n+2-1，用，用C0000 C1111表示表
207、示(n个个)；5.55.5游程编码游程编码2021/5/232875.55.5游程编码游程编码线性码线性码码字长度正比于游程长度的编码码字长度正比于游程长度的编码 常称为常称为A A码码码长为块长整数倍码长为块长整数倍 如：如：A3A3码码( (每块每块3bit)3bit)，A5A5码码( (每块每块5bit)5bit)A3码码每块每块3bit游程游程长度长度编码码字编码码字1234567 001 010 011 100 101 110 111891011121314 000001 000010 000011 000100 000101 000110 00011115000000001修正：按
208、出现概率分组，每组用等长修正：按出现概率分组，每组用等长度编码。通常，短游程出现概率大，度编码。通常，短游程出现概率大，又可按游程长度分组、编码又可按游程长度分组、编码2021/5/232885.65.6连续信源编码连续信源编码n 最佳标量量化最佳标量量化均匀量化均匀量化PCMPCM均匀量化输入均匀量化输入- -输出分层特性曲线输出分层特性曲线1 1）量化误差：也成为量化噪声，其功率取决）量化误差：也成为量化噪声，其功率取决于量化间隔于量化间隔 ，而与输入信号的功率和概率，而与输入信号的功率和概率分布无关。分布无关。2 2）量化信噪比）量化信噪比 假设量化误差假设量化误差e(n)e(n)符合均
209、匀分布，则由符合均匀分布，则由于量化噪声，所得数字语音的信噪比为：于量化噪声，所得数字语音的信噪比为：其中其中B B为量化器字长。由上式知，信噪比为量化器字长。由上式知，信噪比取决于量化字长。取决于量化字长。 当要求当要求60 dB60 dB的的SNRSNR时，时，B B至少应取至少应取1212，此时，对于带宽为，此时，对于带宽为4kHz4kHz的电话语音信的电话语音信号，若采样率为号，若采样率为8kHz8kHz，则，则PCMPCM要求的速率为要求的速率为8k 8k 12 1296kbit/s96kbit/s。这样高的。这样高的比特率是无法承受的，因而必须采用具有更高性能的编码方法。比特率是无
210、法承受的，因而必须采用具有更高性能的编码方法。 SNR(dB)SNR(dB)6.026.02B B 7.2 7.2 2021/5/23289非均匀量化特性非均匀量化特性语音非均匀量化特性语音非均匀量化特性非均丹量化波形示意非均丹量化波形示意非均匀量化非均匀量化PCMPCM二二 波形编码波形编码小信号概率高，大信号概率小。应采用非均匀量小信号概率高，大信号概率小。应采用非均匀量化化: : 小信号分层密，大信号分层稀！小信号分层密，大信号分层稀！5.65.6连续信源编码连续信源编码2021/5/232905.65.6连续信源编码连续信源编码 语音非均匀量化的实现语音非均匀量化的实现(1)(1) 律
211、压扩律压扩(2)A(2)A律压扩律压扩小信号扩张，大信号压缩后小信号扩张，大信号压缩后 再均匀量化再均匀量化 = = 非均匀量化！非均匀量化！2021/5/232915.65.6连续信源编码连续信源编码压扩特性的数学表达式：压扩特性的数学表达式：(1)(1) 律压扩律压扩(2)A(2)A律压扩律压扩 =ysgnx=+1 , -1,符号函数符号函数2021/5/23292A A律、律、律的数字实现律的数字实现1313折线折线 实现实现A A律；律；15 15 折线折线 实现实现 律！律！1313折线折线A A律律1515折线折线 律律5.65.6连续信源编码连续信源编码2021/5/23293n 矢量量化矢量量化LBG算法算法n 相关信源编码相关信源编码 预测编码预测编码 差值编码：增量调制；差分脉冲编码调制；自适应差分差值编码：增量调制；差分脉冲编码调制；自适应差分 脉冲编码调制；脉冲编码调制；n 变换编码变换编码 子带编码子带编码: 语音信号语音信号 小波变换小波变换: 语音信号语音信号, 图像图像jpeg200 DCT变换变换: 图像编码图像编码jpeg5.65.6连续信源编码连续信源编码2021/5/23294
