第4章 信息率失真函数.ppt

Page,*,第,4,章 信息率失真函数,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,Page,*,第,4,章 信息率失真函数,本章节教学内容、基本要求、重点与难点,1.教学内容：,失真函数的定义,率失真函数的定义、性质,率失真函数的计算,2.教学基本要求：,掌握率失真函数的定义和意义,掌握率失真函数的性质、计算,3.重点与难点：,率失真函数的计算,主要内容,第,4,章 信息率失真函数,4.1,基本概念,4.1.1,失真函数（失真度）,4.1.2,平均失真度,4.1.3,信息率失真函数,4.1.4,信息率失真函数的性质,4.2,离散信源,R(D),的计算,4.3*,连续信源的计算,本次课内容,4.1,基本概念,4.1.1,失真函数（失真度）,4.1.2,平均失真度,4.1.3,信息率失真函数,4.1.4,信息率失真函数的性质,第,4,章 信息率失真函数,在实际信息处理过程中，由于存在信道噪声的干扰，或信源信息以超过信道容量的速率传输时产生的差错或失真,信宿接收到的信息会有一定的失真。,实际传输允许有一定的失真，关键是如何减小失真，允许失真到什么程度。在允许一定程度的失真条件下，把信源信息压缩到什么程度。,本章我们从最少信息率，失真函数、平均失真出发，研究信息率失真函数的定义和性质，给出离散信源和连续信源求解信息率失真函数的常用简单方法。,4.1,基本概念,4.1.1,失真函数（失真度）,为什么引入失真函数？,在实际问题中，信号有一定的失真是可以容忍的，但是当失真大于某一限度后，将丧失其实用价值。,要规定失真限度，必须先有一个定量的失真测度。为此可引入失真函数,.,4.1.1,失真函数,失真函数定义,:,若 则认为,没有失真,；若 就产生了,失真,。失真的大小，用一个量表示，即失真函数,来衡量用,b,j,代替,a,i,所引起的失真程度。,4.1.1,失真函数,1.,离散信源单个符号的失真函数,定义,:,设离散无记忆信源输出变量 ，,概率分布为,经过有失真的,信源编码器，输出的随机变量 。,将所有的 排列起来，用,矩阵形式表示，称为失真矩阵，即,4.1.1,失真函数,例：设信源符号,X,0,，,1,编码器输出符号,Y,0,1,2,规定失真函数为,d(0,0),d(1,1),0;d(0,1),d(1,0)=1;,d(0,2),d(1,2),0.5,求失真矩阵,d.,解,:,失真矩阵,4.1.1,失真函数,若失真矩阵中,每一行,都是,同一集合中诸元素的不同排列,，并且,每一列,也都是,同一集合中诸元素的不同排列,，则称具有,对称性,。以这种具有对称性的失真矩阵度量失真的信源称为失真对称信源（简称对称信源）。,将在其它章节讲。,4.1.1,失真函数,2.,离散信源序列的失真函数,失真函数的定义可以推广到序列编码情况，如果离散信源输出,N,维符号序列,X,=,X,1,X,2,X,N,，其中,X,i,(i,=1,2,3,N),取自于同一符号集,X=,a,1,a,2,.,a,r,，,X,共有,r,N,个不同的符号序列 。而经过信源编码后，输出的是,N,维符号序列 ，其中 取自于同一符号集,Y,共有,s,N,个不同的符号序列,4.1.1,失真函数,定义,:,信源序列的失真函数,信源序列失真函数等于信源序列中对应的单符号失真函数之和。也可写成 阶矩阵形式。,信源序列的单个符号失真函数为,4.1,基本概念,4.1.2,平均失真度,定义,:,由于,a,i,和,b,j,都是随机变量，所以失真函数,d(a,i,b,j,),也是随机变量，要分析整个信源的,失真大小，需要用其数学期望或统计平均值,表示，将失真函数的数学期望称为平均失真,度，即。,4.1.2,平均失真度,1.,离散信源平均失真度,平均失真度 是对给定信源分布 经过某一种转移概率分布 的有失真信源编码器后产生失真的总体度量。,-,联合分布,-,信源符号概率分布,-,符号转移概率分布,-,离散随机变量的失真函数,其中,:,4.1.2,平均失真度,2.,离散信源序列的平均失真度,(1),信源序列的平均失真度：,(2),信源序列的单个符号平均失真度，也称信源的平均失真度：,当信源和信道都是无记忆时，则有：,及,其中,是第个 分量的平均失真度,4.1.2,平均失真度,3.,连续信源的失真函数和平均失真度,定义：,设连续信源输出随机变量,X,，取值于实数,域,R,，其概率密度分布为,P(X),，经过有失,真的信源编码器，输出的随机变量,Y,，取值,于实数域,R,。,在对应的,a,和,b,之间确定非负二元实函数,d(a,b),0,，,(a,bR),连续信源的平均失真度为：,4.1.2,平均失真度,4.,常用的失真函数和平均失真度,(1),汉明失真函数,汉明失真矩阵为：,在汉明失真函数 的情况下，信源平均失真度等于信道的平均错误概率,P,e,，即：,适用于离散信源,4.1.2,平均失真度,4.1.2,平均失真度,(2),常数失真函数,失真矩阵为：,（通常为,r,r,阶）,在常数失真函数下,适用于离散信源,(3),均方失真函数,或,在均方失真函数下，平均失真度就是均方误差。,离散信源的均方误差,连续信源的均方误差：,适用于连续信源,4.1.2,平均失真度,(4),绝对失真函数,或,在绝对失真函数下,离散信源平均失真度：,连续信源平均失真度,：,dadb,适用于连续信源,4.1.2,平均失真度,(5),相对失真函数,或,在绝对失真函数下,离散信源平均失真度：,连续信源平均失真度：,dadb,适用于连续信源,4.1.2,平均失真度,均方失真和绝对失真只与,a-b,有关，而不是分别与,a,及,b,有关，在数学处理上比较方便；相对失真与主观特性比较匹配但在数学处理中困难得多。,在实际问题中还可提出许多其它形式的失真函数。,4.1.2,平均失真度,例,:,等概信源,通过信道转移概率矩阵为,的信道传输,失真函数为均方失真函数,.,求,:,平均失真。,信源输出符号,X=(0.1.2),信道输出符号,Y=(0.1.2),4.1.2,平均失真度,解：,均方失真函数,4.1.2,平均失真度,信源输出符号,X=(0.1.2),信道输出符号,Y=(0.1.2),又例,:,信源输出符号,X=(0.1.2),信道输出符号,Y=(0.1.2),给出失真函数,d,ij,=(x,i,-y,j,),2,d,ij,=x,i,-,y,j,(1),求平方误差失真函数矩阵,2),求绝对值误差失真函数矩阵,.,解,(1),(2),4.1.2,平均失真度,4.1.3,信息率失真函数,信源编码器的目的是使编码后所需的信息传输率尽量小，然而越小，引起的平均失真就越大。通常要将平均失真限制在某一有限值内，即，并选择一种方法使信息率尽可能小。对失真的限制条件称为保真度准则。,4.1.3,信息率失真函数,单位为比特（奈特，哈特）,/,信源符号。,定义,:,选定信源和失真函数后，可以看成条件概率 的函数。设 满足保真度准则的所有信道集合，这种信道称为失真度,D,允许信道（或试验信道）。,B,D,中任一转移概率都与一个,D,允许信道,（编码器）,对应，在,B,D,中寻求一个寻求一个特定编码器）,使,I(X;Y),最小，这个最小的平均互信息量称为信息率失真函数，简称为率失真函数，记为,对于给定信源，,R(D),是保真度准则下 容许压缩的最小值，也是熵压缩编码器输出可能达到的最低熵率。,4.1.3,信息率失真函数,信息率失真函数推广到序列情况,:,若信源和信道均无记忆，则有：,N,维序列的信息率失真函数：,此时试验信道为所有满足保真度准则 的信道的集合，并且有,.,4.1.3,信息率失真函数,4.1.4,信息率失真函数的性质,1.,函数的定义域为,(1),定义域下界：,4.1.4,信息率失真函数的性质,对于每一个,a,i,找一个,b,j,与其相对应。使,d(a,i,b,j,),最小，不同的,a,i,对应的最小的,d(a,i,b,j,),不同，这相当于在失真矩阵的每一行找出一个最小的的,d(a,i,b,j,),，各行最小的,d(a,i,b,j,),不同，对于所有这些不同的最小值取数学期望，就是所谓的最小平均失真度,只有当失真矩阵的每一行至少有一个零元素时，信源的平均失真度才能达到下线值零。,当,D,min,=0,，也就是说，信源不允许任何失真存在，信息率至少等于信源输出的平均信息量,-,信源熵，,R,（,0,）,=H,（,X,）,对于连续熵,(2),定义域上界：,由于,R(D),是用从,B,D,中选出 求得的最小平均互信息，所以,R(D),非负。当增大时,B,D,的范围增大，所求的最小值不大于范围扩大前的最小值，因此,R(D),为,D,的非增函数。当,D,增大时，,R(D),可能减小，直到减小到,R(D)=0,，此时对应着,D,max,。当再增大，,R(D),仍然为,0,。所以选择所有满足,R(D)=0,中的,D,的最小值定义为定义域的上限 ，是使,R(D)=0,的最小平均失真。,4.1.4,信息率失真函数的性质,当,a,b,独立时，使得,R(D)=0,。所以,给定,而且对不同的,b,有不同的值。所以，求 时，使对应的,p(b,)=1,，其余为,0,。这样就可使平均失真最小。,4.1.4,信息率失真函数的性质,注,:,(1),当失真矩阵的每一行至少有一个零元素时,.,（,2,）可适当修改失真函数使得；,（,3,）,D,min,和,D,max,仅与,p(a,),和,d(a,b,),有关；,(4),信息率失真函数有,4.1.4,信息率失真函数的性质,【,例,4.1-1】,设试验信道输入符号,a,1,a,2,a,3,，概率分别为 ，失真矩阵如下所示,.,求,D,max,和,D,min,以及相应的试验信道的转移概率矩阵。,解：,4.1.4,信息率失真函数的性质,令对应最小,d(a,i,b,j,),的 ，其它为,0,。可得对应的的转移概率矩阵为,4.1.4,信息率失真函数的性质,上式中第,2,项最小，,令,。可得对应的转移概率矩阵为,4.1.4,信息率失真函数的性质,求,D,max,例 设输入输出符号,X=Y=0,，,1,，输入概率分布为,p(x,)=1/3,2/3,，失真矩阵为,4.1.4,信息率失真函数的性质,解,：,p(x,)=1/3,2/3,输出符号概率,4.1.4,信息率失真函数的性质,、,R(D),是关于,D,的的下凸函数,设,D,1,D,2,为任意两个平均失真，那么,证明略,3.R(D),是定义域上的连续和非增函数,证明略,4.1.4,信息率失真函数的性质,4.1.4,信息率失真函数的性质,一个信源含有三个消息,概率分布为,p,1,=0.2,p,2,=0.3,p,3,=0.5,失真函数矩阵为,求,:,D,max,D,min,R(D,max,),R(D,min,),练习题,R(D,max,)=0,R(D,min,)=R(0)=,H,max,(x,)=0.2log0.2+0.3log0.3+0.5log0.5,p,1,=0.2,p,2,=0.3,p,3,=0.5,在给定的失真函数矩阵中,对每一个,x,i,找一个最小的,d,ij,然后求,上次课内容,复习,4.1,基本概念,4.1.1,失真函数（失真度）,4.1.2,平均失真度,4.1.3,信息率失真函数,4.1.4,信息率失真函数的性质,复习,有失真,失真度,D,能否等于零,与给定的单个符号失真函数,d,ij,有关,d,ij,每一行至少有一个零,才能有,Dmin,=0,当,D,min,=0,时表示不允许有任何失真,.,D,min,=0,无失真,R(D,max,)=0 R(0)=,H(x,),无失真,信息率失真函数的值域,0R(D)H(X),相当于在失真矩阵的每一行找出一个最小的,d,ij,所有这些不同最小值取数学期望,这就是信源最小平均值,.,4.1.4,信息率失真函数的性质,例,:,令,X=0,1,设失真矩阵为,对于一个等概分布的随机变量,求,对应的定义域,(,D,min,D,max,),解,:,定义域,(1.5,2),复习,本次课内容,4.2,离散信源,R(D),的计算,第,4,章 信源编码,4.1,数据压缩概述,4.2,无失真信源编码的基本原理,4.2.1,信源编码器,4.2.2,码的类型,4.2,离散信源,R(D),的计算,已知信源的概率分布,P(a),和失真函数,d(a,b),，离散信源的,R(D),函数是选取试验信道 满足,的约束条件下，求平均互信息,的极小值。,4.2,离散信源,R(D),的计算,引入待定参量,S,和,i,，在失真不超过,D,时，使平均互信息达到极小值的试验信道的传递概率密度函数必满足,S,为拉格朗日乘子,4.2,离散信源,R(D),的计算,这时，,R(D),函数和失真函数,D,的参量方程为,参量,S,是信息率失真函数,R(D),的斜率，即,4.2,离散信源,R(D),的计算,因信息率失真函数,R(D),是,D,的单调递减函数且是,U,型凸函数，所以,R(D),的斜率,S,0,，,S,随,D,的增加递增，即。,当,D,由,D,min,增大,D,max,到时,S,的数值随之由,S,min,=-,增至,S,max,=0,当,D,D,max,，,R(D)=0,。因此在一般情况下，在,D=,D,max,处，参量,S,将从一个很小的负值跳跃到零，,S,在这一点不连续，而在开区间,(0,D,max,),内，,S,是失真度,D,的连续函数。,4.2,离散信源,R(D),的计算,4.2,离散信源,R(D),的计算,离散信源函数,R(D),求解步骤,（,4.2-1,）,（,4.2-2,）,（,4.2-3,）4.2-4,）,1.,根据（,4.2-1,）求,i,，,i=1,2,3,.r,；,2.,根据（,4.2-2,）求，,q,j,；,j=1,2,3,s,4.,根据（,4.2-3,）求,D(S),；,4.,根据（,4.2-4,）求,R(S),。,4.2,离散信源,R(D),的计算,某些特殊情况下,R(D),的表示式为：,4.2,离散信源,R(D),的计算,平方误差失真函数,绝对失真函数,误码失真：,上述信息率失真函数的三条曲线如图,最大失真率,D,max,均对应,R(D),随着的减小,R(D),单调增加,当等于零时,(,)(,)R(D),趋于无穷，将无法进行无损编码,对于离散信源,(3),时,),(,).,4.2,离散信源,R(D),的计算,其中,失真函数定义为,【,例,4.2-1】,二进制对称信源,设信源输入符号集为,(0,1),其概率分布,设输入符号集为,(0,1),，,求信源失真函数,R(D).,4.2,离散信源,R(D),的计算,P,1,=P(0)=P,P,2,=P(1)=1-P,q,1,=P(y,1,),q,2,=P(y,2,),(1),由上面第一个公式计算,解：引入记号：,解方程得,:,代入,4.2,离散信源,R(D),的计算,(2),由计算公式,计算,q,1,q,2,已知,P,1,=P(0)=P,P,2,=P(1)=1-P,已知,:q,1,=P(y,1,),q,2,=P(y,2,),4.2,离散信源,R(D),的计算,解方程且,i=j,时，,d,ij,=0,则,4.2,离散信源,R(D),的计算,（,3,）,将求出的 代入公式,得,:,4.2,离散信源,R(D),的计算,求,s,得,:,由式,4.2,离散信源,R(D),的计算,取 的曲线，通过曲线可知，对于给定的平均失真度,D,，信源分布越均匀,(p,接近,0.5),，信源的冗余度越小，,R(D),就越大，信源压缩的可能性就越小。反之，如果过信源分布越不均匀，信源的冗余度越大，,R(D),就,越大，信源压缩的可能性就越大。,4.2,离散信源,R(D),的计算,机械 爊棅曓,