信息论与编码纠错第6章.ppt

第6章 率失真编码 信息论与编码信息论与编码 第四章： 率失真编码 主讲：刘立 内容提要 数据压缩是信息传输和处理的重要研究内容，率失真理论研 究的就是在允许一定失真的前提下，对信源的压缩编码。率失真 信源编码定理（香农第三定理）指出：率失真函数R ( D ) 就是在 给定失真测度条件下，对信源熵可压缩的最低程度。 本章只限于研究率失真理论最基本的内容，失真测度，率失 真函数，率失真函数的定义域，值域，性质。R (D) 的计算很烦 琐，一般情况只能用参数法求解（不作要求）。 信息论与编码信息论与编码 第四章： 率失真编码 主讲：刘立 6.1失真测度与平均失真 在允许一定失真的前提下，从提高传输效率的角度出发，可以对信 源信息量事先进行压缩再予传输，这章要讨论的问题就是给定一个失真 度，求出在平均失真小于给定值的条件下，信源所能压缩的最低程度， 即率失真函数R(D)。 一失真测度d( x, y ) 给定离散信源 ，信道输出符号yj 引起的失真用d (xi, y j)（i =1, 2, ,I j = 1, 2, , J）表示，简记为d i j， 将所有的d i j列出来，可以得到下面的失真测度矩阵： 信息论与编码信息论与编码 第四章： 率失真编码 主讲：刘立 【例】 汉明（Hamming）失真测度 信源输出符号X=x1, x2, , xK，信道输出符号Y=y1, y2, , yK，约 定失真测度 上述约定可以用矩阵表示为： 式中d i j 0（i, j = 1, 2, , K）为信源方发送符号xi而信宿方判为yj 引起的失真度。 信息论与编码信息论与编码 第四章： 率失真编码 主讲：刘立 【例】 平方误差失真测度 信源输出符号X = 0, 1, 2， 信道输出符号Y = 0, 1, 2 ， 给出失真测度 d i j = (xi - yj )2 i, j = 0, 1, 2 则失真测度矩阵为 信息论与编码信息论与编码 第四章： 率失真编码 主讲：刘立 【例】 绝对值误差失真测度 信源输出符号X = 0, 1, 2，信道输出符号Y = 0, 1, 2 ，给出失真测度 d i j = xi - yj i, j = 0, 1, 2 则失真测度矩阵为 信息论与编码信息论与编码 第四章： 率失真编码 主讲：刘立 对于矢量传输情况，若信道的输入、输出均为N 长序列 定义失真测度为 序列间的失真测度为序列中各符号失真测度的均值。 信息论与编码信息论与编码 第四章： 率失真编码 主讲：刘立 【例】 信源离散无记忆，输入符号X = 0，1 ，信道输出符号Y = 0，1 ， 失真测度为汉明失真测度 对信源做二次扩展 ，经离散无记忆有扰信道传输，输出符 号 ，计算扩展后的失真测度矩阵。 【解】根据 ，得 失真测度矩阵为： 信息论与编码信息论与编码 第四章： 率失真编码 主讲：刘立 二. 平均失真 离散信源 ，经有扰信道传输 ，信道输出符号为Y = y1, y2, , yJ，平均失真即对d i j（i =1, 2, , I ；j = 1, 2, , J）求统计平均值，记为 平均失真是对在给定信源分布p(x)条件下，通过有扰信道传输而引 起失真的统计平均度量。 信息论与编码信息论与编码 第四章： 率失真编码 主讲：刘立 【例】等概信源 ，经过信道转移概率矩阵为 的信道传输，失真测度为平方误差失真测度， 求平均失真。 【解】由平均失真计算公式得： 信息论与编码信息论与编码 第四章： 率失真编码 主讲：刘立 对于矢量传输情况，若信道的输入、输出符号均为长度为N序列， 平均失真定义为： 序列中第k个符号的平均失真 上式表明离散无记忆N次扩展信道的输入符号序列和输出符号序列之间 的平均失真，等于单个符号xki与ykj之间失真统计值的总和。 若矢量信源是原离散无记忆信源的N次扩展，且矢量信道也是无记忆的 N次扩展，则每个 对一维信源信道所取的均值相等，即 从而 信息论与编码信息论与编码 第四章： 率失真编码 主讲：刘立 6.2 信息率失真函数R(D) 一率失真函数的定义 给定信源，即信源概率分布p (x) 一定，给定失真测度矩阵d=dij， 寻找信道，记它的转移概率矩阵为 ，要求满足 式中D是预先给定的失真度，上式称为保真度准则。 根据定理2.2，当信源p(x)一定时，平均互信息量I(X ;Y)是信道转移概 率函数p(y/x)的型凸函数，这意味着可以关于p(y/x)对平均互信息量I (X;Y) 求得极小值，定义这个极小值为率失真函数R(D)，即： 信息论与编码信息论与编码 第四章： 率失真编码 主讲：刘立 几点说明： 在允许一定失真前提下，对信源进行有失真编码，编码方法不同意 味着p(y/x)不同； 这里的p(y/x)并不是真正的信道，对于真正的信道，要改变其特性 p(y/x)代价太大，所以，式中的p(y/x)只是试验信道，是我们假想的 信道，它对应于不同的信源编码； 上式的意义在于，选择p(y/x)即选择某种编码方法在满足 的 前提下，使I (X ; Y) 达到最小值R(D) ，这就是满足 平均失真 条件下的信源信息量可压缩的最低程度。 信息论与编码信息论与编码 第四章： 率失真编码 主讲：刘立 二 率失真函数的值域、定义域 1R(D)的值域 由平均互信息量的公式 若忽略信道干扰， 这说明在不允许失真的前提下，平均互 信息量等于信 源熵，若给定失真度D0就表示不允许任何失真，根据 率失真函数定义可得： 由平均互信息量的性质 得 综上，R(D)的值域为： 信息论与编码信息论与编码 第四章： 率失真编码 主讲：刘立 2R(D)的定义域 （1）D的最小值Dmin 在给定的失真测度矩阵中，对每一个xi ，找一个最小的d i j，然 后对所有的i =1, 2, I求统计平均值，就是D的最小值，即 从表达式可以看出，只有在失真测度矩阵d中，每一行至少有一个 零元素，才可能有Dmin0，当Dmin0时，表示不允许任何失真，此 时，R(D) = H(X)。 信息论与编码信息论与编码 第四章： 率失真编码 主讲：刘立 （2）D的最大值Dmax 当R (D) 达到其最小值R(D)min= 0时，对应的失真最大，这种情况下D 对应着R (D) 函数定义域的上界值Dmax 当信源符号与信宿符号不相干时，有p( yj / xi ) = p( yj )，此时，经过 一次通信得不到任何信息，平均互信息量为零，故上式变为： Dmax的计算公式 在失真测度矩阵中，将第j列的每个元素dij乘上相应的p(xi)，再把它们加 起来，这样就得到J个和值，在这J个和值中，找一个最小值，就是Dmax。 信息论与编码信息论与编码 第四章： 率失真编码 主讲：刘立 【例】 一信源含有三个消息，概率分布为p1=0.2，p2=0.3，p3=0.5，失真测度 矩阵为 求Dmin和Dmax。 【解】 信息论与编码信息论与编码 第四章： 率失真编码 主讲：刘立 三率失真函数的性质 率失真函数有如下几条性质： 1R(D)是D的型凸函数 分别给定两个失真度D1和D2（Dmin D1，D2 Dmax），则下式成立： 函数的均值大于等于均值的函数。 2R(D)是D的连续、单调、减