信息论基础1第四章

1、第4章率失真编码 内容提要数据压缩是信息传输和处理的重要研究内容，率失真理论研究的就是在允许一定失真的前提下，对信源的压缩编码。率失真信源编码定理（香农第三定理）指出：率失真函数R (D) 就是在给定失真测度条件下，对信源熵可压缩的最低程度。本章只限于研究率失真理论最基本的内容，失真测度，率失真函数，率失真函数的定义域，值域，性质及定量计算。R (D) 的计算很烦琐，文中通过二个例子介绍了几种特殊情况下R (D )的求法，一般情况只能用参数法求解。第4章 率失真编码1失真测度d( x, y ) 给定离散信源 ，信道输出符号yj引起的失真用 d (xi ,y j)（i =1, 2, ,I j =

2、 1, 2, , J）表示，简记为d i j，将所有的d i j列出来，可以得到下面的失真测度矩阵(4-1) 在允许一定失真的前提下，从提高传输效率的角度出发，可以对信源信息量事先进行压缩再予传输，这章要讨论的问题就是给定一个失真度，求出在平均失真小于给定值的条件下，信源所能压缩的最低程度，即率失真函数R(D)。4.1 失真测度与平均失真【例4.1】 汉明（Hamming）失真测度信源输出符号X = x1, x2, , xK，信道输出符号Y = y1, y2, , yK，约定失真测度上述约定可以用矩阵表示为 式中di j 0 i, j = 1, 2, , K为信源方发送符号xi而信宿方判为yj

3、引起的失真度。对于矢量传输情况，若信道的输入、输出均为N 长序列X = X1 X2 XN ，Y = Y1 Y2 YN ，定义失真测度为 （4-2） 【例4.2】 平方误差失真测度信源输出符号X = 0, 1, 2， 信道输出符号Y = 0, 1, 2 ， 给出失真测度d i j = (xi - yj )2 i, j = 0, 1, 2则失真测度矩阵为 【例4.3】 绝对值误差失真测度信源输出符号X = 0, 1, 2，信道输出符号Y = 0, 1, 2 ，给出失真测度d i j = xi - yj i, j = 0, 1, 2则失真测度矩阵为 2.平均失真离散信源 ，经有扰信道传输，信道输出符

4、号为Y = y1, y2, , yJ，平均失真即对d i j（i =1, 2, ,I; j = 1, 2, , J）求统计平均值，记为 （4-4）平均失真 是对在给定信源分布q(x)条件下，通过有扰信道传输而引起失真的统计平均度量。 4.2.1 率失真函数的定义给定信源，即信源概率分布q (x) 一定，给定失真测度矩阵d=dij，寻找信道，记它的转移概率矩阵为 ，要求满足 （4-11）式中D是预先给定的失真度，上式称为保真度准则。4.2 信息率失真函数R(D)根据定理2.2，当信源q (x)一定时，平均互信息量I (X ; Y)是信道转移概率函数p(yx)的型凸函数，这意味着可以关于p(yx)

5、对平均互信息量I (X ; Y)求得极小值，定义这个极小值为率失真函数R(D)，即： (4-12) 式(4-12)的意义在于，选择p(yx)即选择某种编码方法在满足 的 前提下，使I (X ; Y) 达到最小值R(D) ，这就是满足平均失真 条件下的信源信息量可压缩的最低程度。（1）D的最小值Dmin 在给定的失真测度矩阵中，对每一个xi，找一个最小的 d i j ，然后对所有的i =1, 2, ,I求统计平均值，就是D的最小值，即 (4-14) 2. R(D)的定义域4.2.2 率失真函数的值域、定义域 1.R(D)的值域（参见图4-1） 率失真函数的值域为 0 R（D） H（X） (4-1

6、3) D图41 R（D）的值域Dmax0DminH（X）R(D)求出计算Dmax的显式: j =1,2, , J（4-18） （2）D的最大值Dmax 当R (D) 达到其最小值Rmin（D）= 0时，对应的失真最大，这种情况下D对应着R (D) 函数定义域的上界值Dmax，如图4-1所示。=minD: I (X; Y ) = 0 （4-15) 纵上所述，R(D)的定义域为：D min D D max，式中D min和D max可分别由式（4-14）和式（4-18）求出。 4.2.3 率失真函数的性质 率失真函数有如下几条性质:： 3.对于离散无记忆信源（DMS） R (N ) (D) = N

7、 R (D) 2. R(D)是D的连续、单调、减函数 1.R(D)是D的型凸函数分别给定两个失真度D1和D2（Dmin D1, D2 Dmax），则下式成立： R (1D1+2D2) 1R (D1)+2 R (D2) （4-19） 4.3.1二种特殊情况下的求解 【例4.8】 信源含两个消息x1=0，x2=1,其概率分布为 ,0.5，信道输出符号Y = y1=0，y2=1， 失真测度为汉明（Hamming）失真测度，求率失真函数R(D)。 (1) 根据式(4-14)和(4-18)可求出R(D)的定义域 Dmin = 0+0(1-) = 0 D max = min 1-, = (2) 求R(D)

8、的值域R (Dmin=0) = H(U ) = -log- (1-) log (1-) = H2 () R (Dmax) = R () = 0 4.3 率失真函数的计算根据熵的性质 H（XY） H (X) H (XY)，又算出 H (X) = - log -(1-) log (1-) = H2 ( )将这两个结果代入平均互信息量的表达式 I (X; Y) = H (X) -H (XY)，得到 I (X; Y ) H2 () -H (XY) （4-32） （3）在0 D 的范围内，计算R(D ）对于汉明失真测度，失真测度矩阵为平均失真 在R(D)的定义中，要求满足 ，取等号 ，则 H（XY）=

9、H2（XY）= H2 p (XY ) = H2 (D)将这一结果代入式（4-32），得I（X；Y） H2 ()- H2 (D) 根据定义 = H2 ()- H2 (D ) 根据d的对称性，假设一个反向信道(YX ) 反向信道的转移概率矩阵为，假设的反向信道应满足： (xiyj) 0 i, j = 1,2（4）上面是按照定义求出了R(D)，下面的问题是要真正找到这么一个信道转移概率矩阵为P的信道，使H（YX）= H2（D），从而R(D)= H2 () - H2 (D)，且P中的每一个元素p (yjxi) 都满足p (yjxi) 0 i, j = 1,2由假设的反向信道计算平均失真，得 = (y1

10、) +(y2) D = D 计算条件熵： = - (1-D) log (1-D) - D log D= H2 (D)则平均互信息量I (X; Y) = H (X) -H (XY) = H2 () - H2 (D )， 假设的(xy)确实在满足 的条件下，使 I (X; Y) = H2 () - H2 ( D )。从而有 由上式知 ，满足失真条件 。 （5）要找出正向信道，可由 ，反解出(yj)， j = 1, 2，再计算出 。=（1-D）（y1）+ D (y2)1- = D （y1）+（1-D） (y2)由上面方程组解出， 再算出【例4.9】 信源分布 ，失真测度矩阵为: ，计算率失真函数 (

11、1) 求出R(D)的定义域（2)计算R (D)根据d的对称性，可假设信道转移概率矩阵 , 式中 为待定常数。由假设的信道转移概率计算信息量 （4-33）先算出 (4-34)将式(4-34)代入式(4-33)得 即 （4-35）由假设的信道转移概率计算平均失真，得 （4-36）因为 ，由式(4-36)得 考虑到 ，则如图4-3所示：在 的范围内，H2()是单调递增函数，有 H2()图 4-3 H2()- 曲线010.5根据式(4-35)，得从而 4.3.2 R（D）的参数表示法 (2) 由式(4-40) 求 ；(3) 由式(4-39) 求p(yjxi)；(4) 由式(4-42) 求D；(5) 由

12、式(4-43) 求R (D)。用参数法求R (D)， 可按下述步骤进行：（1）由式(4-41) 求 ；用此法求解，有时候会出现(yj)0的情况碰到这种情况，就要令某一(y*j) = 0，重复刚才的求解过程，这种情况下求得的R (D)是一折线，折点对应(y*j) = 0，如图45所示。图4-5(y*j) 0的情况D0对应(y*j) = 0R (D)【例4.10】 仍考虑例4.8的输入概率分布q (x1) = ，q (x2) = 1， 0.5，失真测度矩阵 ，用参数法求R (D)。解：(1) 根据式(4-41)，即 得解出 (2) 由式(4-40)，即 ，得解出 (3) 由式(4-39)，即 ，得(4) 由式(4-42)，即 ， 得(5) 由式(4-43)，即 ，得=D lnD + (1-D) ln (1-D) + H 2 () = H 2 () -H 2 (D ) （3）如何求R (D)的定义域和值域 （2）平均失真 对给定信源q (x) 进行压缩编码，不同的编码方法对应不同的实验信道，可用信道转移概率p(yx) 来描述该实验信道，用概率分布 p(x y) = q (x) p(yx)对给定的失真测度求统计平均值就得到平均失真.（1）失真测度 可以理解为误码带来的代价，实际上发送同一符号而错成不同符号所带来的代价是不同的 。本 章 小 结本章介绍在允许