信息率失真函数与限失真信源编码.ppt

《信息率失真函数与限失真信源编码.ppt》由会员分享，可在线阅读，更多相关《信息率失真函数与限失真信源编码.ppt（57页珍藏版）》请在三一办公上搜索。

1、第七章：信息率失真函数与限失真信源编码定理,本章研究内容,概述失真的度量信息率失真函数限失真信源编码定理限失真信源编码定理应用实用型信源编码香农三大定理的关系和比较,7.1:概述1,无噪信道编码定理回顾：总可以找到一种输入分布（信源编码方法），使在无噪无损信道上，能够以信道容量C无误地传输信息。,压缩冗余度,最好地利用C,限：平均码长最小值Hr(S)每个码符号平均能够携带的最大信息量,7.1:概述2,有噪信道编码定理回顾：只要RC，总可以找到一种信道编码方法，使在信道上能够以尽可能小的PE传输信息。,增加冗余度，最好地匹配信道特性,限：信息传输率最大值C每个信道符号平均能够携带的最大信息量,7

2、.1:概述3,存在问题对于连续和模拟信源H(S)=信道传输率R=H(S)/n（比特/码符号）R=平均码长l=Hr(S)=H(S)/logr,l=,实际上，因为B有限，C一定有限，RC,7.1:概述4,实际需求特点：信宿对真实度的要求：实际语音信号：20Hz8KHz 人耳能够分辨：300Hz3400Hz图象色差：可达足够多 视觉分辨：256级（黑白）已足够可以允许一定的失真度完全保真没必要,7.1:概述5,引出的研究内容限失真的信源编码问题允许一定的失真度下，能将信源信息压缩到什么程度？（最少需要多少比特才能在收端描述信源？）一定的信息传输率R下，可能达到的最小的平均失真是多少？相关问题失真如何

3、度量？率失真函数如何计算？,7.1:概述6,方法：抽象：将与讨论重点关系小的部分抽象因为涉及信源编码，对信道进行抽象信道编码信道信道译码 信道*研究失真影响时，“信道*”可以忽略根据信道编码定理：信道*是一个没有干扰的广义信道，信宿收到信息的失真只来自于信源编码,7.1:概述7,方法：虚拟：将讨论重点虚拟细化将限失真信源的编译码过程虚拟信源编码过程信道*信源译码过程 试验信道可以用信道传递概率来描述限失真信源编译码前后的关系,信源编码,信道*,信源译码,信源,信宿,信源,信宿,试验信道,U,V,P(V|U),7.2:失真的度量1,失真度定义平均失真度保真度准则试验信道,7.2:失真的度量2,失

4、真度定义在U,V联合空间上定义：d（ui，vj），uiU，vjV 为U,V的失真测度。d（ui，vj）有距离的概念性质1：ui=vj时，d=0性质2：min d=0性质3：0d,7.2:失真的度量3,失真度定义 0,ui=vj 离散信源：用失真矩阵描述。dij=0,ui vj 0,ui=vj 汉明距离度量时：dij=1,ui vj连续信源：用失真函数描述。d(u,v)=(u-v)2=|u-v|,7.2:失真的度量4,平均失真度单符号失真度：d（ui，vj）0，（i=1r，j=1s）信源的失真矩阵可表示为：共rs个元素,7.2:失真的度量5,平均失真度平均失真度：U，V是随机变量；d（ui，vj

5、）也是随机变量平均失真度：,7.2:失真的度量6,平均失真度confer:d&d：描述了某个信源符号通过传输后失真的大小，不同的信源符号，其d不同。：描述了某一个单符号信源在某一试验信道传输 下的失真，它不仅与单个符号的d有关，还与 试验信道的统计特性有关。,7.2:失真的度量7,平均失真度N维信源符号序列的平均失真度：此时D为一 rNsN阶的矩阵与：d（u，v）、p(u)、p(v|u)、N均有关,7.2:失真的度量8,平均失真度N维信源符号序列信源平均失真度信源、信道均无记忆时：信源平稳时：,序列中第l个分量的平均失真度,7.2:失真的度量9,保真度准则给定D，若 D，则称此为保真度准则对于

6、序列信源，保真度准则为：ND,7.2:失真的度量10,试验信道：P(v|u)不是实际的信道特性矩阵，在此相当于不同的编码方法，编码方法不同，不同。定义：所有 D的试验信道构成D失真许可的试验信道集合BD,7.3:率失真函数1,问题引出度量了失真，进一步关心的问题是：一定的失真D下，最小的信息传输率R是多少？一定的失真D下，收端再现信源需要的最低的平均信息量是多少？定义：（信息）率失真函数R(D),对于N维序列信源：,7.3:率失真函数2,率失真函数的进一步解释单位：比特/信源符号（同互信息）离散无记忆信源：RN(D)=NR(D)P(v|u)无实际信道含义，只代表不同编码方法求R(D)就是在D条

7、件下，选择一种编码方法，使R最小。定义域：D 0,DmaxR(D)的性质：凸状性单调递减性连续性,一般情况下:Dmin=0,R(Dmin)=H(U)(有条件)当D Dmax时，R(D)=0;而当DminR(D)0.,7.3：删除信道，求,7.3:率失真函数3,7.3:率失真函数4,Dmax与R(Dmax),定义当DDmax时，R(Dmax)=0使R(Dmax)=0的p(v|u)不止一个不同的p(v|u)有不同的 对我们有意义的：具有最小的 的p(v|u)利用该p(v|u)求得使R(Dmax)=0时的DmaxR=0时，U,V统计独立p(v|u)只是v的函数,则有：p(v|u)P(v),例：二元信

8、源,计算。,7.3:率失真函数5,7.3:率失真函数6,R(D)的计算求解R(D)，-求解互信息的极小值互信息I(X,Y)是条件转移概率的下凸函数极小值存在一般情况下很难得到R(D)的显函数表达式，只能得到参量表达式具体计算很困难，一般利用计算机进行迭代计算,7.3:率失真函数7,二进制对称信源的R(D)计算已知条件：二进制对称信源U=0,1，接收变量V=0,1，允许的 失真DP(u)=，1，1/2汉明失真矩阵,7.3:率失真函数8,求解步骤：由Dmin=0，找到满足最小失真的试验信道p(v|u),得到R(0)由汉明失真矩阵和失真度定义，计算最大允许的失真度Dmax由Dmax，找到满足最大失真

9、的试验信道p,并得到R(Dmax)在一般条件下当0DDmax时，计算平均失真度选取一个信道，使 D，求互信息求互信息的下限值得到R(D)验证：找到满足R(D)的试验信道，验证其正确性结果分析：R(D)曲线分析,7.3:率失真函数9,对于同一个D：信源分布越均匀，R(D)就越大，信源压缩的可能性越小反之，若信源分布越不均匀，即信源剩余度越大，R(D)就越小，压缩的可能性就越大。,二进制对称信源的R(D)函数,等概信源的信息率失真函数。信源输出符号集，等概分布，输出符号集，失真函数定义为,7.3:率失真函数10,7.3:率失真函数11,高斯信源的R(D)计算已知条件：高斯信源U，其均值为m，方差为

10、2，接收变量V概密函数：失真函数：均方误差失真，即：求解步骤：计算平均失真度当 D，求互信息求互信息的下限值得到包含有D和2 的R(D)表达式讨论D和2 比值不同时R(D)的取值验证：找到满足R(D)的试验信道，验证其正确性结果分析：R(D)曲线分析,7.3:率失真函数12,当D 2时，R(D)0。即：如果允许失真等于信源的方差，则只需用均值m来表示信源输出，而不需要传送信源的任何实际输出。当D0时，R(D)。即：在连续信源情况下，要毫无失真地传送连续信源必须要求信道具有无限大的容量。当D0.25 2时,R(D)=1（比特/自由度）。即：允许均方误差小于或等于2/4时，连续信号的每个样本值最少

11、需要用一个二元符号来传输。,高斯信源在均方误差准则下的R(D)函数,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足够长，总可以找到一种编

12、码C，使编码后每个信源符号的信息传输率:R=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空间统计平均的基础

13、上计算平均失真度,7.4:限失真信源编码定理5,限失真信源编码定理的几点说明只是一个存在性定理，没有构造方法存在问题：符合实际信源的R(D)函数计算相当困难信源统计特性的确切数学描述难得符合主客观实际的失真测度难得R(D)计算本身困难即使求得了R(D)，还需研究最佳编码方法才能达到极限值R(D)。,7.4:限失真信源编码定理6,限失真信源编码定理的实用意义存在性R（D）的实用意义在允许一定失真的情况下，信源的R(D)函数可以作为衡量各种压缩编码方法性能优劣的一种尺度。举例：,举例：二进制无记忆对称信源编译码：,无噪无损信道传输,举例：结论,R=1/3（比特/信源符号）该压缩编码方法下的信息传输

14、率d(C)=1/4该压缩编码方法下的平均失真R(1/4)=1-H(1/4)=0.189(比特/信源符号）失真1/4下，最小的信息传输率R是0.189(比特/信源符号）R(1/4)R在1/4失真度下，该压缩编码方法不是最佳的，或该信源还可以压缩,7.5:限失真信源编码定理应用1,定理：对任一连续非正态信源，若已知其方差为，熵为，并规定失真函数为，则其R(D)满足下列不等式：（正态）（上限）结论：在平均功率受限条件下，正态分布R(D)函数值最大，它是其他一切分布的上限值，也是信源压缩比中最小的。所以人们往往将它作为连续信源压缩比中最保守的估计值。,7.5:限失真信源编码定理应用2,利用连续信源的R

15、(D)函数，分析语音的波形编码：为了分析方便，假设语音遵从平稳正态分布：例1：分析PCM编码及其压缩潜力：采样率：8KHz；量化位数：8 信息率：8*8=64Kb/s 相关性：样点间独立，且每个样点8bit 信噪比：入公用网的要求 26dB，,7.5:限失真信源编码定理应用3,其中D为噪声（允许失真）功率。,R（D）：由正态分布的信息率失真函数的公式：,实际语音的R(D)值要小于4.3bit，因为语音不遵从正态分布，而是近似遵从Laplace分布（一级近似）、Gamma分布（二级近似）。它们的R(D)函数值均小于正态分布的R(D)值。可见，4.3bit至现用的PCM 8bit，大约有一倍差距。

16、,7.5:限失真信源编码定理应用4,例2：若对语音编码进一步计入相关性，则其R(D)函数为：则可算出其R(D)值，即对应压缩比（相对于PCM编码64Kb/s）若计入语音实际分布，R(D)值小于正态分布值，以及R(D)的主观特征，在25-26dB要求下，实际R(D)值大约等于2左右，可以获得大约4倍的压缩比。,结论：,压缩比K,1）,2）,压缩比K,7.5:限失真信源编码定理应用5,例3：参量编码：以英语为例，其音素大约为128256个，按照通常讲话速率，每秒大约平均发出10 个音素，这时语音信源给出的信息率为：,7.6:香农三大定理的关系和比较1,7.7:香农三大定理的关系和比较2,作业,1、

17、一个四元对称信源U接收符号为V=0，1，2，3，其失真矩阵为：求Dmax和Dmin及信源的R(D)函数，并画出其曲线(取4至5个点)。,二元对称信源的R(D)函数,已知：U0,1,P(u)=，1,=1/2，,V0,1,(1)Dmin=0,可以找到满足该最小失真的信道，且是一个无噪无损的信道，信道矩阵为：,计算得：R(0)=I(U;V)=H(),Dmin=Dmax,可以找到满足该最大失真的信道，信道矩阵为：,计算得：R(Dmax)=R()=I(U;V)=0,(2),(3)0DDmax=时，平均失真为：,选取任一信道使 得平均互信息,根据费诺不等式，二进制时有：,所以有：,为了验证这一点，需要找到一个试验信道，使其,汉明失真测度下，二元对称信源的信息率失真函数为：,高斯信源的R(D)计算已知条件：高斯信源U，其均值为m，方差为2，接收变量V概密函数：失真函数：均方误差失真，即：计算平均失真度,设：,根据连续信源最大熵原理，在已知v的条件下，得条件熵,因此：,詹森不等式,当允许失真为D，而当 时，有：,又因：,而信源U时高斯信源，故：,由此得，在任何情况下：,根据R(D)的定义，有：,因为在任何情况下，有R(D)=0，所以：,