限失真信源编码定理－1

7.4:限失真信源编码定理1,限失真信源编码定理限失真信源编码定理的证明限失真信源编码定理的实用意义,7.4:限失真信源编码定理2,限失真信源编码定理设R(D)为一离散无记忆平稳信源的信息率失真函数，并且有有限的失真测度。对于任意D0，0，0以及任意足够长的码长n，则一定存在一种信源编码C，其码字个数为:M=expnR(D)+而编码后码的平均失真度: d(C)D+如果用二元编码，R(D)取比特为单位，则上式M可写成: M=2nR(D)+,7.4:限失真信源编码定理3,定理解释：对于任何失真度D0，只要码长n足够长，总可以找到一种编码C，使编码后每个信源符号的信息传输率: R=logM/n=R(D)+ 即: RR(D) 而码的平均失真度d(C)D。在允许失真D的条件下，信源最小的、可达的信息传输率是信源的R(D)。,7.4:限失真信源编码定理4,限失真信源编码定理的证明问题：设有达到R(D)的试验信道p(v|u),要证明对于任意的RR(D)时，存在一种信息传输率为R的信源编码，其平均失真度D+思路：产生码书选取编译码方法计算失真度方法：产生码书：在Vn空间随机抽取M=2nR个随机序列v编码方法：若存在与信源序列u构成失真典型序列对的序列v(),则编码uv(),否则编码uv(1)译码：再现v()失真度计算：在所有随机码书和Un空间统计平均的基础上计算平均失真度,7.4:限失真信源编码定理5,限失真信源编码定理的几点说明只是一个存在性定理，没有构造方法存在问题：符合实际信源的R(D)函数计算相当困难信源统计特性的确切数学描述难得符合主客观实际的失真测度难得R(D)计算本身困难即使求得了R(D)，还需研究最佳编码方法才能达到极限值R(D)。,7.4:限失真信源编码定理6,限失真信源编码定理的实用意义如何进行限失真信源编码？举例：R（D）的实用意义在允许一定失真的情况下，信源的R(D)函数可以作为衡量各种压缩编码方法性能优劣的一种尺度。,举例：二进制无记忆对称信源编译码：,无噪无损信道传输,举例：结论,R=1/3（比特/信源符号）该压缩编码方法下的信息传输率d(C)=1/4该压缩编码方法下的平均失真R(1/4)=1-H(1/4)=0.189(比特/信源符号）失真1/4下，最小的信息传输率R是0.189(比特/信源符号）R(1/4),量化,它包括标量和矢量两种，这是重点讲标量量化1 标量量化适用范围：连续无记忆信源2标量量化的概念：连续信号量化K个若干可能离散值 举例：A/D采集版,量化,量化概念A/D中的量化量化过程示意图一个量化实例,量化处理是使数据比特率下降的一个强有力的措施。 量化输入值动态范围很大，需要以多比特数表示一个数值，量化输出只能取有限个整数，称量化级。每个量化输入被强迫归一到与其接近的某个输出，即量化到某个级。量化处理总是把一批输入量化到一个输出级上，所以量化是个多对一的处理过程，量化中由信息丢失，或者说，会引起量化误差（量化噪声）。,模拟量经过A/D转换，得到二进制码的过程，就是脉冲编码调制（PCM）编码过程，也称PCM编码。 A/D转换中的采样和量化分别是对时间和模拟量进行数字化的过程。,量化,量化概念A/D中的量化量化过程示意图一个量化实例,输入,输出,量化曲线,量化,量化概念A/D中的量化量化过程示意图一个量化实例,24位标准图像 8位（256色）标准图像,量化,量化概念A/D中的量化量化过程示意图一个量化实例,预测编码方法基本原理,从相邻数据之间有很强的相关性特点考虑，可以利用前面已经出现的数值，进行预测（估计），得到一个预测值，将实际值与预测值求差，对这个差值信号进行编码、传送，这种编码方法即成为预测编码方法。,预测编码,最佳的预测编码：en=yn-un 最小有三种不同的标准：最小均方误差；最小平均绝对误差；最大零误差概率；,DPCM基本原理,DPCM编、解码原理图,预测编码,不带量化器的DPCM线性预测编码，属于无失真编码系统；带有量化器的DPCM线性预测编码，属于有失真编码系统。 DPCM线性预测系统是一个负反馈系统，对误差有收敛性。发送端与接收端之间的误差等于量化误差。 最佳量化器的设计，可利用人眼的视觉可见度阈值和视觉掩蔽效应等生理特征，来确定量化器的级数和步距，使量化误差总处于人眼难以觉察的范围内，达到主观评定准则的要求。,最佳量化,预测编码,自适应预测编码ADPCM,自适应技术的概念是：预测器的预测系数和量化器的量化参数，能够根据图像的局部区域分布特点自动调整。 实践证明，ADPCM编、解码系统与DPCM编、解码系统相比，不仅能改善恢复图像的评测质量和视觉效果，同时还能进一步压缩数据。 ADPCM系统包括自适应预测，即预测系数的自适应调整和自适应量化，即量化器参数的自适应调整两部分内容。,预测编码,变换编码原理,定义：将空域图像信号映射变换到另一个正交矢量空间（变换域或频域），产生一批变换系数，对系数进行编码处理原理：信号在时域描述时信息冗余度大，变换后，参数独立，去掉相关性，减少冗余，数据量大大减少。利用人的视觉特性，对高频细节不敏感，可以滤除高频系数，保留低频系数。,变换原理在数学上的解释,信号在时域描述时信息冗余度大，变换后，参数独立，数据量减少。空间内的变换就是寻找一组新的规范正交基，求去原向量在新的正交基上的系数。,利用人的视觉特性，对高频细节不敏感，可以滤除高频系数，保留低频系数。用有限维线性组合去逼近原向量，投影定理。,最佳正交变换K-L变换,X1,X2,对相关向量求协方差矩阵，按照特征值的大小排列特征向量。变换域中能量集中到少数几个变换系数上（特征值大的特征向量上的系数），编码效率最高，误差最小。,K-L变换图示,3） 标量量化涉及几个性解指标 P243信息速率RK平均失真DK量化器输出最大速率Mk=log2k显然：取不同的TK和qk,量化将有不同的RK，DK，MKTK:门限电平（k+1个）qk:电平值 （k个）,4） 均匀量化概念：量化间隔相等最优均匀量化：使DK达到最小均匀量化 例：对高斯信源 即:Rk=1/4+1/2log(Pu/Dk)问题：均匀量化不是DK最小的一个、提出一种Uoyd-Max算法,5）Lioyd-Max算法思想：反复对TK、qk在使DK最小的两个必要条件进行迭代（必要条件为：P235） Tk-1=1/2(qk-1+qk) (u- qk)p(u)du=0 则求