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

率失真函数理论及限失真信源编码第1页，课件共71页，创作于2023年2月第六章：限失真信源编码

§6.1

信息率失真函数的基本概念与定义

(TheBasicConceptsandDefinitionsofRate-DistortionFunction)

到目前为止，从数学角度看我们所讲的《信息论》的内容也仅有两个最基本的概念；而由这两概念出发，引出了一系列的概念和应用的讨论。下面我们将这些概念、定义相继出现的思路作一介绍：随机事件

自信息(不确定度)平均不确定度平均不确定度的解除量最大传信率

下的最小传信率满足失真

要求第2页，课件共71页，创作于2023年2月§6.1

率失真函数的基本概念与定义

①.有关对信源的客观描述即H(X)

问题，注意这种描述是与信道、信宿无关，它仅反映信源本身含有信息的度量和它发送信息的能力。

②

.指如何描述给定信道的功能特征，这也是在与信源、信宿无关的条件下，纯客观地评价一个信道固有特性问题。即，C

是反映当给定信道后与某种信源处于最佳匹配时的最大信息传输量问题。

③.指了解信宿与信源之间的某种需求并且体现与信道无关的客观描述——R(D)

信息率失真函数。如果从系统模型来看我们也只讲了两个内容：信源Source信道Channel信宿DestinationXY第3页，课件共71页，创作于2023年2月§6.1

率失真函数的基本概念与定义

由于我们学习的是窄义信息论(SpecialInformationTheorem)是要求从事物的客观性(objectivity)出发讨论问题，而不涉及它的主观性(subjectivity)

。但对于信宿而言，它是系统中依赖于主观性最多的部分。一般来说Shannon’s信息论是不具体讨论信宿问题，最多采用使它理想化(idealize)的策略来描述系统中一种固有的信源与信宿间的匹配关系。换句话说，是去掉了信宿中的主观因素，而后讨论仍属于窄义信息论的问题。对于R(D)

率失真函数的概念，从数学上讲它是一个与信道容量相对偶(dualproblem)的数学问题。即，一个是求某种条件下互信息的最大值问题；而另一个是求某种条件下互信息的极小值问题。所以它们都是互信息的条件极值问题。但是从物理概念上看，率失真函数它反映的是实际信源与理想化信宿之间的某种依赖关系。即实际中存在的信息率与失真程度间的关系，因为在源端所发出的信息率越高，则在收端所收到第4页，课件共71页，创作于2023年2月§6.1

率失真函数的基本概念与定义的信息损失才能越少。比如：语音源是发出速码率为R＝64kbit/s

的语声信号时，对于人耳来说应该几乎没有失真；而当速码率降低为R＝32kbit/s时，人耳就会对此类语声信息的接受产生失真影响，如感觉到沙沙声，但有这点失真也无妨，因为它对人类的理解毫无影响；如果再进一步降低信息率，若R＝16kbit/s

时，则明显感到失真加大，听起来费劲；如果再低当R＝8kbit/s

时，人类的听觉器官就可能不适应，甚至时间一长会厌烦此类信号，因为它不仅带来了语声清晰度的失真，而且也大大影响了可懂度方面的效果。因此信息率R与失真程度之间的确存在某种依赖关系，问题时如何用某种数学方法将它描述。问题的另一方面是如何用数学关系式定量地描述失真限度，即什么是信宿可接受的失真程度；什么情况下又是信宿不能接受的失真程度。所以这种数学描述的第一步是如何将失真程度的大小定量地给出；其次才是能否在失真度D定义给出之后，找到一第5页，课件共71页，创作于2023年2月§6.1

率失真函数的基本概念与定义种信息率的性能界限：R(D);使得信宿在R>R(D)时，收到信息后所产生的失真应不会大于所给定的失真要求D。一旦R<R(D)以后实际失真将必定大于失真要求D。这种信源与信宿的依存关系，就是与信道无关的条件下，所要讨论的率失真函数的概念。一、失真度的定义:

(TheDefinitionofDistortionFunction)

所谓失真函数或失真度，即信息传输中所产生的失真。可采用以下数学方法描述：如果用d(x,y)

表示当发端为x，而收端为

y

时所定义的某种误差代价；或者是当用y

来代替x

时，所定量的失真度。具体的讲，对于离散信源设发端;收端：；当发时收到符号的情况下定义失真度为：第6页，课件共71页，创作于2023年2月§6.1

率失真函数的基本概念与定义

当然，可以是一个常量，也可以是一变量。如果用某一个来代替任何一个，所造成的失真都是等效的，那么应是常量；反之它就是变量，因为它所反映的失真代价和效果各不相同。下面我们各举一例说明失真函数的表示方法。例6-1.0011则，失真度矩阵可表示为：第7页，课件共71页，创作于2023年2月§6.1

率失真函数的基本概念与定义例6-2.则，失真度的三种表示方法为：第8页，课件共71页，创作于2023年2月§6.1

率失真函数的基本概念与定义

注意这仅是给出的失真度定义，为了衡量整个信源与信宿的总体失真关系，还得有一个总体统计参量：失真函数的统计平均值——平均失真(averagedistortion)第9页，课件共71页，创作于2023年2月§6.1

率失真函数的基本概念与定义

在连续信源的情况下，失真函数的定义形式就更多，最常见的几种误差准则是：绝对误差准则：(absoluteerrorcriterion)相对误差准则：(relativeerrorcriterion)均方误差准则：(squarederrorcriterion)对数失真准则：(logarithmicdistortioncriterion)第10页，课件共71页，创作于2023年2月§6.1

率失真函数的基本概念与定义注意：d(x,y)

是人为的传输失真定义，它仅表示后果的代价程度，是一‘权值’的概念。但它是与信息传输本身无关的量；而E[d(x,y)]则是一个与信源、信道特性均有关的统计参量。如果对信息传输过程中的平均失真规定在一个范围之内，比如小于某一指定值D即，这无疑是对传输特性P(y/x)

有了规定限制，是要保证：

因为Pi反映信源特性，而给定信源则表示Pi已给定，不能改变；而Pji是代表传输特性，这时只有它可以在某种范围内选择，即表示改变不同的传输手段。如果选出的每一种传输方案都能保证平均失真满足要求，则可以定义：凡是满足失真要求的信道Pji;我们把它归为一类,记为集合BD

。该集合中的任一元素都可使上式成立，即满足失真要求。第11页，课件共71页，创作于2023年2月§6.1

率失真函数的基本概念与定义

只有这样才能把失真要求D和传输特性P(y/x)联系起来，才为引出率失真函数打下基础。二、信息率失真函数的定义:

(TheDefinitionofRate-distortionFunction)

互信息I(X;Y)不仅是P(x)的函数；而且也是P(y/x)的函数。严格地讲I(X;Y)应是P(x)和P(y/x)的泛函(functional)。在第四章我们讨论过

I(X;Y)是关于P(x)的上凸函数，从而才有它的极大值问题。从数学上讲，这还有一个对偶问题，即求互信息的极小值问题。书中定理4.2.2给出了在给定P(x)的条件下，I(X;Y)是P(y/x)的下凸函数的证明。这预示在一定条件下存在着I(X;Y)的极小值问题。第12页，课件共71页，创作于2023年2月§6.1

率失真函数的基本概念与定义

如果我们引入一个条件，即平均失真受限的条件，则求互信息的极小值问题就变成了非常有用的问题。

Definition:这就是信息率失真函数的数学定义式，从定义来看，它似乎是一个非常简单的数学问题。把它与信道容量的定义和概念相比较，我们就能得出它们之间的对偶关系：第13页，课件共71页，创作于2023年2月§6.1

率失真函数的基本概念与定义DualRelations1º2º3º4º5ºFindingmaximum;Findingminimum;I(X;Y)

isa

functionof

p(x).I(X;Y)

isa

functionof

P(y/x).

C是表示信源与信道在匹配条件下的最大传信率；在RC下,可实现可靠传输。R(D)是表达信源与失真要求匹配条件下的最小传信率；在RR(D)下，总能找到一种编码方法,满足信宿要求。Guideaction:ChannelcodingproblemSourcecodingproblemwithfinitedistortion(DataCompression)第14页，课件共71页，创作于2023年2月§6.1

率失真函数的基本概念与定义注意：在定义R(D)时用到了条件概率P(y/x)

，在此之前我们都认为P(y/x)

表征了某信道的特征；但在讨论率失真函数时P(y/x)

已不代表实际信道了，因为它仅是数学中为调整I(X;Y)而变化的参量。一般我们称P(y/x)

为试验信道特性，这是一个虚拟的、可变的信道，目的是为了寻求在满足失真要求下，最小容量的传输方案，一旦有了结论，则在实际工程设计中就可参照此试验信道特性设计合理的编码方法。下面举一例来讨论R(D)函数的作用。例6-3.

设一八种符号的等概率离散信源：如果要实现无失真编码，则要有3个二进制代码。所以信息率R为：若假设编解码系统只允许有一位代码失真，且失真度定义为：第15页，课件共71页，创作于2023年2月§6.1

率失真函数的基本概念与定义问：寻求一种压缩编码方案，且比较它是否还有进一步压缩的余地？解：

这里设计了一种压缩编码方法，对凡是有两个‘0’的码字序列都按‘000’处理；凡是有两个‘1’的序列都按‘111’处理。这样原来发3bit的信息只发一比特。因为原来发三位码的时间内，只需发一位码，所以:但是失真一定满足要求。第16页，课件共71页，创作于2023年2月§6.1

率失真函数的基本概念与定义计算它的平均失真：

可见经过压缩编码后，信息率由1bit压缩到1/3bit;而付出的代价是产生了1/4的平均失真。如果问当允许平均失真为1/4时，此压缩方案是否最佳？这就要看R(D)的作用了。因为对任何二进制信源在对称失真函数的定义下有：第17页，课件共71页，创作于2023年2月第六章：限失真信源编码§6.2

信息率失真函数的性质

(ThePropertiesofRate-DistortionFunction)

一、非负性

即，D0,R(D)0

因为I(X;Y)0

二、这就是使得R(D)=0

的最小的D值。

由于，R(D)是一个非负函数，则它的下界就是‘0’,因此下界与D对应的值设定为D

max，设脚标为最大即意味着所允许的最大失真。当DD

max时，R(D)一定为零，所以

D

max实际就是D允许的上界。第18页，课件共71页，创作于2023年2月§6.2

率失真函数的性质第19页，课件共71页，创作于2023年2月§6.2

率失真函数的性质三、离散信源下：R(0)=H(X)连续信源下：

R(D

min

)=

H

max(

Y

)四、Indomain[0,D

max],R(D)isalowerconvexfunctionforD.

五、Indomain[0,D

max],R(D)isastrictlyreduceandcontinuousfunctionforD.在定义域中，R(D)是D的单调递减而且连续的函数。第20页，课件共71页，创作于2023年2月§6.2

率失真函数的性质六、

如果设S为R(D)在D点的斜率，则斜率曲线S(D)将有可能是在定义域(0,D

max]边界处产生间断的曲线。(证明见后)

有了以上六条性质，就可以大致画出R(D)函数和S(D)斜率曲线形式。很明显在D＝0处的斜率将趋于无穷大，尤其对于连续信源，其R(D)函数曲线将不予R轴相交，如虚线所示。如果限定失真为D1=P

e

；则，限失真条件下的信息压缩率的最小值为R(D1)，此处将为一分界点把R轴分为两部分。在其上部，即

RR(D1)才有可能出现合理的压缩编码方式；否则一切编码均要产生超出失真要求的平均失真。R(D);S(D)D0H(X)R(D1)D1S

max第21页，课件共71页，创作于2023年2月第六章：限失真信源编码

§6.3

离散信源率失真函数的计算

(TheCalculationofRate-DistortionFunctionforDiscreteSource)一、一般离散信源率失真函数的参量表达式：

虽然率失真函数和信道容量一样是求一个条件极值的数学问题，但真正计算起来并不容易,特别是要想得到它的解析表达式相当困难，一般我们仅采用参量表达式。其中，S为R(D)函数的斜率，是以它为参量的表达式。第22页，课件共71页，创作于2023年2月§6.3离散信源率失真函数的计算下面我们分析求解R(D)函数的一般计算规律：带入n+1个约束条件：第23页，课件共71页，创作于2023年2月§6.3离散信源率失真函数的计算因为有n＋1个约束条件，则求条件极值共需要n＋1个Lagrangemultipliers：求偏导并整理后得：上式两边共除以Pi得：第24页，课件共71页，创作于2023年2月§6.3离散信源率失真函数的计算得到n*m个联立方程组：整理后得：不算参量S还有三个未知量，再改变一下形式得：第25页，课件共71页，创作于2023年2月§6.3离散信源率失真函数的计算对<1>式两边同乘Pi再对i求和得：其中的λi为唯一的未知数，在n=m的条件下有唯一的解；若nm

，则上式失去一般性。故再将<2>式代入<3>式中：得m个关于qj的联立方程组：第26页，课件共71页，创作于2023年2月§6.3离散信源率失真函数的计算

为了使得qj>0，则对S的取值就应有一定的要求，这就是参量S的定义域问题。关于S的选取问题我们将会详细讨论。这样我们就可以由<4>式解出m个qj来；然后再从<2>式求得n个λi来;则再由<1>式求得nm个以S为参量的Pji

。由于我们严格按导数为零的方法求解得到的一组Pji°，因此若将此组Pji°代入互信息公式，则一定得到我们所期望的最小值——R(D)。第27页，课件共71页，创作于2023年2月二、参量S的性质：

首先我们证明：S是R(D)函数的斜率；即：§6.3离散信源率失真函数的计算这是因为根据全导数公式：第28页，课件共71页，创作于2023年2月§6.3离散信源率失真函数的计算第29页，课件共71页，创作于2023年2月§6.3离散信源率失真函数的计算则，对上式两边对S求导：再对两边同乘qj

并对j求和得：第30页，课件共71页，创作于2023年2月§6.3离散信源率失真函数的计算所以S一定是D的具有严格递增和下凸性的函数。因为在R(D)的性质讨论中R(D)具有严格递减和下凸性：下面我们再讨论当D＝0时和D＝Dmax时S的值？第31页，课件共71页，创作于2023年2月§6.3离散信源率失真函数的计算所以此刻要使D＝0

；必有S＝－∞。考虑普遍性，即在m*n个乘积项中只要有一项使得：下面再讨论当D＝Dmax时S的值？第32页，课件共71页，创作于2023年2月

有了以上讨论，就可以大致画出R(D)函数和斜率曲线S(D)形式。很明显在D＝0处的斜率S将趋于无穷大，尤其对于连续信源其R(D)函数曲线将不予R轴相交。如虚线所示。而在D＝Dmax处的斜率S常有从某一负值突跳到0,因而在这一点上S(D)曲线有时不连续,而其它定义域内均为D的连续函数。§6.3离散信源率失真函数的计算R(D);S(D)D0H(X)R(D1)D1S

max定义域是值域是。第33页，课件共71页，创作于2023年2月三、一般离散信源率失真函数的计算步骤：

1º.给定信源特性及失真函数定义。

2º.设定参数S和计算相关变量。§6.3离散信源率失真函数的计算第34页，课件共71页，创作于2023年2月§6.3离散信源率失真函数的计算3º.计算率失真函数的参量表达式(Parametricexpression)：四、二元信源在对称失真函数定义下的率失真函数

这样的条件下，我们称该信源为二元对称信源。BinarySymmetricSource---BSS

由于此类信源的特殊性，故可以求得它的信息率失真函数的解析表达式:第35页，课件共71页，创作于2023年2月§6.3离散信源率失真函数的计算例6-4：我们按照上节所给出的求解步骤依次解答。第36页，课件共71页，创作于2023年2月§6.3离散信源率失真函数的计算第二步：求解参数方程解之:第37页，课件共71页，创作于2023年2月§6.3离散信源率失真函数的计算又根据所计算出的i列出方程：其中的q为理想的输出分布。带入i得联立方程组：第38页，课件共71页，创作于2023年2月§6.3离散信源率失真函数的计算解之：下一步带入参数表达式R(D)：第39页，课件共71页，创作于2023年2月§6.3离散信源率失真函数的计算

实际上对于这种最简单的离散信源，我们可以利用S和D的关系来消掉参数S，从而得到R(D)

的解析式，但它仅是一个特例。第40页，课件共71页，创作于2023年2月§6.3离散信源率失真函数的计算

我们只要将S和exp(s)带入R(s)中就可得到R(D)函数的解析表达式：以下我们讨论该式的物理意义：第41页，课件共71页，创作于2023年2月§6.3离散信源率失真函数的计算

此式表达了这样一种含义：由于第一项H(X)=H(Pi)

反映出信源本身客观存在的信息率；而后一项H(D/)，则给出由于信宿可以容忍一定的失真，因而可需压缩的信息率。

H(X)就是原有的信息率，减去由于容忍一定的失真D，而可以节省掉的信息率H(D)，所剩下的就是必须要传送的信息率R(D)。第42页，课件共71页，创作于2023年2月第六章：限失真信源编码

§6.4

离散信源率失真函数的迭代算法

(Theiterationalgorithmofrate-distortionfunctionfordiscretesource)

一般来说求解R(D)函数并非易事，仅有某些特例方可得到R(D)函数的解析式,而绝大多数均由参量表达式给出。即使这种场合计算起来也很困难,因此我们大都借助计算机计算。因此求证R(D)函数的迭代算法公式是非常必要的环节，本节将导出一种常用的计算机迭代算法。注意：当给定参量S后,可以证明：第43页，课件共71页，创作于2023年2月§6.4离散信源率失真函数的迭代算法

此式表达了这样一种含义：可以把Pji和qj分别看成是独立的变量看待；而使F为极小，从而所求得的P*ji和q*j为最佳分布。下面我们就可推导R(D)函数的迭代公式。因为F(S,Pji,qj)是Pji

和

qj的下凸函数，所以可以先固定Pji

，求q*j

？第44页，课件共71页，创作于2023年2月§6.4离散信源率失真函数的迭代算法

<1>式说明了只要q*j是通常意义下Y的无条件概率，就可以使的在固定Pji的条件下，而使F为极小。此式也是求q*j的迭代计算公式。第45页，课件共71页，创作于2023年2月§6.4离散信源率失真函数的迭代算法

下面再换过来，若固定qj不变，则在的约束条件下求F的极小值：第46页，课件共71页，创作于2023年2月§6.4离散信源率失真函数的迭代算法第47页，课件共71页，创作于2023年2月§6.4离散信源率失真函数的迭代算法

<2>式说明了当qj固定以后，而使F为极小时的条件概率P*ji的迭代计算公式。这样有了这两个计算公式，在给定了任选的初始值[Pji](0)后就可启动迭代计算。第48页，课件共71页，创作于2023年2月§6.4离散信源率失真函数的迭代算法第49页，课件共71页，创作于2023年2月§6.4离散信源率失真函数的迭代算法

这两个表达式表明了上述迭代算法的一致收敛性，有参考书中可以查到收敛性的证明，如北邮出版社的《信息理论与编码》，这里证明从略。上述算法的程序流程图与信道容量的迭代算法流程框图基本相似。但需要指出的是在那里计算的仅是一个C的值；而这里的每一次迭代计算值，仅是一个R(D)曲线上的坐标点。要将无数多个不同的参量S所对应的不同的D(S)、R(S)值都求出来才能构成一个函数曲线。第50页，课件共71页，创作于2023年2月第六章：限失真信源编码

§6.5

高斯信源的率失真函数

(TheRate-DistortionFunctionforGaussianSource)

由于连续信源的率失真函数要涉及到求泛涵的极值问题，所采用的数学工具为变分法VariationalMethod。因此我们只得直接给出最典型的连续信源——高斯信源的率失真函数：注意：这仍然还是一个解析式！它也是一特例！第51页，课件共71页，创作于2023年2月§6.5高斯信源的率失真函数

例6－5.对于语音信源，假设它的概率分布为高斯分布，其信号功率为²，编码后失真为D，且失真度为：d(x,y)=(x-y)²下，问：当数字电话中要求输入信噪比²/D为26dB时，它的最小传输信息率为何？这就是高斯变量在均方误差准则下的率失真函数解析表达式。可见信息率只与信噪比有关，即，编码失真信噪比。第52页，课件共71页，创作于2023年2月§6.5高斯信源的率失真函数

但实际上的数字量化技术所采用的A/D芯片，最少也得八位(8bit)采样量化。最后还有一个实际问题，就是如果连续信源不是高斯分布的情况，(如此例中语音信号应是指数分布)则求得率失真函数的精确解就非常困难。通常我们仍然采用老办法：即，用高斯分布来代替非高斯的情况。但它仍是一个保守的估计。DR(D)0这是工程设计所坚持的原则！第53页，课件共71页，创作于2023年2月第六章：限失真信源编码§6.6Shannon’s编码定理体系

(TheShannon’sCodingTheoremSystem)信源Source信道Channel信宿DestinationXYObjectiveexistence

客观存在性

H(X)

Possibility最大可能性

CPracticalrequirement

实际需求性

R(D)编码极限定理——CodingLimitedTheorem第54页，课件共71页，创作于2023年2月§6.6Shannon’s编码定理体制

以上三个不等式分别代表了三类编码极限定理：Shannon’s1stlimitingtheorem为无失真信源编码定理。Shannon’s2ndlimitingtheorem为信道编码定理。Shannon’s3rdlimitingtheorem为限失真信源编码定理。这三个极限定理构成了Shannon’编码定理体系。极限定理都有其共性，也有个性。所给出的指导作用也各不相同，但其证明方式都采用随机编码方式证明。所谓存在性，是指定理仅给出是否存在着一种(至少一种)编码方式可以满足要求；但如何编码则无可奉告。它们的逆定理则给出了不存在性，这是它们的共性。所谓构造性，是指定理不仅指出了存在性，而且还给出了最佳码字的结构特性，如码长、代码形式等。第55页，课件共71页，创作于2023年2月谢谢！第六章(结束)第56页，课件共71页，创作于2023年2月课程复习大纲《ElementsofInformationTheorem》

SummarySourceCoding无失真限失真第57页，课件共71页，创作于2023年2月课程复习大纲⑴.Information，message&signal

任何一种通信方式都可以归结为：某一信源在发消息；而消息又要变成适合某种信道传输的信号。对接收者来说，则是通过所接受到的信号，而得知消息；从消息中所包含随机事件不确定度的是否减少来获得信息。所以消息是信息的载体；信息是消息的内涵；但信号又是消息符合某种物理特性的载体。要重点理解信息的基本属性，消息的基本特征和信号的固有特征。⑵.概率信息的特征:(三要素）ⅰ.

随机事件的随机性——随机变量。ⅱ.从事物的客观性出发，所带给人们的新知