信息论与编码-第4章

1、第4章 信息率失真函数l本章主要讨论在信源允许一定失真情况下所需 的最少信息率； 从分析失真函数、平均失真出发，求出信息率失真函数 R(D) l4.1 平均失真和信息率失真函数l4.2 离散信源和连续信源的 R(D) 计算4.1 平均失真和信息率失真函数l在实际问题中，信号有一定的失真是可以容忍的;l但是当失真大于某一限度后，信息质量将被严重损伤，甚至丧失其实用价值;l要规定失真限度，必须先有一个定量的失真测度;l为此可引入失真函数4.1.1 失真函数l假如某一信源 X，输出样值为 xi，xia1,an，经过有失真的信源编码器，输出 Y，样值为 yj，yj b1,bml如果xiyj，则认为没有

2、失真；如果 xiyj，那么就产生了失真l失真的大小，用一个非负量来表示，即失真函数 d(xi,yj)，以衡量用 yj 代替 xi 所引起的失真程度l一般失真函数定义式为jijijiyxyx),yd(x004.1.1 失真函数l失真矩阵 单个符号的失真函数的全体排列起来构成的矩阵，称为失真矩阵注意：失真函数d(xi,yj)的数值是依据实际情况,用yj代替xi 所导致的失真大小是人为决定的111212122212( , )( , )( ,)( , )( , )( ,)( , )( , )( ,)mmnnnmd a bd a bd a bd a bd a bd a bd a bd a bd a bd

3、均方失真：ijijixyxyxd/),(2),(jijiyxyxdjijiyxyxd),(其它，1, 0),(),(jijijiyxyxyxd相对失真：误码失真：绝对失真：前三种失真函数适用于连续信源，后一种适用于离散信源 l最常用的失真函数 4.1.1 失真函数失真函数的定义可以推广到序列编码情况如果假定离散信源输出符号序列X=(X1X2XlXL)，其中L长符号序列样值xi(xi1xi2xilxiL)，经信源编码后，输出符号序列Y=(Y 1Y 2Y lY L)，其中L长符号序列样值yj(yj1yj2yjlyjL)，则序列失真函数定义为： 其中d(xil，yjl)是信源输出L长符号样值xi中的

4、第l个符号xil时，编码输出L长符号样值yj中的第l个符号yjl的失真函数。 11( ,)(,)LLijiljlldd x yLx y4.1.1 失真函数4.1.2 平均失真 由于xi和yj都是随机变量，所以失真函数d(xi,yj)也是随机变量，考察整个信源有失真编码状况，需要用它的数学期望或统计平均值，因此将失真函数的数学期望称为平均失真，记为 1111() (,)()(/) (,)nmijijijnmijiijijDp a bd a bp ap ba d a b符号转移概率分布ixjyjip y x信源编码器 对于连续随机变量同样可以定义平均失真,( , ) ( , )X YDpx y d

5、 x y dxdy LllLljlilLDLyxdELD111),(1对于L长序列编码情况，平均失真为4.1.2 平均失真 其中pX,Y(x,y)是连续随机变量的联合概率密度其中 是第l个符号的平均失真lD4.1.3 信息率失真函数R(D)12,nXa aa信源编码器12,nYb bbXY假想信道信源X经过有失真的信源编码器将信源编码器输出Y，将这样的编码器看作存在干扰的假想信道4.1.3 信息率失真函数R(D)l信源编码器的目的：使编码后所需的信息传输率 R 尽量小；l然而R越小，引起的平均失真就越大；l信息率 R 就是所需输出的有关信源 X 的信息量；l对应到假想信道，即为接收端 Y 需要

6、获得的有关 X 的信息量，也就是互信息 I(X;Y)；l这样，选择信源编码方法的问题就变成了选择假想信道的问题，符号转移概率 p(yj/xi) 就对应信道转移概率DDl给出一个失真的限制值 D，在满足平均失真 （保真度准则）的条件下，选择一种编码方法使信息率 R 尽可能小；4.1.3 信息率失真函数R(D)mjniDDabpPijD, 2 , 1;, 2 , 1:)/(D允许试验信道此信道集合称为D允许试验信道平均失真由信源分布 p(xi)、假想信道的转移概率 p(yj/xi)和失真函数 d(xi,yj) 决定，若 p(xi) 和 d(xi,yj) 已定，则可给出满足 条件的所有转移概率分布

7、pij，它们构成了一个信道集合PDDD4.1.3 信息率失真函数R(D)由于互信息取决于信源分布和信道转移概率分布，根据 2-2 节所述，当 p(xi) 一定时，互信息 I(X;Y) 是关于 p(yj/xi) 的 U 型凸函数，存在极小值。因而在上述允许信道 PD 中，可以寻找一种信道 pij，使给定的信源 p(xi) 经过此信道传输后，互信息 I(X;Y) 达到最小。该最小的互信息就称为信息率失真函数 R(D)，即 信息率失真函数 R(D)的物理意义：对于给定信源，在平均失真不超过失真限度D的条件下，信息率容许减小到（压缩）的最小值 R(D);(min)(YXIDRDP信息率失真函数R(D)

8、4.1.3 信息率失真函数R(D) p(ai)，i1，2，n 是信源符号概率分布； p(bj/ai)，i1，2，n，j1，2，m 是转移概率分布； p(bj)，j1，2，m 是接收端收到符号概率分布。 nimjjijijiPPbpabpabpapDRDij11)()/(log)/()(min)( 对于离散无记忆信源，R(D)函数可写成 例4.1 (p.74) 设信源的符号表为Aa1，a2，a2n，概率分布为p(ai)1/2n，i1，2，2n，失真函数规定为 即符号不发生差错时失真为0，一旦出错，失真为1，试研究在一定编码条件下信息压缩的程度jijiaadji01),(4.1.3 信息率失真函数

9、R(D)4.1.3 信息率失真函数R(D)解：信源熵 设失真限度 D=1/2 等效试验信道为一个确定信道 则 信道输出概率分布为 则输出熵为11,log2 bit/22Hnnn符号1 0 0ijpH Y X或， ;I X YH YH Y XH Y12111, 22nnnppppnn 111 11,log2log12222nnnH YHnnnnnn 个12DD平均失真应为4.1.4 信息率失真函数的性质1.R(D)函数的定义域函数的定义域 Dmin和 R(Dmin) Dmin0 对于离散信源 对于连续信源 )() 0 ()(minXHRDR )()0()(minxHRDRc (2) Dmax和

10、R(Dmax)niijimjdpD1, 2, 1maxmin选择所有满足R(D)0中D的最小值，定义为R(D)定义域的上限Dmax，即DDDR0)(maxmin因此可以得到R(D)的定义域为max,0 DD 4.1.4 信息率失真函数的性质Dmax是怎样来计算R(D)0就是I(X;Y)0，这时试验信道输入与输出是互相独立的，所以条件概率 p(yj/xi) 与xi 无关。即jjijijpypxypp)()/(4.1.4 信息率失真函数的性质mjniijijdppD11maxmin nimjijjidppD11此时平均失真为4.1.4 信息率失真函数的性质的D中的最小值，即11mjjp求出满足条件

11、从上式观察可得：在 j=1,2,m 中，可找到 值最小的 j，当该 j 对应的 pj1，而其余 pj 为零时，上式右边达到最小，这时上式可简化成niijidp1niijimjdpD1, 2 , 1maxmin例4.2 (p.76) 设输入输出符号表为 XY0，1，输入概率分布p(x)=1/3，2/3，失真矩阵为分析R(D)定义域两端的状态11122122( , )( ,)01(, )(,)10d a bd a bd a bd a bd4.1.4 信息率失真函数的性质解：当Dmin0时，R(Dmin)H(X)H(1/3，2/3)0.91比特/符号，这时信源编码器无失真，所以该编码器的转移概率为

12、1001P4.1.4 信息率失真函数的性质1,21212min01,103333j 当R(Dmax)0时 此时输出符号概率 p(b1)0，p(b2)1， 所以这时的编码器的转移概率为 2221,baba0101P4.1.4 信息率失真函数的性质2max1,21miniijjiDp d1112211122221,2min,jp dp dp dp d1,22 11min,3 33j2、R(D)函数的下凸性和连续性函数的下凸性和连续性 下凸性： 连续性：3、R(D)函数的单调递减性函数的单调递减性 物理意义：容许的失真度越大，所要求的信息率越小。反之亦然。4.1.4 信息率失真函数的性质 1 01;

13、 1R DR DR DDDD其中0lim R DR DDD其中 DDR DR D若则综上所述，可以得出如下结论：R(D)是非负的实数，即 R(D)0。其定义域为0Dmax，其值为0H(X)。当 DDmax 时， R(D) 0。R(D) 是关于D的下凸函数，因而也是关于D的连续函数。R(D)是关于D的严格单调递减函数。4.1.4 信息率失真函数的性质由以上三点结论，对一般R(D)曲线的形态可以画出来： 4.1.4 信息率失真函数的性质R(D)H(X)R(D) 0 D Dmax DR(D) 0 Dmax D 信息率失真曲线(a) 离散系统(b) 连续系统4.1.5 信息率失真函数与信道容量的比较信

14、道容量信道容量C率失真函数率失真函数R(D)研究对象信道信源给定条件信道转移概率p(y/x)信源概率分布p(xi)选择参数信源概率分布p(xi)信源编码器映射关系p(y/x)结论噪声干扰消失的信息量H(X/Y)信源压缩损失的信息量H(X/Y)()max (; )ip aCI X Y()min (; )DPR DI X Y(; )()(/)I X YH XH X Y表4-1 R(D)与C的比较 信道容量表示信道的最大传输能力，反映信道的特性，与信源无关，以信源中能使平均互信息达到最大的信源为参考；信息率失真函数表示保真度条件下信源的信息率可被压缩的最低限度，反映信源本身的特性，与信道无关，以编码

15、器中能使平均互信息达到最小的信道为参考； 计算R(D)的显式表达式一般是很困难的 某些特殊情况下 R(D) 的表示式为：DDRlog)(4.2 离散信源和连续信源的R(D)计算22221)(xexp（1）当d(x,y)=(x-y)2， 时，(2)当d(x,y)=|x-y|， 时，xexp2)(DDR1log)(3)当d(x,y)=(x,y)，p(x=0)=p，p(x=1)=1-p时， 4.2 离散信源和连续信源的R(D)计算()( )() R DH pH D4.2 离散信源和连续信源的R(D)计算 0 Dmax D R(D) H(3)(1)(2)图4-5 信息率失真函数R(D)这些 R(D)

16、可画成三条曲线l对于R(D)函数，只在有限情况下，能够得到它的解析表达式l更多的情况，只能通过计算机计算它的数值解l这种方法通常称为参量表达式法l田宝玉等编著的信息论基础习题解答（人民邮电出版社2010年版）一书中的192-193页有一个例子的Matlab程序和迭代流程图，以及解析解与数值解的对照曲线，结果是非常吻合的4.2 离散信源和连续信源的R(D)计算求信息率失真函数R(D)。解：（略）11122122( ,)( ,)01(,)(,)10d a bd a bd a bd a bd例4.3 (p.81)设输入输出符号表为XY0，1，输入概率分布p(x)=(p，1-p)，0Dmax 时， R

17、(D) 0lR(D) 是关于D的下凸函数，也是关于D的连续函数lR(D)是关于D的严格单调递减函数第第4章章 复习复习R(D)H(X)R(D) 0 D Dmax DR(D) 0 Dmax D 信息率失真曲线(a) 离散系统(b) 连续系统第第4章章 复习复习信道容量信道容量C率失真函数率失真函数R(D)研究对象信道信源给定条件信道转移概率p(y/x)信源概率分布p(xi)选择参数信源概率分布p(xi)信源编码器映射关系p(y/x)结论噪声干扰消失的信息量H(X/Y)信源压缩损失的信息量H(X/Y)()max (; )ip aCI X Y( )min (; )DPR DI X Y(; )()(/

18、)I X YH XH X Y信道容量C 与率失真函数R(D)的比较 l对于R(D)函数，只在有限情况下，能够得到它的解析表达式l更多的情况，只能通过计算机计算它的数值解 例4.1 (p.74) 设信源的符号表为Aa1，a2，a2n，概率分布为p(ai)1/2n，i1，2，2n，失真函数规定为 即符号不发生差错时失真为0，一旦出错，失真为1，试研究在一定编码条件下信息压缩的程度jijiaadji01),(4.1.3 信息率失真函数R(D)4.1.3 信息率失真函数R(D)解：信源熵 设失真限度 D=1/2 等效试验信道为一个确定信道 则 信道输出概率分布为 则输出熵为11,log2 bit/22

19、Hnnn符号1 0 0ijpH Y X或， ;I X YH YH Y XH Y12111, 22nnnppppnn 111 11,log2log12222nnnH YHnnnnnn 个12DD平均失真应为015.2 无失真信源编码无失真信源编码01例5.5 (p.96) 对例5.3中的信源进行哈夫曼编码 0.610.390.200.190.180.170.150.110.260.200.190.180.170.350.260.200.190.390.350.261.00.200.190.180.170.150.100.01a1a2a3a4a5a6a701010101信源ai概率p(ai)码字Wi码长Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.0101114平均码长 码元/符号 72. 2)(71iiiKapK信息效率bit/符号96. 072. 261. 2)(KXHR5.2 无失真信源编码无失真信源编码可见，Huffman码的平均码长最小，R最大、编码效率最高值得注意：哈夫曼编码方法得到的码并非唯一的