九章率失真函数.ppt

《九章率失真函数.ppt》由会员分享，可在线阅读，更多相关《九章率失真函数.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、九章率失真函数 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望无失真信源编码和有噪信道编码告诉我们：只要信道的无失真信源编码和有噪信道编码告诉我们：只要信道的信息传输速率小于信道容量，总能找到一种编码方法信息传输速率小于信道容量，总能找到一种编码方法,使得使得在该信道上的信息传输的差错概率任意小；反之，若信道在该信道上的信息传输的差错概率任意小；反之，若信道的信息传输速率大于信道容量，则不可能使信息传输差错的信息传输速率大于信道容量，则不可能使信息传输差错概率任意

2、小。概率任意小。但是，无失真的编码并非总是必要的。但是，无失真的编码并非总是必要的。香农首先定义了信息率失真函数香农首先定义了信息率失真函数R(D)，并论述了关于这个，并论述了关于这个函数的基本定理。函数的基本定理。定理指出：在允许一定失真度定理指出：在允许一定失真度D的情况下，信源输出的信息的情况下，信源输出的信息传输率可压缩到传输率可压缩到R(D)值，这就从理论上给出了信息传输率与允值，这就从理论上给出了信息传输率与允许失真之间的关系，奠定了信息率失真理论的基础。许失真之间的关系，奠定了信息率失真理论的基础。信息率失真理论是进行量化、数模转换、频带压缩和数据信息率失真理论是进行量化、数模转

3、换、频带压缩和数据压缩的理论基础。压缩的理论基础。本章主要介绍信息率失真理论的基本内容，侧重讨论离散本章主要介绍信息率失真理论的基本内容，侧重讨论离散无记忆信源。无记忆信源。首先给出信源的失真度和信息率失真函数的定义与性质；首先给出信源的失真度和信息率失真函数的定义与性质；然后讨论离散信源和连续信源的信息率失真函数计算；在这基然后讨论离散信源和连续信源的信息率失真函数计算；在这基础上论述保真度准则下的信源编码定理。础上论述保真度准则下的信源编码定理。失真测度失真测度一、失真度一、失真度l从直观感觉可知，若允许失真越大，信息传输率可从直观感觉可知，若允许失真越大，信息传输率可 越小；若允许失真越

4、小，信息传输率需越大。越小；若允许失真越小，信息传输率需越大。l所以信息传输率与信源编码所引起的失真所以信息传输率与信源编码所引起的失真(或误差或误差)是有关的。是有关的。首先讨论首先讨论失真的测度失真的测度。离散无记忆信源离散无记忆信源U，信源变量，信源变量Uu1,u2,ur，概率分布为概率分布为P(u)P(u1),P(u2),P(ur)。信源符号通过信道传输到某接收端，接收端的信源符号通过信道传输到某接收端，接收端的接收变量接收变量V v1,v2,vs。对应于每一对对应于每一对(u,v)，我们指定一个非负的函数：，我们指定一个非负的函数：称为单个符号的称为单个符号的失真度失真度(或失真函数

5、或失真函数)。通常较小的通常较小的d值代表较小的失真，而值代表较小的失真，而d(ui,vj)0表示没有失真。表示没有失真。若信源变量若信源变量U有有r个符号，接收变量个符号，接收变量V有有s个符号，个符号，则则d(ui,vj)就有就有rs个个,它可以排列成矩阵形式，即：它可以排列成矩阵形式，即：它为失真矩阵它为失真矩阵D，是，是 rs 阶矩阵。阶矩阵。须强调须强调:这里这里假设假设U U是信源，是信源，V V是信宿，那么是信宿，那么U U和和V V之间必之间必有信道。有信道。实际实际这里这里U U指的是原始的未失真信源，而指的是原始的未失真信源，而V V是指失真以后是指失真以后的信源。的信源。

6、因此，从因此，从U U到到V V之间实际上是失真算法，所以这里的转移之间实际上是失真算法，所以这里的转移概率概率p(vp(vj j/u/ui i)是指一种失真算法，是指一种失真算法，有时又把有时又把p(vp(vj j/u/ui i)称为称为试验信道试验信道的转移概率，如图所示。的转移概率，如图所示。原始信源原始信源失真信源失真信源试验信道试验信道信道信道UVp(vj/ui)例例1 离散对称信源离散对称信源(r=s)。信源变量。信源变量Uu1,u2,ur，接收变，接收变量量V v1,v2,vs。定义单个符号失真度：。定义单个符号失真度：这种失真称为汉明失真。汉明失真矩阵是一方阵，对角线上的这种失

7、真称为汉明失真。汉明失真矩阵是一方阵，对角线上的元素为零，即：元素为零，即：对二元对称信源对二元对称信源(sr2)，信源，信源U0,1，接收变量，接收变量V0,1。在。在汉明失真定义下，失真矩阵为：汉明失真定义下，失真矩阵为：例例2 删除信源删除信源。信源变量。信源变量Uu1,u2,ur，接收变量，接收变量V v1,v2,vs(s=r+1)。定义其单个符号失真度为：。定义其单个符号失真度为：l其中接收符号其中接收符号vs作为一个删除符号。作为一个删除符号。l在这种情况下，意味着若把信源符号再现为删除符号在这种情况下，意味着若把信源符号再现为删除符号vs时，时，其失真程度要比再现为其他接收符号的

8、失真程度少一半。其失真程度要比再现为其他接收符号的失真程度少一半。l若二元删除信源若二元删除信源s 2，r3，U0,1，V0,1,2。失真度为：失真度为：则d(0,0)=d(1,2)=0 d(0,2)=d(1,0)=1d(0,1)=d(1,1)=1/2除j=s以外所有的j和i所有i 例例3 对称信源对称信源(s=r)。信源变量。信源变量Uu1,u2,ur，接收变，接收变量量V v1,v2,vs。失真度定义为：。失真度定义为：若信源符号代表信源输出信号的幅度值，这就是一种若信源符号代表信源输出信号的幅度值，这就是一种以方以方差表示的失真度差表示的失真度。它意味着幅度差值大的要比幅度差值小的所。它

9、意味着幅度差值大的要比幅度差值小的所引起的失真更为严重，严重程度用平方来表示。引起的失真更为严重，严重程度用平方来表示。当当 r3时，时，U0,1,2，V0,1,2，则失真矩阵为：，则失真矩阵为：上述上述三个例子三个例子说明了具体失真度的定义。一般情况下根据说明了具体失真度的定义。一般情况下根据实际信源的失真，可以定义不同的失真和误差的度量。另外实际信源的失真，可以定义不同的失真和误差的度量。另外还可以按其他标准，如引起的损失、风险、主观感觉上的差还可以按其他标准，如引起的损失、风险、主观感觉上的差别大小等来定义失真度别大小等来定义失真度d(u,v)。二、二、平均失真度平均失真度信源信源 U

10、和信宿和信宿 V 都是随机变量，故单个符号失真度都是随机变量，故单个符号失真度d(ui,vj)也是随机变也是随机变量。显然，规定了单个符号失真度量。显然，规定了单个符号失真度d(ui,vj)后，传输一个符号引起的平均后，传输一个符号引起的平均失真，即信源平均失真度：失真，即信源平均失真度：在在离散情况下离散情况下，信源，信源Uu1,u2,ur，其概率分布，其概率分布P(u)P(u1),P(u2),P(ur)，信宿，信宿V v1,v2,vs。若已知试验信道的传递概率为若已知试验信道的传递概率为P(vj/ui)时，则平均失其度为：时，则平均失其度为：l 若平均失真度若平均失真度D不大于我们所允许的

11、失真不大于我们所允许的失真D，即：，即：D D 称此为称此为保真度准则保真度准则。信源固定信源固定(给给定定P(u)，单单个符号失真度固定个符号失真度固定时时(给给定定d(ui,vj)，选择选择不同不同试验试验信道，相当于不同的信道，相当于不同的编码编码方法，所得的平均失方法，所得的平均失真度是不同的。真度是不同的。有些有些试验试验信道信道满满足足D D，而有些，而有些试验试验信道信道DD。凡凡满满足保真度准足保真度准则则-平均失真度平均失真度D D的的试验试验信通称信通称为为-D失真失真许许可的可的试验试验信道。信道。把所有把所有D失真失真许许可的可的试验试验信道信道组组成一个集合，用符号成

12、一个集合，用符号BD表表示，即：示，即：BD=P(vj/ui)：D D信息率失真函数及其性质信息率失真函数及其性质一、信息率失真函数的定义一、信息率失真函数的定义 信源给定，且又具体定义了失真函数以后，总希望在满足信源给定，且又具体定义了失真函数以后，总希望在满足一定失真的情况下，使信源传输给收信者的信息传输率一定失真的情况下，使信源传输给收信者的信息传输率R尽可尽可能地小。即在满足保真度准则下，寻找信源必须传输给收信者能地小。即在满足保真度准则下，寻找信源必须传输给收信者的信息率的信息率R的下限值的下限值-这个下限值与这个下限值与D有关。有关。从接收端来看，就是在满足保真度准则下，寻找再现信

13、源从接收端来看，就是在满足保真度准则下，寻找再现信源消息所必须获得的最低平均信息量。消息所必须获得的最低平均信息量。而接收端获得的平均信息量可用平均互信息而接收端获得的平均信息量可用平均互信息I(U;V)来表示，来表示，这就变成了在满足保真度准则的条件下，寻找平均互信息这就变成了在满足保真度准则的条件下，寻找平均互信息I(U;V)的最小值。的最小值。寻找平均互信息寻找平均互信息I(U;V)的最小值。而的最小值。而BD是所有满足保真是所有满足保真度准则的试验信道集合，因而可以在度准则的试验信道集合，因而可以在D失真许可的试验信道失真许可的试验信道集合集合BD中寻找一个信道中寻找一个信道P(vj|

14、ui)，使，使I(U;V)取极小值。取极小值。由于平均互信息由于平均互信息I(U;V)是是P(vj|ui)的的U型凸函数，所以在型凸函数，所以在BD集合中，极小值存在。这个最小值就是在集合中，极小值存在。这个最小值就是在D D的条件下，的条件下，信源必须传输的最小平均信息量信源必须传输的最小平均信息量。即：。即：R(D)-信息率失真函数或简称率失真函数率失真函数。单位是奈特信源符号 或 比特信源符号率失真函数给出了熵压缩编码可能达到的最小熵率率失真函数给出了熵压缩编码可能达到的最小熵率与失真的关系，其逆函数称为失真率函数，表示一与失真的关系，其逆函数称为失真率函数，表示一定信息速率下所可能达到

15、的最小的平均失真。定信息速率下所可能达到的最小的平均失真。二、信息率失真函数的性质二、信息率失真函数的性质允许失真度D的下限可以是零，即不允许任何失真的情况。1、R(D)的定义域R(D)的定义域为 且：解：解：解：解：例例例例4 4 设设设设试验信道输入符号集试验信道输入符号集试验信道输入符号集试验信道输入符号集 ，各符号对应概率分各符号对应概率分各符号对应概率分各符号对应概率分别为别为别为别为)=1/3,1/3,1/3)=1/3,1/3,1/3 ，失真矩阵如下所示，求，失真矩阵如下所示，求，失真矩阵如下所示，求，失真矩阵如下所示，求 和和和和 以及相应的试验信道的转移概率矩阵。以及相应的试验

16、信道的转移概率矩阵。以及相应的试验信道的转移概率矩阵。以及相应的试验信道的转移概率矩阵。令对应最小失真度令对应最小失真度令对应最小失真度令对应最小失真度 的的的的 ，其它为，其它为，其它为，其它为“0”0”，可得对应可得对应可得对应可得对应 的试验信道转移概率矩阵为的试验信道转移概率矩阵为的试验信道转移概率矩阵为的试验信道转移概率矩阵为 上式中第二项最小，所以令上式中第二项最小，所以令上式中第二项最小，所以令上式中第二项最小，所以令 ，可得对应，可得对应，可得对应，可得对应 的试验信道转移概率矩阵为的试验信道转移概率矩阵为的试验信道转移概率矩阵为的试验信道转移概率矩阵为 2、R(D)是关于平均

17、失真度是关于平均失真度D的下凸函数的下凸函数 设设 为任意两个平均失真，为任意两个平均失真，则有：，则有：3、R(D)是是 区间上的连续和严格单调递减函数。区间上的连续和严格单调递减函数。由信息率失真函数的下凸性可知，由信息率失真函数的下凸性可知，R(D)在在 上连续。又由上连续。又由R(D)函数的非增性且不为常数知，函数的非增性且不为常数知，R(D)是是区间区间 上的严格单调递减函数。上的严格单调递减函数。信息率失真函数的一般形状信息率失真函数的一般形状 已知信源的概率分布P(u)和失真函数d(u,v)，就可求得信源的R(D)函数。原则上它与信道容量一样，即在有约束条件下求极小值的问题。也就

18、是适当选取试验信道P(v|u)使平均互信息最小化，其约束条件为:离散无记忆信源的信息率失真函数离散无记忆信源的信息率失真函数 对对于等概、于等概、对对称失真的信源，存在一个与失真矩称失真的信源，存在一个与失真矩阵阵具有具有同同样对样对称性的称性的转转移概率分布达到率失真移概率分布达到率失真R(D)。解：由解：由例例5有一个二元等概平稳无记忆信源有一个二元等概平稳无记忆信源 ，接收符号集接收符号集为为 ,且失真矩阵为且失真矩阵为：求率失真函数求率失真函数R(D)。由于信源等概分布，失真函数具有对称，因此，存在着与失真由于信源等概分布，失真函数具有对称，因此，存在着与失真矩阵具有同样对称性的转移概

19、率分布达到率失真矩阵具有同样对称性的转移概率分布达到率失真R(D)，该转，该转移概率矩阵可写为：移概率矩阵可写为：由于由于 ，因此对于任何有限平均失真，因此对于任何有限平均失真，必须必须 。于是转移概率矩阵变为：。于是转移概率矩阵变为：对应此转移概率矩阵的平均失真：因此 可求出此时的互信息为：相应的率失真函数相应的率失真函数R(D)如图所示。如图所示。保真度准则下的信源编码定理保真度准则下的信源编码定理定理定理 (保真度准则下的信源编码定理，香农第三定理保真度准则下的信源编码定理，香农第三定理)设设R(D)为为一一离离散散无无记记忆忆信信源源的的信信息息率率失失真真函函数数，并并且且有有有有限

20、限的的失失真真测测度度D。对对于于任任意意D ，以以及及任任意意长长的的码码长长k，一定存在一种信源编码，一定存在一种信源编码C，其码字个数为，其码字个数为 使编码后码的平均失真度使编码后码的平均失真度 。定理的含定理的含义义是：只要是：只要码长码长k足足够长够长，总总可以找到一种信源可以找到一种信源编编码码，使，使编码编码后的信息后的信息传输传输率略大于率略大于(直至无限逼近直至无限逼近)率失真函数率失真函数R(D)，而，而码码的平均失真度不大于的平均失真度不大于给给定的允定的允许许失真度，即：失真度，即：由于由于R(D)为给为给定定D前提下信源前提下信源编码编码可能达到的下限，可能达到的下限，所以所以香香农农第三定理即第三定理即说说明了：明了：达到此下限的最佳信源达到此下限的最佳信源编码编码是存在的是存在的