信息论与编码第5章限失真信源编码.ppt

第五章 保真度准则下的信源编码,前 言第一节 失真度和平均失真度第二节 信息率失真函数第三节 信息率失真函数的性质第四节 二元信源和离散对称信源的R(D)函数第五节 保真度准则下的信源编码定理第六节 标量量化编码第七节 矢量量化编码,前 言,无失真离散信源编码定理:无论是无噪信道还是有噪信道,信息传输率小于信道容量,总能以任意接近信道容量的传输率来传送信息;但若信息传输率大于信道容量,就不可能实现无失真传输.,前 言,无失真传输存在的问题:实际信源的输出常常是连续的,如语言、图像等.因为连续信源的绝对熵为无限大,若要无失真地传送连续信源,则信息传输率也必须无限大。信道带宽是有限的,即信道容量是受限的.为此实际通信中信息传输率总是远大于信道容量的,因此不可能实现完全无失真地传输信源信息。,前 言,失真传输的必要性:无失真信源编码定理:描述信源所需的最少比特数是信源的熵值.那么连续信源需要用无穷多个比特数才能无失真地描述,这是绝对不可能的.若用有限的比特数来描述连续的消息就会带来失真.,前 言,失真传输的必要性:数字系统需要传送、存储和处理大量的数据.如实际数字通信系统中,普通电话的数码率为64 kb/s;可视电话的数码率为8.448 Mb/s;黑白电视的数码率为60 Mb/s等.传输信号质量要求越高,数码率也越高.数码率高,不仅对传输不利,而且也增加了存储和处理的困难.为了提高传输和存储的效率,就必须对有待传送和存储的数据进行压缩,这样也会损失一定的信息,带来失真.,前 言,失真传输的可能性:实际生活中信宿一般并不要求完全无失真地恢复消息.通常总是要求在保证一定质量(一定保真度)的条件下近似地再现原来的消息,也就是允许有一定的错误(失真)存在.例如:传送语音时,由于人耳接受带宽和分辨率有限,可把频谱范围从20 Hz8 kHz的语音信号去掉低端和高端的频率,看成带宽只有300 Hz3.4 kHz的信号.这样,即使传输的语音信号会有一些失真,人耳还是可以分辨或感觉出原来的语音,满足语音信号传输的要求,所以这种失真是允许的.,前 言,失真传输的可能性:传送图像时,也并不是需要全部精确地把图像传送到观察者.只需将电视信号每一像素的黑白灰度级分成256级,屏幕上的画面就已足够清晰悦目.对于静止图像或活动图像,从空间频域来看,每一帧一般只含有大量的低频域分量,高频域分量很少.若将高频分量丢弃,只传输或存储低频分量,数据率便大大减少,而图像质量仍能令人满意.这是因为人眼有一定的主观视觉特征,允许传送图像时有一定的误差存在.,前 言,失真传输的研究方向:在允许一定程度失真的条件下,能把信源信息压缩到什么程度,即最少需要多少比特数才能描述信源;也就是说,在允许一定程度失真的条件下,如何能快速地传输信息,这是本章要讨论的问题。,前 言,这个问题在香农1948年最初发表的经典论文中已经有所体现,但直到1959年香农又发表了“保真度准则下的离散信源编码定理”这篇重要文章之后,它才引起了人们的注意.定理指出:在允许一定失真度D的情况下,信源输出信息传输率可压缩到R(D)值,这就从理论上给出了信息传输率与允许失真之间的关系,奠定了信息率失真理论的基础.,前 言,那么在允许一定程度失真的条件下,能够把信源信息压缩到什么程度,也就是,允许一定程度失真的条件下,如何能快速的传输信息,这就是本章所要讨论的问题.本章所讨论的内容是量化、数模转换、频带压缩和数据压缩的理论基础.,前 言,本章主要介绍信息率失真理论的基本内容,侧重讨论离散无记忆信源.首先给出信源的失真度和信息率失真函数的定义与性质,然后讨论离散信源的信息率失真函数计算.在这个基础上论述保真度准则下的信源编码定理.,1、失真度,信源,信源编码,信道编码,信道,信道译码,信源译码,信宿,干扰,失真范围:由于只涉及信源编码问题,所以可以将信道编码和信道译码看成是信道的一部分.这样信宿收到消息的失真(或误差)只是由信源编码带来的.,第一节 失真测度,广义无扰信道,第一节 失真测度,试验信道:由于是失真编码,所以信道不是一一对应的,可用信道传递概率描述编、译码前后关系,这样通信系统可简化为下图所示.,第一节 失真测度,失真大小与信息传输率的关系:从直观感觉可知,若允许失真越大,信息传输率可越小;若允许失真越小,信息传输率需越大.所以信息传输率与信源编码所引起的失真(或误差)是有关的.现在要研究在给定允许失真的条件下,是否可以设计一种信源编码使信息传输率为最低.为此,我们首先讨论失真的测度.,第一节 失真测度,设信源变量为U=u1,ur,接收端变量为V=v1,vs,对于每一对(u,v),指定一个非负函数d(ui,vj)0称为单个符号的失真度(或称失真函数).失真函数用来表征信源发出符号ui,而接收端再现成符号vj所引起的误差或失真.d越小表示失真越小,等于0表示没有失真.,第一节 失真测度,可以将所有的失真函数排列成矩阵的形式:,我们称它为失真矩阵D(rs).,第一节 失真测度,失真函数可有多种形式,但应尽可能符合信宿的主观特性,即主观的失真感觉应与失真函数d(ui,vj)的值相对应.d越大,所感觉到的失真也越大,最好成正比;当ui=vj时,d应等于零,表示没有失真;当uivj时,d应为正值.,第一节 失真测度,常用失真函数的类型:1）平方失真:d(x,y)=(x-y)22）绝对失真:d(x,y)=|x-y|3）相对失真:d(x,y)=|x-y|/|x|4）误码失真:d(x,y)=(x,y)式中:x信源输出消息;y信宿收到消息.,第一节 失真测度,常用失真函数的特点:平方失真和绝对失真只与(x-y)有关,而不是分别与x及y有关,数学处理方便;相对失真与主观特性比较匹配,因为主观感觉往往与客观量的对数成正比，但其数学处理困难得多.前三种失真函数适用于连续信源,最后一种失真函数适用于离散信源.,第一节 失真测度？,下面给出三个典型例子说明失真函数及其相应的失真矩阵。例1:离散对称信源(r=s).信源变量U=u1,ur,接收变量V=v1,vs.定义单个符号失真度,失真矩阵为：,发送符号为ui,再现的接收符号为vj(ij)所引起的失真d(ui,vj)(uivj)都相同,为一常数,常数为1时,则称汉明失真.,在二元情况下：,第一节 失真测度,例2:删除信源.信源变量U=u1,ur,接收变量V=v1,vs.其中,s=r+1.定义单个符号失真度如下:,其中,接收符号vs作为一个删除符号.在这种情况下,意味着若把信源符号再现为删除符号vs时,其失真程度要比再现成为其他错误接收符号的失真程度少一半.对于二元删除信源r=2,s=3,第一节 失真测度,例3:对称信源r=s,定义失真度为：,这里信源符号代表信源输出的幅值,以方差表示失真度.它意味着幅度差值大的要比幅度差值小引起的失真更为严重,其程度用平方表示.可用语音音量大小或图像灰度高低来理解.当r=s=3时,U=0,1,2,V=0,1,2.,失真矩阵为:,第一节 失真测度,以上所举的三个例子说明了具体失真度的定义.一般情况下根据实际信源的失真,可以定义不同的失真和误差的度量.另外还可按照其他标准,如引起的损失、风险、主观感受上的差别大小等来定义失真度d(ui,vj).从实用意义上说,研究符号实际信源主观要求的、合理的失真函数是很重要的.,第一节 失真测度,2、平均失真度:传输一个符号引起的平均失真,若已知试验信道的传递概率p(vj|ui),则平均失真度为:,第一节 失真测度,单个符号的失真度d(ui,vj)描述了某个信源符号通过传输后失真的大小.对于不同的信源符号和接收符号,其值不同.平均失真度 对信源p(u)和信道p(v|u)进行了统计平均,是描述某一信源在某一广义无扰信道(或试验信道)传输下的失真大小,是从总体上(统计上)描述整个系统失真情况的.,第一节 失真测度,保真度准则:平均失真度 不大于我们所允许的失真D,即 当信源p(u)和失真度d(ui,vj)给定,选择不同的信道(相当于选择不同编码方法),所得平均失真度不同.D失真许可试验信道:满足保真度的试验信道.把所有D失真许可试验信道组成一个集合BD,即,第二节 信息率失真函数,在信源和失真函数给定以后,总希望在满足一定失真下,使信息传输率R尽可能地小.或者说,在满足保真度准则下,寻找信源必须传输给信宿的信息率R的下限值,这个下限值与D有关.,第二节 信息率失真函数,从接收端来看,就是在满足保真度准则下,寻找再现信源消息所必须获得的最低平均信息量.接收端获得的平均信息量可用平均互信息量I(U;V)表示;这就变成了在满足保真度准则的条件下,寻找平均互信息量I(U;V)的最小值.因为BD是所有满足保真度准则的试验信道集合,即可以在D失真许可的试验信道集合BD中寻找某一个信道p(vj|ui),使I(U;V)取最小值.,第二节 信息率失真函数,由于平均互信息量I(U;V)是p(vj|ui)的U型凸函数,所以在BD集合中,I(U;V)的极小值存在.这个最小值就是在 的条件下,信源必须传输的最小平均信息量.即,第二节 信息率失真函数,应该指出,研究R(D)时,条件概率p(v|u)并没有实际信道的含义.只是为了求互信息的最小值而引用的、假想的可变试验信道.实际上这些信道反映的仅是不同的有失真信源编码或信源压缩.所以改变试验信道求平均互信息最小值,实质上是选择编码方式使信息传输率为最小.,率失真理论与信息传输理论的对偶关系,平均互信息I(U;V)是信源分布p(u)的型凸函数;I(U;V)又是信道特性p(v|u)的U型凸函数;因此,信道容量C和信息率失真函数R(D)具有对偶性.见下图,率失真理论与信息传输理论的对偶关系,第三节 信息率失真函数的性质,D是允许的失真度;R(D)是对应于D的一个确定的信息传输率;对于不同D,R(D)就不同,所以它是允许失真度的函数.下面讨论函数R(D)的一些基本性质.,第三节 信息率失真函数的性质,1)R(D)的定义域是(Dmin=0,Dmax)(1)Dmin和R(Dmin)根据定义,平均失真度 是非负实函数d(ui,vj)的数学期望,因此平均失真度 也是一个非负的实数,所以 的下限必须是零.那么,允许失真度D的下限也必然是零,这就是不允许任何失真的情况.,第三节 信息率失真函数的性质,一般,当给定信源u,p(u),及给定失真度矩阵D,信源的最小平均失真度为:其中,第三节 信息率失真函数的性质,允许失真度D是否能够达到零,这与单个符号的失真函数有关.只有当失真矩阵D中每行至少有一个零元素时,信源的平均失真度 才能够达到零值.否则,信源的最小平均失真不等于零值.假设Dmin=0可不失其普遍性.在实际情况中,一般Dmin=0.另外,假如Dmin0时,可以适当改变单个符号的失真度,令,使Dmin=0.而对信息率失真函数来说,它只是起了坐标平移作用.,第三节 信息率失真函数的性质,当Dmin=0时,表示信源不允许任何失真存在.一般直观地理解就是,若信源要求无失真地传输,则信息传输率至少应等于信源输出的信息量信息熵,即R(Dmin)=R(0)=H(U).上式能否成立与失真矩阵形式有关,只有当失真矩阵中每行至少有一个零时,并且每一列最多只有一个零时,等式成立.否则,R(0)小于H(U),它表示这时信源符号集中有些符号可以压缩、合并,而不带来任何失真.,第三节 信息率失真函数的性质,例4 删除信源U0,1,V0,1,2,而失真矩阵D 最小允许失真度为满足最小允许失真度的试验信道是无噪无损,信道转移矩阵P若允许失真度D=Dmin=0,则BD中只有这个信道是唯一可取试验信道,即无失真一一对应编码.那么,第三节 信息率失真函数的性质,例5 设信源U0,1,2且等概率分布,信宿V0,1.失真矩阵D为Dmin=1/3*0+1/3*1/2+1/3*0=1/6使平均失真度达到最小值(D=1/6)的信道必须满足第二个条件限制的p(v1|u2)和p(v2|u2)可有无穷多个,其最小平均失真度都是1/6,即(BD)min集合中试验信道有无数个.其共同特征是信道矩阵中每列有不止一个非零元素,所以其信道疑义度H(U|V)0，则,第三节 信息率失真函数的性质？,(2)Dmax和R(Dmax)平均失真度也有一上界值Dmax.根据R(D)的定义知,R(D)随 D 增加而递减的函数.R(D)是在一定的约束条件下平均互信息I(U;V)的极小值.I(U;V)是非负的,其下限值为零.R(D)也是非负的,下限值也为零.因此,当R(D)等于零时,所对应的平均失真度的下界就是上界值Dmax,如右图所示.,第三节 信息率失真函数的性质,求上界值Dmax:允许失真D越大,信息传输率R(D)越小,最小为0;当D再大时,由于R(D)是非负的,也只能为0.即I(U;V)=0.此时,信源与接收符号已经统计独立,即:p(v|u)=q(v)失真度函数变为：,第三节 信息率失真函数的性质,所以,Dmax就是在R(D)=0的情况下,求 的最小值,当DDmax,R(D)=0;当DminR(D)0,这就是求Ed(v)的最小值.可以这样选q(v),当d(v)最小时,取q(v)等于1,其它为零,则:,第三节 信息率失真函数的性质,2)、R(D)是允许失真度D的U型凸函数;3)、R(D)函数的单调递减性和连续性.,0,D,R(D),R(D)的非增性是很容易理解的.因为允许的失真越大,所要求的信息传输速率可以越小.,第四节 二元信源和离散对称信源的R(D)函数,1、二元对称信源的R(D)函数设二元信源U=0,1,其分布概率p(0)=,p(1)=1-,0.5.接收变量V=0,1,设汉明失真矩阵D为:因而最小失真度Dmin=0,并能找到满足该最小失真的试验信道,且是一个无噪无损信道,其信道矩阵为:,第四节 二元信源和离散对称信源的R(D)函数,要达到最大允许失真的试验信道,唯一确定为,即这个试验信道无论传输信源信号是u=1,还是u=0,接收符号一定为v=1.也就是说接收符号与发送的信源符号无关.此时,可计算得信息传输率得,q(v)选取:当d(v)最小时,取q(v)等于1,其它为零,第四节 二元信源和离散对称信源的R(D)函数,其中,PE是信道传输的平均错误概率.这说明在汉明失真的情况下,平均失真度等于平均错误概率.可以计算得:二元信源得信息率失真函数为,一般情况下,当0DDmax=时,第四节 二元信源和离散对称信源的R(D)函数,综上所述,在汉明失真测度下,二元对称信源的信息率失真函数,第四节 二元信源和离散对称信源的R(D)函数,例:=0.4,D=0.2,结论:对同一D,信源分布越均匀,R(D)越大,信源压缩的可能性越小.反之,信源分布越不均匀(剩余度越大),R(D)越小,压缩可能性越大.,第四节 二元信源和离散对称信源的R(D)函数,对于离散对称信源,在汉明失真条件下:,由该式可知:对于同一失真度D,r越大,R(D)越大,信源压缩性越小.若把r的取值看成信源分成后的符号数,即r越大就表示信源分层数越多.那么,在满足相同的允许失真要求下,分层越多,信源的可压缩性就越小.反之越大.这个规律对于实际信源的量化分层、数据压缩是有深刻的指导意义的.,第五节 保真度准则下的信源编码定理,定理7.1 保真度准则下的信源编码定理设R(D)为离散无记忆信源的信息率失真函数,并且有有限的失真测度.对于D0,0,以及任意足够长的码长k,则一定存在一种信源编码C,其码字个数为M=ekR(D)+而编码后的平均失真度为 d(C)D+.如果用二元编码,R(D)取比特为单位,则M可写成:M=2kR(D)+,第五节 保真度准则下的信源编码定理,该定理又称为香农第三定理.它告诉我们,对于任何失真度D0,只要码长k足够长,总可以找到一种编码C,使编码后的每个信源符号的信息传输率 而码的平均失真度d(C)D.,第五节 保真度准则下的信源编码定理,定理7.2(信源编码逆定理)不存在平均失真度为D,而平均信息传输率RD.逆定理告诉我们:如果编码后平均每个信源符号的信息传输率R小于信息率失真函数R(D),就不能在保真度准则下再现信源的消息.,第五节 保真度准则下的信源编码定理,意义:这两个定理证实了允许失真D确定后,总存在一种编码方法,使编码的信息传输率R大于R(D)且可任意接近于R(D),而平均失真度小于允许失真D.反之,若RR(D),编码的平均失真度将大于D.如果用二元码符号编码,允许一定失真D,平均每个信源符号所需二元码符号的下限值为R(D).,第五节 保真度准则下的信源编码定理,比较香农第一和第三定理可知,当信源给定后,无失真信源压缩的极限值是信源熵H(S);有失真信源压缩的极限值是信息率失真函数R(D).在给定D后,一般有R(D)H(S).,第六节 有失真信源编码定理的实用意义,香农第三定理是一个存在定理,至于如何寻找这种最佳压缩编码方法并没有给出.在实际应用中,存在以下两方面问题:1、符合实际信源的R(D)函数的计算相当困难.1)需要对实际信源的统计特性有确切的数学描述;2)需要对符合主客观实际的失真给予正确的度量.2、即使求得了符合实际的信息率失真函数R(D),还需要研究采取何种最佳编码方法才能达到极限值R(D).目前,这两方面工作都有进展.,第六节 标量量化编码,连续信源限失真编码的主要方法是量化;量化(也称数字化):把连续的样值离散化为某些量化级数;量化后的信号也可称为数字信号,这种转换必将引入失真,量化时必须使这些失真最小.常用的量化方法:标量量化、矢量量化.标量量化:每次只量化一个模拟样本值,故又叫做零记忆量化.均匀量化最优量化,第六节 标量量化编码,均匀量化:将区间a0,an分割为n个相等距离且互不重叠的子区间ai,ai+1,取每个小区间的中点值作为量化值yi,即aixai+1时,yi=(ai+1+ai)/2;,第六节 标量量化编码,量化误差:e=x-Q(x)=x-yi 量化器均方误差:量化器输入方差:量化器的信噪比:量化区的工作区间:正常量化区:xa0,an限幅区:xana0+/2或an-/2,失真较大.空载区:-/2x-ai/2,第六节 标量量化编码,量化器设计准则:将样本值量化总要带来误差,因此,设计量化器时,总希望其误差越小越好,即寻求最优量化误差.最优量化:使量化器的均方误差最小的量化.可见ai的最佳位置是输出yi-1和yi的中点,yi最佳位置在ai和ai+1区间的概率中心.,第六节 标量量化编码,一般情况下,ai和yi是互相制约、相互依赖的,不容易求出解析解,所以只能用递推公式获得近似解.Max-Livod采用的迭代方法如下:(1)根据a0,任取y0;(2)计算a1;(3)计算y1;(4)重复步骤(2)、(3),分别计算出a2,y2,a3,y3,直至最后求得yn-1;(5)检验yn是否为an-1,an的概率中心,即式是否成立,或在允许的一定误差范围内成立;(6)若步骤(5)满足,过程结束;否则,重新选y0,重复上述操作步骤.,第七节 矢量量化编码,当把多个信源符号联合起来形成多维矢量,再对矢量进行标量量化时,自由度将更大,同样的失真下,量化级数可进一步减少,码率可进一步压缩.矢量量化编码:将一个K维欧氏空间的模拟连续量xRk变换(或映射)为另一个K维欧氏空间的一个有限子空间的整数据集集合yi=CRk.标量量化是指逐个样点量化,矢量量化则是将每K个信号样点分为一组的多维量化,即将K维欧氏空间中的一个信号矢量进行多维量化.若用QK表示K维矢量量化编码,则有:QK:RKyi,其中,yi=0,1,2M-1,矢量量化过程可以分解为编码与译码两个过程,如下图:压缩能力:总码字个数J一般远小于总的输入信号NK,压缩能力非常大。码书控制着矢量的大小:码书的码字越多,维数越大,失真就越小.因此,只要适当地选择码字数量,就能控制失真量不超过某一给定值.工作量大:矢量量化时每输入一个Xj，都要和J个码字Yi逐一比较，搜索与其最接近的码字Yi.由于两者均为K维矢量,所以工作量很大.容易处理:矢量量化是定长码.,