限失真信源编码1

信息学院信息工程教研室牛秋娜InformationTheory&Coding第四章限失真信源编码（计划学时12）第四章限失真信源编码4.1信源的有损压缩14.2率失真函数24.3保真度准则下的信源编码14.4连续信源的限失真编码24.5预测编码34.6变换编码3教学目的与要求深刻理解限失真编码的意义。理解率失真函数的概念，了解变化规律。了解离散信源和连续信源的限失真编码。了解预测编码和变换编码的原理，及其在语音和图像压缩中的应用。参考文献1.吴乐南：数据压缩电子工业出版社（2001年6月第一版）2.吴伟陵：信息处理与编码人民邮电出版社（1999年7月第一版）3.曹雪虹：信息论与编码北京邮电大学出版社（2001年8月第一版）第四章限失真信源编码4.1信源的有损压缩本节主要内容限失真信源编码定义失真度的定义单个符号的失真度平均符号失真度序列的平均失真度限失真信源编码：distortionconstraintsourcecoding失真度：distortion平均失真度：averagedistortion外语关键词[温旧引新]信源编码：压缩代码长度的编码。平均互信息的极值性：当信道给定时，互信息仅由信源决定，总存在一个信源能使互信息取极大值；当信源给定时，互信息仅由信道决定，总存在一个信道能使互信息取极小值。传信率与平均互信息：Rt=RB·I(X;Y)连续信源的相对熵：4.1信源的有损压缩4.1.1信源有损压缩的实际意义在许多情况下，比如连续信源，数字通信不可能实现对消息的完全无失真传输。实际问题中，即使存在少量失真，往往并不会明显影响通信质量。既然允许一定的失真存在，就可以人为地削减一些信息，信息率便可大大降低，对于提高通信效率与节约成本都有利。信源有损压缩实例话音通信中信息的有损压缩：PCM脉冲编码调制LPC语音参数编码图像处理中信息的有损压缩：传真通信图像压缩存储（JPG与GIF格式）视频传输中信息的有损压缩：数字电视VCD与DVD然而，有损压缩不能无限制地进行，过大的压缩必然造成较大的失真，将严重影响通信质量。因此，科学的语言是限失真信源编码，而不是有失真信源编码。在容许失真且限定失真的条件下压缩信源代码长度的编码，叫做限失真信源编码。本章理论上需要探讨的问题是：所限定的失真度与信道最少需要传输的信息率的关系。这个关系叫做率失真函数。实践上需要解决的问题是：在保证失真不超过规定大小的条件下，如何通过编码把信源消息压缩到最小。两种限失真传输：一种是离散信源限失真传输，这里主要是编码的问题。另一类是连续信源限失真传输，主要是数字化的问题。更广义的认识，凡是不要求完全无失真地恢复原信号的信号处理过程，都可当作限失真传输过程，比如图像技术中广泛使用的变换编码、预测编码以及语音系统中的声码合成技术等。1、单个符号的失真度：对于所收发的每一对符号(ui,vj)定义一个非负的函数：d(ui,vj)≥0(i=1,2,3,……r；j=1,2,3,……s)称为单个符号的失真度，用它来测度信源发出符号ui而在接收端再现成符号vj的失真程度。这个函数的定义应当使d值的大小能反映失真的大小，d=0应代表没有失真。信源信源编码信宿译码信宿广义无扰信道UVp(ui,vj)4.1.2失真度的定义失真函数的形式失真函数d(ui,vj)的具体形式，在不同问题中可以有不同的规定。常见的形式：平方失真：绝对失真：相对失真：误码失真：失真度矩阵由于有r个ui和s个vj，所以可定义出r×s个d(ui,vj)，构成一个失真度矩阵：[例1]求汉明失真（即误码失真）的失真度矩阵。由误码失真定义，若经传输后再现的接收符号与发送符号相同，则无失真；若不同，则不论是其他哪个符号，都有相同的失真度1。于是失真矩阵必然是对角为零，非对角元为1的形式：对二元对称信源，d(0,0)=d(1,1)=0；d(1,0)=d(0,1)=1：[例2]已知U=[0,1,2],V=[0,1,2],求平方失真度矩阵。如果信宿感觉到失真的严重程度与幅度偏差的平方成正比的话，可按平方失真d(ui,vj)=(ui-vj)2定义失真度，则：d(0,0)＝d(1,1)＝d(2,2)＝0d(0,1)＝d(1,0)＝d(1,2)＝d(2,1)＝1d(0,2)＝d(2,0)＝4014101410D所以：小结：单个符号的失真度d(ui,vj)定义了该种误码（若发送ui而接收的是vj）对通信质量的影响程度。单符号失真度排列成的失真度矩阵D，它与信道传输矩阵P一样，“行”为发送符号，“列”为接收符号。但是P的矩阵元是各种传输情况出现的概率，D却反映各种传输情况失真的大小。失真度的定义是人为的，因事而异的，旨在体现误码对该问题影响的严重程度。一般说来，对于不同的发送接收符号对，失真度是不同的。2、平均符号失真度：通信过程中不同符号的失真程度一般是不一样的，我们可以用平均失真度来定义系统收发每对符号的的平均失真度：P(uv)是联合概率密度，利用P(uv)=P(u)P(v|u)则：若定义失真函数为绝对失真，求平均失真度。解：按绝对失真d(ui,vj)=|ui-vj|的定义，有：联合概率：[例3]已知等概信源U=[0,1]，信宿V=[0,1,2]，信道传输矩阵为：平均失真度：=0×0.3+1×0.15+2×0.05+1×0.15+0×0.35+1×0=0.43、序列的平均失真度：信源发出长为K的序列αi，各符号均取自同一符号集U=[u1u2…….ur]，经信道再现为长为K的序列βj，各符号取自符号集V=[v1v2……vs]，于是在rK个αi与sK个βj之间可定义序列失真度：（i=1,2,…,rK；j=1,2,…,sK）序列的平均失真度：如果信源和信道都是无记忆的，则序列的平均失真度等于各位符号的平均失真度之和：是序列中第l个符号的单符号平均失真度。lD在离散信源为平稳信源的情况下，序列先后发出K个符号时统计性质不因时间而变化，所以：于是：第四章限失真信源编码4.2率失真函数本节主要内容保真度准则率失真函数的定义率失真函数的性质率失真函数的计算保真度准则：FidelityCriteria率失真函数：ratedistortionfunction汉明失真：Hammingdistortion外语关键词外语关键词4.2.1保真度准则作为限失真传输，首先，允许失真存在，其次，要限制失真的大小。为了定量化，可预先指定一个允许失真的上限值D，叫做保真度，要求通信系统的平均每符号失真度不得大于此值：DD即满足保真度准则：对于平稳无记忆信源序列，保真度准则为：4.2.2率失真函数的定义保真度要求越高（D值小），需要传输给信宿信息就应越多；无失真系统，应该传送全部信源信息（当然冗余可被压缩掉）。若允许失真，就可以少传输一些信息；保真度要求越低，需要传输的信息量就可以越少。在满足保真度准则下，必须传输给信宿的传信率R有一个下限值，这个下限值R是保真度D值的函数，函数R(D)就叫做（信息）率失真函数。引言求率失真函数的理论依据本质上讲，失真是因为没有得到足够多的互信息，而满足保真要求则必须获得起码数量的互信息。互信息是信源符号概率和信道传输概率的泛函。互信息的极值性告诉我们：在信道给定的情况下，总存在一种信源能使互信息取极大值（求信道容量就是寻找这个极大值的问题）；在信源给定的情况下，总存在一种信道能使互信息取极小值。如果给定信源能使互信息的极小值（最差信道）满足保真要求的最小数额，则其他任何信道满足保真度都将没有问题。因此求率失真函数，就是在满足保真度准则的约束下求互信息极小值的问题。施加保真约束的方案一是首先在所有信道中求出给定信源的互信息极小值(即得到最差信道)，然后计算该信道的，并检验它是否满足保真度准则。若满足则得到结果，但若不满足则很难继续进行下去。二是先把所有满足满足保真度准则的信道求出来，然后在这些信道中求互信息的极小值。这个极小值作为预先指定的D值的函数就是率失真函数。DD求互信息极小的约束条件是满足保真度准则。而是信源符号概率和信道传输概率的泛函，在信源给定的情况下，取决于信道。存在两种施加保真约束的方案：求率失真函数的思路求率失真函数满足保真度准则下求R极小值R=RB·I(X;Y)把时间效应计入RB中，R正比于I(X;Y)采用单符号信息率R=I(X;Y)满足保真度准则下求互信息的极小值求满足保真度准则的信道集合BD在信道集合BD中寻求能使互信息取极小值的信道率失真函数[例1]二元等概信源失真度矩阵为:求率失真函数。解：先来寻求满足保真度准则的信道集合BD：首先，它应当与D矩阵一样是2行3列，并应具有如下形式：1、失真度Dij为∞的矩阵元表明该传输犯有不能容许的错误，相应的传输矩阵元只能是0，否则便产生无穷失真。2、失真度Dij为0的矩阵元表明该传输无失真，相应接收符号为正确码；而Dij为1的矩阵元表明接收符号为误码。从归一化考虑，其概率可分别设为1-p与p。其次，由联合概率矩阵：可求出平均失真度为：可见，对于任意预先指定的失真度D，只要是上述形式的信道，且p≤D，就是能满足保真度准则的信道集合BD。然后在满足保真度准则的信道BD中求互信息的极小值：接收符号概率为：后验概率为：后验熵为：互信息为：I(X;Y)=H(X)-H(X|Y)=1-p其极小值发生在p极大处，即：R(D)=1-DDR(D)0111、率失真函数R(D)是信源的属性，每给定一个信源，就存在一个互信息的极小值，也就是存在一组信息率与平均失真度的依赖关系，即率失真函数。只要信源给定，率失真函数就被确定。找遍信道集合BD只是对搜寻范围的一种限制，并不表示它是信道的函数。即使不去找，这个极小值也存在，极小值并不会因为寻求它的方法而改变。2、率失真函数还与失真度的定义有关，D的定义不同，R(D)的形式也就不同。3、率失真函数是保真度准则下信源信息率的下限值，在设计限失真信源编码时，信息的削减压缩就应当以此为界，尽量接近它，但不能小于它。对率失真函数的理解信道容量和率失真函数比较RC信道编码定理信道给定，寻找能使平均互信息取极大的信源与极大值。反映信道的传输能力。只与信道有关，是信道的属性，对给定信道是个常数。信源和失真度D给定，寻找满足失真要求的互信息的极小值。反映了信源可压缩的程度。是信源的属性，还与预先指定的保真度有关，是个函数。RR(D)信源编码定理RC,信道编码定理研究信道容量C是为了解决在已知信道中传送最大信息量而错误概率任意小——信道编码问题。RR(D),信源编码定理研究信息率失真函数是为了解决在已知信源和允许失真度D的条件下，使信源必须传送给用户的信息量最小，即，在一定D条件下，用最少的码符号来传送信源消息，提高通信的有效性——信源编码问题。1.R(D)的变化形式（1）在0DDmax区间：R(D)随D单调递减，连续变化到0。（2）在DDmax区间：R(D)≡0（3）在D=0处：连续信源R(0)→∞离散信源R(0)=H(U)4.2.3率失真函数的性质D0DmaxR(D)H(U)连续信源离散信源R=0区图4.1R(D)随D单调递减连续变化（1）Dmin：2．R(D)的定义域保真度准则∴D亦应是非负，即D=0代表无失真，无失真传输时信道损失熵为零，所以该点的信息率等于信源熵：R(Dmin)=R(0)=H(U)对于连续信源，信息熵为无穷大，使R(0)→∞，允许的失真度越大，需要传送的信息就可以越少，率失真函数R(D)是随着失真度D的变大而减小的。R(D)作为互信息是一个非负的值，最小为零。R(D)减小到零时对应的D，就是R(D)非零区的右端点Dmax，即：R(Dmax)=0就是说失真大到一定程度后，从收到的符号已经完全得不到发送符号的信息了。即使继续增大D值，互信息也不可能为负。这个失真度区域的左端点就是Dmax。在DDmax的区域，R(D)将一直保持零。可见Dmax是R(D)的非零区域与全零区域的分界点。（2）Dmax：Dmax可以由R(D)=0的区域求出：在R(D)=0的区域，也就是I(U;V