第六章率失真函数理论及限失真信源编码

第六章：限失真信源编码6.TheSourceCodingWithFiniteDistortion6.1信息率失真函数的基本概念与定义6.2信息率失真函数的性质6.3离散信源的率失真函数计算6.4离散信源率失真函数的迭代算法6.5连续信源的率失真函数6.6限失真信源编码编码定理的应用,信息论1,第六章：限失真信源编码,6.1信息率失真函数的基本概念与定义(TheBasicConceptsandDefinitionsofRate-DistortionFunction)到目前为止，从数学角度看我们所讲的信息论的内容也仅有两个最基本的概念；而由这两概念出发，引出了一系列的概念和应用的讨论。下面我们将这些概念、定义相继出现的思路作一介绍：,随机事件,自信息(不确定度),平均不确定度,平均不确定度的解除量,最大传信率,6.1率失真函数的基本概念与定义,.有关对信源的客观描述即H(X)问题，注意这种描述是与信道、信宿无关，它仅反映信源本身含有信息的度量和它发送信息的能力。.指如何描述给定信道的功能特征，这也是在与信源、信宿无关的条件下，纯客观地评价一个信道固有特性问题。即，C是反映当给定信道后与某种信源处于最佳匹配时的最大信息传输量问题。.指了解信宿与信源之间的某种需求并且体现与信道无关的客观描述R(D)信息率失真函数。,如果从系统模型来看我们也只讲了两个内容：,6.1率失真函数的基本概念与定义,由于我们学习的是窄义信息论(SpecialInformationTheorem)是要求从事物的客观性(objectivity)出发讨论问题，而不涉及它的主观性(subjectivity)。但对于信宿而言，它是系统中依赖于主观性最多的部分。一般来说Shannons信息论是不具体讨论信宿问题，最多采用使它理想化(idealize)的策略来描述系统中一种固有的信源与信宿间的匹配关系。换句话说，是去掉了信宿中的主观因素，而后讨论仍属于窄义信息论的问题。对于R(D)率失真函数的概念，从数学上讲它是一个与信道容量相对偶(dualproblem)的数学问题。即，一个是求某种条件下互信息的最大值问题；而另一个是求某种条件下互信息的极小值问题。所以它们都是互信息的条件极值问题。但是从物理概念上看，率失真函数它反映的是实际信源与理想化信宿之间的某种依赖关系。即实际中存在的信息率与失真程度间的关系，因为在源端所发出的信息率越高，则在收端所收到,6.1率失真函数的基本概念与定义,的信息损失才能越少。比如：语音源是发出速码率为R64kbit/s的语声信号时，对于人耳来说应该几乎没有失真；而当速码率降低为R32kbit/s时，人耳就会对此类语声信息的接受产生失真影响，如感觉到沙沙声，但有这点失真也无妨，因为它对人类的理解毫无影响；如果再进一步降低信息率，若R16kbit/s时，则明显感到失真加大，听起来费劲；如果再低当R8kbit/s时，人类的听觉器官就可能不适应，甚至时间一长会厌烦此类信号，因为它不仅带来了语声清晰度的失真，而且也大大影响了可懂度方面的效果。因此信息率R与失真程度之间的确存在某种依赖关系，问题时如何用某种数学方法将它描述。问题的另一方面是如何用数学关系式定量地描述失真限度，即什么是信宿可接受的失真程度；什么情况下又是信宿不能接受的失真程度。所以这种数学描述的第一步是如何将失真程度的大小定量地给出；其次才是能否在失真度D定义给出之后，找到一,6.1率失真函数的基本概念与定义,种信息率的性能界限：R(D);使得信宿在RR(D)时，收到信息后所产生的失真应不会大于所给定的失真要求D。一旦R0，则对S的取值就应有一定的要求，这就是参量S的定义域问题。关于S的选取问题我们将会详细讨论。这样我们就可以由式解出m个qj来；然后再从式求得n个i来;则再由式求得nm个以S为参量的Pji。由于我们严格按导数为零的方法求解得到的一组Pji，因此若将此组Pji代入互信息公式，则一定得到我们所期望的最小值R(D)。,二、参量S的性质：首先我们证明：S是R(D)函数的斜率；即：,6.3离散信源率失真函数的计算,这是因为根据全导数公式：,6.3离散信源率失真函数的计算,6.3离散信源率失真函数的计算,则，对上式两边对S求导：,再对两边同乘qj并对j求和得：,6.3离散信源率失真函数的计算,所以S一定是D的具有严格递增和下凸性的函数。,因为在R(D)的性质讨论中R(D)具有严格递减和下凸性：,下面我们再讨论当D0时和DDmax时S的值？,6.3离散信源率失真函数的计算,所以此刻要使D0；必有S。,考虑普遍性，即在m*n个乘积项中只要有一项使得：,下面再讨论当DDmax时S的值？,有了以上讨论，就可以大致画出R(D)函数和斜率曲线S(D)形式。很明显在D0处的斜率S将趋于无穷大，尤其对于连续信源其R(D)函数曲线将不予R轴相交。如虚线所示。而在DDmax处的斜率S常有从某一负值突跳到0,因而在这一点上S(D)曲线有时不连续,而其它定义域内均为D的连续函数。,6.3离散信源率失真函数的计算,三、一般离散信源率失真函数的计算步骤：1.给定信源特性及失真函数定义。2.设定参数S和计算相关变量。,6.3离散信源率失真函数的计算,6.3离散信源率失真函数的计算,3.计算率失真函数的参量表达式(Parametricexpression)：,四、二元信源在对称失真函数定义下的率失真函数,这样的条件下，我们称该信源为二元对称信源。BinarySymmetricSource-BSS由于此类信源的特殊性，故可以求得它的信息率失真函数的解析表达式:,6.3离散信源率失真函数的计算,例6-4：我们按照上节所给出的求解步骤依次解答。,6.3离散信源率失真函数的计算,第二步：求解参数方程,解之:,6.3离散信源率失真函数的计算,又根据所计算出的i列出方程：,其中的q为理想的输出分布。,6.3离散信源率失真函数的计算,解之：,下一步带入参数表达式R(D)：,6.3离散信源率失真函数的计算,实际上对于这种最简单的离散信源，我们可以利用S和D的关系来消掉参数S，从而得到R(D)的解析式，但它仅是一个特例。,6.3离散信源率失真函数的计算,我们只要将S和exp(s)带入R(s)中就可得到R(D)函数的解析表达式：,以下我们讨论该式的物理意义：,6.3离散信源率失真函数的计算,此式表达了这样一种含义：由于第一项H(X)=H(Pi)反映出信源本身客观存在的信息率；而后一项H(D/)，则给出由于信宿可以容忍一定的失真，因而可需压缩的信息率。,H(X)就是原有的信息率，减去由于容忍一定的失真D，而可以节省掉的信息率H(D)，所剩下的就是必须要传送的信息率R(D)。,第六章：限失真信源编码,6.4离散信源率失真函数的迭代算法(Theiterationalgorithmofrate-distortionfunctionfordiscretesource)一般来说求解R(D)函数并非易事，仅有某些特例方可得到R(D)函数的解析式,而绝大多数均由参量表达式给出。即使这种场合计算起来也很困难,因此我们大都借助计算机计算。因此求证R(D)函数的迭代算法公式是非常必要的环节，本节将导出一种常用的计算机迭代算法。,注意：当给定参量S后,可以证明：,6.4离散信源率失真函数的迭代算法,此式表达了这样一种含义：可以把Pji和qj分别看成是独立的变量看待；而使F为极小，从而所求得的P*ji和q*j为最佳分布。,下面我们就可推导R(D)函数的迭代公式。因为F(S,Pji,qj)是Pji和qj的下凸函数，所以可以先固定Pji，求q*j？,6.4离散信源率失真函数的迭代算法,式说明了只要q*j是通常意义下Y的无条件概率，就可以使的在固定Pji的条件下，而使F为极小。此式也是求q*j的迭代计算公式。,6.4离散信源率失真函数的迭代算法,下面再换过来，若固定qj不变，则在的约束条件下求F的极小值：,6.4离散信源率失真函数的迭代算法,6.4离散信源率失真函数的迭代算法,式说明了当qj固定以后，而使F为极小时的条件概率P*ji的迭代计算公式。这样有了这两个计算公式，在给定了任选的初始值Pji(0)后就可启动迭代计算。,6.4离散信源率失真函数的迭代算法,6.4离散信源率失真函数的迭代算法,这两个表达式表明了上述迭代算法的一致收敛性，有参考书中可以查到收敛性的证明，如北邮出版社的信息理论与编码，这里证明从略。上述算法的程序流程图与信道容量的迭代算法流程框图基本相似。但需要指出的是在那里计算的仅是一个C的值；而这里的每一次迭代计算值，仅是一个R(D)曲线上的坐标点。要将无数多个不同的参量S所对应的不同的D(S)、R(S)值都求出来才能构成一个函数曲线。,第六章：限失真信源编码,6.5连续信源的率失真函数(TheRate-DistortionFunctionforContinuousSource)由于连续信源的率失真函数要涉及到求泛涵的极值问题，所采用的数学工具为变分法VariationalMethod。为此我们只得先简单地给出数学中解决泛函极值问题的变分法的基本概念和具体应用。先看求解率失真函数的数学机理：,而互信息的定义式为：,6.5连续信源的率失真函数,所谓下确界是指那些连续变量的泛函的极值点不是可以达到，而是无限逼近这一数值点。,一、变分法的定义与应用.泛函（functional）如果对于某一类函数的集合y(x)中每一个函数y(x)均有唯一的一个值v与之对应，那么变量V则称为依赖于函数y(x)的泛函。,6.5连续信源的率失真函数,.函数的变分（Variationoffunction）所谓泛函的自变量，即函数y(x)的改变量，我们称为变分。即：两个函数的差，其中y0(x)是与y(x)属于同一函数类y(x)。,一、变分法的定义与应用,.泛函的变分（Variationoffunctional）,一、变分法的定义与应用,注意：通常可以按数学定义写出泛函的变分表达式，但是计算比较麻烦，因而可用采用表达式(I)这样的具体办法来求解泛函变分的表达式。其数学证明见下：,一、变分法的定义与应用,一、变分法的定义与应用,.泛函的极值（Limitoffunctional）若泛函在与接近的任意曲线上的值不小于(或不大于)即：,一、变分法的定义与应用,一般来讲，寻求泛函的极值问题，就是要寻求某一函数y(x)，而使其泛函的值达到极大或极小，显然利用变分为零的特性，是很容易求解的，这就是变分法求极值的基本概念。现在回到求连续信源的率失真函数的实际问题上，我们是要求一个泛函的条件极值问题：即：,一、变分法的定义与应用,由于求的是条件极值问题，就要引入一个待定函数(x)和一个待定的常数S，用来约束引入的条件。,显然JP(y/x)也是P(y/x)的泛函，因此可按变分法的法则来求这个泛函的极小值。首先求其变分，再令它为零，从而得出P(y/x)的特定分布。,一、变分法的定义与应用,以上这是按泛函变分的定义解法，即寻求泛函改变量中有关(x,y)的一次项表达式。,一、变分法的定义与应用,一、变分法的定义与应用,一、变分法的定义与应用,一、变分法的定义与应用,一、变分法的定义与应用,一、变分法的定义与应用,下面总结一下计算连续信源R(D)函数的步骤：,一、变分法的定义与应用,一、变分法的定义与应用,5o将所有S的应取值选到，得所对应的和坐标值，从而得到函数曲线。,以上推到仅从变分法入手，得到求解泛函极小值的目的，但是实际求解积分方程，并非易事。特别是想得到(x)和q(y)的严格解非常困难，通常都是采用数值解法得到近似解。不过实际应用也有特例，应用数学技巧可以简化求解方法。比如一些相对于失真函数为：时；有解析式！,（留做习题！）,一、变分法的定义与应用,二、某些失真函数定义下的连续信源的率失真函数当d(x,y)=f(x-y)时：这种场合下，求泛函条件极值的问题，可以大大简化。,6.5连续信源的率失真函数,二、特殊失真定义下连续信源的R(D),二、特殊失真定义下连续信源的R(D),这种场合下，求解积分方程问题就变成求两个函数卷积的问题。,二、特殊失真定义下连续信源的R(D),如果当gs(x)和p(x)已知时，从两个函数的卷积关系中可以得到qo(x)的值,从而避免了求解积分方程的麻烦。但是一般性的求解卷积问题也不轻松,所以还要利用一些变换关系来继续简化。,二、特殊失真定义下连续信源的R(D),二、特殊失真定义下连续信源的R(D),然后再利用Fourier反变换公式求得qo(y):,二、特殊失真定义下连续信源的R(D),下面我们利用此种解法，求解高斯信源的率失真函数R(D)。,三、高斯信源的率失真函数(TheRate-DistortionFunctionforGaussianSource),当配方成正态分布的形式后,可见gs(x)体现为均值为零，方差为(-1/2S)高斯变量的概率密度函数,即：（0,-1/2S）。,6.5连续信源的率失真函数,三、高斯信源的率失真函数,由随机过程的理论可知，正态变量N(m,2)的特征函数为：,三、高斯信源的率失真函数,显然由qo(y)的特征函数的形式看出它也是高斯变量的特征函数，只不过方差是为(2+1/2S)，均值为m。,当解析式中的数字-()被消掉之后，对数函数就可以任意数为底，这样单位就不会被限定。这是高斯变量在均方失真定义下的信息率失真函数,其值仅与压缩信噪比D=E(x-y)2有关,而与均值m无关。,三、高斯信源的率失真函数,若设2=1时，由标准正态变量所对应的和的曲线如图所示,显然,这说明倘若允许失真的方差是1,那么不用传送信源实际输出,仅用信源的均值m表示信源的任意值,都可以得到均方误差为1的代价。而对于D1的情况,就得传输信息,但要满足失真要求就不容易了,如：D=；R()=1比特，这就是说至少需要1比特/符号的信息率才能保证平均误差达到，但实际的单符号量化编码很难达到。不妨用二进制编码来传输这个连续变量！设：,三、高斯信源的率失真函数,若采用这样的标量量化方案，其所对应的均方失真D的计算值为：,三、高斯信源的率失真函数,例67.对于语音信源，假设它的概率分布为高斯分布，其信号功率为，编码后失真为D，且失真度为：d(x,y)=(x-y)下，问：当数字电话中要求输入信噪比/D为26dB时，它的最小传输信息率为何？,即为编码失真信噪比。可见高斯变量在均方误差准则下的率失真函数解析表达式中信息率只与信噪比有关。,三、高斯信源的率失真函数,但实际上的数字量化技术所采用的A/D芯片，最少也得八位(8bit)采样量化。最后还有一个实际问题，就是如果连续信源不是高斯分布的情况，(如此例中语音信号应是指数分布)则求得率失真函数的精确解就非常困难。通常我们仍然采用老办法：,即，用高斯分布来代替非高斯的情况。但它仍是一个保守的估计。,这是工程设计所坚持的原则！,三、高斯信源的率失真函数,第六章：限失真信源编码,6.6Shannons编码定理体系(TheShannonsCodingTheoremSystem),Objectiveexistence客观存在性H(X),Possibility最大可能性C,Practicalrequirement实际需求性R(D),编码极限定理CodingLimitedTheorem,6.6Shannons编码定理体制,以上三个不等式分别代表了三类编码极限定理：Shannons1stlimitingtheorem为无失真信源编码定理。Shannons2ndlimitingtheorem为信道编码定理。Shannons3rdlimitingtheorem为限失真信源编码定理。这三个极限定理构成了Shannon编码定理体系。极限定理都有其共性，也有个性。所给出的指导作用也各不相同，但其证明方式都采用随机编码方式证明。所谓存在性，是指定理仅给出是否存在着一种(至少一种)编码方式可以满足要求；但如何编码则无可奉告。它们的逆定理则给出了不存在性，这是它们的共性。所谓构造性，是指定理不仅指出了存在性，而且还给出了最佳码字的结构特性，如码长、代码形式等。,谢谢！,第六章(结束),课程复习大纲,ElementsofInformationTheoremSummary,SourceCoding,限失真,课程复习大纲,.Information，message&signal任何一种通信方式都可以归结为：某一信源在发消息；而消息又要变成适合某种信道传输的信号。对接收者来说，则是通过所接受到的信号，而得知消息；从消息中所包含随机事件不确定度的是否减少来获得信息。所以消息是信息的载体；信息是消息的内涵；但信号又是消息符合某种物理特性的载体。要重点理解信息的基本属性，消息的基本特征和信号的固有特征。.概率信息的特征:(三要素）.随机事件的随机性随机变量。.从事物的客观性出发，所带给人们的新知识。.