打开主菜单

求真百科

率失真理论

率失真理论

来自 人人文库 的图片

中文名:率失真理论

外文名:Rate distortion theory

定 义:码率下能达到最小期望失真

类 型:理论

应用学科:通信(信息论)

率失真理论是用信息论的基本观点和方法研究数据压缩问题的理论,又称限失真信源编码理论

率失真理论的基本问题可以归结如下:对于一个给定的信源分布失真度量,在特定的码率下能达到的最小期望失真;或者为了满足一定的失真限制,最小描述码率可以是多少。[1]

目录

起源

率失真理论的名称来源于信息速率失真函数,率失真理论包含两个中心内容:一是率失真函数失真率函数,二是限失真编码定理。这就是针对不同的信源、不同的失真量度和不同信源概率分布计算率失真函数和证明相应的限失真编码定理。

量度

率失真理论涉及三个基本概念:信源编码失真量度

失真量度是这一理论特有的。它是对编译码器输入x和输出y之间的失真所给予的量度,即d(x,y)。数学上,任何范数或距离(度量)都可作为失真量度。但在具体选择时要考虑到物理上或主观上应有意义,且数学上易处理和计算方便。

已有的失真量度按量度的性质可分为范数失真量度拟范数失真量度,按高阶失真量度与一阶失真量度的关系又可分为可加性量度非可加性量度

现在常用的是差值失真量度汉明失真量度。均方误差失真量度,即d(x,y)=(x-y)2,既属于范数失真量度,也属于距离失真量度,又是一种差值失真量度,不仅有明确的物理意义,而且数学上也易于处理。

计算

率失真函数和失真率函数(即率失真函数的反函数)是通过互信息的概念加以定义的。

将编译码器看成是一种信道,称为试验信道有条件概率P(y|x)。这一信道的输入x和输出y分别对应编码的输入和译码的输出。试验信道输入输出间的互信息相当于信源通过编译码器给信宿的信息量。这样,率失真函数R(D)被定义为试验信道输入输出间的平均失真量度,失真量度不超过D的条件下,试验信道输入输出间互信息量的最小值,即如 R(D)=min I(X;Y) P(y|x)

而D=Ed(x,y),失真率函数D(R)则相反,它是指互信息的值不超过R的条件下,失真度D可能达到的最小值。

这两个函数的计算在原则上都可以用拉格朗日乘子法或变分法来解决,但除了一些简单的情况,如独立二元信源,平稳高斯信源以外,一般很难得到解析解。R.E.勃拉赫特提出的迭代算法为获得数值解提供了一种通用的算法。

此外,在某些情况下利用求出上下界的办法对函数进行估计。

限失真编码定理

在最简单的离散、无记忆、平稳信源和分组编况下,设信源的率失真函数是R(D),当R>R(D)时,一定存在一种具体的编码方法,使其失真小于D+ε,其中ε是一个无穷小量。反之若R<R(D),则不论用什么编码方法,其失真必大于D;对一般遍历信源,平稳非遍历信源、渐近平稳非遍历信源等其它信源,以及移不变码(滑动分组码)等非分组码的情况下,也有类似的定理。

该定理的证明所使用的是随机编码的方法,虽然不能从中得到一种具体的编译码方法,但却证明了这样的好码必然存在。这样,信源编码定理就在数据压缩的具体编码方法和率失真函数之间建立起一种联系,对具体编码方法的研究起到了指导作用。

应用

率失真理论的主要应用有两种:

①数据压缩。为数据压缩的性能提供理论极限和比较标准,对具体编码方法的研究起方向指导作用;

②模式识别。统计模式识别数据压缩是两个具有交叉领域的学科。率失真理论在模式分类、特征选择等问题上有重要的应用。

率失真理论在应用中,也存在一些问题。例如:它解决得较好的信源是平稳遍历信源,而在实际中,信源经常是非平稳非遍历的;它解决得比较好的编码是分组码,但在实际应用中,非分组码相当普遍。同时,理论上要求对信源建立精确的模型,但实际上只能得到近似的模型;理论上假定已有正确的失真量度,但如何得到这量度尚无有效的办法。[2]

参考资料

  1. 率失真函数PPT课件,人人文库
  2. 06图像编码1,无忧文档