第4章 信息率失真函数.ppt

第四章第四章 信息率失真函数信息率失真函数 无失真信源编码和有噪信道编码（香农第一定理和香农无失真信源编码和有噪信道编码（香农第一定理和香农第二定理）告诉我们：第二定理）告诉我们：只要信道的信息传输速率小于信道容量，总能找到一种只要信道的信息传输速率小于信道容量，总能找到一种编码方法，使得在该信道上的信息传输的差错概率任意小；编码方法，使得在该信道上的信息传输的差错概率任意小；反之，若信道的信息传输速率大于信道容量，则不可能使信反之，若信道的信息传输速率大于信道容量，则不可能使信息传输差错概率任意小息传输差错概率任意小但是，无失真的编码但是，无失真的编码并非并非总是必要的总是必要的原始图像原始图像红色图像红色图像绿色图像绿色图像蓝色图像蓝色图像原始图像和限失真图像原始图像和限失真图像原始图像和限失真图像原始图像和限失真图像香农首先定义了信息率失真函数香农首先定义了信息率失真函数R(D)，，并论述了关于这个并论述了关于这个函数的基本定理函数的基本定理定理指出：在允许一定失真度定理指出：在允许一定失真度D的情况下，信源输出的信息的情况下，信源输出的信息传输率可压缩到传输率可压缩到R(D)值，这就从理论上给出了信息传输率与允值，这就从理论上给出了信息传输率与允许失真之间的关系，奠定了信息率失真理论的基础。

许失真之间的关系，奠定了信息率失真理论的基础信息率失真理论是进行量化、数模转换、频带压缩和数据信息率失真理论是进行量化、数模转换、频带压缩和数据压缩的理论基础压缩的理论基础本章本章主要介绍主要介绍信息率失真理论的基本内容，重点讨论离散信息率失真理论的基本内容，重点讨论离散无记忆信源无记忆信源l给出信源的失真度和信息率失真函数的定义与性质；给出信源的失真度和信息率失真函数的定义与性质；l讨论离散信源和连续信源的信息率失真函数计算；讨论离散信源和连续信源的信息率失真函数计算；l在此基础上论述保真度准则下的信源编码定理在此基础上论述保真度准则下的信源编码定理 4.1 失真测度失真测度一、失真度一、失真度•从直观感觉可知，若允许失真越大，信息传输率就可越小；从直观感觉可知，若允许失真越大，信息传输率就可越小；若允许失真越小，信息传输率需越大若允许失真越小，信息传输率需越大•所以信息传输率与（信源）编码所引起的失真所以信息传输率与（信源）编码所引起的失真(或误差或误差)是是有关的 首先讨论首先讨论失真的测度失真的测度 离散无记忆信源离散无记忆信源X，信源符号集，信源符号集X＝＝{a1,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)就有就有r×s个个,它可以排列成矩阵形式，即：它可以排列成矩阵形式，即：该失真矩阵该失真矩阵D，，是是 r×s 阶矩阵实际实际这里这里X X指的是原始的未失真信源，而指的是原始的未失真信源，而Y Y是指失真以后是指失真以后的信源如果的信源如果假设假设X X是信源，是信源，Y Y是信宿，那么是信宿，那么X X和和Y Y之间必有信之间必有信道从从X X到到Y Y之间实际上是失真算法，所以这里的转移概率之间实际上是失真算法，所以这里的转移概率p(b(bj j/ /ai i) )是指一种失真算法，是指一种失真算法，有时又把有时又把 p(b(bj j/ /ai i) ) 称为称为试验信道试验信道的转移概率，如图所的转移概率，如图所示。

示原始信源原始信源失真信源失真信源试验信道试验信道信道信道XYp (bj/ai) [例例1] 离散对称信源离散对称信源(r=s)，，“0-1”失真失真信源X＝＝{a1,a2,…ar} ，，接收接收Y＝＝ {b1,b2,…bs}定义单个符号失真度：定义单个符号失真度：这种失真称为汉明失真汉明失真矩阵是一方阵，对角线上的这种失真称为汉明失真汉明失真矩阵是一方阵，对角线上的元素为零，即：元素为零，即： 　　　对二元对称信源　　　对二元对称信源(s＝＝r＝＝2)，，信源信源X＝＝{0,1}，，接收接收变量变量Y＝＝{0,1}在汉明失真定义下在汉明失真定义下，，失真矩阵为：失真矩阵为： [例例2] 删除信源删除信源信源信源X＝＝{a1,a2,…ar} ，，接收接收Y＝＝ {b1,b2,…bs} (s = r+1) 定义其单个符号失真度为：定义其单个符号失真度为：•其中接收符号其中接收符号bs作为一个删除符号作为一个删除符号•此时，意味着若把信源符号再现为删除符号此时，意味着若把信源符号再现为删除符号bs时，其失真时，其失真程度要比再现为其他接收符号的失真程度少一半程度要比再现为其他接收符号的失真程度少一半。

•二元删除信源二元删除信源 r ＝＝2，， s ＝＝3，，X＝＝{0,1}，，Y＝＝{0,1 ,2} 失真度为：失真度为： 则d(0,0)=d(1,1)=0 d(0,1)=d(1,0)=1d(0,2)=d(1,2)=1/2除除j=s以外所有的以外所有的j和和i所有所有i [例３例３] 对称信源对称信源(s = r) 信源信源X＝＝{a1,a2,…ar} ，，接收接收Y＝＝ {b1,b2,…bs} 若若失真度定义为：失真度定义为：如果信源符号代表信源输出信号的幅度值，这就是一种如果信源符号代表信源输出信号的幅度值，这就是一种平平方误差失真度方误差失真度它意味着幅度差值大的要比幅度差值小的所引它意味着幅度差值大的要比幅度差值小的所引起的失真更为严重，其严重的程度用平方来表示起的失真更为严重，其严重的程度用平方来表示 当当 r＝＝3时，时， Ｘ＝Ｘ＝{0,1,2}，Ｙ＝，Ｙ＝{0,1,2} ，，则失真矩阵为：则失真矩阵为：上述例子说明了失真度的具体定义上述例子说明了失真度的具体定义一般情况下根据实际信源的失真，可以定义不同的失真和一般情况下根据实际信源的失真，可以定义不同的失真和误差的度量。

另外还可以按其他标准，如引起的损失、风险、误差的度量另外还可以按其他标准，如引起的损失、风险、主观感觉上的差别大小等来定义失真度主观感觉上的差别大小等来定义失真度d(a,b)二、序列失真度二、序列失真度设设 ，其中，其中取自信源符号集取自信源符号集A；； 其中其中取自取自信宿信宿符号集符号集B则序列失真度定义为：则序列失真度定义为： 三、三、 平均失真度平均失真度信源信源 X 和信宿和信宿 Y 都是随机变量，故单个符号失真度都是随机变量，故单个符号失真度d(ai,bj) 也是随机变量也是随机变量规定了单个符号失真度规定了单个符号失真度d(ai,bj) 后，后，传输一个符号引起的平均传输一个符号引起的平均失真，即信源平均失真度失真，即信源平均失真度：： 在在离散情况下离散情况下，信源，信源X＝＝{a1,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，而有些试验信道，而有些试验信道D＞＞D0凡满足保真度准则凡满足保真度准则-----平均失真度平均失真度D   D0的试验信通称的试验信通称为为 ----D D失真许可的试验信道失真许可的试验信道失真许可的试验信道失真许可的试验信道把所有把所有D失真许可的试验信道组成一个集合，用符号失真许可的试验信道组成一个集合，用符号PD表表示，则：示，则： PD={p (bj / ai)：： D   D0}4.2 4.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 i(i＝＝1,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 连续无记忆信源的信息率失真函数连续无记忆信源的信息率失真函数研研究究连连续续信信源源的的信信息息率率失失真真函函数数比比离离散散信信源源更更有有实实际际意意义义，，因因为为连连续续随随机机变变量量不不可可能能用用有有限限比比特特加加以以精精确确描描述述，，即即连连续续信信源源信信息息量量为为无无限限大大，，传传送送无无限限大大信信息息量量既既无无必必要要，，也不可能也不可能所以连续信源的讨论都属于限失真范畴所以连续信源的讨论都属于限失真范畴一、连续无记忆信源的信息率失真函数的定义一、连续无记忆信源的信息率失真函数的定义 连续信源的平均失真度定义为：连续信源的平均失真度定义为： 通过试验信道获得的平均互信息为：通过试验信道获得的平均互信息为：同样，确定一允许失真度同样，确定一允许失真度D，凡满足平均失真小于，凡满足平均失真小于D的所有的所有试验信道的集合记为试验信道的集合记为PD，则连续信源的信息率失真函数定义，则连续信源的信息率失真函数定义为：为： 二、高斯信源的信息率失真函数二、高斯信源的信息率失真函数 对对高高斯斯信信源源，，在在一一般般失失真真函函数数下下，，其其率率失失真真函函数数是是很很难难求求得得的的，，但但在在平平方方误误差差失失真真度度量量下下，，其其率率失失真真函函数数有有简简单单的的封闭表达式。

封闭表达式 对对平平方方误误差差失失真真，，试试验验信信道道输输入入符符号号和和输输出出符符号号之之间间失失真为：真为： 对应的平均失真度为：对应的平均失真度为：在平方误差失真下，设允许失真为在平方误差失真下，设允许失真为D，则高斯信源，则高斯信源 的率失真函数为：的率失真函数为：下图表示当下图表示当 时，时， 的曲线4.5 4.5 保真度准则下的信源编码定理保真度准则下的信源编码定理 定理定理4.1 (保真度准则下的信源编码定理，保真度准则下的信源编码定理，香农第三定理香农第三定理) 设设R(D)为为一一离离散散无无记记忆忆信信源源的的信信息息率率失失真真函函数数，，并并且且有有有有限限的的失失真真测测度度D对对于于任任意意 D ，，以以及及任任意意长长的的码长码长k，一定存在一种信源编码，一定存在一种信源编码C，其码字个数为，其码字个数为 使编码后码的平均失真度使编码后码的平均失真度 定理的含定理的含义义是：是：只要只要码长码长k足足够长够长，，总总可以找到一种信源可以找到一种信源编编码码，使，使编码编码后的信息后的信息传输传输率略大于率略大于(直至无限逼近直至无限逼近)率失真函数率失真函数R(D)，而，而码码的平均失真度不大于的平均失真度不大于给给定的允定的允许许失真度，失真度，即：即： 由于由于R(D)为给为给定定D前提下信源前提下信源编码编码可能达到的可能达到的传传信率的信率的下限，下限， 所以香所以香农农第三定理第三定理说说明了明了：： 达到此下限的最佳信源达到此下限的最佳信源编码编码是存在的是存在的。

实际的信源编码实际的信源编码(无失真编码或先进行限失真编码后再进无失真编码或先进行限失真编码后再进行无失真编码行无失真编码)的最终目标是尽量接近最佳编码，使编码信息的最终目标是尽量接近最佳编码，使编码信息传输率接近最大值，或者对给定的信源用尽量少的编码符号传输率接近最大值，或者对给定的信源用尽量少的编码符号进行传输，而同时又能保证译码后能无失真地恢复信源进行传输，而同时又能保证译码后能无失真地恢复信源编码后信息传输率的提高使每个编码符号能携带尽可能编码后信息传输率的提高使每个编码符号能携带尽可能多的信息量，多的信息量，-----使得传输同样多的信源总信息量所需的码符号数减使得传输同样多的信源总信息量所需的码符号数减少；少；------使所需的单位时间传输信道单位时间信道容量使所需的单位时间传输信道单位时间信道容量Ct减少，或在减少，或在Ct不变的前提下使传输时间缩短，从而提高通信不变的前提下使传输时间缩短，从而提高通信的效率。