第21讲——无记忆信源的有失真编码(1)

1、n 由于信道的干扰，信息在传输过程中也会产生由于信道的干扰，信息在传输过程中也会产生差错或失真；差错或失真；n 对信源无失真压缩的极限是熵，如果再继续压对信源无失真压缩的极限是熵，如果再继续压缩就要失真。缩就要失真。n 信宿的灵敏度和分辨力有限，无需要求传输过信宿的灵敏度和分辨力有限，无需要求传输过程中信息绝对无失真；程中信息绝对无失真；n 允许信息有某些失真，可以降低信息传输速率，允许信息有某些失真，可以降低信息传输速率，从而降低通信成本。从而降低通信成本。 结论：失真不可避免，有时甚至必要结论：失真不可避免，有时甚至必要失失 真真n 通过压缩所得到的编码序列不能完全恢复原来信源的通过压缩所

2、得到的编码序列不能完全恢复原来信源的信息，是信息，是有失真信源编码；有失真信源编码；n 希望在不大于一定的编码速率的条件下，使平均失真希望在不大于一定的编码速率的条件下，使平均失真限制到最小；或者在平均失真不大于某个值的条件下，限制到最小；或者在平均失真不大于某个值的条件下，使编码速率限制到最小（使编码速率限制到最小（限失真信源编码）限失真信源编码）。n 从信息论的观点处理数据压缩的学科称为从信息论的观点处理数据压缩的学科称为信息率失真信息率失真理论理论，是数据压缩的基本理论。它确定了为满足某一，是数据压缩的基本理论。它确定了为满足某一给定保真度准则恢复信源消息理论上传送每信源符号给定保真度准

3、则恢复信源消息理论上传送每信源符号所需的平均的二进制数字数。所需的平均的二进制数字数。有失真信源编码有失真信源编码有失真与无失真编码实例有失真与无失真编码实例信源符号信源符号u1u2u3u4u5p(ui)不等长编码不等长编码等长编码等长编码允许失真允许失真0.2500000000.2501001010.25100101001011110011H(U)=1.944bit1) 不等长编码：不等长编码：R=2.25bits2) 等长编码：等长编码： R=3bit3) 允许失真编码：允许失真编码：R=2bitlogRnD失真函数失真函数12,.,KUVa aa0, ,0 ,i

4、jijijdd ua vaij 2,d u vuvd u vuv 或失真函数失真函数根据具体实际情况决定，可以根据具体实际情况决定，可以若信源变量若信源变量U有有r个符号，接收变量个符号，接收变量V有有s个符号，个符号， 则则d(ui,vj)就有就有rs个个,它可以排列成矩阵形式，即：它可以排列成矩阵形式，即：),(.),(),(:.:),(.),(),(),(.),(),(212221212111srrrssvudvudvudvudvudvudvudvudvudD失真矩阵失真矩阵这里这里U指原始的未失真信源，而指原始的未失真信源，而V是指失真以后的信源。是指失真以后的信源。因此，从因此，从U

5、到到V之间实际上是失真算法，即转移概率之间实际上是失真算法，即转移概率p(vj/ui)也也就是一种失真算法，有时又把就是一种失真算法，有时又把p(vj/ui) 称为称为试验信道试验信道的转移概的转移概率。率。I(U;V)就是信源通过编码器传输的信息速率。就是信源通过编码器传输的信息速率。试验信道试验信道 例例1 离散对称离散对称信源变量信源变量U=u1,u2,ur ，接收变量，接收变量V= v1,v2,vs ，r=s。定义单个符号失真度为：。定义单个符号失真度为：这种失真称为汉明失真。汉明失真矩阵是一方阵，这种失真称为汉明失真。汉明失真矩阵是一方阵，对角线上的元素为零，即：对角线上的元素为零，

6、即：jijijivuvuvud10),(rrD0.11:.:1.011.10 对二元对称信源对二元对称信源(s=r=2)，信源，信源U=0,1，接收变量，接收变量V=0,1。在汉明失真定义下，失真矩阵为：。在汉明失真定义下，失真矩阵为：0110D 例例2 删除信源删除信源。信源变量。信源变量U=u1,u2,ur ，接收变量，接收变量V= v1,v2,vs (s = r+1) 。定义其单个符号失真度为：。定义其单个符号失真度为： 其中接收符号其中接收符号vs作为一个删除符号。作为一个删除符号。 在这种情况下，意味着若把信源符号再现为删除符号在这种情况下，意味着若把信源符号再现为删除符号vs时，时

7、，其失真程度要比再现为其他接收符号的失真程度少一半。其失真程度要比再现为其他接收符号的失真程度少一半。 若二元删除信源若二元删除信源s 2，r3， U0,1，V0,1 ,2 。失真度为：失真度为：02111210Dd(0,0)=d(1,2)=0 d(0,2)=d(1,0)=1d(0,1)=d(1,1)=1/2sjjijivudji 2/110),(除除j=s以外所有的以外所有的j和和i所有所有i 例例3 对称信源对称信源(s = r) 。信源变量。信源变量U=u1,u2,ur ，接收变量，接收变量 V= v1,v2,vs 。失真度定义为：。失真度定义为：若信源符号代表信源输出信号的幅度，这是一

8、种若信源符号代表信源输出信号的幅度，这是一种以方差以方差表示的失真度表示的失真度。它意味着幅度差值大的要比幅度差值小的。它意味着幅度差值大的要比幅度差值小的所引起的失真更为严重，严重程度用平方来表示。所引起的失真更为严重，严重程度用平方来表示。 当当 r=3时，时， U=0,1,2，V=0,1,2 ，则失真矩阵为，则失真矩阵为：2)(),(ijjiuvvud014101410D一般情况下根据实际信源的失真，可以定义不一般情况下根据实际信源的失真，可以定义不同的失真和误差的度量。另外还可以按其他标准同的失真和误差的度量。另外还可以按其他标准，如引起的损失、风险、主观感觉上的差别大小，如引起的损失

9、、风险、主观感觉上的差别大小等来定义失真度等来定义失真度d(u,v)。平均失真平均失真,ddEvdVvUuu是上的随机变量,定义平均失真 ,iijijijjiijq p dpva ua |,vudq u pv u d u v dudv连续随机变量L1L111Lu,vdu,v,11du,vE,LlllLLllllld u vLd u vdLL维矢量之间失真 平均失真 保真度准则保真度准则n 若平均失真度若平均失真度 不大于所允许的失真不大于所允许的失真D, 即即 称为称为保真度准则保真度准则n 当信源当信源q(u)固定固定, 单个符号失真度单个符号失真度d(ui,vj)固定，选择不同的固定，选择

10、不同的试验信道试验信道p(vj/ui), 相当于选择不同的编码方法。相当于选择不同的编码方法。n D失真许可的试验信道失真许可的试验信道 ddDDBp:D,iijijijjiijv udq p dpva ua信息速率失真函数信息速率失真函数从从D失真许可的试验信道中选择一种信息率为最小失真许可的试验信道中选择一种信息率为最小 min;ijBDpR DI U V由于平均互信息由于平均互信息I(U;V)是是P(vj / ui)的的U型凸函数，所以在型凸函数，所以在BD集合中，极小值存在。这个最小值就是在集合中，极小值存在。这个最小值就是在 的条件下，的条件下，信源必须传输的最小平均信息量，信源必须

11、传输的最小平均信息量，称为信息率失真函数或称为信息率失真函数或简称率失真函数。简称率失真函数。单位是奈特信源符号；比特信源符号单位是奈特信源符号；比特信源符号dD 率失真函数给出了熵压缩编码可能达到的最小熵率与失率失真函数给出了熵压缩编码可能达到的最小熵率与失真的关系，其逆函数称为失真率函数，表示一定信息速真的关系，其逆函数称为失真率函数，表示一定信息速率下可能达到的最小的平均失真。率下可能达到的最小的平均失真。 minRD DD RD失真失真-信息速率信息速率D(R)函数函数失真信息速率函数失真信息速率函数 min;ijBDpR DI U V信息率失真函数信息率失真函数信息传输理论和率失真理

12、论的信息传输理论和率失真理论的对偶关系对偶关系信息传输理论信息传输理论率失真理论率失真理论附注附注信道信道p=p(y|x)失真度失真度d(u,v)信源信源q=q(x)固定固定信源信源q=(q(x)信道信道p=p(v|u)可变的可变的码码C：MXN信源码信源码C: UL C错误概率错误概率pe平均失真平均失真 信道容量信道容量 率失真函数率失真函数RR(D) 信源编码定信源编码定理理LD( )max ( ( )q xCI q x( | )( )min ( ( | )p vuR DI p v u率失真函数的基本性质率失真函数的基本性质 失真度失真度D的下限可以是零，即不允许任何失真的情况。的下限可

13、以是零，即不允许任何失真的情况。 1. R(D)的定义域的定义域minmax0DDD0R DH U 0limDR DH UuvuvvuduqDvuduqD),()(min),(min)(maxmin率失真函数的基本性质率失真函数的基本性质 1. R(D)的定义域的定义域minmax0DDDDmax是是R(D)=0时时D的最小值的最小值 max:,0min,ijDijppp I u vDE d u v max,10min,uvuq u d u vvvDq u d u v对于最小的，取，其余)()(, 0);(VwUVpVUIuvppuvppvuduqvwvuduvpuqDDijDij),()()

14、(min),()()(minmax率失真函数的基本性质率失真函数的基本性质 1. R(D)的定义域的定义域minmax0DDD01)(),(),(min)(),()()(min),()()(minmin，其余为相应的取最小uvpvudvuduqvuduvpuqvuduquvpDvuvuppuvppDijDij 123,a a aminDmaxD 123213321d123()min(1,2,3)()min(2,1,3)()min(3,2,1)p ap ap amin( )min( , )yxDp xd x y (,)ijd a b(|)1jip baminD100(|)010001p y x

15、max123123123min( )( , )min() 1() 2() 3 ,() 2() 1() 2 ,() 3() 3() 15 3yxDp x d x yp ap ap ap ap ap ap ap ap a 2()1p b13()()0p bp bmaxD010( | )010010p y x 123213321d 2. R(D)是关于平均失真度是关于平均失真度D的下凸函数的下凸函数 设设 为任意两个平均失真，为任意两个平均失真， ，则有：，则有： 12,D D01a1212(1)()(1) ()R aDa DaR Da R D3. R(D) 是是 区间上的连续和严格单调递减函数。区

16、间上的连续和严格单调递减函数。 minmax(,)DD率失真函数的基本性质率失真函数的基本性质率失真函数示意率失真函数示意信息率失真函数的一般形状信息率失真函数的一般形状 率失真函数示意率失真函数示意离散无记忆信源的离散无记忆信源的信息率失真函数信息率失真函数已知信源的概率分布已知信源的概率分布P(u)和失真函数和失真函数d(u,v)，就可求得信源的，就可求得信源的R(D)函数。原则上与信道容量一样，是约束条件下求极小值函数。原则上与信道容量一样，是约束条件下求极小值问题，即适当选取试验信道问题，即适当选取试验信道P(v/u)使平均互信息最小化。使平均互信息最小化。其约束条件为其约束条件为:0

17、)/(ijuvPsjijuvP11)/(DvuduvPuPjirisjiji),()/()(11riijiijrisjijiuvPuPuvPuvPuPVUI111)/()()/(log)/()(),(二元对称信源的二元对称信源的R(D)函数函数 设信源设信源U=0,1, 其概率分布其概率分布P(u)= ,1- , 1/2, V= 0,1. 设汉明失真矩阵是设汉明失真矩阵是 Dmin=0，满足该最小失真的是一个无噪无损信道满足该最小失真的是一个无噪无损信道, 其信其信道矩阵为道矩阵为 R(0)=H( ) 0110D10P01 要达到要达到Dmax的试验信道为的试验信道为 maxmin, min

18、p 0 d 0,0p 1 d 1,0 ,p 0 d 0,1p 1 d 1,1 min 1,vuvvDp u d u v 01P01二元对称信源的二元对称信源的R(D)函数函数由矩阵由矩阵P可知，发送可知，发送u=0一定出错，因此一定出错，因此D=w。在这种试验信道下在这种试验信道下 R(Dmax)=R( )=I(U;V)=0 当当0D HH DR D二元对称信源的二元对称信源的R(D)函数函数对于同一对于同一D值，信源分布越值，信源分布越均匀，均匀，R(D)越大，信源压缩越大，信源压缩的可能性越小。的可能性越小。 0,1X 0,1,2Y 01 01d求率失真函数求率失真函数R(D) 。min( )min( , )0yxDp xd x ymaxmin( )( , )1yxDp x d x y由于信源等概分布，失真函数具有对称，因此，存在