第四章第四章 信息率失真函数信息率失真函数 无失真信源编码和有噪信道编码（香农第一定理和香农 第二定理）告诉我们：只要信道的信息传输速率小于信道容量，总能找到一种 编码方法，使得在该信道上的信息传输的差错概率任意小； 反之，若信道的信息传输速率大于信道容量，则不可能使信 息传输差错概率任意小。但是，无失真的编码并非总是必要的。原始图像红色图像绿色图像蓝色图像原始图像和限失真图像原始图像和限失真图像香农首先定义了信息率失真函数R(D)，并论述了关于这个函 数的基本定理。 定理指出：在允许一定失真度D的情况下，信源输出的信息 传输率可压缩到R(D)值，这就从理论上给出了信息传输率与允 许失真之间的关系，奠定了信息率失真理论的基础。信息率失真理论是进行量化、数模转换、频带压缩和数据压 缩的理论基础。本章主要介绍信息率失真理论的基本内容，重点讨论离散无 记忆信源。l给出信源的失真度和信息率失真函数的定义与性质；l讨论离散信源和连续信源的信息率失真函数计算；l在此基础上论述保真度准则下的信源编码定理。4.1 4.1 失真测度失真测度一、失真度从直观感觉可知，若允许失真越大，信息传输率就可越 小；若允许失真越小，信息传输率需越大。 所以信息传输率与（信源）编码所引起的失真(或误差) 是有关的。首先讨论失真的测度。离散无记忆信源X，信源符号集Xa1,a2,ar，概率分 布为p(x)p(a1),p(a2),p(ar) 。信源符号通过信道传输到接收端，接收端的接收符号集 Y b1,b2,bs 。对应于每一对(ai,bj)，我们指定一个非负的函数：称为单个符号的失真度(或失真函数)。通常较小的d值代表较小的失真，而d(ai,bj)0表示没有 失真。若信源变量X有r个符号，接收变量Y有s个符号，则 d(ai,bj)就有rs个,它可以排列成矩阵形式，即：该失真矩阵D，是 rs 阶矩阵。实际这里X指的是原始的未失真信源，而Y是指失真以后的信源。如果假设X是信源，Y是信宿，那么X和Y之间必有信 道。从X到Y之间实际上是失真算法，所以这里的转移概率 p(bj/ai)是指一种失真算法，有时又把 p(bj/ai) 称为试验信道的转移概率，如图所示。原始信源失真信源试验信道信道XYp (bj/ai)例1 离散对称信源(r=s)，“0-1”失真。信源Xa1,a2,ar ， 接收Y b1,b2,bs。定义单个符号失真度：这种失真称为汉明失真。汉明失真矩阵是一方阵，对角线 上的元素为零，即：对二元对称信源(sr2)，信源X0,1，接收 变量Y0,1。在汉明失真定义下，失真矩阵为：例2 删除信源。信源Xa1,a2,ar ，接收Y b1,b2,bs (s = r+1) 。定义其单个符号失真度为：其中接收符号bs作为一个删除符号。此时，意味着若把信源符号再现为删除符号bs时，其失 真程度要比再现为其他接收符号的失真程度少一半。 二元删除信源 r 2， s 3，X0,1，Y0,1 ,2 。失真度为：则d(0,0)=d(1,1)=0 d(0,1)=d(1,0)=1 d(0,2)=d(1,2)=1/2除j=s以外所有的j和i所有i例 对称信源(s = r) 。信源Xa1,a2,ar ，接收Y b1,b2,bs 。若失真度定义为：如果信源符号代表信源输出信号的幅度值，这就是一种平 方误差失真度。它意味着幅度差值大的要比幅度差值小的所引 起的失真更为严重，其严重的程度用平方来表示。当 r3时， 0,1,2，0,1,2 ，则失真矩阵为：上述例子说明了失真度的具体定义。 一般情况下根据实际信源的失真，可以定义不同的失真和 误差的度量。另外还可以按其他标准，如引起的损失、风险 、主观感觉上的差别大小等来定义失真度d(a,b)。二、序列失真度设 ，其中取自信源符号集A；其中取自信宿符号集B。则序列失真度定义为：三、 平均失真度信源 X 和信宿 Y 都是随机变量，故单个符号失真度d(ai,bj) 也 是随机变量。规定了单个符号失真度d(ai,bj) 后，传输一个符号引起的平均 失真，即信源平均失真度：在离散情况下，信源Xa1,a2,ar ，其概率分布p(x) p(a1),p(a2),p(ar) ，信宿Y b1,b2,bs 。若已知试验信道的传递概率为p(bj/ai)时，则平均失其度为： 若平均失真度D不大于我们所允许的失真D0，即：D D0称此为保真度准则。 信源固定（即给定了p(x)），单个符号失真度固定时（即 给定了d(ai,bj)） ，选择不同试验信道，相当于不同的编码方法 ，所得的平均失真度是不同的。有些试验信道满足D D0，而有些试验信道DD0。凡满足保真度准则-平均失真度D D0的试验信通称为 -D D失真许可的试验信道失真许可的试验信道。把所有D失真许可的试验信道组成一个集合，用符号PD表 示，则：PD=p (bj / ai)： D D04.2 信息率失真函数及其性质一、信息率失真函数的定义 信源给定，且又具体定义了失真函数以后，总希望在满足 一定失真的情况下，使信源传输给收信者的信息传输率R尽可 能地小。-即在满足保真度准则下，寻找信源必须传输给信 宿的信息率R的下限值-这个下限值与D有关。从接收端来看，就是在满足保真度准则下，寻找再现信源 消息所必须获得的最低平均信息量。而接收端获得的平均信息量可用平均互信息I(X;Y)来表示，这就变成了在满足保真度准则的条件下，寻找平均互信息 I(X;Y)的最小值。寻找平均互信息I(X;Y)的最小值。而PD是所有满足保真度 准则的试验信道集合，因而可以在D失真许可的试验信道集合PD中寻找一个信道p(bj / ai) ，使I(X;Y) 取极小值。由于平均互信息I(X;Y)是p(bj / ai)的U型凸函数，所以在PD集合中，极小值存在。这个最小值就是在D D0的条件下，信源进行传输的最小平均信息量。即：R(D)-信息率失真函数或简称率失真函数单位是：比特信源符号率失真函数给出了熵压缩编码可能达到的最小熵率与失真 的关系;其逆函数D(R)称为失真率函数, D(R)表示一定信息速率下所可能达到的最小的平均失真。 二、信息率失真函数的性 质 允许失真度D的下限可以是零，这是不允许任何失真的情况。1、 R(D)的定义域R(D)的定义域为 且：解：解： 例例4 4 设设试验信道输入符号集试验信道输入符号集 ，各符号等概分布各符号等概分布 ， 失真矩阵如下所示，求失真矩阵如下所示，求 和和 以及相应的试验信道的转移以及相应的试验信道的转移 概率矩阵。概率矩阵。 令对应最小失真度令对应最小失真度 的的 ，其它为，其它为“ “0”0”，可得，可得 对应对应 的试验信道转移概率矩阵为：的试验信道转移概率矩阵为： 上式中第二项最小，所以令上式中第二项最小，所以令 ， ，可得对应可得对应 的试验信道转移概率矩阵为的试验信道转移概率矩阵为: :2、 R(D)是关于平均失真度D的下凸函数 设 为任意两个平均失真， ，则有： 3 、 R(D) 是 区间上的连续和严格单调递减函数。 信息率失真函数的一般形状 ( )4.3 4.3 离散无记忆信源的信息率失真函数离散无记忆信源的信息率失真函数已知信源的概率分布p(x)和失真函数d(x,y)，就可求得信源 的R(D)函数。原则上它与信道容量一样，即在有约束条件下求 极小值的问题。也即选取适当的试验信道p(x/y)使平均互信息最小化：其约束条件为:一般取等号一、 等概率、对称失真信源的R(D) 计算 对对于等概、对对称失真的信源，存在一个与失真矩阵阵具有 同样对样对 称性的转转移概率分布达到率失真R(D)。解： 例例5 5 有一个二元等概平稳无记忆信源有一个二元等概平稳无记忆信源 ，接收符号集为接收符号集为 且失真矩阵为且失真矩阵为 ： 求率失真函数求率失真函数R(D) R(D) 。由于信源等概分布，失真函数具有对称性，因此，存在着与失 真矩阵具有同样对称性的转移概率分布达到率失真R(D) ，该 转移概率矩阵可写为：由于 ，因此对于任何有限平均失真，必 须 ,于是转移概率矩阵为：对应此转移概率矩阵的平均失真： 因此: 可求得此时的互信息为：二、 信息率失真函数的参量表述求信源的R(D)函数，原则上与求信道容量一样，是在有约 束条件下求极小值的问题。也就是适当选取试验信道p(y/x)使平均互信息最小化，应用拉格朗日乘子法，原则上可以求出解来。困难在于： 要得到显式的解析表达式，则比较困难，通常只能用参量 形式来表达。 要保证约束条件式p(bj/ai) 0，应用拉格朗日乘子法解得的 某些p(bj/ai)很可能是负的。在这情况下，必须假设其 p(bj/ai) =0，然后重新计算，这就使得计算复杂化了。 下面介绍用拉格朗日乘子法求解R(D)函数，并用s作为参 量来表述率失真函数R(s)和失真函数D(s)。 由 (1)式知，当信源的概率分布p(x)固定，平均互信息仅仅 是试验信道p(bj/ai)的函数。 若先不考虑 (2)式的约束，约束条件 (3)式包含n个等式， 取拉格朗日乘子i(i1,2, n)分别与之对应；并取拉氏乘 子s与 (4)式对应。由此构成辅助函数：(2)(2)(3)(3)(4)(4)(1)(1)求极值，即为求(5) 式一阶导数等于零的方程组的解。已知平均互信息I(X;Y)是信道P的U型凸函数，所以，若极值存在，它一定是极小值。即求：得： -(6)-(6)(1)(1)(3)(3)(4)(4)经整理得结论：注：这时所得的结果是以s为参量的表达式，而不 是显式表达式，因而所得到的R(D)的表达式也是以s为 参量的表达式。参量s对应的限制条件为(4)式，它与允许的失真度 D有关，所以，以s为参量就相当于以D为参量。(4)(4)例6 设离散信源和接收变量：并设失真矩阵为:求该信源的信息率失真函数R(D)。 解：根据(4.2.4)式计算可得 ，由题已知，根据参量表达式按如下步骤进行。 第一步：由式(4.3.14)求第二步：由式(4.3.13)求第三步：由式(4.3.16)求D(s)，将上述结果代入式(4.3.16)有第四步：由式(4.3.17)求R(s) ：应用式(4.3.11)，还可求得此时的试验信道转移概率：4.4 4.4 连续无记忆信源的信息率失真函数连续无