第5章 有失真信源编码

第５章 有失真信源编码（信息率失真函数）

离散信源有失真编码 连续信源有失真编码

5.1信息率－失真函数的概念

在第２章我们证明了当输入随机变量的概率分布确定时，互信道是条件转移概率的下凸函数，即互信息必存在一个最小值。然而，在没有其它约束条件的情况下，这个最小值就是零。因为一方面互信息总是非负的，另一方面，当输入和输出随机变量相互独立时互信息等于零。所以研究一般情况下互信息的极小值问题没有什么意义。 无失真信源编码时，信源的熵是信息率所能达到的下限。在很多实际情况下，要做到完全没有失真是没有必要的，特别是对连续信源编码，由于信源的绝对熵无穷大，要达到无失真编码是不可能的。为此，我们有必要研究在满足某种失真准则下互信息的极小值问题，即信息率－失真函数。 首先看离散信源的情况。

设Ｘ和Ｙ是定义在相同取值域A?B?{a1,a2,?,an}上的离散型随机变量。失真函数d(x,y) 是

定义在A?B上的非负函数

d(x,y)?d(X?x,Y?y),x?A,y?B

例如，可定义

?0,i?jd(i,j)?d(ai,aj)????,i?j

（５.１.１）

其物理意义是当输入和输出相等时没有失真，当输入和输出不相等时失真是相同的。显然失真函数d(x,y)是对Ｙ代表Ｘ所引起失真的量度。失真函数的定义由所研究的客观问题决定。（５.１.１）式的失真函数称为汉明失真准则。 失真函数只定义了若干具体失真的数值，为了反映随机变量之间的总体失真情况，我们定义平均失真

d?E?d(x,y)?

对离散型变量

（５.１.２）

d???p(i)p(j|i)d(i,j)ij

（５.１.３）

如果Ｘ和Ｙ都是Ｌ维随机矢量，可定义矢量间的失真为

1LdL(X,Y)??d(xl,yl)Ll?1

平均失真

（５.１.４）

1L1LdL?E?dL(X,Y)???E[d(xl,yl)]??dlLl?1Ll?1

其中dl是第l个分量的平均失真。

（５.１.５）

如果我们要求平均失真不大于某个定值Ｄ。令PD?p(j|i)|d?D表示所有满足平均失真不

??大于Ｄ的条件概率矩阵Ｐ的集合，我们定义

R(D)?minI(X,Y)P?PD （５.１.６）

为信息率－失真函数，或简称率失真函数。它表示在给定失真限度Ｄ条件下互信息的极小值。

在率失真函数的定义中涉及条件转移概率矩阵，似乎它也是表征率失真函数的参量，然而，率失真函数是表征信源的量，它只与信源和失真Ｄ有关，而与转移概率矩阵无关。如果把转移概率矩阵看成信道，我们把这些不同的信道称为试验信道，对不同的试验信道，失真和互信息是不同的，只有当试验信道使互信息达到最小时，这个最小值就是率失真函数的值。

为了理解率失真函数的实际意义，我们看如下有失真信源编码问题。

设有一个有2n个符号a1,a2,?,a2n的等概率信源，失真函数是

?0,i?j d(i,j)???1,i?j

当（５。１。２）式的汉明失真准则。可允许的平均失真Ｄ＝１／２。在无失真情况下，传送每个符号的信息率至少log2n。在有失真条件下我们采用下述编码方案：

?Y?ai,当X?ai,i?1,2,?,n ??Y?an,当X?ai,i?n,n?1,?,2n这时平均失真不大于１／２。编码后信息率

???11n?1?n?1R?H?,?,,log(n?1) ??log2n?2n2n2n2n????????n?1个?n?1log(n?1)，所付出的代价是容忍了１／２的平均失显然，Ｒ小于原来的log2n。信息率压缩了2n真。 现在的问题是，（１）在失真为１／２时，信息率能否更小，最小值是多少；（２）采用何种编码方式使信息率尽可能小。第一个问题是率失真函数的计算问题，实际上是有失真信源编码问题；第二个问题是怎样进行信源编码问题，即信源编码方法问题。实际上，信息率可以更小些，但编码方法要复杂得多。

5.2率失真函数的性质

5.2.1 Ｒ（Ｄ）函数的定义域

（１） 失真函数的下限

失真函数d(i,j)组成一个n?m失真矩阵

Dmin?min??p(i)p(j|i)d(i,j)

ij??p(i)min?p(j|i)d(i,j)

ij只要令对应于d(i,j)最小的p(j|i)=1，其它所有的都为零，可得

Dmin??p(i)mind(i,j)ij （５.２.１）

当且仅当失真矩阵中每行中至少有一个零时Dmin?0。通常情况下这是能够做到的。如果Dmin?0，只要改变单个符号的失真度，令d(j|i)?d(j|i)?mind(j|i)就可以保证失真矩阵每行至少有一

j'个零，使Dmin?0。对率失真函数来说，它只是起了坐标平衡的作用。所以假设Dmin?0并不失一般性。Ｄ＝０对应于无失真情况，这时应该有

R(0)?H(X)?H[p(i)]

但是上式成立是有条件的，它与失真矩阵的形式有关。

只有当失真矩阵中每行至少有一个零，并且每列最多只有一个零时，R(0)?H(X)。 否则Ｒ（０）小于Ｈ（Ｘ），这表示对信源符号集中有些符号进行压缩、合并，但没有引入失真（在具体的失真准则之下）。

（２） 失真函数的上限Dmax 定义域的上界定义为

Dmax?min?D|R(D)?0?p(j|i) （５.２.２）

必有R(Dmax)?0。由于

R(D)?0?I(X,Y)?0?X,Y相互独立?p(j|i)?q(j)

所以

Dmax?min??p(i)q(j)d(i,j)?min?q(j)?p(i)d(i,j)

q(j)ijq(j)ji令D(j)??p(i)d(i,j)，只要令对应于D(j)最小的q(j)等于1，那么

iDmax?min?p(i)d(i,j)ji

（５.２.３）

5.2.2 Ｒ（Ｄ）函数的下凸性

定理５.２.１ 率失真函数是定义域?Dmin,Dmax?上的下凸函数 证明

（１）Ｒ（Ｄ）函数的定义域是凸域。令

D??D1?(1??)D2,0???1,D1,D2??Dmin,Dmax?

由率失真函数的定义

R(D1)?minI[p(j|i)]?I?p1(j|i)?

p(j|i)?PD1其中p1(j|i)是使互信息达到极小值的信道转移概率，对应的平均失真d1[p1(j|i)]?D1。

R(D2)?minI[p(j|i)]?I?p2(j|i)?

p(j|i)?PD2其中p2(j|i)是使互信息达到极小值的信道转移概率，对应的平均失真d2[p2(j|i)]?D2。

作p(j|i)??p1(j|i)?(1??)p2(j|i)，对应的平均失真

d[p(j|i)]???p(i)p(j|i)d(i,j)

ij???p(i)[?p1(j|i)?(1??)p2(j|i)]d(i,j)ij????p(i)p1(j|i)d(i,j)?(1??)??p(i)p2(j|i)d(i,j)ijij

??d1[p1(j|i)]?(1??)d2[p2(j|i)]??D1?(1??)D2?D因此p(j|i)?PD，即定义域是凸的。

（２） Ｒ（Ｄ）函数的下凸性。由率函数的定义和互信息的下凸性

R(D)?I[p(j|i)]??I[p1(j|i)]?(1??)I[p2(j|i)]??R(D1)?(1??)R(D2)

证毕。

5.2.3 Ｒ（Ｄ）函数的单调递减性和连续性。

（１） Ｒ（Ｄ）函数的单调递减性

R(D)函数的递减性由定义直接得到，其单调递减性可以通过Ｒ（Ｄ）函数的下凸性来证明。 （２） Ｒ（Ｄ）函数的连续性

由互信息的连续性可以得到Ｒ（Ｄ）函数的连续性。

R(D)

H（X）

D Dmax

Ｒ（Ｄ）函数示意图

5.3 离散信源R(D)函数的计算

5.3.1 Ｒ(D)函数的参量表达式

Ｒ（Ｄ）函数的计算是目标函数

I(X,Y)???p(i)p(j|i)logijp(j|i)q(j)

（５.３.１）

在约束条件

??p(i)p(j|i)d(i,j)?Dij （５.３.２）

?p(j|i)?1,i?1,2,?,nj?1m

i （５.３.３）

下的极小值问题，其中q(j)?

?p(i)p(j|i)。

用拉格朗日乘子法，引入n+1常数个s 和?i,i?1,2,?,n，求如下目标函数的极值。

f[p(j|i)]?I[p(j|i)]?s??p(i)p(j|i)d(i,j)－??i?p(j|i) （５.３.４）

ijij令

?f[p(j|i)]?0

?p(j|i)得

?[1?lnq(j)]p(i)?[1?lnp(j|i)]p(i)?sp(i)d(i,j)??i?0

整理得

ln?p(j|i)?sd(i,j)?iq(j)p(i)

（５.３.５）

也就是

p(j|i)??iq(j)exp[sd(i,j)],i?1,2,?,n;j?1,2,?,m （５.３.６）

其中

?i?ln?ip(i)

（５.３.７）

（５．３．６）式是一个由nm个方程组成的方程组。两边对j求和得

?i?q(j)exp[sd(i,j)]?1,i?1,2,?,n

j

（５.３.８） （５.３.９）

?i?1,i?1,2,?,n

q(j)exp[sd(i,j)]?j（５．３．６）式两边乘以p(i)并对i求和得

q(j)?q(j)??ip(i)exp[sd(i,j)]i （５.３.１０）

即

本文来源：https://www.bwwdw.com/article/asmt.html