第5 章
信息率失真函数与限失真编码
现实中,有些时候不得不进行某些不可逆编码的处理,或者有时候没有必要要求编码
完全没有损失。例如,在实际的通信中,信息在信道的传输过程中总会受到噪声和干扰的
影响,一般不可能完全保持原样发送,而或多或少总会产生一些失真。此外,随着科学技
术的发展,数字系统的应用越来越广泛,这就需要传送、存储和处理大量数据。为了提高
传送和存储的效率,往往需要压缩数据,这样也会带来一定的信息损失。信道编码定理虽
然告诉我们有噪声信道的无失真编码似乎是可能的,但是这里的无失真只能是无限逼近
0,而无法达到0,除非编码分组的长度无穷大。因此从这个角度讲,有噪声信道的无失真
要求也是不可能达到的。而在实际生活中,人们一般并不要求完全无失真地恢复信息,通
常要求在保证一定质量(一定保证度)的条件下再现原来的消息,也就是说允许失真的存
在。例如,音频信号的带宽是20~20000Hz,但只要取其中一部分即可保留主要的信息;
在公用电话网中只选取带宽中的300~3400Hz即可使通话者较好地获取主要的信息;在
要求有现场感的语音传输中取50~7000Hz的频带即可较好地满足要求。还有诸如连续
信源、无理数这样的编码,在完全无失真的需求下,编码的长度将会是无穷大。
由此可见,不同的要求允许不同大小的失真存在,完全无失真的通信既不可能也无必
要,而有必要进行将失真控制在一定限度内的压缩编码,将其称为限失真编码。
信息率失真理论是进行量化、数模转换、频带压缩和数据压缩的理论基础。本章主要
介绍信息率失真理论的基本内容及相关的编码方法。
如何进行这种限失真编码呢? 考虑我们前面提出的问题,如果要将有10万位小数的
1~100的数字进行压缩,可以采取四舍五入的方法,将这个数转换为只有10位小数的数
值。由于小数点10位之后的数值都是微不足道的,所以这种压缩带来的失真并不大。可
以理解为将一个集合中的元素映射为另外一个集合中的压缩,或者是映射为原集合中的
一部分的元素。
5.1 失真测度
5.1.1 系统模型
通过前面的例子和讨论,可以建立研究限失真信源编码(有损压缩)的系统模型,如
图5-1所示。信源发出的消息X 通过有失真的信源编码输出为Y,由于是有失真的编
码,所以X 和Y 的元素之间不存在一一对应的关系,可以假设X 通过一个信道输出Y,
1 56 信息论与编码（第2 版）
这种假想的信道称为试验信道。这样,就可以通过研究信道的互信息来研究限失真编码,
而X 和Y 的关系也可以用转移概率矩阵(信道矩阵)来表示。
图5-1 限失真编码模型
除了描述输入输出的关系外,我们还关心如何才能限制失真的问题,因为这一切都是
建立在限失真的要求之上的。既然要限制失真,就需要有关于失真的度量。
5.1.2 失真度和平均失真度
如何来度量失真呢? 我们先从最简单的单个符号的信源的失真度量(distortion
measure)开始,然后以此为基础来建立更多符号的失真度量。
1.单个符号失真度
设有离散无记忆信源:
X
p(xi)
é
. êê
ù
. úú
=
x1 x2 … xn
p(x1) p(x2) … p(xn)
é
. êê
ù
. úú
信源符号通过信道传送到接收端Y:
Y
p(yj)
é
. êê
ù
. úú
=
y1 y2 … ym
p(y1) p(y2) … p(ym )
é
. êê
ù
. úú 信道的转移概率矩阵为:
[p(Y|X )]=
p(y1|x1) p(y2|x1) … p(ym |x1)
p(y1|x2) p(y2|x2) … p(ym |x2)
. . .
p(y1|xn) p(y2|xn) … p(ym |xn)
é
.
êêêêê
ù
.
úúúúú
对于每一对(xi,yj),指定一个非负的函数d(xi,yj)为单个符号的失真度或失真函
数(distortionfunction),用它来表示信源发出一个符号xi 并在接收端再现yj 所引起的
误差或失真。
失真函数是根据人们的实际需要以及失真引起的损失、风险和主观感觉上的差别大
小等因素人为规定的。有时候未必能够证明为什么采用这个函数是合理的,而其他的函
数没有它好。假设发出一个符号,如果收到的也是它,则失真为0;如果收到的不是它,而
是其他的符号,则存在失真。失真函数大于0,有:
d(xi,yj)= 0, xi =yj
α, xi ≠yj,α >0
注意:这里的xi=yj 从表面上看,两者的符号是相同的,xi、yj 的符号集也应该是
相同的。但是实际上没有必要要求符号相同,只需要符号代表的值相同就行了,比如圆周
率π经过定义可以代表3.1415926…。
失真度还可表示成矩阵的形式:
第5 章 信息率失真函数与限失真编码1 57
[D]=
d(x1,y1) d(x1,y2) … d(x1,ym )
d(x2,y1) d(x2,y2) … d(x2,ym )
. . .
d(xn ,y1) d(xn ,y2) … d(xn ,ym )
é
.
êêêêê
ù
.
úúúúú
(5-1)
[D]称为失真矩阵,它是n×m 阶矩阵。
常用的失真函数有以下4个。
(1)误码失真函数
d(xi,yj)=δ(xi,yj)= 0, xi =yj
a, 其他
这种失真函数表示:当i=j 时,X 与Y 的取值是一样的,用Y 来代表X 就没有误
差,所以定义失真度为0。当i≠j 时,用Y 代表X 就有误差,所有不同的i 和j 引起的误
差都一样,所以定义失真度为常数a。通常规定a=1,此时失真称为汉明失真,失真矩阵
为汉明失真矩阵,该矩阵的特点为主对角线上的元素全部为0,其他全为1。
D =
0 1 … 1
1 0 … 1
. . .
1 1 … 0
é
.
êêêêê
ù
.
úúúúú
r×r
(5-2)
(2)均方失真函数
d(xi,yj)=(xi -yj)2
这种失真函数称为平方误差失真函数,相应的失真矩阵称为平方误差失真矩阵。假
如信源符号代表信源输出信号的幅度值,则意味着较大的幅度失真要比较小的幅度失真
引起的错误更为严重,严重的程度用平方表示。
(3)绝对失真函数
d(xi,yj)= xi -yj
(4)相对失真函数
d(xi,yj)= xi -yj xi
上述4种失真函数的第一种适用于离散信源,后3种适用于连续信源。
2.序列失真度
许多情况下,需要处理的信源为一个序列,可以将序列的每一个符号对应的失真求和
进行平均。设x=(x1,x2,…,xN ),其中xi 取自符号集A ,而y=(y1,y2,…,yN ),yj 取
自符号集B,则序列的失真度定义为:
d(x,y)=ΣN
i=1
d(xi,yj) (5-3)
序列的单个符号的失真度定义为:
dN (x,y)=1 NΣN
i=1
d(xi,yj) (5-4)
在一些教材中,将序列的单个符号的失真度(求平均后的失真度)定义为序列的失真
度,而实际上以上两种失真度量各有其不同的应用场合和意义。
1 58 信息论与编码（第2 版）
这种定义必然合理吗? 从直观角度看,它们各自有什么样的适用场合?
3.平均失真度
失真度d(xi,yj)只能表示两个特定的具体符号xi 和yj 之间的失真,为了能在平均
意义上表示信道每传递一个符号所引起的失真大小,我们定义平均失真度为失真函数的
数学期望,即d(xi,yj)在随机变量X 和Y 的联合概率分布P(X ,Y)中的统计平均值。
..D =E[d(xi,yj)] (5-5)
由数学期望的定义可得:
..D =Σn
i=1Σm
j=1
p(xi,yj)d(xi,yj)
=Σn
i=1Σm
j=1
p(xi)p(yj|xj)d(xi,yj) (5-6)
对于连续随机信源,定义平均失真度为:
..D =∫∞
-∞∫∞
-∞
px,y (x,y)d(x,y)dxdy (5-7)
对于长度为L 的离散信源序列,平均失真度为:
..D (L)=ΣnL
i=1ΣmL
j=1
p(xi,yj)d(xi,yj)
=ΣnL
i=1ΣmL
j=1
p(xi)p(yj|xi)d(xi,yj) (5-8)
信源序列的单个符号的平均失真度(有时也称为信源的平均失真度)为:
..DL =1 LΣnL
i=1ΣmL
j=1
p(xi,yj)d(xi,yj)
=1 LΣnL
i=1ΣmL
j=1
p(xi)p(yj|xi)d(xi,yj) (5-9)
对于试验信道的信源和信道均无记忆的长度为L 的离散信源序列,单个符号的平均
失真度为:
DL =1 LΣL
l=1
E[d(xil ,yjl )]=1 LΣL
l=1
Dl (5-10)
以上小写的x 和y 均表示一个具体的值,而不是随机变量,d 代表针对具体符号的
失真度,而..D 则代表平均值。
如果信源和失真度一定,就只是信道统计特性的函数。信道传递概率不同,平均失真
度也随之改变。
如果规定其平均失真度..D 不能超过某一限定的值D ,即
..D ≤D (5-11)
则D 就是允许失真的上界。上式称为保真度准则(fidelitycriteria)。把保真度准则作为
对信道传递概率的约束,再求信道信息率R =I(X ;Y)的最小值就有实用意义了,即在可
以接受的失真范围内进行压缩。
159
第
5
章 信息率失真函数与限失真编码
5.信息率失真函数及其性质
2
要进行压缩,必须考虑信息压缩造成的失真是在一定的限度内的,因此这个编码长度
应该在允许的失真范围内尽量小。从直观感觉可知,若允许失真越大,信息传输率可以越
小;若允许失真越小,信息传输率需要越大。所以信息传输率与信源编码所引起的失真
(或误差)是有关的,对信息进行压缩的效果与失真也是相关的。
5.2.1
信息率失真函数的定义
在允许一定失真
D
的情况下,信源可以压缩的极限应该是一个与失真相关的函数,
可以定义信息率失真函数(n)为这一极限,简称率失真
函数,记为R(D)。
informationratedistortionfunctio
在给定信源的概率分布P(X)和失真度
D
以后,PD
是满足保真度准则
D
≤
D
的试
..
验信道集合,即如果把
X
和
Y
当作信道的输入输出的话,这个信道集合中的信道的决定
性参数就是信道传递(转移)概率p(yj|xi)。在给定信源和失真度以后,信道的输入和输
出的平均互信息I(X;是信道传递概率p(xi)的下凸函数,所以在这些满足保真度
Y) yj|
准则的PD
集合中一定可以找到某个试验信道,使信宿的信息量达到最小(可以证明为
I(
X
;而这个最小值可以从直观上理解为并且可以被证明为在保真度准则下的信源
Y)),
压缩极限,即信息率失真函数R(D), 所以:
R(D)mn I(Y)} 512)
=
i{X;(
P(yj|xi)∈PD
或者可以直接表述为:
R(D)=
P(yj|min
D
≤DI(X;
{Y)}
i):..
其中,R(D)的单位是奈特/信源符号或比特/(x) 信源符号。
上面定义的式子为限失真编码的压缩极限,可以利用渐进等分性来证明,本章后面部
分会给出证明。
信息率失真函数这一命名也体现了信息的压缩极限是与允许的失真
D
相对应的一
个函数,所以下面将会讨论这个函数的性质。
如果说试验信道的说法可能难以理解的话,可以将试验信道理解为限失真信源编码
器的输入
X
和输出
Y
之间的一种概率上的映射关系,或者直接理解为概率p(yj|xi)。
在离散无记忆平稳信源的情况下,可证得序列信源的信息率失真函数为:
RN
(D)=NR(D) (5-13)
从数学上来看,平均互信息I(Y) x)的∩型上凸函数,
X
;是输入信源的概率分布P(
而平均互信息I(
X
;是信道传递概率p(yj|的U型下凸函数。因此,可以认为信道
Y) xi)
容量
C
和信息率失真函数R(D)具有对偶性。
研究信道容量
C
是为了解决在已知信道中传送最大的信息量。充分利用给定的信
道,使传输的信息量最大而错误概率任意小,就是一般信道编码问题。研究信息率失真函
数是为了解决在已知信源和允许失真度
D
的条件下,使信源必须传送给用户的信息量最
160
信息论与编码（第
2
版）
小。这个问题就是在可以接受的失真度
D
的条件下,尽可能用最少的码符号来传送信源
消息,使信源的信息尽快地传送出去以提高通信的有效性。这是信源编码问题。
信息容量
C
和信息率失真函数R(D)之间的对应关系如表5-1所示。
表5-
1
信道容量
C
和信息率失真函数R(D)的比较
信道容量
C
信息率失真函数R(D)
研究对象信道信源
给定条件信道转移概率p(yj|xi) 信源分布p(x)
选择参数(变动参数)
结论
信源分布p(x)
求I(X;Y)最大值
试验信道转移概率或者信源编码器
的映射关系p(yj|xi)
求I(X;Y)最小值
概念上(反映) 固定信道,改变信源,使信息率最大(信
道传输能力)
固定信源,改变信道,使信息率最小
(信源可压缩程度)
通信上
在使得错误概率Pe→0 的限制下,使传
输信息量最大———信道编码
在给定
D
的限制下,用尽可能少的
码符号传送———信源编码
对应定理有噪信道编码定理限失真信源编码定理
5.2.2
信息率失真函数的性质
下面讨论函数R(D)的性质,作为一个函数,其函数值取决于自变量,所以首先讨论
关于它的自变量的取值范围,即定义域。
1.
信息率失真函数的定义域
..
个值不可以任意选取,这是因为平均失真度的值是受制约的,而且失真度与平均失真度均
为非负值,显然满足下式:
0≤Dmin≤
D
(5-14)
R(D)的自变量是允许平均失真度D,它是人们规定的平均失真度
D
的上限值。这
Dmi=Σ x)my
n x,(515)
np(id(y)
x
以上最小值的计算方法都是直接求各个失真度的最小值,然后按照概率加权平均,这
是否正确? 为什么?
(1)最小值。对于离散信源,在一般的情况下可以采用前面的定义,当
X
和
Y
一一对
应时,平均失真度为0,而平均失真度显然不可能小于0,所以Dmin为0,此时,R(Dmin)=
R(0)=
H
(X)。
对于连续信源,Dmin趋向于0时,R(Dmin)=R(0)=Hc(X)=∞ 。
连续信源无失真的时候,传输的信息量是无穷大,实际信道容量总是有限的,无失真
传送这种连续信息是不可能的。只有当允许失真(R(D)为有限值)时,传送才是可能的。
(2)最大值。信源最大平均失真度Dma:必需的信息率越小,容忍的失真就越大。
当R(D)等于0时,对应的平均失真最大, 是函数R(D)定义域的上界值Dmax最大。也就(x)
第
5
章 信息率失真函数与限失真编码
161
由于信息率失真函数是平均互信息量的极小值,平均互信息量大于或等于0,当R(D)=0
时,即平均互信息量的极小值等于0。满足信息率为0的
D
值可能存在多个,但是鉴于我
们总是希望失真度最小,存在多种选择时,总是选择最小值,所以这里定义当R(D)=0
时,
D
的最小值为R(D)定义域的上限,即Dmax是使R(D)=0的最小平均失真度。
R(D)=0时,
X
和
Y
相互独立,所以有:
) (2,…,
p(yj|xi)p(i=1,n)
满足
X
和
Y
相互独立的试验信道有许多,相应地可求出许多平均失真值,这类平均
失真值的下界就是Dmax。
=yj
n
=min p(xi)p()d(xi,)
Dmaxp(yj)ΣΣ(m) yjyji=1j=1
(5-16)
=min p((mn) p(xi)d(xi,)
p(yj)Σ yj)Σ yj
j=1i=1
令
Σ(n) p(xi)d(yj)
xi,=Dj
i=1
则
m
=min p()(5-17)
Dmaxp(yj)Σ yjDj
j=
上式是用不同的概率分布{p()} 对Dj 求(1) 数学期望,取数学期望中最小的一个作为
Dmax。实际上是用p(yj)对Dj
进行线性分配,并使线性分配的结果最小。
当p(xi)和失真矩阵已给定时,必可计算出Dj
。Dj
随
j
的变化而变化。p(yj)是任
选的,只需满足非负性和归一性。若Ds
是所有Dj
当中最小的一个,可取p(ys)=1,其
yj
他p()=0,此时Dj
的线性分配值(或数学期望)必然最小,即有:
)1,j=
s
p(
=
0,
j
≠
s
yj
yj
Dmax=minDj
(5-18)
j
通俗地说,在进行最大限度地压缩的时候,极端的情况就是将输出端符号压缩为一
个,可以将任意的信源符号xi
都转换为一个相同的符号ys,由于对方接收到的符号是确
定的,因此无须传递任何信息,或者说传递的信息量为0。对于不同的ys,会带来不同的
失真度,我们当然会选择失真度最小的一个。
以上定义体现了在两个目标下的一种理性选择,人们追求对信源的最大压缩,同时也
追求最小的失真度。当其中某个条件相同时,就会追求另外一个指标的最优化。比如信
息率失真函数定义为最小值就是在相同的失真(或允许失真)的情况下追求最大的压缩
(后面给出证明), 而最大失真度的定义其实是在最大压缩的情况下追求最小的失真度。
在限失真编码中,还有哪些需求或者目标?
实际上,不是有意去进行理性的选择,平均失真度的值是可以超过这一值的。
由于R(D)是非负函数,并且它是用从PD
中选出的p(x)求得的最小平均互信息
y|
1 62 信息论与编码（第2 版）
量,所以当D 增大时,PD 的范围增大,所求的最小值不大于范围扩大前的最小值,因此
R(D )为D 的非增函数。当D 增大时,R(D )可能减小,直至减小到R(D )=0,此时对应
着D max。当D >D max时,R(D )仍然为0。
可以得到下面的结论:
(1)当且仅当失真矩阵的每一行至少有一个零元素时,D min=0,一般情况下的失真
矩阵均满足此条件。
(2)可适当修改失真函数,使得min y
d(x,y)=0。
(3)D max和D min仅与p(x)和d(x,y)有关。
例5-1 设试验信道输入符号集{a1,a2,a3},各符号对应概率分别为1/3、1/3、1/3,
失真矩阵如下所示,求D max和D min以及相应的试验信道的转移概率矩阵。
(dij)=
1 2 3
2 1 3
3 2 1
é
.
êêêê
ù
.
úúúú
解:
D min =Σx
p(x)min y
d(x,y)
=p(a1)min(1,2,3)+p(a2)min(2,1,3)+p(a3)min(3,2,1)
=1
令对应最小失真度d(ai,bj)的p(bj|ai)=1,其他为0,可得对应D min的试验信道转
移概率矩阵为:
[p(y|x)]=
1 0 0
0 1 0
0 0 1
é
.
êêêê
ù
.
úúúú
D max =min y Σx
p(x)d(x,y)
=min{[p(a1)×1+p(a2)×2+p(a3)×3],
[p(a1)×2+p(a2)×1+p(a3)×2],[p(a1)×3+p(a2)×3+p(a3)×1]}
=5/3
上式中第二项最小,所以令p(b2)=1,p(b1)=p(b3)=0,可得对应D max的试验信道
转移概率矩阵为:
[p(y|x)]=
0 1 0
0 1 0
0 1 0
é
.
êêêê
ù
.
úúúú
本例给出的是一种特异的失真矩阵,在输入和输出符号数目相等的时候,这种失真矩
阵对应的输出符号是一种理性的选择吗?
例5-2 离散二元信源p(x)= 13
,23
é
. êê
ù
. úú
,[D]= 0 1
1 0
é
. êê
ù
. úú
,求D max。
第5 章 信息率失真函数与限失真编码1 63
解:
D1 =13
×0+23
×1=23
D2 =13
×1+23
×0=13
ü
t
y
..
..
D max =min 23
,13
.
è .
.
. ÷
=13
例5-3 二元信源为
x1 x2
0.4 0.6
é
. êê
ù
. úú
,相应的失真矩阵为
α 0
0 α
é
. êê
ù
. úú
,计算D max。
解:先计算Dj。由定义得D1=0.4α,D2=0.6α,所以D max=min(D1,D2)=0.4α。
2.R(D)是关于平均失真度D 的(下)凸函数
设D1 和D2 为任意两个平均失真,0≤α≤1,则有:
R[αD1 + (1-α)D2]≤αR(D1)+ (1-α)R(D2) (5-19)
证明:当信源分布给定后,R(D )可以视为试验信道转移概率p(y|x)的函数,即
R(D1)= min p(y|x)∈PD1
I[p(y|x)]=I[p1(y|x)]
R(D2)= min p(y|x)∈PD2
I[p(y|x)]=I[p2(y|x)]
且有:
Σx,y
p(x)p1(y|x)d(x,y)≤D1.p1(y|x)∈pD1
Σx,y
p(x)p2(y|x)d(x,y)≤D2.p2(y|x)∈pD2
令D0=αD1+(1-α)D2,p0(y|x)=αp1(y|x)+(1-α)p2(y|x),那么:
Σx,y
p(x)p0(y|x)d(x,y)=Σx,y
p(x)[αp1(y|x)+ (1-α)p2(y|x)]d(x,y)
≤αD1 + (1-α)D2 =D0
可知p0(y|x)满足保真度准则D0,即p0(y|x)∈PD0 。
R(D0)= min p(y|x)∈PD0
I[P(y|x)]≤I[p0(y|x)]
=I[αp1(y|x)+ (1-α)p2(y|x)]
≤αI[p1(y|x)+ (1-α)p2(y|x)]
=αR(D1)+ (1-α)R(D2)
上式利用了平均互信息量是条件概率的下凸函数的性质。
图5-2 R(D)函数的一般形式
3.R(D)是(Dmin,Dmax)区间的连续和严格的递减函数
证明:R(D )在定义域内为凸函数,从而保证了连续性。下面证明在定义域内也是非
增函数。由D1>D2 可得PD1 .PD2 ,在较大范围内
求得的极小值一定不大于在所含小范围内求的极小
值,所以R(D1)≤R(D2)。由于在定义域内R(D )不
是常数,而是非增的下凸函数,可以通过反证法证明
R(D )是严格递减函数。
R(D )的非增性也是容易理解的。因为允许的失
真越大,所要求的信息率可以越小。
图5-2为R(D )函数的一般形式,连续信源和离
1 64 信息论与编码（第2 版）
散信源的信息率失真函数有所不同,图中虚线代表连续信源,实线代表离散信源。
综上所述,信息率失真函数R (D )的定义域为(D min,D max),这一定义域为一种理性
的选择条件下的定义域,实际上,可以让平均失真度超过该值。一般情况下输出端符号足
够多且选择合理时,D min=0,R (D min)=H (X );当D ≥D max时,R (D )=0;而当D min<
D <D max时,H (X )>R(D )>0。通过信息率失真函数可以看出信源在允许一定失真的
情况下的压缩潜力。
此外,如果将自变量和因变量颠倒过来,可得D (R ),称为失真信息率函数,它是
R(D )的逆函数。如何来理解和记忆两个函数的命名呢,信息率失真函数是因变量信息
率随着自变量失真度函数关系的表示,失真信息率函数则颠倒过来。
例5-4 若有一个离散、等概率单消息(或无记忆)二元信源:p(u0)=p(u1)=12
,且
采用汉明距离作为失真度量标准,即dij = 0, ui=uj
1, ui≠uj
时,若有一具体信源编码方案为:
N 个码元中允许错一个码元,实现时N 个码元仅传送N -1个,剩下一个不传送,在接收
端用随机方式决定这个码元(为掷硬币方式)。此时,速率R'为:
R'=N -1 N =1-1N
(b/符号)
抛硬币错误的概率为1/2,所以:
D =1N
×12
= 1
2N
所以信息率为R'(D )=1-1 N=1-2× 1
2N =1-2D 。
若已知这一类信源理论上的信息率失真函数R (D )=H 12
.
è .
.
. ÷
-H (D )(后面将进一
步给出计算),则可以对两者进行比较。在图5-3中,阴影范围表示实际信源编码方案与
理论值之间的差距,我们完全可以找到更好即更靠近理论值并且缩小阴影范围的信源编
码,这就是工程界寻找好的信源编码的方向和任务。
图5-3 实际信息率与信息率失真函数值的对比