《信息理论与编码》课程教学资源（知识点）第6章 限失真信源编码

第6章限失真信源编码6.1基本要求通过本章学习，了解限失真信源编码的目的，掌握失真度和平均失真度的概念和计算、信息率失真函数的定义和性质、限失真信源编码定理（香农第三定理）的基本思想。了解信息率失真函数的参量表示计算方法和迭代计算方法。6.2学习要点6.2.1失真测度6.2.1.1失真度设信源编码器输入为U={u,u,u,，编码后的输出信源为V={,"2,,")失真度（或失真函数）：编码器输入符号u与输出符号v，之间的误差或失真，用非负实值函数d(u,v）来描述。常用的失真度有：[0,u,=y]误码失真：d(u,y,)=[1,u,y,d(u,y)=(u,-y,)2平方失真：d(u,)=u,-y,l绝对失真：d(u,y,)=|u, -y, l/lu, 1相对失真：6.2.1.2失真矩阵将rxs个d(u,y)排成矩阵形式，称为失真矩阵，记为[d]：VV2Vsd(u,)d(u,v2)d(u,y,)ud(uz,n)d(u,r2)d(uz,v,)(6.1)u[d] =:：:：+.+.d(u,y)d(ur,v,).d(u,,y,)ju,16.2.1.3平均失真度192

192 第 6 章 限失真信源编码 6.1 基本要求 通过本章学习，了解限失真信源编码的目的，掌握失真度和平均失真度的概念和计算、 信息率失真函数的定义和性质、限失真信源编码定理（香农第三定理）的基本思想。了解信 息率失真函数的参量表示计算方法和迭代计算方法。 6.2 学习要点 6.2.1 失真测度 6.2.1.1 失真度 设信源编码器输入为 1 2 {, , , } U uu u   r ，编码后的输出信源为 1 2 {, , , } V vv v   s 失真度（或失真函数）：编码器输入符号 i u 与输出符号 j v 之间的误差或失真，用非负实 值函数 (, ) i j du v 来描述。 常用的失真度有： 误码失真： 0 , (, ) 1, i j i j i j u v du v u v         平方失真： 2 (, ) ( ) ij i j du v u v   绝对失真： (, )| | ij i j du v u v   相对失真： ( , ) | || | ij i j i du v u v u   6.2.1.2 失真矩阵 将 r s  个 (, ) i j du v 排成矩阵形式，称为失真矩阵，记为[ ] d ： 1 2 11 12 1 1 21 22 2 2 1 2 (,) (, ) (,) (,) (,) (,) [ ] (,) (,) (,) s s s r r rs r vv v du v du v du v u du v du v du v u d du v du v du v u               （6.1） 6.2.1.3 平均失真度

对所有符号的失真度[d(u,y,)取统计平均，称为平均失真度或平均失真，记为D：D=E(d(u,y)=ZZP(u,y,)d(u,y,)i=l j=l(6.2)2 P(u,)P(y,lu,)d(u,y)i=l j=l6.2.1.4符号序列的失真度和平均失真度对于符号序列，可将失真度或失真函数的定义可推广到失量形式。设编码器输入α,和输出β,均为N长符号序列，即h=1,2....,rNa,=UnUmUny(6.3)1=1,2,..,sMβ, = V,h"-Vi则N长符号序列的失真度d(αhβ）可定义为d(an,β)=Zd(un,,)(6.4)k=l式中d(uw，）是输入/输出序列第k位符号的失真度。N长符号序列的平均失真度为D(N)=E(d(αn,β)=P(αn,β,)d(αn,β)h=l1=l(6.5)VEP(αh,)Ed(un，Vn)h=1 /=1k=当信源和信道（编码器）均无记忆时，由上式不难推证NNZE(d(un,))-ZD=NDD(N)= (6.6)k=lk=l式中D=D,=·=D=D是单符号的平均失真度。6.2.2信息率失真函数及其性质6.2.2.1试验信道如果要求平均失真D小于某个给定值D，即要求D= E[d(u,y))-2Z P(u,)P(y, lu,)d(u,v)≤D(6.7)i=1j=)193

193 对所有符号的失真度  , (, ) i j i j du v 取统计平均，称为平均失真度或平均失真，记为 D ：   1 1 1 1 ( , ) ( , )( , ) ( )( | )( , ) r s ij ij ij i j r s i j i ij i j D E du v Pu v du v Pu Pv u du v          （6.2） 6.2.1.4 符号序列的失真度和平均失真度 对于符号序列，可将失真度或失真函数的定义可推广到矢量形式。设编码器输入h 和输 出  l 均为 N 长符号序列，即 1 2 1 2 1,2, , 1,2, , N N N h hh h N l ll l uu u h r vv v l s           （6.3） 则 N 长符号序列的失真度 (,) h l d   可定义为 1 (,) (,) k k N hl hl k d du v      （6.4） 式中 (,) k k h l du v 是输入/输出序列第 k 位符号的失真度。 N 长符号序列的平均失真度为   1 1 11 1 ( ) ( , ) ( , )( , ) (,) ( ,) N N N N k k r s hl hl hl h l rs N hl hl hl k DN E d P d P du v                （6.5） 当信源和信道（编码器）均无记忆时，由上式不难推证   1 1 () ( , ) k k N N hl k k k D N E d u v D ND       （6.6） 式中 D1 2    D DD  N 是单符号的平均失真度。 6.2.2 信息率失真函数及其性质 6.2.2.1 试验信道 如果要求平均失真 D 小于某个给定值 D ，即要求   1 1 ( , ) ( )( | )( , ) r s ij i j i ij i j D E du v Pu Pv u du v D      （6.7）

这意味着对转移概率Pyu施加了相应的限制，式（6.7）所给的限制条件称为保真度准则。满足保真度准则D<D的信道称为D允许（试验）信道。所有试验信道的转移概率组成一个集合，记为B,：B,=(Pyu,D≤D)(6.8)要使限失真编码满足保真度准则，则编码器必须是D允许试验信道，即编码器的转移概率Pyu Bp。6.2.2.2率失真函数的定义在B，中寻求一个Pvy（即寻求一个特定的编码器）使I(U;V）最小，这个最小的平均互信息量称为信息率失真函数，简称为率失真函数，记为R(D），即R(D)= min I(U;V)=min(I(U;V);D≤D(6.9)PiyeBp当最小值不存在时，可用下界值代替：R(D)= ,inf I(U;V)(6.10)PyEBp对于离散信源，R(D)可表示成P(y, |u,)R(D)= min P(u,)P(y, /u,)log(6.11)P(v)PryeB台R(D)是保真度准则（D<D）下所必须传输的信息率，也是焰压缩编码器输出可能达到的最低熵率。6.2.2.3序列的信息率失真函数率失真函数可推广到序列情形，对于序列，可用N次扩展信源UN和N次扩展信道{UN,PyNN,VN予以讨论。这种情形下，试验信道为所有满足保真度准则D(N）≤ND的信道的集合，这些试验信道的转移概率组成集合BND：wwun;D(N)≤ ND)BND =(6.12)194

194 这意味着对转移概率 PV U| 施加了相应的限制，式（6.7）所给的限制条件称为保真度准则。满 足保真度准则 D D 的信道称为 D 允许（试验）信道。所有试验信道的转移概率组成一个 集合，记为 BD ： B P DD D VU    | ;  （6.8） 要使限失真编码满足保真度准则，则编码器必须是 D 允许试验信道，即编码器的转移概 率 PVU D |  B 。 6.2.2.2 率失真函数的定义 在 BD 中寻求一个 PV U| （即寻求一个特定的编码器）使 IUV (;) 最小，这个最小的平均互 信息量称为信息率失真函数，简称为率失真函数，记为 R D( ) ，即   | ( ) min ( ; ) min ( ; ); P B VU D R D IUV IUV D D    （6.9） 当最小值不存在时，可用下界值代替： | ( ) inf ( ; ) P B VU D R D IUV   （6.10） 对于离散信源， R D( ) 可表示成 | 1 1 (|) ( ) min ( ) ( | ) log VU D ( ) r s j i i ji P B i j j Pv u RD Pu Pv u    P v   （6.11） R D( ) 是保真度准则（ D D ）下所必须传输的信息率，也是熵压缩编码器输出可能达到的 最低熵率。 6.2.2.3 序列的信息率失真函数 率失真函数可推广到序列情形，对于序列，可用 N 次扩展信源 N U 和 N 次扩展信道 | {, ,} N N N N V U UP V 予以讨论。 这种情形下，试验信道为所有满足保真度准则 D N ND ( )  的信道的集合，这些试验信 道的转移概率组成集合 BND ： BND   P D N ND V UN N | ;()  （6.12）

BND必存在一个转移概率（代表某个试验信道）使I(UNVN）最小，这个最小值就是N次扩展信源UN的信息率失真函数，记为R(ND)：R(ND)=, minI(UN;VN)=minI(UN;VN),D(N)<≤ND)(6.14)P-NNEBND若信源和信道均无记忆，则有R(ND)=min I(UN;VN);D(N)≤ND)= min [NI(U;V), D≤D)(6.15)= NR(D)编码后的信息率R就是通过信道的平均互信息量I（U:V），为便于传输和处理，希望将信息率R压缩到最小，其最小值就是R(D）。若R<R(D)，就不能满足保真度准则了。6.2.2.4信息率失真函数的性质1)R(D)的定义域R(D)的定义域是[0,Dmax]。由于D是失真度d(u,v,)的统计平均，而d(u,）非负，因此D也非负，其下界是零，对应于无失真情况。由R(D)的定义式可知其非负，下限值为零，取满足R(D)=O的所有D中最小者为R(D)定义域的上限值Dmax。R(D)=0意味着I(U:V)=0，这时试验信道输入与输出是互相统计独立的，即P(y,lu)=P(y)，这时平均失真为D-ZZ P(u,)P(y,)d(u,y)(6.16)i=l j=l取上式D的最小值为Dmax，即Dmax = min ZP(u,)P(v,)d(u,v)(=l j=l(6.17)=minP(y)P(u)d(u,y)j=li=l195

195 BND 必存在一个转移概率（代表某个试验信道）使 (;) N N I U V 最小，这个最小值就是 N 次 扩展信源 N U 的信息率失真函数，记为 R ND ( ) ：   | ( ) min ( ; ) min ( ; ); ( ) N N ND V U NN NN P B R ND I U V I U V D N ND    （6.14） 若信源和信道均无记忆，则有     ( ) min ( ; ); ( ) min ( ; ); ( ) N N R ND I U V D N ND NI U V D D NR D      （6.15） 编码后的信息率 R 就是通过信道的平均互信息量 IUV (;) ，为便于传输和处理，希望将 信息率 R 压缩到最小，其最小值就是 R D( ) 。若 R RD  ( )，就不能满足保真度准则了。 6.2.2.4 信息率失真函数的性质 1) R D( ) 的定义域 R D( ) 的定义域是 max [0, ] D 。 由于 D 是失真度 (, ) i j du v 的统计平均，而 (, ) i j du v 非负，因此 D 也非负，其下界是零， 对应于无失真情况。 由 R D( ) 的定义式可知其非负，下限值为零，取满足 R D() 0  的所有 D 中最小者为 R D( ) 定义域的上限值 Dmax 。 R D() 0  意味着 IUV (;) 0  ，这时试验信道输入与输出是互相统计独立的，即 ( |) () P j i j v u Pv  ，这时平均失真为 1 1 ( )( )( , ) r s i j ij i j D Pu Pv du v     （6.16） 取上式 D 的最小值为 Dmax ，即 max 1 1 1 1 min ( ) ( ) ( , ) min ( ) ( ) ( , ) r s i j ij i j s r j i ij j i D Pu Pv du v Pv Pu du v          （6.17）

2）R(D)是D的下凸函数若有、及D、D、D，满足+=1和D=D+D，则有R(D)≤R(D)+R(D,)3）R(D）是定义域上的非增函数4）R(D)曲线根据率失真函数的上述性质，R(D)曲线的一般形状如图6.1所示。R(D)DoDainDamax图6.1R(D)曲线的一般形状6.2.3限失真信源编码定理设离散无记忆平稳信源的信息率失真函数为R(D)，只要满足R>R(D)，当信源序列N足够长时，一定存在一种编码方法，其译码失真小于或等于D+6，其中ε是任意小的正数；反过来，若R<R(D)，则无论采用什么样的编码方法，其译码失真必大于D。该定理包含两部分，R>R(D）的情形称为正定理，R<R(D)的情形称为逆定理。与香农第二定理（即有噪信道编码定理）一样，限失真信源编码定理只是码的存在性定理。正定理告诉我们，R>R(D)时，译码失真小于或等于D+6的码肯定存在，但定理本身并未告知码的具体构造方法。6.2.4信息率失真函数的计算已知信源的概率分布[U,Pu]=[u,p(u,)]，失真函数为d(u,,",)，其中i=l,.,rj=1.,S，选取合适的试验信道p(vlu)，使平均互信息达到极小值，这个最小值即信息率失真函数R(D)。196

196 2） R D( ) 是 D 的下凸函数 若有1、2 及 D1 、 D2 、 D ，满足 1 2    1和 DD D  11 2 2   ，则有 11 2 2 R() ( ) ( ) D RD RD     3） R D( ) 是定义域上的非增函数 4） R D( ) 曲线 根据率失真函数的上述性质， R D( ) 曲线的一般形状如图 6.1 所示。 图 6.1 R D( ) 曲线的一般形状 6.2.3 限失真信源编码定理 设离散无记忆平稳信源的信息率失真函数为 R D( ) ，只要满足 R RD  ( ) ，当信源序列 N 足够长时，一定存在一种编码方法，其译码失真小于或等于 D   ，其中 是任意小的正 数；反过来，若 R RD  ( )，则无论采用什么样的编码方法，其译码失真必大于 D 。 该定理包含两部分， R RD  ( ) 的情形称为正定理， R RD  ( )的情形称为逆定理。 与香农第二定理（即有噪信道编码定理）一样，限失真信源编码定理只是码的存在性定理。 正定理告诉我们， R RD  ( ) 时，译码失真小于或等于 D   的码肯定存在，但定理本身并 未告知码的具体构造方法。 6.2.4 信息率失真函数的计算 已知信源的概率分布U P u pu , ,() U ii     ，失真函数为 d( u ,v ) i j ，其中 i r 1,., ， j 1,.,s ，选取合适的试验信道 p( v |u )，使平均互信息达到极小值，这个最小值即信息率 失真函数 R D( ) 。 R D( ) D Dmin Dmax 0