(精品)《数字通信原理》第4章信息论基础

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2010 Copyright,SCUT DT&P Labs,*,数字通信原理,(4),冯穗力等编著,电子工业出版社,2012,年,8,月,2010 Copyright,1,SCUT DT&P Labs,第,4,章 信息论基础,本章的基本内容,：,信息的度量方法；,离散信道及容量；,连续信源、信道及容量；,信源编码的基本方法；,率失真理论。,2010 Copyright,2,SCUT DT&P Labs,4.1,引言,2010 Copyright,3,SCUT DT&P Labs,消息与信息,1948,年，美国科学家香农的论文,通信的数学理论,，,奠定了信息论的理论基础。,消息与信息,(1),消息是由符号、文字、数字、语音或图像组成的序列；,(2),消息是信息的,载体,，信息是消息的,内涵,；消息中可能包,含信息，也可能不包含信息；,(3),收到一则消息后，所得的信息量，在数量上等于获得,消息前后,“,不确定性,”,的消除量；,(4),通信的目的在与传送信息。,第,4,章 信息论基础,2010 Copyright,4,SCUT DT&P Labs,消息与信息,(,续,),通信系统传递信息的机制和本质,形式化,：通信的基本任务是在接收端把发送端发出的消息从形式上恢复出来，而对消息内容的理解和判断，不是通信的任务。,非决定论,：通信过程传递的消息中所包含的内容，对接收者来说事先是无法预料的。,不确定性,：是指收到该消息之前，对其中的内容出现与否，具有不确定的因素；不确定的因素可以通过通信来加以消除或部分消除。,第,4,章 信息论基础,2010 Copyright,5,SCUT DT&P Labs,4.2,信息的度量,2010 Copyright,6,SCUT DT&P Labs,信息度量的概念,(1),某消息的,信息量获得该消息后,不确定性的消除量,；,不确定性,可能性,概率问题,：,信息量可用概率的某种函数来度量,(2),不同的消息有信息量的多少的区别，因此,信息的度量方式应满足信息量的可加性,信息量应该是满足可加性的概率的函数,。,第,4,章 信息论基础,2010 Copyright,7,SCUT DT&P Labs,离散信源信息的度量,离散信源的信息量,离散信源统计特性的描述方法,概率场,设离散信源包含,N,种可能的不同符号，相应的概率场可表述为,概率场应满足条件：,第,4,章 信息论基础,2010 Copyright,8,SCUT DT&P Labs,离散信源的信息量,(,续,),信息量,作为概率的函数，具有形式,若 与 统计独立，满足可加性要求,如定义,显然有,可同时满足,是概率的函数,和,可加性,两个要求。,第,4,章 信息论基础,2010 Copyright,9,SCUT DT&P Labs,离散信源信的息量,(,续,),定义 离散消息,x,i,的信息量,:,信息量的单位与对数的底有关,：,log,以,2,为底时，单位为,比特,：,bit,log,以,e,为底时，单位为,奈特,：,nit,log,以,10,为底时，单位为,哈特,，,hart,一般在没有特别声明时均信息的单位为比特,。,第,4,章 信息论基础,2010 Copyright,10,SCUT DT&P Labs,离散信源信的息量,(,续,),示例,：已知某信源的概率场为,输出的各符号统计独立，计算序列,S,“,113200,”,的信息量,第,4,章 信息论基础,2010 Copyright,11,SCUT DT&P Labs,离散信源的平均信息量：信源的熵,离散信源的熵,定义,4.2.2,离散信源 的熵,熵是信源在统计意义上,每个符号的平均信息量,。,第,4,章 信息论基础,2010 Copyright,12,SCUT DT&P Labs,离散信源的熵,(,续,),示例,：求离散信源,的熵。,按照定义：,熵的单位：,比特,/,符号,第,4,章 信息论基础,2010 Copyright,13,SCUT DT&P Labs,离散信源的熵,(,续,),示例,（续）：若上述离散信源发送独立的符号序列：,201 020 130 213 001 203 210 100 321 010,023 102 002 10 312 032 100 120 210,(1),求总的信息量；,(2),利用熵估计总的信息量。,解：,(1),(2),第,4,章 信息论基础,2010 Copyright,14,SCUT DT&P Labs,离散信源的最大熵定理,定义,4.2.3,凸集,对任意 ，有,定义,4.2.4,若,型凸函数,(,下凸函数,),型凸函数,(,上凸函数,),第,4,章 信息论基础,2010 Copyright,15,SCUT DT&P Labs,离散信源的最大熵定理,(,续,),若函数为,型凸函数,(,下凸函数,),，则一定存在最小值,若函数为,型凸函数,(,上凸函数,),，则一定存在最大值,型凸函数示例,第,4,章 信息论基础,2010 Copyright,16,SCUT DT&P Labs,离散信源的最大熵定理,(,续,),若 是一组,概率,； 是一个,型凸函数,，则一般地有如下的关系式,利用上面的关系式，可以证明如下的定理,定理,4.2.5,熵函数 是概率,的,型凸函数,。,第,4,章 信息论基础,2010 Copyright,17,SCUT DT&P Labs,离散信源的最大熵定理,(,续,),定理,4.2.6,当离散信源,X,取等概分布时，其熵 取最大值。,即：,当信源取等概分布时，具有最大的不确定性,。,示例,：两个信源符号的情形。,P(x,1,)=p,P(x,2,)=1-p,当,p=1/2,时，,H(X)=,H,max,第,4,章 信息论基础,2010 Copyright,18,SCUT DT&P Labs,离散信源的联合熵与条件熵,两随机变量,的,概率场,满足条件：,第,4,章 信息论基础,2010 Copyright,19,SCUT DT&P Labs,离散信源的联合熵与条件熵,(,续,),两随机变量的,联合熵,定义,4.2.3,两随机变量,的联合熵,如两随机变量统计独立，有,第,4,章 信息论基础,2010 Copyright,20,SCUT DT&P Labs,两随机变量的联合熵,(,续,),对于统计独立的两随机变量，不能从其中一个获得有关另外一个的任何信息,。,第,4,章 信息论基础,2010 Copyright,21,SCUT DT&P Labs,离散信源的联合熵与条件熵,(,续,),两随机变量的,条件熵,定义,4.2.4,两随机变量,的条件熵,一般地有,(,利用稍后的平均互信息量的非负性,),具有某种相关性的两随机变量,，,一个随机变量的出现总是,有助于降低另一随机变量的不确定性,。,第,4,章 信息论基础,2010 Copyright,22,SCUT DT&P Labs,4.3,离散信道及容量,2010 Copyright,23,SCUT DT&P Labs,离散信源及容量,信道模型,信道的,输入,：,信道的,输出,：,信道模型,(,特性,),可用其,转移概率,来描述,第,4,章 信息论基础,2010 Copyright,24,SCUT DT&P Labs,离散信源及容量,(,续,),信道模型,信道模型,(,特性,),可用其转移概率来描述，一般地有,输出不仅与当前的输入有关，而且与之前的若干个输入值,有关，呈现某种,“,记忆,”,效应。,第,4,章 信息论基础,2010 Copyright,25,SCUT DT&P Labs,离散信源及容量,(,续,),离散无记忆信道,的转移矩阵,输出仅与当前的输入,有关,离散无记忆信道的,后验概率矩阵,第,4,章 信息论基础,2010 Copyright,26,SCUT DT&P Labs,离散无记忆信道的转移矩阵,(,续,),示例,：二元的离散无记忆信道,发,“,0,”,和发,“,1,”,时,能正确接收的概率为,0.99,，,错误的概率为,0.01,。,即有,转移矩阵,第,4,章 信息论基础,2010 Copyright,27,SCUT DT&P Labs,离散信源及容量,互信息量,转移概率 是一种条件概率，在通信系统中可表示,收到 后，发送端发送的是符号 的概率。,接收端收到 后，关于 的不确定性可表示为,定义,4.3.1,互信息量为：,互信息量,为收到 后，关于 的,不确定性的消除量,。,第,4,章 信息论基础,2010 Copyright,28,SCUT DT&P Labs,互信息量,(,续,),互信息量具有,对称性,互信息量的,性质,(1),若,(2),若,(3),若,(4),若,第,4,章 信息论基础,2010 Copyright,29,SCUT DT&P Labs,离散信源及容量,(,续,),平均互信息量,定义,4.3.2,平均互信息量为：,平均互信息量具有非负性,表明从统计上来说，两相关联的随机变量集，其中一个的出,现总是有利于提供有关另外一个的信息。,第,4,章 信息论基础,2010 Copyright,30,SCUT DT&P Labs,离散信源及容量,(,续,),熵函数,与,平均互信息量,间的关系,第,4,章 信息论基础,2010 Copyright,31,SCUT DT&P Labs,熵函数与平均互信息量间的关系,(,续,),当信源,X,与,Y,统计独立时,(1),两个符号同时出现时提供的平均信息量等于每个符号的平均信息量之和；,(2),一个符号不能提供有关另一符号的任何信息。,第,4,章 信息论基础,2010 Copyright,32,SCUT DT&P Labs,熵函数与平均互信息量间的关系,(,续,),当两个信源相关时,(1),联合熵小于两个信源的熵的和,:,(2),平均互信息量等于两信源熵重合的部分；,(3),信源的条件熵等于其熵减去平均互信息量：,第,4,章 信息论基础,2010 Copyright,33,SCUT DT&P Labs,离散信道的容量,已知信道的,转移矩阵,信源符号集,： ；,符号传输速率,：,系统的,平均信息速率,为：,第,4,章 信息论基础,2010 Copyright,34,SCUT DT&P Labs,离散信道的容量,(,续,),定义,4.3.3,离散信道的最大传输速率为其信道容量,匹配信源的概念,信道容量由信道特性和信源的统计特性决定。,信道特性确定之后，其容量由信源的统计特性决定。,匹配信源,：能使单位时间内信道可传输的平均信息量达到信,道容量的信源称之。,记匹配信源的分布特性：,信道容量：,第,4,章 信息论基础,2010 Copyright,35,SCUT DT&P Labs,离散信道的容量,(,续,),匹配信源,(,续,),已知信道转移概率，匹配信源统计特性的求解,约束条件,求 使得 达到最大。,由拉格朗日求极值的原理：,定义辅助方程,令,可得信源分布特性应满足的条件,第,4,章 信息论基础,2010 Copyright,36,SCUT DT&P Labs,离散信道的容量,(,续,),由此可导出,匹配信源,统计特性的,求解步骤,：,(1),解方程组,求解得,(2),求最大平均互信息量：,(3),求相应后验概率：,(4),解方程组，确定匹配信源的分布特性,第,4,章 信息论基础,2010 Copyright,37,SCUT DT&P Labs,离散信道的容量,(,续,),示例,：求匹配信源的统计特性。已知信道转移概率,(1),解方程组的参数：,(2),求最大平均互信息量：,(3),求相应后验概率：,第,4,章 信息论基础,2010 Copyright,38,SCUT DT&P Labs,离散信道的容量,(,续,),示例,(,续,),：,(4),获得匹配信源统计特性：,(5),信道容量为：,注,：若求解过程中出现 ，可在方程组中令,，重新求解。,第,4,章 信息论基础,2010 Copyright,39,SCUT DT&P Labs,离散无记忆对称信道的容量,(,续,),离散无记忆对称信道,(,定义,),：,转移矩阵,转移矩阵各行各列均具有相同的元素集的信道称之。,离散无记忆对称信道满足条件：,任意的列元素和,任意的行元素和,第,4,章 信息论基础,2010 Copyright,40,SCUT DT&P Labs,离散无记忆对称信道的容量,(,续,),离散无记忆对称信道特性,：,(1),离散无记忆对称信道的条件熵满足：,条件熵取值仅由信道特性决定,，,与信源的统计特性无关,。,(2),若输入信道的信源符号等概,则信道的输出符号也等概,第,4,章 信息论基础,2010 Copyright,41,SCUT DT&P Labs,离散无记忆对称信道的容量,(,续,),信道容量,：,对于离散无记忆对称信道，若要使信息传输速率达到信道容量，要求信源的符号等概分布,。,对于非等概的信源，可设法对其输出的符号进行适当的组合,，使得重新构建后的符号,(,信源,),，具有近似等概的分布特性。,(,参见,“,信源的等长编码,”,一节,),第,4,章 信息论基础,2010 Copyright,42,SCUT DT&P Labs,4.4,连续信源、信道及容量,2010 Copyright,43,SCUT DT&P Labs,连续信源、信道及容量,连续信源的相对熵,若已知随机信号 幅度取值的概率密度函数：,取值在任意小区间 内的概率,(,参见示意图,),连续信源转变为具有,n,个随机变量的信源，且有,利用离散随机变量熵的定义，得,第,4,章 信息论基础,2010 Copyright,44,SCUT DT&P Labs,连续信源、信道及容量,(,续,),连续信源的相对熵,概率密度函数的离散化示意图，输入的取值范围,第,4,章 信息论基础,2010 Copyright,45,SCUT DT&P Labs,连续信源的相对熵,(,续,),连续信源的熵,应为,可见,连续信源的熵无限大,。该熵称为,连续信源的绝对熵,，,无,法确切地定义,。,通常上式的第一项是有限值，且其具有特定的物理意义。,第,4,章 信息论基础,2010 Copyright,46,SCUT DT&P Labs,连续信源的相对熵,(,续,),定义,4.4.1,连续信源的相对熵为,示例,某信号的相对熵为,信号经,2,倍幅度放大后的相对熵为,信号的简单放大并没有增加任何新的信息，但其相对熵发生,了增大的变化，这说明,相对熵已经不再具有信源平均信息量,的内涵,。,第,4,章 信息论基础,2010 Copyright,47,SCUT DT&P Labs,连续信源的相对条件熵,对于连续随机变量，同样可以导出其,条件熵,可见连续信源的条件熵取值无限大，同样无法确切定义,。但通常上式的第一项是一个有限取值的量。,连续信源的熵和条件熵均取值无限大，说明,要在一个容量有,限的通信系统中传递连续信源的全部信息是不可能的。,第,4,章 信息论基础,2010 Copyright,48,SCUT DT&P Labs,连续信源的相对条件熵,(,续,),定义,4.4.3,连续信源的相对条件熵,因为：,说明,相对熵,和,相对条件熵,的差值与普通的熵和条件熵的差值,一样，仍然等于,平均互信息量。,同理可以导出：,第,4,章 信息论基础,2010 Copyright,49,SCUT DT&P Labs,连续信源相对熵的最大化,定理,4.4.3,连续信源的相对熵函数 是信源概率密度函,数 的,型凸函数。,相对熵 作为概率密度函数 的函数存在最大值。,第,4,章 信息论基础,2010 Copyright,50,SCUT DT&P Labs,连续信源相对熵的最大化,(,续,),(1),峰值功率受限情况下的相对熵最大化条件,可以证明：,当连续信源的概率密度函数服从,均匀分布,时，该连续信源有最大的相对熵。,在区间 分布连续信源 的概率密度函数为,其相对熵为,峰值受限信号,若,第,4,章 信息论基础,2010 Copyright,51,SCUT DT&P Labs,连续信源相对熵的最大化,(,续,),(2),均值受限情况下的相对熵最大化条件,可以证明：,当连续信源的概率密度函数服从,指数分布,时，该连续信源有最大的相对熵。,均值受限信号,指数分布,相对熵,第,4,章 信息论基础,2010 Copyright,52,SCUT DT&P Labs,连续信源相对熵的最大化,(,续,),(3),平均功率受限情况下的相对熵最大化条件,可以证明：,当连续信源的概率密度函数服从,高斯分布,时，该连续信源有最大的相对熵。,平均功率受限信号,高斯分布,相对熵,第,4,章 信息论基础,2010 Copyright,53,SCUT DT&P Labs,加性高斯噪声信道的容量,加性高斯噪声,(,干扰,),信道,(,AWGN,),信道输入： 信道输出： 加性高斯噪声：,已知通过信道后，从 可获得的关于 的平均互信息量,若已知信号 的带宽为： 。 对任意的这类信号,则无失真的抽样频率至少应为：,(,单位时间的样点数,),单位时间内传输的信息量，即信息速率为,第,4,章 信息论基础,2010 Copyright,54,SCUT DT&P Labs,加性高斯噪声信道的容量,(,续,),加性高斯噪声,(,干扰,),信道,(AWGN),的,信道容量,信号与噪声间的关系可用方程组表示为,或,二维函数概率密度间的关系,为,雅可比行列式,第,4,章 信息论基础,2010 Copyright,55,SCUT DT&P Labs,加性高斯噪声信道的容量,(,续,),因为,所以有,若已知信源,x,的统计特性，收到,y,后不可确定的部分为,噪声造成影响的部分。,第,4,章 信息论基础,2010 Copyright,56,SCUT DT&P Labs,加性高斯噪声信道的容量,(,续,),因此可得,第,4,章 信息论基础,2010 Copyright,57,SCUT DT&P Labs,加性高斯噪声信道的信道容量,(,续,),因为,(1),在均方受限的条件下，高斯分布的信源有最大的相对熵,(2),两高斯分布的随机变量之和,( ),仍为高斯随机变量,(3),信号 与噪声 统计独立,因而有,第,4,章 信息论基础,2010 Copyright,58,SCUT DT&P Labs,加性高斯噪声信道容量,(,续,),信道容量,若记,得,香农公式,第,4,章 信息论基础,2010 Copyright,59,SCUT DT&P Labs,加性高斯噪声信道容量,(,续,),由,香农公式,(,香农定理,),得到的,重要结论,：,(1),信道容量,C,随,S/N,增大而增大；,(2) C,一定时，,W,与,S/N,之间可以彼此互换；,(3) N 0, C , ：无扰信道的容量为无穷大；,(4),对受高斯噪声干扰的信道，当,W ,， 信道容量趋于,一有限的确定值：,(,S,与,N,0,固定时,),第,4,章 信息论基础,2010 Copyright,60,SCUT DT&P Labs,信道容量和带宽的归一化分析,归一化信道容量,：,单位时间单位频带内可达到的信息速率,。,注：所谓物理不可,实现是指不可,能实现无差错,传输。,第,4,章 信息论基础,2010 Copyright,61,SCUT DT&P Labs,信道容量和带宽的归一化分析,(,续,),归一化信道带宽：单位信息速率所需要的最小带宽。,第,4,章 信息论基础,2010 Copyright,62,SCUT DT&P Labs,信道容量和带宽的归一化分析,(,续,),关于,E,b,/N,0,的归一化信道带宽,E,b,：比特能量；,N,0,：噪声功率密度谱；,当,E,b,/N,0,1.59dB,时，无法实现无差,错的传输。,第,4,章 信息论基础,2010 Copyright,63,SCUT DT&P Labs,4.5,信源编码的基本方法,2010 Copyright,64,SCUT DT&P Labs,信源编码的基本方法,信源编码的目的：提高传输效率,（,1,）去除信息中的冗余度，使传输的符号尽可能都是独立的，没有多余的成分,(,如语音、图像信号压缩,),；,（,2,）使传输的符号所含的信息最大化。例如，通过编码使符号以等概分布的形式出现，使每个符号可能携带的信息量达到最大；,（,3,）采用不等长编码，让出现概率大的符号用较短的码元序列表示，对概率小的符号用较长的码元序列；,(4),在允许一定失真的条件下，如何实现高效率的编码。,第,4,章 信息论基础,2010 Copyright,65,SCUT DT&P Labs,离散无记忆信源,(DMS: Discrete,Memoryless,Source,）,离散无记忆信源的输出序列：,各个,符号间彼此独立,其中,反之，若输出的各符号间,有一定的相关性,，则其为一种,有记忆的信源,。,有记忆的信源，经过处理后，有可能变为一种无记忆的信,源。如有记忆的信源，经过理想的、完全去除冗余的,压缩编码后产生的输出。,第,4,章 信息论基础,2010 Copyright,66,SCUT DT&P Labs,离散无记忆信源编码与译码,若将信源输出的符号按每,J,个为一组进行编码，则任意的第,m,个分组可以表示为,编码输出,其中,为输出的码元集。,接收端的,译码输出,第,4,章 信息论基础,2010 Copyright,67,SCUT DT&P Labs,离散无记忆信源编码与译码,(,续,),待编码码组,编码,输出码组,(,码字,),第,4,章 信息论基础,2010 Copyright,68,SCUT DT&P Labs,离散无记忆信源编码与译码,(,续,),定义,4.5.1,若对信源的每个不同的符号或不同的符号序列，编,码后产生的码字不同的，则称该码为,唯一可译码,。,若待编码的符号序列的不同组合个数为,码字集中不同的码字个数,唯一可译码的条件,第,4,章 信息论基础,2010 Copyright,69,SCUT DT&P Labs,离散无记忆信源,编码与译码,(,续,),定义,4.5.2,编码表示一个信源符号所需的平均信息量的定义为,编码速率,。,码字长度为常数的编码称为,等长编码,，发之称为,不等长编码,。,等长编码,的,编码速率,不等长编码,的,编码速率,其中 为不等长编码的,平均码长。,第,4,章 信息论基础,2010 Copyright,70,SCUT DT&P Labs,离散无记忆信源编码与译码,(,续,),定义,4.5.3,信源的熵 与编码速率 的比值定义为编码效率,要保证编码没有信息丢失，要求,第,4,章 信息论基础,2010 Copyright,71,SCUT DT&P Labs,离散无记忆信源的等长编码,等长编码：对信源的每个符号，或每组符号，用长度相等的代码来表示。,单个符号独立编码,采用 进制码元编码,若信源符号集有,L,种符号，要保证译码的惟一性，由,码字长度应取,取整得,编码效率：,第,4,章 信息论基础,2010 Copyright,72,SCUT DT&P Labs,离散无记忆信源的等长编码,(,续,),扩展编码,(,联合编码,),：,将,J,个信源符号进行联合编码,由译码唯一性要求,取整得,平均每个符号所需的码元数,J,取值的增大有利于效率的提高。,第,4,章 信息论基础,2010 Copyright,73,SCUT DT&P Labs,离散无记忆信源的等长编码,(,续,),信源统计特性对编码效率的影响,例,4.5.1,采用二进制码元分别对,J,4,的两信源符号序列进行编码。,信源,1,：,因为 故可取,平均每个符号的码元数,编码效率,第,4,章 信息论基础,2010 Copyright,74,SCUT DT&P Labs,离散无记忆信源的等长编码,(,续,),信源,2,：,同理有,编码效率,第,4,章 信息论基础,2010 Copyright,75,SCUT DT&P Labs,离散无记忆信源的等长编码,(,续,),不同统计特性的信源，因其熵不同,编码效率可能差异很大,。,第,4,章 信息论基础,2010 Copyright,76,SCUT DT&P Labs,离散无记忆信源,(DMS),的有损等长编码,一种考虑信源统计特性的编码,信源符号集,由最大熵定理,由熵的定义，可知,由译码的唯一性要求,可得,码组长度应满足条件,由 得,第,4,章 信息论基础,2010 Copyright,77,SCUT DT&P Labs,离散无记忆信源,(DMS),的有损等长编码,一种考虑信源统计特性的编码,(,续,),对任意统计特性的信源，要使下式成立，即获得较高的编码效率，通常,J,取值要非常大。,无损的等长编码,，往往会因为,J,的取值过大，难以实际应用。,下面考虑有损的等长编码。,第,4,章 信息论基础,2010 Copyright,78,SCUT DT&P Labs,离散无记忆信源,(DMS),的有损等长编码,对于长度为,J,的,DMS,码组,(,或称为一序列,):,码组中的每个符号：,由符号间的独立性，有,码组 包含的信息量为：,根据熵的定义，随着,J,的增大，有,或,可以证明,第,4,章 信息论基础,2010 Copyright,79,SCUT DT&P Labs,离散无记忆信源,(DMS),的有损等长编码,(,续,),即：,定义,4.5.4,典型序列集,：满足下列条件的序列 的集合称之。,其中 ，通常是一个很小的数。,非典型序列集,：典型序列集的补集称之。,典型序列集和非典型序列集构成了序列 所有组合构成,该符号序列的空间。,第,4,章 信息论基础,2010 Copyright,80,SCUT DT&P Labs,离散无记忆信源,(DMS),的有损等长编码,(,续,),定理,4.5.5,(,信源划分定理,),：任给 ，当,J,足够大时,有,即有：,典型序列出现的概率,：若,则,即有：,典型序列趋于等概分布,。,典型序列的数目,：,第,4,章 信息论基础,2010 Copyright,81,SCUT DT&P Labs,离散无记忆信源,(DMS),的有损等长编码,(,续,),典型序列的出现概率,：,即：,典型序列集 为,高概率集,；,非典型序列集 为,低概率集,。,第,4,章 信息论基础,2010 Copyright,82,SCUT DT&P Labs,离散无记忆信源,(DMS),的有损等长编码,(,续,),典型序列集在整个序列空间中所占的,比例,：,通常 取值很小，满足,因此,说明虽然,典型序列集是一个高概率集,，但,其数目在整个序列空间中可能只占很小的比例,；,第,4,章 信息论基础,2010 Copyright,83,SCUT DT&P Labs,离散无记忆信源,(DMS),的有损等长编码,(,续,),典型序列集的形象说明,如果容许一定的失真，只对典型序列编码，对非典型序列不,予编码传输，码字长度可大大缩短，从而有效提高传输效率,。,第,4,章 信息论基础,2010 Copyright,84,SCUT DT&P Labs,离散无记忆信源,(DMS),的有损等长编码,(,续,),例,4.5.2,：已知二元信源,信源的熵为：,所有的序列,构成的集合,为,第,4,章 信息论基础,2010 Copyright,85,SCUT DT&P Labs,离散无记忆信源,(DMS),的有损等长编码,(,续,),示例,(,续,),：,(1),若取,由,平均信息量落在该范围内的序列,(,典型序列,),为,其概率和,第,4,章 信息论基础,2010 Copyright,86,SCUT DT&P Labs,离散无记忆信源,(DMS),的有损等长编码,(,续,),示例,(,续,),：,(1),若取,由,平均信息量落在该范围内的序列,(,典型序列,),为,其概率和,第,4,章 信息论基础,2010 Copyright,87,SCUT DT&P Labs,离散无记忆信源,(DMS),的有损等长编码,(,续,),可达速率的概念,译码错误概率定义为,定义,4.5.4,可达速率,给定信源和编码速率,R,，对任意的 若存在,和编译码方法： 、,使当 时，有 则该编码速率称为,可达的,反之称速率是,不可达的。,编码速率,第,4,章 信息论基础,2010 Copyright,88,SCUT DT&P Labs,离散无记忆信源,(DMS),的有损等长编码,(,续,),定理,4.5.5,若 ，则速率,R,是,可达的,；,若 ，则速率,R,是,不可达的,。,该定理说明，若 ，则存在编码方法，当,J,足够,大时，只需对典型序列进行编码，可使编码误差足够地小。,第,4,章 信息论基础,2010 Copyright,89,SCUT DT&P Labs,离散无记忆信源,(DMS),的有损等长编码,(,续,),分析在满足一定的译码错误概率的条件下，若只对典型序列编码，如何,确定编码长度,：,若记：编码速率：,自信息方差：,则不能正确译码的概率 满足关系式,(,参见信源划分定理证明,),根据上式，可确定编码序列的长度,J,。,第,4,章 信息论基础,2010 Copyright,90,SCUT DT&P Labs,离散无记忆信源,(DMS),的有损等长编码,(,续,),示例,：,(1),对二元符号进行无差错的二进制编码,此时 、 、,(2),若要求编码效率 ，,求所需的编码序列长度,J,由,得,第,4,章 信息论基础,2010 Copyright,91,SCUT DT&P Labs,离散无记忆信源,(DMS),的有损等长编码,(,续,),自信息方差：,最后得所需的符号序列长度,(,该取值太大，可见等长编码不易在实际系统中应用,),第,4,章 信息论基础,2010 Copyright,92,SCUT DT&P Labs,不等长编码的基本概念,定义,4.5.8,若码中个码字都含有一个特定的符号用于标识一,个码字的起点，则称这种码为,逗点码,。,例：,0,，,01,，,011,，,0111,为逗点码。,定义,4.5.9,对任一码字 ，称该码字的前面 位,， ，为码字 的长为 的,字头,或,前缀,。,定义,4.5.10,若码字集中任一码字都不是另一码字的字头，则,称这种码为,异字头码,，或,异前缀码,。,定义,4.5.11,对具有 个元素的信源符号集：,若符号 用 元码编码后输出的码字长度为 ，则定,义信源符号的,平均码字长度,为：,第,4,章 信息论基础,2010 Copyright,93,SCUT DT&P Labs,异字头不等长编码,异字头码的,优点,：异字头码译码时具有即时性，即当收到一个完整的码字后即可译码，不用担心这一码字是另一码字的字头部分。,异字头码的编码树,：异字头码的编码可用编码树来描述,第,4,章 信息论基础,2010 Copyright,94,SCUT DT&P Labs,第,4,章 信息论基础,异字头不等长编码,(,续,),异字头码的编码原则,编码时应尽可能地使码字中的任一码元载荷达到其最大的信息量： 。,应使每个节点发出的种 分支出现的概率尽可能相等。,异字头码的编码方法,将信源符号分成尽可能等概的个,子集,，与码树的第一级的个节点对应；,对每个子集按同样的方法又分为个,二级子集,，与码树的第二级节点相对应；,以此类推，直至子集不能再分为止。,2010 Copyright,95,SCUT DT&P Labs,第,4,章 信息论基础,异字头不等长编码,(,续,),示例：,对信源符号集,做 的三进制异字头不等长编码。,解,：,2010 Copyright,96,SCUT DT&P Labs,第,4,章 信息论基础,不等长编码的基本定理,*,定理,4.5.12,对具有个符号的信源符号集： ，其相应的长度为 的元异字头码存在的充要条件是如下的不等式成立,定理,4.5.13,唯一可译码必满足,(Kraft),不等式：,(,定理,4.5.13,）,系,：任一唯一可译码可用相应的码字长度一样的异字头码代替。,即：任一唯一可译码可用相应的码字长度一样的异字头码代替，而不改变该码的任何性质。,2010 Copyright,97,SCUT DT&P Labs,第,4,章 信息论基础,不等长编码的基本定理,*,(,续,),定理,4.5.14,（不等长编码定理）,（,1,）若 是组成码字的元素的个数，则任一唯一可译码的平均码长满足：,（,2,）存在有 元的可译码，其平均长度,2010 Copyright,98,SCUT DT&P Labs,第,4,章 信息论基础,不等长编码的基本定理,*,(,续,),多个符号的联合不等长编码,记：,信源符号集,：,待编码的符号序列,：,特定符号序列 编码后输出的码字长度,符号序列 编码后的,平均码字长度,符号序列 的,熵函数,则由,定理,4.5.14,，可得,2010 Copyright,99,SCUT DT&P Labs,第,4,章 信息论基础,不等长编码的基本定理,*,(,续,),定义,4.5.15,对个信源符号进行不等长联合编码时平均一个信源符号的编码长度定义为,由前面的讨论可得,可见：,多个符号的不等长联合编码有同样利于提高编码效率,。,2010 Copyright,100,SCUT DT&P Labs,第,4,章 信息论基础,不等长编码的基本定理,(,续,),离散无记忆信源的扩展信源的编码,以,J,个离散无记忆信源符号为一组可构成一个扩展信源,扩展信源的熵函数为,由前面的分析可得,可见,对扩展后的离散无记忆信源的编码有利于提高编码效率,。,且有,2010 Copyright,101,SCUT DT&P Labs,第,4,章 信息论基础,不等长编码的基本定理,(,续,),定义,4.5.16,不等长码的,编码速率,定义为,是平均每个,信源符号,编码时所需的,码元,的个数；,是每个码元可能携带的最大信息量；,编码速率的物理意义是 个码元可携带的最大信息量。,定义,4.5.17,不等长码的,编码效率,定义为,编码效率,表示的是每个信源符号平均信息量与编码所需的平均码字符号可携带最大信息量的比值。,2010 Copyright,102,SCUT DT&P Labs,霍夫曼,(Huffman),编码,霍夫曼编码是一种,异字头不等长编码,，其基本思想是：,对出现概率大的符号或符号组用位数较少的码字表示；,对出现概率小的符号或符号组用位数较多的码字表示。,由此可提高编码效率。,霍夫曼编码,：,定理,4.5.17,霍夫曼编码一种,最佳的不等长编码,。,霍夫曼编码的,应用条件,：,信源的分布,(,统计,),特性已知。,记 信源符号集为：,编码输出符号集为：,第,4,章 信息论基础,2010 Copyright,103,SCUT DT&P Labs,霍夫曼编码,(,续,),霍夫曼编码的步骤,：,(1),将,L,个信源符号按概率大小，以递减次序，从上到下排成一列；,(2),对处于最下面的概率最小的,D,个信源符号，一一对应地分别赋予码字元素,Z,1,、,Z,2,、,、,Z,D,，把这,D,个概率最小的信源符号相应的概率相加，所得的值用一个虚拟的符号代表，与余下的,L-D,个符号组成含有,(L-D)+1=L-(D-1),个符号的第一次缩减信源,S,(1),；,(3),对缩减信源,S,(1),仍按其概率大小以递减次序从上到下排列，按照步骤,(2),的方法处理，得到一个含有,(L-D)+1-D+1=L-2(D-1),个符号的第二次缩减信源,S,(2),；,(4),按照上述的方法，依次继续下去，每次缩减所减少的符号数是,D-1,个；只要缩减后的信源,S,i,符号的个数大于,D,，缩减就继续进行；,(5),当进行第,k,次缩减后信源,S,(k,),符号个数刚好等于,D,，即有,则对最后这,D,个符号分别赋予码字元素,Z,1,、,Z,2,、,、,Z,D,；,第,4,章 信息论基础,2010 Copyright,104,SCUT DT&P Labs,霍夫曼编码,(,续,),霍夫曼编码的步骤：,(6),从最后赋予的码符号开始，沿着每一信源符号在各次缩减过程中得到的码字元素进行路线前向返回，达至每一信源符号，按前后次序，把返回路途中所遇到的码元素排成序列，这个序列，就是相应信源符号对应的码字；,(7),若进行,k,次缩减后，当进行第,k,次缩减后信源,S,(k,),符号个数不等于,D,，即有,则中止缩减，增加 个概率为,0,的虚假信源符号,重新编码，使在,k,次编码后一定有 。,第,4,章 信息论基础,2010 Copyright,105,SCUT DT&P Labs,霍夫曼编码,(,续,),示例,：已知信源符号集,编码输出的码字符号集为,解：已知： 尝试,需要增加虚假符号数为,新构建的信源满足：,第,4,章 信息论基础,2010 Copyright,106,SCUT DT&P Labs,霍夫曼编码,示例,(,续,),：改造后的符号概率场为,编码过程如下,第,4,章 信息论基础,2010 Copyright,107,SCUT DT&P Labs,霍夫曼编码,(,续,),示例,(,续,),：,平均码字长度：,第,4,章 信息论基础,2010 Copyright,108,SCUT DT&P Labs,霍夫曼编码,(,续,),示例,(,续,),：,如果不加入虚假符号，直接进行编码，则有,平均码字长度,第,4,章 信息论基础,2010 Copyright,109,SCUT DT&P Labs,霍夫曼编码,(,续,),码字长度的均匀性和方差,在同样的平均码字长度的情况下，码字长度越均匀，对传输越有利。,定义,4.5.16,码字长度的,方差,其中,编码过程的排序过程不同会影响码长的方差。,第,4,章 信息论基础,2010 Copyright,110,SCUT DT&P Labs,霍夫曼编码,(,续,),码字长度的均匀性和方差,(,续,),示例：信源的符号空间为,编码输出码字集,编码方式,1,将局部概率和置于相同概率的最低位置,第,4,章 信息论基础,2010 Copyright,111,SCUT DT&P Labs,霍夫曼编码,示例：,编码方式,1(,续,),平均码长,：,方差,：,第,4,章 信息论基础,2010 Copyright,112,SCUT DT&P Labs,霍夫曼编码,编码方式,2,将局部概率和置于相同概率的最高位置,平均码长,：,方差,：,第,4,章 信息论基础,2010 Copyright,113,SCUT DT&P Labs,霍夫曼编码,(,续,),可见,虽然平均码长一样，但编码方法,2,使得输出的码长更为均匀。,在编码过程中，当对缩减信源概率重新排列时，应使合并得到的局部概率和，尽量使其处于最高位置；使得合并元素重复编码的次数减少，有利于降低码字长度的方差。,第,4,章 信息论基础,2010 Copyright,114,SCUT DT&P Labs,4.6,率失真理论,2010 Copyright,115,SCUT DT&P Labs,实际系统中的权衡问题,实际系统中通常需要考虑,性能,与,经济性,之间的权衡问题；,可采用以某些不可察觉或可察觉但不影响应用的信号失真代价，来换取所需的传输速率、存储空间、运算复杂度和系统实现成本的降低；,电话系统采样,8kHz,采样，,8,比特量化；,数字音响系统采样,44kHz,采样，,16,或,24,比特量化；,第,4,章 信息论基础,2010 Copyright,116,SCUT DT&P Labs,失真的概念,失真,是指用某种尺度衡量的理想信源样值 与,“,变换,”,后的样值,间的差异。,这里所谓的,“,变换,”,，可以是某种有损的编码，或者是经传输后受到劣化的信号。,失真函数,：对由符号 变为符号 产生失真造成的影响，可根据不同的情况定义一个非负函数 来描述，该函数就称为失真函数。,失真函数的取值通常反映失真产生的代价。,第,4,章 信息论基础,2010 Copyright,117,SCUT DT&P Labs,失真的概念,(,续,),失真函数的示例：,第,4,章 信息论基础,2010 Copyright,118,SCUT DT&P Labs,率失真理论研究的问题,率失真理论研究的是限定失真条件下信源的编码和信息传输问题的方法。,分析在允许一定失真的条件下，要重构信源的符号，至少应获得多少信源的信息量；,第,4,章 信息论基础,2010 Copyright,119,SCUT DT&P Labs,率失真理论在通信系统中应用时的参数,输入信号集：,输出信号集：,对离散无记忆信道，有,失真函数：,其中 为输入符号； 为输出符号,第,4,章 信息论基础,2010 Copyright,120,SCUT DT&P Labs,平均失真度,失真函数矩阵,与转移概率矩阵对应，可定义相应的失真度矩阵：,定义,4.6.1,平均失真度定义为,平均失真度是从统计意义上来说每个符号失真的平均值。,第,4,章 信息论基础,2010 Copyright,121,SCUT DT&P Labs,平均失真度,(,续,),在通信系统中，失真通常在信道中产生，平均失真度与信道的关系可由转移概率的函数来描述。,给定信源的统计特性,和失真函数的定义,平均失真度由信道转移概率决定,第,4,章 信息论基础,2010 Copyright,122,SCUT DT&P Labs,平均失真度,(,续,),平均失真度与信道转移概率的关系,示例,已知信源统计特性,信道转移概率矩阵,当失真测度采用汉明失真函数时，平均失真度为,第,4,章 信息论基础,2010 Copyright,123,SCUT DT&P Labs,率失真函数,回顾平均互信息定义,定理,4.6.2,给定信源的统计特性,平均互信息量是信道转移概率,的,型凸函数。,定理成立的主要依据：,对数函数 的,型凸函数特性；,概率的基本关系式：,第,4,章 信息论基础,2010 Copyright,124,SCUT DT&P Labs,率失真函数,(,续,),定义,4.6.3,给定信源统计特性,给定失真度准则,率失真函数,定义为,其中,转移概率矩阵集,定理,4.6.2,保证了率失真函数的存在。,第,4,章 信息论基础,2010 Copyright,125,SCUT DT&P Labs,率失真函数,(,续,),率失真函数的物理意义,：,如果将符号通过信道传输看作某种变换过程，,为了以小于,等于,D,C,的失真度恢复信源的输出，,