第五章--信息率失真函数及限失真信源编码

第五章信息率失真函数及限失真信源编码第五章信息率失真函数及限失真信源编码5.1信息率失真函数概念和定义5.2信息率失真函数R（D）的性质5.3离散信源的R(D)函数的计算5.4连续信源的R(D)函数5.5限失真信源编码定理（香农第三定理）5.6限失真信源编码原理第五章信息率失真函数及限失真信源编码5.1信息率失真函数概念和定义在实际应用场合，容许一定程度失真的情况比要求无失真的情况更为重要。信息率失真函数拟解决的问题：信息率和失真之间的关系。信息率失真理论的基本概念：在允许传输消息出现一定的失真时，传输该消息所需要的信息速率（最小值）将比不允许失真时小，且允许的失真愈大，则信息速率（最小值）允许减小的程度也愈大。在给定平均失真函数D的条件下，可以求出信息速率的最小值。第五章信息率失真函数及限失真信源编码一、失真函数失真函数d(x,y)表征了接收消息y与发送消息x之间的定量失真度。即：d(x,y)∣x=ai,y=aj＝dij其中，失真函数dij是一个与失真情况相对应的非负实数：0，i＝jdij＝d,d＞0i≠j显然：i＝j时，收发之间无失真，失真函数dij＝0i≠j时，意味着出现了失真，dij值的大小表示这种失真的程度。第五章信息率失真函数及限失真信源编码若X集有N个符号，Y集有M个符号时，则联合集上有N×M个不同i、j取值的失真函数。失真函数dij的二种表示方式：（1）矩阵表示法（2）连线表示法平均失真度：失真函数的统计平均值（数学期望）D数学式为：两个L维矢量之间的失真函数为：信源的平均失真度：第五章信息率失真函数及限失真信源编码若平均失真度不大于所允许的失真，则称为保真度准则。二、信息率失真函数（率失真函数）当某条件概率P(yj/xi)能使互信息I最小，此时的I就称为在保真度准则下所必须具有的最小信息速率，用R(D)表示。数学式为：R(D)＝minI(X;Y)＝minI(X;Y)其中PD为满足失真条件的转移概率Pji的集合，D为允许的失真。Pji∈PDd≤D第五章信息率失真函数及限失真信源编码信息率失真函数R(D)定义：在给定信源消息的概率分布{P(xi)}及平均失真函数允许值D的前提下，传输这些信源消息并使其失真程度在允许范围内时，所需要的信息传输速率的极小值。R(D)反映了信源可以压缩的程度，是在满足一定失真度要求下，信源可压缩的最低值，对不同的信源，R(D)不同。第五章信息率失真函数及限失真信源编码例：设信源符号有2n种，且等概，失真函数定义为：dij＝0（i＝j时），dij＝1（i≠j时），允许平均失真D＝1/2，要传送此信源，需要多少信息率？第五章信息率失真函数及限失真信源编码课堂练习：设信源具有100个以等概率出现的符号，并以每秒发出1个符号的速率从信源输出，试求在允许失真度D＝0.1的条件下，传输这些符号所需要的最小信息传输速率的大小。结论：在允许一定失真的条件下，信息传输速率可以减小，同时所需要的信道容量也可以相应地减小，允许的失真度愈大，则信息传输速率可被压缩的程度亦愈大。第五章信息率失真函数及限失真信源编码5.2信息率失真函数R(D)的性质一、当D＝0时，R(0)＝H(X)通常Dmin＝0；D＝0时不允许有失真；注意：D是否能达到0，与单个符号的失真函数有关，只有当失真矩阵中每行至少有一个0元素时，D才能达到0值。定义域下界满足Dmin≥0。二、R(Dmax)＝0Dmax是平均失真度的上界值，使平均互信息量等于0时所允许的失真度。注意：D≥Dmax时，R(D)仍为0，R(D)的定义域为（0，Dmax）第五章信息率失真函数及限失真信源编码三、在0～Dmax范围内，R(D)是D上的凹函数（下凸函数）四、R(D)是D的单调递减的连续函数如图为R(D)的典型曲线：在连续信源的情况下，R(0)→∞，曲线不与R(D)轴相交。第五章信息率失真函数及限失真信源编码5.3离散信源的R(D)函数的计算一、R(D)的参量表达式已知：其中：求R(D)就是求I的极值引入拉氏乘子S和ui，再对Pji求导，并令其为0，即第五章信息率失真函数及限失真信源编码几个有用的结果：（1）（2）（3）信息率失真函数参量表达式：第五章信息率失真函数及限失真信源编码注意：参变数S是R(D)函数曲线的斜率，即：dR/dD＝S，由于R(D)曲线是单调递减的凹函数曲线，所以该曲线的斜率S为负值，同时，在D从0～Dmax过程中，S值逐渐增大（S的绝对值逐渐减小）。二、二元信源和对称失真函数的R(D)函数信源概率：p1＝p≤1/2，p2＝1－p≥1/2失真函数：dij第五章信息率失真函数及限失真信源编码可分别求得平均失真函数：可得最大允许的失真度：引用（2）式，得：第五章信息率失真函数及限失真信源编码结果：试验信道的传输概率：第五章信息率失真函数及限失真信源编码可见：平均失真函数D就是平均误码率。如图为不同信源概率值的R(D)曲线：显然Dmax＝p，R(Dmax)＝0第五章信息率失真函数及限失真信源编码结论：在信源压缩问题中，规定D是一个困难的任务。实际中，失真总是可以容忍的，只是如何定义失真函数dij和规定可容许的D值，D↑→压缩量↑→传输代价↓要发挥R(D)函数理论的作用，核心问题是研究失真函数和平均失真值的合理性问题，这须通过大量实验才能达到。第五章信息率失真函数及限失真信源编码三、迭代算法基本步骤：1）任选一个Pji①代入下式，求得各qj①2）再代入下式求得各Pji②，依此类推，直到各阶段的R(S)值稳定为止。第五章信息率失真函数及限失真信源编码5.4连续信源的R(D)函数一、定义和表达式设：平均失真≤允许失真度时，{P(y/x)}∈PD则定义连续信源的率失真函数R(D)为：R（D）＝InfI（P(y/x)）{P(y/x)}∈PD第五章信息率失真函数及限失真信源编码•与离散情况类似，并设得公式：（1）（2）（3）（4）第五章信息率失真函数及限失真信源编码二、d(x,y)只与(x－y)有关时的求解法令：且：最终得：第五章信息率失真函数及限失真信源编码常用方法：（1）分别求出p(x)和g(x)的特征函数（2）则：（3）若q0(x)符合概率密度函数的要求（非负性、归一性），就可得到R(D)函数的参量表达式。第五章信息率失真函数及限失真信源编码例：设连续信源的变量x服从正态分布，即定义失真函数且求信息率失真函数R(D)。解：第五章信息率失真函数及限失真信源编码给定允许失真度D＝－1/2S，即：上式为正态变量在均方误差准则下的率失真函数。第五章信息率失真函数及限失真信源编码当＝1时的R(D)曲线可见：1）D＝1时，R(1)＝0；2）D＞1时，R(D)保持为0，与离散情况一致；3）D＝0时，R(D)→∞，与离散情况不同。第五章信息率失真函数及限失真信源编码5.5限失真信源编码定理（香农第三定理）限失真信源编码定理也称香农第三定理，是保真度准则下的信源编码定理。（具体描述可参考相关教材）限失真编码定理说明：当传输速率R＞R(D)时，只要码长足够长，就一定存在一种编码方法，使平均失真任意接近于D，否则这种编码不存在。注意：不同的编码，将有不同的平均失真，希望找到平均失真最小的编码，即最佳编码。第五章信息率失真函数及限失真信源编码小结：比较香农第一和第三定理可知，当信源给定后，无失真信源压缩的极限值是信源熵H(S)，而有失真信源压缩的极限值是信息率失真函数R(D)，在给定失真值D后，一般R(D)＜H(S)。存在的问题：1）符合实际信源的R(D)函数的计算相当困难；2）采用何种实用的最佳编码方法才能达到R(D)？第五章信息率失真函数及限失真信源编码以下例子可说明如何进行限失真的信源编码和信息率失真函数R(D)的实用意义：•P216，例8.6第五章信息率失真函数及限失真信源编码5.6限失真信源编码原理•采用限失真的信源编码，能够以一定限度的失真换取更加有效地数据压缩，这可大大提高信息传输和存储系统的有效性。•实际工程中常用其他的主、客观评价准则来衡量限失真编码的效果。第五章信息率失真函数及限失真信源编码一、保真度准则1、客观保真度准则通过计算输入与输出之间的误差，客观地评价两者的差异，以度量信源压缩编码所产生的失真大小，比较不同信源编码方法的失真性能。计算并客观度量压缩编码失真大小的方法有均方根误差和均方根信噪比等。第五章信息率失真函数及限失真信源编码2、主观保真度准则根据人们的生理和心理特性，由观察者对编码结果做出主观评价的一种方法。因为多数信息传输和存储处理的结果最终由人接受，所以主观评价准则也是压缩编码处理质量评价的主要方法。第五章信息率失真函数及限失真信源编码二、预测编码方法预测编码：编码传输或存储的并不是信源输出地数据本身，而是当前数据的预测值（或称估值）与实际值之间的差值。这是一种直接利用数据间的相关性进行估计预测，误差数据间的相关性减小，信息冗余降低，差值信号的信息熵较小，若不量化直接编码，则构成无失真预测编码；若根据人的感觉特性对差值重新量化，将实现更大的数据压缩，构成限失真预测编码方法。第五章信息率失真函数及限失真信源编码预测编码方法主要有：1）差值脉冲编码调制（DPCM）；2）线性预测（前值预测、一维线性预测、二维线性预测）；3）量化编码。第五章信息率失真函数及限失真信源编码三、正交变换编码正交变换编码：通过施加某种正交变换，使得变换域中数据的相关性减小或消除，从而减小信源的信息冗余，实现数据压缩。此方法首先对输入数据序列施加某种形式的正交变换，然后用滤波器取出信源信息中的主要部分，舍弃次要部分，从而实现数据压缩。最佳正交变换：K-L变换，但计算量大，难以实用；准最佳正交变换：DFT、DCT、W-HT第五章信息率失真函数及限失真信源编码正交变换编码基本方法有：1）区域采样法：利用变换域中能量集中于低频区域的特点，用一个二维低通滤波器使低频分量的变换域系数被保留和编码，其他分量被舍弃。解码后的误差与变换形式及能量集中程度有关。2）区域编码法：在区域采样的基础上，依据变换域系数特点，分成子区域进行量化和编码。可进一步节省数码率，更有效地压缩数据。第五章信息率失真函数及限失真信源编码以上讨论的信源数据压缩编码中采用的是标量量化方法，即对信源进行去相关处理后，对其输出地单个符号数据（标量）进行量化和编码；标量量化的不足是不能有效利用数据之间的剩余相关性，且失真控制策略不够合理。实际中也可采用矢量量化编码方法，这是对随机变量序列进行量化处理，在信源输出信息的传输或储存系统中，仅对典型矢量的序号进行编码，解码时依据码矢量地址查找典型矢量，恢复信源输出地数据，可以实现高效的数据压缩。