信息论与编码限失真信源编码优秀PPT.ppt

信息论与编码限失真信源编码第1页，本讲稿共45页信息论与编码-限失真信源编码第三章我们讨论了无失真信源编码。但是，在很多场合，特别是对于连续信源，因为其绝对熵为无限大，若要求无失真地对其进行传输，则要求信道的信息传输率也为无限大，这是不现实的。因此也就不可能实现完全无失真传输。另一方面，从无失真信源编码定理来考虑，由于要求码字包含的信息量大于等于信源的熵，所以对于连续信源，要用无限多个比特才能完全无失真地来描述。第2页，本讲稿共45页信息论与编码-限失真信源编码即使对于离散信源，由于处理的信息量越来越大，使得信息的存储和传输成本很高，而且在很多场合，过高的信息率也没有必要，例如：由于人耳能够接收的带宽和分辨率是有限的，因此对数字音频传输的时候，就允许有一定的失真，并且对欣赏没有影响。又如对于数字电视，由于人的视觉系统的分辨率有限，并且对低频比较敏感，对高频不太敏感，因此也可以损失部分高频分量，当然要在一定的限度内。等等这些，都决定了限失真信源编码的重要性。第3页，本讲稿共45页信息论与编码-限失真信源编码在限失真信源编码里，一个重要的问题就是在一定程度的允许失真限度内，能把信源信息压缩到什么程度，即最少用多少比特数才能描述信源。这个问题已经被香农解决。香农在1948年的经典论文中已经提到了这个问题，在1959年，香农又在他的一篇论文“保真度准则下的离散信源编码定理”里讨论了这个问题。研究这个问题并做出较大贡献的还有前苏联的柯尔莫郭洛夫（Kolmogorov）以及伯格（T.Berger）等。第4页，本讲稿共45页信息论与编码-限失真信源编码信息率失真理论矢量化、数摸转换、频带压缩和数据压缩的理论基础。本章主要介绍信息率失真理论的基本内容，包括信源的失真度和信息率失真函数的定义与性质，离散信源和连续信源的信息率失真函数计算，介绍一些常用的限失真编码方法等。第5页，本讲稿共45页信息论与编码-限失真信源编码4.1 平均失真和信息率失真函数平均失真和信息率失真函数一、失真函数设某信源输出的随机变量为X，其值集合为 ，经过编码后输出为 ，设 对应 ，如果则认为没有失真。当 时，就产生了失真，失真的大小，用失真函数来衡量。失真函数的定义为第6页，本讲稿共45页信息论与编码-限失真信源编码由于输入符号有n个，输出符号有m个，所以共有 个，写成矩阵形式，就是d被称为失真矩阵。第7页，本讲稿共45页信息论与编码-限失真信源编码失真函数 的函数形式可以根据需要适当选取，如平方代价函数、绝对代价函数、均匀代价函数等：平方失真：绝对失真：相对失真：误码失真：第8页，本讲稿共45页信息论与编码-限失真信源编码也可以按其它的标准，如引起的损失、风险、主观感觉上的差别等来定义失真函数。二、平均失真由于信源X和信宿Y都是随机变量，所以符号失真度函数也是一个随机变量，传输时引起的平均失真应该是符号失真度函数 在信源概率空间和信宿概率空间求平均，即第9页，本讲稿共45页信息论与编码-限失真信源编码平均失真是符号失真函数在信源空间和信宿空间平均的结果，是描述某一信源在某一信道传输时失真的大小，是从整体上描述系统的失真情况。三、信源符号序列的失真从上面的单符号失真函数，可以得到信源符号序列的失真函数和平均失真度。由于序列时相当于是一个由单符号随机变量组成的随机矢量，仿照单符号时的情况，可得：第10页，本讲稿共45页信息论与编码-限失真信源编码设信源输出的符号序列为 ，其中的每一个随机变量 取自同一符号集 ，所以X共有 种不同的符号序列，记为 ，接收到的符号为 式中每一个符号取自符号集 ，所以Y共有 种不同的符号序列，记为 ，则 第11页，本讲稿共45页信息论与编码-限失真信源编码失真函数矩阵应该是一个 的矩阵。故对L长的信源序列，其平均失真度为平均每个符号的平均失真度为当信源无记忆时，而第12页，本讲稿共45页信息论与编码-限失真信源编码若平均失真度不大于我们所允许的失真D，即我们称此为保真度准则。四、信息率失真函数在信源给定，并且也定义了具体的失真函数之后，我们总是希望在满足一定的失真限度要求的情况下，使信源最后输出的信息率R尽可能地小。也就是说，要在满足保真度准则下（），寻找信源输出信息率R的下限值。如果将信源编码也看成是一个信道，构成了一类假想信道，第13页，本讲稿共45页信息论与编码-限失真信源编码称为D允许信道（或D失真许可的试验信道），记为对于离散无记忆信道，有我们的目的，就是要在上述允许信道 中，寻找到一个信道P(Y/X)，使得从输入端传送过来的信息量最少，即I(X;Y)最小。这个最小的互信息就称为信息率失真函数R(D)，简称为率失真函数，即第14页，本讲稿共45页信息论与编码-限失真信源编码其单位是比特/信源符号。应当注意，在研究R(D)时，我们引用的条件概率 并没有实际信道的含义，只是为了求平均互信息的最小值而引用的、假想的可变试验信道。实际上这些信道反应的仅是不同的有失真信源编码，或称信源压缩。所以改变试验信道求最小值，实质上是选择一种编码方式式信息第15页，本讲稿共45页信息论与编码-限失真信源编码传输率为最小，也就是在保真度准则下，使信源的压缩率最高。五、信息率失真函数的性质 1.R(D)的定义域R(D)的定义域，即D的取值范围。（1）因为D是非负函数d(x,y)的数学期望，因此D也是非负函数，其下界为0。此时，第16页，本讲稿共45页信息论与编码-限失真信源编码意味着不允许失真，所以信道的信息率等于信源的熵，即（2）平均失真D也有一上界值 。根据R(D)的定义，R(D)是在一定的约束条件下，平均互信息量I(X;Y)的最小值，其下界为0。R(D)和D的关系曲线一般如下图所示。当D大到一定程度，R(D)就达到其下界0，我们定义这时的D为 。第17页，本讲稿共45页信息论与编码-限失真信源编码n 的计算：设当平均失真 时，R(D)以达到其下界0。当允许更大失真时，即 时，R(D)仍只能继续是0。因为当X和Y统计独立时，平均互信息I(X;Y)=0，可见当 时，信源X和接收符号Y已经统计独立了，因此 ，与x无关。R(D)DR(D)0R(D)=0第18页，本讲稿共45页信息论与编码-限失真信源编码因此，就是在R(D)=0的条件下，看在什么分布下，能够得到的平均失真D的最小值，即也可以改写成第19页，本讲稿共45页信息论与编码-限失真信源编码也就是说，要求 的数学期望的最小值。这个最小值是一定存在的。比如 这样分布：当某一个 使得 为最小时，就取 ，而其余的 ，此时求得的 的数学期望一定是最小的。此时，有例题：设输入输出符号表为X=Y=0,1，输入概率分布为 ，失真矩阵为第20页，本讲稿共45页信息论与编码-限失真信源编码求解：第21页，本讲稿共45页信息论与编码-限失真信源编码而输出符号概率为例题2：输入输出符号表同上题，失真矩阵为求解：第22页，本讲稿共45页信息论与编码-限失真信源编码此时，（2）R(D)函数的单调递减性和连续性R(D)的单调递减性是很容易理解的。因为允许的失真越大，所要求的信息率就可以越小。根据R(D)的定义，他是在平均失真度小于或等于允许失真度D的所有试验信道集合 中，取I(X;Y)的最小值。当允许失真D扩大，则 的集合也扩大，当然仍然包含原来满足条件的所有信道。这是在扩大了的 集合中找I(X;Y)的最小值，第23页，本讲稿共45页信息论与编码-限失真信源编码显然或者是最小值不变，或者是变小了，所以R(D)是非增的。关于R(D)的连续性，这里我们就不再证明了。所以，R(D)有如下基本性质：n ，定义域为 ，当 时，R(D)=0。nR(D)是关于D的连续函数。nR(D)是关于D的严格递减函数。第24页，本讲稿共45页信息论与编码-限失真信源编码因此，当规定了允许失真，又找到了适当的失真函数 ，就可以找到该失真条件下的最小信息率R(D)，用不同的方法进行数据压缩时（在允许的失真限度D内），其压缩的程度如何，可以用R(D)来衡量。由它可知是否还有压缩潜力，有多大的压缩潜力。因此，有关R(D)的研究也是信息论领域的一个研究热点。4.2 R(D)的计算的计算已知信源的概率分布和失真函数 ，就可以求得信源的R(D)函数。第25页，本讲稿共45页信息论与编码-限失真信源编码求R(D)函数，实际上是一个求有约束问题的最小值问题。即适当选取试验信道的 使平均互信息最小化，并使 满足以下约束条件第26页，本讲稿共45页信息论与编码-限失真信源编码应用拉格朗日乘子法，原则上总是可以求出上述问题的界。但一般来说，求解会是非常复杂的。这里不准备做复杂的推导过程，只给出几个结果。（1）当 ，时，第27页，本讲稿共45页信息论与编码-限失真信源编码 ，（2）当 ，时，（3）当 ，时，第28页，本讲稿共45页信息论与编码-限失真信源编码4.3 限失真信源编码定理（香农第三定理）限失真信源编码定理（香农第三定理）设R(D)唯一离散误记忆平稳信源的信息率失真函数，并且有有限的失真测度。则对于任意的 和 ，当信息率RR(D)时，一定存在一种编码方法，其译码失真小于或等于 ，条件是编码的信源序列长度L足够长。反之，如果RR(D)，则无论采用什么编码方法，其译码失真必大于D。定理说明，在允许失真为D的条件下，信源最小可第29页，本讲稿共45页信息论与编码-限失真信源编码达的信息传输率是信源的R(D)。保真度准则下的信源编码定理（限失真信源编码定理）是有失真信源压缩的理论基础。定理说明了在允许失真D确定后，总存在一种编码方法，使编码的信息传输率大于R(D)且可以任意接近R(D)，而平均失真度小于允许失真D。而当信息传输率小于R(D)时，编码的平均失真将大于D。可见，R(D)是允许失真度为D的情况下信源信息压缩的下限值。比较香农第一定理和香农第三定理可知，当信源给定后，无失真信源压缩的第30页，本讲稿共45页信息论与编码-限失真信源编码极限值是信源熵H(X)，而又失真信源压缩的极限值是信息率失真函数R(D)。在给定D后，一般R(D)H(X)。R(D)可以作为衡量各种压缩编码方法性能优劣的一种尺度。但香农第三定理同样是一个指出存在性的定理，至于如何寻找这种最佳压缩编码方法，定理中没有给出。在实际应用中，该理论主要存在以下两类问题：（1）符合实际信源的R(D)函数的计算相当困难。第31页，本讲稿共45页信息论与编码-限失真信源编码首先，对需要对实际信源的统计特性有确切的数学描述，其次，需要符合主客观实际的失真度量。这些都不是很容易的事情。即使有了这些，率失真函数的计算也是相当困难的。（2）即使求得了符合实际的信息率失真函数，还需要研究采用何种编码方法，才能达到或接近极限值R(D)。第32页，本讲稿共45页信息论与编码-限失真信源编码4.4 常用信源编码方法简介常用信源编码方法简介 1.游程编码在二元序列中，只有“0”和“1”两个码元，我们吧连续出现的“0”叫做“0”游程，连续出现的“1”叫做“1”游程。连续出现“0”或者“1”码元的个数叫做游程长度。这样，一个二元序列可以转换成游程序列，例如：二元序列0001100111100010可以变换成3224311，若规定游程必须从“0”游程开始，则上述变换是可逆的。如果连“0”或连第33页，本讲稿共45页信息论与编码-限失真信源编码“1”非常多，则可以达到信源压缩的目的。游程编码是无失真信源编码。第34页，本讲稿共45页信息论与编码-限失真信源编码2.矢量量化连续信源进行编码的主要方法是量化，即将连续的样值 离散化成为 。n是量化级数，这样就把连续值转化为n个实数中的一个，可以用0，1，2，n等n个数字来表示。由于 是一个标量，因此称为标量量化标量量化。在量化的过程中，将会引入失真，量化是必须使这些失真最小。要想得到更好的性能，仅采用标量量化是不可能第35页，本讲稿共45页信息论与编码-限失真信源编码 的。从前面的讨论我们已经知道，把多个信源符号组成一个符号序列进行联合编码可以提高编码效率。连续信源也是如此，当把多个信源符号联合起来形成多维矢量，然后进行量化，可以进一步压缩码率，这种量化方法叫做矢量量矢量量化化。实验证明，即使各信源符号相互独立，矢量量化也可以压缩信息率，因此，人们对矢量量化非常感兴趣，是当前信源编码的一个热点，而且第36页，本讲稿共45页信息论与编码-限失真信源编码 不仅限于连续信源，对离散信源也可以如此。如图像编码时采用矢量量化，但由于联合概率密度不易测定，目前常用的是训练序列的方法，如图像编码时就要采用训练序列的方法，找到其码书，进行量化。还可以与神经网络方法结合，利用神经网络的自组织来得到训练集。3.预测编码预测就是从已收到的符号来提取关于为收到的符号的信息，从而预测其最可能的制作为预测值。第37页，本讲稿共45页信息论与编码-限失真信源编码并把它与实际值之差进行编码，由于这个差值一般都比较小，所以在编码时会出现很多连“0”值，再采用游程编码，就可以大大地压缩码率。由此可见，预测编码是利用信源符号之间的相关性来压缩码率的，对于独立信源，预测就没有可能。4.变换编码变换是一个广泛的概念。变换编码就是经变换后的信号能更有效地编码，也就是通过变换来解第38页，本讲稿共45页信息论与编码-限失真信源编码 除或减弱信源符号间的相关性，以达到压缩码率的效果（如单频率正弦波信号，变换到频域）。一般地，对一个函数 ，变换式为：而反变换为：第39页，本讲稿共45页信息论与编码-限失真信源编码要使上式成立，要求 必须是正交完备的（相当于欧氏空间的坐标投影），求 的公式，实际上就是内积运算，把函数 投影到 上去。信源编码常用的变换有：DCT（discrete Cosine Transform）变换：如JPEG、MPEG等图像压缩标准中，就是主要采用的这种变换压缩方法。K-L变换：K-L变换是均方误差准则下的最佳变换。第40页，本讲稿共45页信息论与编码-限失真信源编码它是一种正交变换，变幻后的随机变量之间互不相关，一般认为，K-L变换是最佳变换，其最大缺点是计算复杂，除了需要测定相关函数和解积分方程外，变换时的运算也十分复杂，也没有快速算法，因此，K-L变换不是一种实用的变换编码方法，但经常用来作为标准，评估其他方法的优劣。小波（Wavelet Transform）变换：小波变换是当前信号处理以及多种应用科学中第41页，本讲稿共45页信息论与编码-限失真信源编码 广泛用到的一种相当有效的数学工具。小波变换的概念首先是由法国的石油地质工程师J.Morlet于 1980年提出的，1990年Mallat等人一起建立了多分辩分析的概念。与经典的Fourier分析相比较，小波的最大优势是变换本身具有时间与频率的双重局部性质，解决了Fourier分析不能处理的许多实际问题，因而小波变换被人们称之为“数学显微镜”。20世纪90年代中期以前，图像压缩主要采用离散余弦变换(DCT)技术，著名的JPEG、H.263第42页，本讲稿共45页信息论与编码-限失真信源编码等图像压缩国际标准均采用DCT方法实现图像压缩。而DCT最大的缺陷是当压缩比较大时，会出现马赛克效应，因而影响图像压缩质量。最近几年来，由于小波变换具有DCT无可比拟的良好压缩性质，在最新推出的静态图像压缩国际标准JPEG2000中，9/7双正交小波变换已经正式取代DCT而作为新的标准变换方法。分形（Fractal Transform）变换：基于块的分形编码是一种利用图像的自相似性第43页，本讲稿共45页信息论与编码-限失真信源编码 来减少图象冗余度的新型编码技术，它具有以下特点：(1)较高的压缩比。(2)解码图象的分辨率无关性。可按任意高于或低于原编码图象的分辨率来进行解码。当要解码成较高分辨率图象时，引入的细节会与整个图象大致和谐一致，从而比象素复制或插值方法得到的图象看起来更自然。这种缩放能力也可以用作图象增强工具。第44页，本讲稿共45页信息论与编码-限失真信源编码（3）解码速度快。分形压缩是一非对称过程，虽然编码很耗时，但解码速度快，因此较适用于一次编码多次解码的应用中。（4）编码时间过长，实时性差，从而阻碍了该方 法在实际中的广泛应用。还有很多其他的编码方法，这里就不再一一介绍了。第45页，本讲稿共45页