信息论课件chap9[1]

《信息论课件chap9[1]》由会员分享，可在线阅读，更多相关《信息论课件chap9[1]（118页珍藏版）》请在金锄头文库上搜索。

1、第九章 率失真函数,引言,Shannon三个编码定理 无失真信源编码定理 RH 有噪声信道编码定理 RC 率失真信源编码定理 有失真时能做什么 结论：只要信道传输速率小于信道容量，总能找到一种编码方法使得差错概率任意小。反之则不可达 问题：并不是所有时刻都需要无失真，有时候需要数据压缩，此时率失真编码出现 ，其研究在允许一定失真的前提下，信源可以压缩的最大程度。,引言,不等长编码平均长度不超过HL(U)/logD+1/L可以无失真 等长编码HL(U)+e/logD失真不会超过给定值 传输信息允许失真，信息率可以下降,引言,香农论述了限定失真范围内的信源编码问题，定义了信息率失真函数R(D)，并

2、论述了关于这个函数的基本定理。 定理指出：在允许一定失真度D的情况下，信源输出的信息传输率可压缩到R(D)值，这就从理论上给出了信息传输率与允许失真之间的关系，奠定了信息率失真理论的基础。 信息率失真理论是进行量化、数模转换、频带压缩和数据压缩的理论基础。,一般概念与定义,系统模型,有扰信道,信源,信源编码,信道,信源译码,信宿,广义无扰信道,信道编码,信道译码,干扰,u,v,系统模型,简化后的信道,信源,信源编码器,无噪信道,信源译码器,信宿,试验信道,u,v,有失真信源编码的问题,无失真的信源通过有噪信道传输的问题,I(X;Y),系统模型,结论： 在试验信道环境下，率失真的研究目标转化为在

3、给定允许失真条件下，是否可以设计一种信源编码使信息传输速率为最低。,信源,试验信道,信宿,u,v,P(u|v),注意: 这里假设U是信源，V是信宿，那么U和V之间必有信道。 实际这里U指的是原始的未失真信源，而V是指失真以后的信源。因此，从U到V之间实际上是失真算法，所以这里的转移概率p(vj/ui)是指一种失真算法， 有时又把p(vj/ui) 称为试验信道的转移概率，如图所示。,系统模型,例：H(U)=2.24,失真度,由来 直观上看，允许的失真越大，则信息传输的速率可 越小；若允许失真越小，信息传输率需越大。信息传输率与信源编码所引起的失真(或误差)是有关的,想定量描述信息率与失真的关系，

4、先定义失真的测度,单符号失真度,离散无记忆信源U，信源变量Uu1,u2,ur，概率分布为P(u)P(u1),P(u2),P(ur) 。 信源符号通过信道传输到某接收端，接收端的接收变量V v1,v2,vs 。 对应于每一对(u,v)，指定一个非负的函数：,称为单个符号的失真度(或失真函数)。 通常较小的d 值代表较小的失真，而d(ui,vj)0表示没有失真。,若信源变量U有r个符号，接收变量V有s个符号，则d(ui,vj)就有rs个,它可以排列成矩阵形式，即：,称之为失真矩阵D，是 rs 阶矩阵。,单符号失真度,例 离散对称信源(r=s)。信源变量Uu1,u2,ur ，接收变量V v1,v2,

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

6、d(0,2)=d(1,0)=1 d(0,1)=d(1,1)=1/2,单符号失真度,例 平方误差失真测度 信源输出符号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 则失真测度矩阵为,单符号失真

7、度,结论： 上述例子说明了具体失真度的定义。一般情况下根据实际信源的失真，可以定义不同的失真和误差的度量。另外还可以按其他标准，如引起的损失、风险、主观感觉上的差别大小等来定义失真度d(u,v)。,单符号失真度,常用失真度小结： 前三种适合连续信源，后一种适合离散信源,单符号失真度,序列失真度,设,取自符号集A（A中元素个数为n）；,，,取自符号集B （B中元素个数为m）。,，,则序列失真度定义为：,序列失真函数矩阵共有nN *mN,对二元对称信源(sr2)，信源U0,1，接收变量V0,1。在汉明失真定义下，失真矩阵为：,对信源做二次扩展，X=x1x2 Y=y1y2,序列失真度,平均失真度,信

8、源 U 和信宿 V 都是随机变量，故单个符号失真度d(ui,vj) 也是随机变量。传输一个符号引起的平均失真即信源平均失真度：,在离散情况下，信源Uu1,u2,ur ，其概率分布P(u)P(u1),P(u2),P(ur) ，信宿V v1,v2,vs 。 若已知试验信道的传递概率为P(vj/ui)时，则单符号平均失真度为：,同理，可定义序列平均失真为：,平均失真度是从总体上度量整个通信系统失真的大小。,平均失真度,上式中Di表示第i位上单个符号的平均失真度，当离散信源为平稳信源时其与单个符号的相同。,例：等概率信源,，通过信道转移概率矩阵为,的信道传输，失真测度为平方误差失真测度，求平均失真？,

9、平均失真度,例：离散无记忆信源,，离散无记忆信道,失真测度为汉明失真测度，求平均失真？,平均失真度,对信源做二次扩展，可得扩展信源概率分布：,，对离散无记忆信道有,对离散无记忆N次扩展序列的讨论看归结为对一维扩展序列的讨论。,平均失真度,若平均失真度D不大于我们所允许的失真D，即： D D 称此为保真度准则。,有些试验信道满足D D，而有些试验信道DD。 凡满足保真度准则-平均失真度D D的试验信道通称为-D失真许可的试验信道。 把所有D失真许可的试验信道组成一个集合，用符号BD表示，即： BD=P (vj / ui)： D D,D失真许可的试验信道,小结,平均失真度的引入，给了我们一种可能，

10、即把能控制的允许的平均失真度D作为对信道传递概率p(bj|ai)的一种约束条件，在此约束条件下，求解试验信道的信息传输速率的最小值并赋予该最小值某种使用价值。,率失真函数及其性质,率失真函数定义,问题的引入： 当信源给定，且失真函数定义明确后，希望在满足一定失真的情况下，使得信源传输给信宿的信息传输速率尽可能小，也就是在满足保真度准则下，希望寻找R的下限。 研究思路： R的最小实质上是平均互信息I(X;Y)最小，所以问题转化为满足保真度准则（一定的D下）时如何求最小的平均互信息。,有失真信源编码的问题,无失真的信源通过有噪信道传输的问题,I(X;Y),信息率失真函数,当失真度被确定，信源X给定

11、时：,率失真函数定义,就可通过选择适当的信道（p(y|x)），使DD0,许可试验信道：凡满足保真度准则DD0的信道。,用PD表示：,回忆：在信源给定条件下，信息传输速率R是信道转移概率p(Y|X)的U型凸函数。,因此，在PD中，总可找到某一试验信道，使R=I(X;Y)达到最小值，记此最小值为R(D):,R(D)称为信源的信息速率失真函数，简称率失真函数。,率失真函数定义,R(D)-信息率失真函数或率失真函数。单位是奈特信源符号或比特信源符号,意义： 对于给定的信源，在满足保真度准则条件下，信源必须传输的最小平均信息量，即，信息允许压缩的最低值。,率失真函数定义,率失真函数R(D)给出了熵压缩编

12、码可能达到的最小熵率与失真的关系，其逆函数称为失真率函数D(R)，表示一定信息速率下所可能达到的最小的平均失真。,1、极值性 平均互信息I(X;Y)是信道转移概率已知（信道固定）情况下，关于信源概率分布p(xi)的上凸函数。所以求信道容量本质上是求该极大值。 平均互信息I(X;Y)是信源概率分布p(xi)已知（信源固定）时，关于信道转移概率p(yj|xi)的下凸函数。所以求信息率失真函数本质上是求在何种试验信道下得到该极小值,率失真函数与信道容量比较,2、特性 信道容量C一旦给定，只反映信道特性，与信源特性无关。 信息率失真函数R(D)一旦给定只反映信源特性，与信道特性无关。 3、解决的问题

13、信道容量是为了解决通信的可靠性问题，是信息传输的理论基础，可靠性是通过信道编码增加信息的冗余度来实现。 信息率失真函数是为了解决通信的有效性问题，是信源压缩的理论基础，有效性是通过信源编码减少信息的发送量（冗余度）来实现。,率失真函数与信道容量比较,4、研究的意义 信道容量充分利用已知信道，使得传送的信息量最大而错误概率任意小，以此得到高可靠性。 信息率失真函数在信源和允许的失真度D已知条件下，使得信源必须传送给信宿的信息量最小，以此提高有效性。,率失真函数与信道容量比较,信息率失真函数的性质,1.R(D)的值域 率失真函数的值域为 0 R（D） H（X）,2. R(D)的定义域,注意：所谓定

14、义域，就是在信源和失真函数已知的情况下，讨论允许平均失真度D的最小和最大取值问题。,率失真函数的定义域为 且：,因为平均失真度D是失真函数d(u,v)的数学期望，而后者为非负值，所以平均失真度D为非负值。当D=0时，表示不允许任何失真，有R(D=0)=Rmax(D)=H(X)。,(1) D的最小值Dmin,D能否达到其下限值0，与单符号的d( xi , yj )有关。,求D的最小值，即在失真测度矩阵中，对每一个xi，找一个最小的d( xi , yj )，然后对所有的i=1,2,I求统计平均值。,信息率失真函数的性质,小结： 只有当失真测度矩阵中，每一行至少有一个零元素，才可能有Dmin=0，当

15、Dmin=0时，表示不允许任何失真，此时R(D)=H(X) 对于连续信源，因为其H(U)为无穷大，所以无法在限定信道容量的信道中无失真的传递，所以其D一定存在一个最小下限。,信息率失真函数的性质,在运行一定失真的前提下，当R(D)达到其最小值Rmin(D)=0时，对应的失真最大，即达到D的上界值Dmax,(2) D的最大值Dmax,信息率失真函数的性质,关于w(yj)求极小值，可这样选择w(yj)的分布：,当,取最小值时，选,当,取其他值时，选,所以，,在失真测度矩阵中，将每一列的每个元素乘上相应的q(xi)，再把它们加起来，得到J个和值，其中找一个最小值，就是Dmax,信息率失真函数的性质,解：,例 设试验信道输入符号集 ，各符号对应概率分别为)=1/3,1/3,1/3 ，失真矩阵如下所示，求 和 以及相应的试验信道的转移概率矩阵。,令对应最小失真度 的 ，其它为“0”，可得对应 的试验信道转移概率矩阵为,上式中第二项最小，所以令 ， ，可得对应 的试验信道转移概率矩阵为,5/3,信息率失真函数的性质,例一信源含有三个消息，概率分布为p1=0.2，p2=0.3，p3=0.5，失真测度矩阵为,求Dmin和Dmax。,解,信息率失真函数的性质,信息率失真函数的性质,小结： R(D)的定义域