压缩理论极限与基本途径6

第三章

理论极限与基本途径

课前回顾很多信源，如语音、图像等，一般都是非平稳的。如何计算各阶熵？在一段时间内作为平稳信源对待，

即将非平稳信源S看成多个平稳子

信源Si

(i=1,2,…,L)构成的组合信源。组合信源的熵HC与复合信源熵HM

的关系HC≤HM3.4率失真理论限失真编码（失真不超过某给定条件下的编码）率失真理论研究的问题：最佳编码：使限失真条件下比特数最少的编码

1959年，Shannon又进一步确立了率失真理论，

从而奠定了信源编码的理论基础；

1948年，Shannon在“通信的数学原理”中首次提到信息率—失真函数的概念；

T.Berger等人接着进行了深入的研究。

率失真函数的基本含义信源编码的过程：输入符号集：Am={a1,a2,…,am}输出符号集：Bn={b1,b2,…,bn}编码器映射条件自信息量概念：I(aj|bk)

和I(bk|aj)例3-5设信源编码器是一个简单的一一对应的关系，即m=n，且：aj=bj，j=1,2,3,…,m用概率表示：P(ak|bk)=1或P(bj|aj)=1I(ak|bk)=0或I(bj|aj)=0也就是说：此时：bj提供了aj

全部信息，或者说解除了aj的全部不确定性。I(aj;bk)=I(aj)回顾：自信息量与条件自信息量之差，即互信息量。信息保持编码aj

：12345678bj：000001010011100101110111aj

：1,23,45,67,8bj：00011011当允许存在一定误差,假设一个实际信源,有8不同消息,但却发现1,2;3,4;5,6;7,8两两相差不多，可用同一码字代表:3bit编码2bit编码误差的产生是由于对信源的某些符号进行了合并,减少了事件的数目,从而使新信源的熵降低。当集合中事件结构发生变化时，就会引起信源概率结构的变化，从而影响信源概率的变化。只要允许误差（量化）的存在，就可以减少编码输出的字符数，因而也就可以降低码率。在给定的失真条件下，最起码需要多大的码率，才能保证不超过允许的失真。讨论：率失真函数的基本含义：在一定的失真条件下，要找出平均互信息量，即：的最小值

minI(X;Y)。X表示信源的随机变量集合，I(X)表示信源信息;

Y表示编码符号的随机变量集合，I(Y)表示编码输出信息。回顾文氏图，互信息表示X和Y的相交的部分。平均互信息量的公式可写为：或者：(3.4-1)(3.4-2)因此,可知平均互信息量由下面几个方面决定：

信源符号概率P(aj)

编码输出符号概率Q(bk)

已知信源符号出现的条件概率Q(bk|aj)在确定信源条件下,P(aj)已确定,所谓选择编码方法,就是通过改变条件概率Q(bk|aj)的分布来控制平均信息量。

离散信源的率失真函数对失真的度量：具有随意性，对不同信源及不同场合,可引入不同的失真度量。常用的有：图像、语音编码中：

常常希望用人的视觉、听觉特性来加权。均方差:

信源发出aj

，被编码成bk

，其误差平方为(aj-bk)2;

00b2b1a2a1d2d1(a)(b)图3.4

失真测量流图与矩阵对离散信源：常用失真测量流图或矩阵作为失真的度量以d(aj,bk)代表失真度量,则平均失真(失真函数)：(3.4-3)若要求平均失真D(Q)≤D，则必存在这样一个条件概率Q(bk|aj)，使D(Q)不超过D，记：QD=Q(D(Q)≤D

)(3.4-4)为保证失真在允许范围D内的条件概率的集合。两个样本之间的距离（误差）率失真函数R(D)(亦称码率-失真函数)定义为:(3.4-5)率失真函数是在允许失真为D的条件下,信源编码给出的平均互信息量的下界,也就是数据压缩的极限数码率(基本极限)。在Q(D)范围内寻找最起码的平均互信息量:定理3.3(有失真时的信源编码逆定理):当数码率R小于率失真函数R(D)时,无论采用什么编译码方式,其平均失真必大于D。R(D)函数对于信源编码具有指导意义，但计算一个具体信源的R(D)函数很困难：

信源符号的概率分布很难确知；

式(3.4-5)的求解也相当复杂。信源编码:就是通过对Q(bk)的设计与实现,使数码率接近R(D)。实际中的一些编码方法却不直接去涉及Q(bk)，而是从最后的数码率与R(D)函数进行比较。率失真函数的性质：①在D<0时，R(D)无定义;②

存在一个Dmax，使D>Dmax

时，R(D)=0;该Dmax应为所有满足R(D)=0的D中的最小值，(3.4-6)R(D)DmaxD0H(X)图3.5离散信源的率失真曲线即对几个bk，择其dk(k=1,2,…,n)最小者为