2008-应用信息论基础-张林-Chap-5-794006594

©THU2008–Allrightsreserved清华大学电子系－张林第五章信息速率失真函数与熵压缩编码Rate-DistortionTheoryandLossyCoding2008年12月3日2008年12月10日©THU2008–Allrightsreserved2本章知识脉络信息的率失真函数率失真编码与失真失真编码存在的必要性香农第三定理马尔可夫模型率失真编码与率失真函数信息的速率失真函数信息的速率失真函数性质与简单计算率失真编码速率失真对的可行性速率失真区域与R(D)失真度量的定义5.1锲子－回顾冗余度压缩编码对信源输出的信息进行有效的表示。信道编码增加信息的冗余度，以对抗信道中的传输错误。以上两个方向的努力都是为了保证信息的可靠、无误传输，是保熵的问题是：©THU2008–Allrightsreserved3是否所有的信源都要进行保熵的编码呢？©THU2008–Allrightsreserved4图像压缩文件大小•107kB•55kB•24.6kB•10kB•4330B©THU2008–Allrightsreserved5视频压缩不同码率条件下的图像编码输出质量对比©THU2008–Allrightsreserved6音频压缩温带森林中近景的鸟鸣（约8秒）原始音频（44.1kHz/16bit采样）1,440kB128kbpsMP3格式压缩132kB32kbpsMP3格式压缩33kB声码器10kB一段著名的演讲（约10秒）原始音频（44.1kHz/16bit采样）1,666kB128kbpsMP3格式压缩152kB32kbpsMP3格式压缩39kB声码器11kB©THU2008–Allrightsreserved7问题的提出是否需要完全表示信源的信息？自然界中很多信源是不需要进行保熵的压缩和传输的对于连续信源，需要使用无限大的码率才能够进行可靠的传输因此，不可能也不必要完全表示信源信息在给定的信息速率条件下，如何可以获得信息的最优表示？什么是最好？失真最小就是最好吗？定义失真的度量©THU2008–Allrightsreserved8连续随机变量的量化考查随机变量用R比特来表示X采用平方误差度量最小化2X~N(0,)22ˆˆExX(x)(xX(x))p(x)dx量化恢复00100101010110Xˆ()XX-2-10120.000.050.100.150.200.250.300.350.400.7979xf(x)-0.7979如果我们只有一个比特（R=1），显然，该比特应该代表x的符号。为了最小化误差，恢复值应该为其代表区域的条件平均。2x0ˆX(x)2x0,若,若©THU2008–Allrightsreserved9连续随机变量的量化（续）如果R1，如何划分量化区间？如何选取这个的取值？这个问题不再是显而易见的了针对随机变量的最优（最小失真）量化准则ˆX(x)R2ˆXxˆxXxVoronoiDirichlet如果给定了一组，那么将随机变量映射到最近的可以最小化量化失真。由这种映射形成的划分称为（）划分。ˆXx的选取可以最小化对应区域中的条件预期失真。1.FranzAurenhammer,―Voronoidiagrams—asurveyofafundamentalgeometricdatastructure,‖ACMComputingSurveys,23(3),1991,pp.345–4052.N.Qin,L.Zhang,et.al.―OnDesigningOptimalLocomotionTrajectoryinWirelessSensorNetworks,‖SubmittedtoICC’07Thepartitioningofaplanewithpointsintoconvexpolygonssuchthat..each..polygoncontainsexactlyonegeneratingpointandeverypointinagivenpolygonisclosertoitsgeneratingpointthantoanyother.Thecellsare..called..Voronoipolygons(cells)……...©THU2008–Allrightsreserved10连续随机变量的量化（续）综合前面提出的两种最优量化准则，不难设计寻找最优量化方案的迭代算法（Lloyd算法）由随机选取的一组重建点出发，可以获得局域最优的量化算法算法是否能够收敛到全局？与失真的定义有关与信源的分布有关可见，对信源的速率失真函数的定义与两个因素密切相关失真度量信源分布随机选取一组2R个重建点以这2R个重建点为生成点，生成Voronoi划分在每一个Voronoi多边形中寻找最优重建点（例如：重心位置），形成新的一组2R个重建点寻找最优量化方案的迭代算法1.S.P.Lloyd,―LeastSquaresQuantizationinPCM,‖BellLab.TechnicalNote,19572.I.Csiszar,―SanovProperty,GeneralizedI-projectionandaConditionalLimitTheory,‖AnnalsofProbability,12,1984,pp.768-793.©THU2008–Allrightsreserved115.2失真度量及其性质定义5.1：失真度量（失真函数）是这样一个映射：它将源字母－恢复字母对映射到一个非负的实数。失真度量代表了用符号表示符号的代价。定义5.2：称一个失真度量是有界的，若最大失真是有限值。即，对离散信源，可以用失真矩阵来表示失真度量。11121J21222JK1K2KJˆˆˆd(x,x)d(x,x)...d(x,x)ˆˆˆd(x,x)d(x,x)...d(x,x)d.........ˆˆˆd(x,x)d(x,x)...d(x,x)ˆ:XXdRˆ,dxxˆxxDEFmaxˆˆx,xˆdmaxd(x,x)XX©THU2008–Allrightsreserved12常见的失真度量离散对称信源，信道输入输出及失真函数为：当恢复符号与发送符号相对应时，失真不存在，即，当恢复符号与信源符号不对应时，失真存在且恒为1。该失真称为汉明失真。失真矩阵为：平方失真度量：语音编码中，常用的失真度量为：Itakura-Saito距离。图像处理中，目前还没有统一的失真度量，因此常用的还是平方失真度量。iid(x,x)012Kˆ{x,x,...,x}X12Kx,x,...,x}X{ij0ijˆd(x,x)1ij,,01...110...1d.........11...02ˆˆ(,)()dxxxx©THU2008–Allrightsreserved13考虑信源的符号分布－平均失真编码器解码器nXˆnX{1,2,,2}nnRnfX失真函数在输入输出联合空间中取统计平均给定信源分布和转移概率分布时，信道传输失真总体的平均量度。熵压缩编码器（信道）ˆ(|)qxx:()XpxˆXˆ(,)dxxijijiijˆx,xˆˆˆDp(x)q(xx)d(x,x)Ed(X,X)©THU2008–Allrightsreserved14假设信源产生符号序列。编码器用对其加以表示，解码器恢复出的序列为。定义5.3：序列与序列之间的和失真度量为定义5.4：针对序列的平均失真为信源输出序列的失真编码器解码器nXˆnX{1,2,,2}nnRnfX(){1,2,,2}nnRnfX12,,,NXXX12ˆˆˆ,,,NXXXNxNˆx1ˆˆ(,)(,)NNNiiidxxdxxˆˆˆˆ(,)(,)ˆˆˆˆ()(,)(,)()()(,)NNNNNNNNNNNNNNNNNxxXXxxXXDNpxxdxxpxqxxdxx©THU2008–Allrightsreserved15信源输出序列的失真定理5.1：在和失真度量下，当输入是独立同分布且信道（编码器）是无记忆时，证明见板书1ˆ()(,)DNEdxxN©THU2008–Allrightsreserved16最小化针对所有可能的条件分布，且联合分布满足要求的失真约束5.2熵压缩编码与率失真理论定义5.5：针对信源X和失真度量，信息的率失真函数R(I)(D)为：ˆ,dxxˆ(,)()ˆˆˆ(|):()(|)(,)ˆ()min(;)xxIqxxpxqxxdxxDRDIXX熵压缩编码器（信道）ˆ(|)qxx:()XpxˆXˆ(;)IXXˆ(|)qxxˆˆ(,)()(|)pxxpxqxx©THU2008–Allrightsreserved17构成了一个码本，以表示。为相应的量化区间。率失真编码定义5.6：率失真编码(2nR,n)包括一个编码函数和一个解码函数以及一个与(2nR,n)相关的失真:{1,2,,2}nnRnfX:{1,2,,2}nRnngXE(,(()))()(,(())nnnnnnnnnnxdXgfXpxdxgfxnRnng(1),,g(2)11nRnnf(1),,f(2)nnnRˆˆX(1),,X(2)©THU2008–Allrightsreserved18定义5.7：称率失真对(R,D)是可行的，若存在一组率失真编码(2nR,n)，使定义5.8：信源的率失真区域是所有可行率失真对(R,D)的闭包(Closure)。定义5.9：给定失真度量约束D，率失真函数R(D)是速率R跑遍率失真区域获得的下确界。定义5.10：给定速率约束R，失真率函数D(R)是失真D跑遍率失真区域获得的下确界。率失真区域nnnnnlimEd(X,g(f(X)))D思考：为什么要n→∞？©THU2008–Allrightsreserved19率失真理论的主要结论定理5.2（率失真理论－Shannon第三定理）：给定具有独立同分布p(x)的信源X和有界的失真度量，率失真函数等于信息的率失真函数，即是在失真约束D下可以获得的最小信息传输速率。ˆdx,xˆ(x,x)(I)ˆˆˆq(x|x):p(x)q(x|x)d(x,x)DˆR(D)R(D)minI(X;X)这是率失真理论的主要结论指出了满足失真约束条件下的编码开销约束©THU2008–Allrightsreserved205.3R(I)(D)的性质由定理5.2可知，R(I)(D)＝R(D)，我们在本节首先研究R(I)(D)的性质。直觉的思维中R(D)的形式高复杂度编码器低复杂度编码器失真DR(D)考查R(I)(D)的几个性质：单调性定义域凸性©THU2008–Allrightsreserved21单调减函数定理5.3：R(I)(D)是非增函数。证明：若D2≥D1，有由于在子集上求得的最小值不小于在全集上求得的最小值，故，从而，R(D2)≤R(D1)。□12ˆˆˆˆq(x|x),Ed(x,x)Dq(x|x),Ed(x,x)D21ˆˆˆˆminI(X;X):Ed(x,x)DminI(X;X):Ed(x,x)D集合的包含也是一种序关系。©THU2008–Allrightsreserved22开始证明前的直觉思考：•显然，平均失真D是非负实函数的期望，其下限为0，则允许失真D的下限也为0，对应于不允许失真的情况。•信源分布p(x)给定，所以失真取决于转移矩阵的取值。•如果允许失真足够大，则即便输出为确定值，信息失真也不会超过允许失真约束，此时，则R(D)=0。•结论与直觉思考得到的物理结论一致，下面开始严格证明。R(I)(D)的定义域定理5.4：R(I)(D)的定义域为(Dmin