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