《信息论与编码6》由会员分享，可在线阅读，更多相关《信息论与编码6（34页珍藏版）》请在金锄头文库上搜索。
1、第6章 率失真编码,内容提要 数据压缩是信息传输和处理的重要研究内容，率失真理论研究的就是在允许一定失真的前提下，对信源的压缩编码。率失真信源编码定理（香农第三定理）指出：率失真函数R (D) 就是在给定失真测度条件下，对信源熵可压缩的最低程度。 本章只限于研究率失真理论最基本的内容，失真测度，率失真函数，率失真函数的定义域，值域，性质及定量计算。R (D) 的计算很烦琐，文中通过二个例子介绍了几种特殊情况下R (D )的求法，一般情况只能用参数法求解。,第6章 率失真编码,在允许一定失真的前提下，从提高传输效率的角度出发，可以对信源信息量事先进行压缩再予传输，这章要讨论的问题就是给定一个失真
2、度，求出在平均失真小于给定值的条件下，信源所能压缩的最低程度，即率失真函数R(D)。,6.1 失真测度与平均失真,【例6.1】 汉明（Hamming）失真测度 信源输出符号X = x1, x2, , xK，信道输出符号Y = y1, y2, , yK，约定失真测度上述约定可以用矩阵表示为 式中di j 0 i, j = 1, 2, , K为信源方发送符号xi而信宿方判为yj引起的失真度。,对于矢量传输情况，若信道的输入、输出均为N 长序列X = X1 X2 XN ，Y = Y1 Y2 YN ，定义失真测度为（6-2）,【例6.2】 平方误差失真测度 信源输出符号X = 0, 1, 2， 信道输
3、出符号Y = 0, 1, 2 ， 给出失真测度d i j = (xi - yj )2 i, j = 0, 1, 2则失真测度矩阵为,【例6.3】 绝对值误差失真测度 信源输出符号X = 0, 1, 2，信道输出符号Y = 0, 1, 2 ，给出失真测度 d i j = xi - yj i, j = 0, 1, 2 则失真测度矩阵为,2.平均失真,离散信源 ，经有扰信道传输，信道输出符号为Y = y1, y2, , yJ，平均失真即对d i j（i =1, 2, ,I; j = 1, 2, , J）求统计平均值，记为（6-4）,平均失真 是对在给定信源分布q(x)条件下，通过有扰信道传输而引起失
4、真的统计平均度量。,6.2.1 率失真函数的定义,给定信源，即信源概率分布q (x) 一定，给定失真测度矩阵d=dij，寻找信道，记它的转移概率矩阵为 ，要求满足（6-11）式中D是预先给定的失真度，上式称为保真度准则。,6.2 信息率失真函数R(D),根据定理2.2，当信源q (x)一定时，平均互信息量I (X ; Y)是信道转移概率函数p(yx)的型凸函数，这意味着可以关于p(yx)对平均互信息量I (X ; Y)求得极小值，定义这个极小值为率失真函数R(D)，即：(6-12),式(4-12)的意义在于，选择p(yx)即选择某种编码方法在满足 的前提下，使I (X ; Y) 达到最小值R(
5、D) ，这就是满足平均失真 条件下的信源信息量可压缩的最低程度。,（1）D的最小值Dmin在给定的失真测度矩阵中，对每一个xi，找一个最小的 d i j ，然后对所有的i =1, 2, ,I 求统计平均值，就是D的最小值，即(6-14),2. R(D)的定义域,6.2.2 率失真函数的值域、定义域,1.R(D)的值域（参见图4-1）率失真函数的值域为0 R（D） H（X） (6-13),图61 R（D）的值域,求出计算Dmax的显式:j =1,2, , J （6-18）,（2）D的最大值Dmax 当R (D) 达到其最小值Rmin（D）= 0时，对应的失真最大，这种情况下D对应着R (D) 函
6、数定义域的上界值Dmax，如图4-1所示。 =minD: I (X; Y ) = 0 （6-15),【例6.7】 一信源含有三个消息，概率分布为q1 = 0.2, q2 = 0.3, q3 = 0.5，失真测度矩阵为 ，求D min和D max。,由式(6-14)可求出 D min= 10.2 + 00.3 + 00.5 = 0.2,由式(6-18)可求出 D max = min 40.2 + 20.5, 20.2 + 30.3, 10.2 + 20.3 + 10.5= min 1.8, 1.3, 1.3 = 1.3,6.2.3 率失真函数的性质,率失真函数有如下几条性质:：,3.对于离散无记
7、忆信源（DMS）R (N ) (D) = N R (D),2. R(D)是D的连续、单调、减函数,1.R(D)是D的型凸函数 分别给定两个失真度D1和D2（Dmin D1, D2 Dmax），则下式成立： R (1D1+2D2) 1R (D1)+2 R (D2) （6-19）,6.3.1二种特殊情况下的求解,【例6.8】 信源含两个消息x1=0，x2=1,其概率分布为,0.5，信道输出符号Y = y1=0，y2=1，失真测度为汉明（Hamming）失真测度，求率失真函数R(D)。,(1) 根据式(6-14)和(6-18)可求出R(D)的定义域Dmin = 0+0(1-) = 0 D max =
8、 min 1-, =,(2) 求R(D)的值域 R (Dmin=0) = H(U ) = -log- (1-) log (1-) = H2 ()R (Dmax) = R () = 0,6.3 率失真函数的计算,根据互信息量的表达式： I (X;Y) = H(X) H (X | Y) I (X;Y) = H2 () H (X|Y) （6-32） 又根据Fano不等式有H (X | Y ) H2 (pe) + pe log (21) 则 I (X;Y)H2 () H2 (pe) （6-33）,（3）在0 D 的范围内，计算R(D ）,式中，pe为传输错误概率，又根据定义= H2 () H2 (pe
9、),从而有 R(D) = H2 () H2 (pe) = H2 () H2 (D),下面找出pe与D的关系记信道转移概率矩阵 信道输入xi，输出yj，i，j =1，2，若i j，则认定传输出错，故 pe = q(x1) p(y2 | x1)+ q(x2) p(y1 | x2),根据d的对称性，假设一个反向信道(YX ),反向信道的转移概率矩阵为，假设的反向信道应满足：(xiyj) 0 i, j = 1,2,（4）上面是按照定义求出了R(D)，下面的问题是要真正找到这么一个信道转移概率矩阵为P的信道,使H（YX）= H2（D），从而R(D)= H2 () - H2 (D)，且P中的每一个元素p
10、(yjxi) 都满足 p (yjxi) 0 i, j = 1,2,由假设的反向信道计算平均失真，得 = (y1) +(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
11、）+（1-D） (y2) 由上面方程组解出， 再算出,【例6.9】 信源分布 ，失真测度矩阵 ，计算率失真函数,(1) 求出R(D)的定义域,（2)计算R (D)根据d的对称性，可假设信道转移概率矩阵 , 式中 为待定常数。由假设的信道转移概率计算信息量,（6-34）,先算出 (6-35)将式(6-35)代入式(6-34)得,即 （6-36）,由假设的信道转移概率计算平均失真，得（6-37）,因为 ，由式(6-37)得 考虑到 ，则,如图6-3所示：在 的范围内，H2()是单调递增函数，有,根据式(6-36)，得从而,6.3.2 R（D）的参数表示法,(2) 由式(6-41) 求 ；,(3)
12、由式(6-40) 求p(yjxi)；,(4) 由式(6-43) 求D；,(5) 由式(6-44) 求R (D)。,用参数法求R (D)， 可按下述步骤进行：,（1）由式(6-42) 求出 ；,用此法求解，有时候会出现(yj)0的情况碰到这种情况，就要令某一(y*j) = 0，重复刚才的求解过程，这种情况下求得的R (D)是一折线，折点对应(y*j) = 0，如图65所示。,【例6.10】 仍考虑例6.8的输入概率分布q (x1) = ，q (x2) = 1， R (D)的情况称为保真度准则下的率失真编码定理，R R (D)的情况称之为逆定理。,6.4 率失真信源编码定理,（3）如何求R (D)的定义域和值域,（2）平均失真对给定信源q (x) 进行压缩编码，不同的编码方法对应不同的实验信道，可用信道转移概率p(yx) 来描述该实验信道，用概率分布 p(x y) = q (x) p(yx)对给定的失真测度求统计平均值就得到平均失真.,
