第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，其中ε是任意小的正数；反过来，若RR(D）的情形称为正定理，RR(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
计算的约束条件为p(y,|u,)≥0 (i=1,2,.,r)(j=1,2,..s)Ep(v,lu)=1 (i=1,2,.,r)(6.18)i=7Ep(u,)p(y,lu,)d(u,v,)=Di=l j=l6.2.4.1参量表示计算方法1) 计算^(i=1,.,r)1=a,p(u,)exp(Sd(u,y,)(j=1,2,..s)(6.19)i=l2) 计算p(v,)(j=1,.,s)1-Zp(y,)exp(Sd(u, y,)(i= ,2....r)(6.20)j=l3)计算D(S)D(S)=ZZ p(u,),p(y,)d(u,y,)exp(Sd(u,y,)(6.21)i=l j=l4)计算R(D)7R(S)= Ep(u,)log 2, + SD(S)(6.22)i=l除某些特定的情况外，参量S一般难以消除，因此很难得到R(D)的显式表达式。通过计算可以得到，参量S是信息率失真函数R(D)的斜率。由于信息率失真函数R(D）是D的单调递减函数，且是U型凸函数。所以R(D)的斜率S≤0，S随D的增加递增，即崇>0。dD斜率S与失真度D，信息率失真函数R(D)与D的关系曲线见图6.2。197
197 计算的约束条件为 1 1 1 ( | ) 0 ( 1,2,., ) ( 1,2,., ) ( | ) 1 ( 1,2,., ) ( )( | )( , ) j i s j i j r s i j i ij i j p vu i r j s pv u i r pu pv u du v D （6.18） 6.2.4.1 参量表示计算方法 1）计算 ( 1,., ) i i r 1 1 ( )exp{ ( , )} ( 1, 2,., ) r i i ij i p u Sd u v j s （6.19） 2）计算 ( )( 1,., ) j p vj s 1 1 ( )exp{ ( , )} ( 1, 2,., ) s i j ij j p v Sd u v i r （6.20） 3）计算 D S( ) 1 1 ( ) ( ) ( ) ( , )exp{ ( , )} r s ii j i j i j i j D S p u p v d u v Sd u v （6.21） 4）计算 R( ) D 1 ( ) ( )log ( ) r i i i R S p u SD S （6.22） 除某些特定的情况外，参量 S 一般难以消除，因此很难得到 R( ) D 的显式表达式。通过 计算可以得到，参量 S 是信息率失真函数 R( ) D 的斜率。 由于信息率失真函数 R( ) D 是 D 的单调递减函数，且是U 型凸函数。所以 R( ) D 的斜率 S 0 ， S 随 D 的增加递增，即 0 dD dS 。 斜率 S 与失真度 D ，信息率失真函数 R( ) D 与 D 的关系曲线见图 6.2
R(D)DmaxD0S图6.2R(D)及S与D的关系曲线6.2.4.2送代计算方法计算一般离散信源的信息率失真函数是相当复杂和困难的，往往需要借助于计算机。1）选代计算条件设离散信源输入序列为[U,Pu]=[u,p(u,]，i=l,.,r；输出序列为[V,P]-[y,p(y)],j=]...s；失真函数为d(u,y,)。信息率失真函数R(D)是平均互信息I(U;V)的极小值。即在满足约束条件（式6.18）情况下，计算双重极小化：Zp(u,)p(, / u,)log (, /u)R(D)=min min I(U;V)=min min >.(6.23)p(y,)p(v)p(rlu)）2）送代计算公式p(y,)exp[Sd(u,y,)]p(y, [u,)"=_(6.24)Ep(y,)exp[Sd(u,y,)]i=lp(y,) -Zp(u,)p(y, [u,)(6.25)i=l式（6.24）和（6.25）是R(D）函数选代的基础。3）迭代计算步骤(1）假定S,为一相当大的负值，选定起始传递概率p("(vlu,）(i=1,2,,r,1j=1,2,.s),可取p("(y,[u)=。将选定的p("(,lu）代入式（6.25)，得到p"(v）。(2)将p((v）代入式（6.24)，得到p(2)(y,lu）。198
198 图 6.2 R D( ) 及 S 与 D 的关系曲线 6.2.4.2 迭代计算方法 计算一般离散信源的信息率失真函数是相当复杂和困难的，往往需要借助于计算机。 1） 迭代计算条件 设离散信源输入序列为 U P u pu , ,() U ii ， i r 1,., ；输出序列为 V P v pv , ,() V jj ， j 1,.,s ；失真函数为 (, ) i j du v 。 信息率失真函数 R( ) D 是平均互信息 I(;) U V 的极小值。 即在满足约束条件（式 6.18）情况下，计算双重极小化： ()( ) ()( ) 1 1 (|) ( ) min min ( ; ) min min ( ) ( | )log j ji j ji ( ) r s j i i ji pv pv u pv pv u i j j p v u RD IUV pu pv u p v （6.23） 2）迭代计算公式 ( )exp[ ( , )] ( )exp[ ( , )] ( | ) 1 * i j s j j j i j j i p v Sd u v p v Sd u v p v u （6.24） * 1 ( ) ()( | ) r j i ji i p v pu pv u （6.25） 式（6.24）和（6.25）是 R( ) D 函数迭代的基础。 3）迭代计算步骤 (1) 假 定 1 S 为一相当大的负值，选定起始传递概率 (1) (|) j i p vu ( 1,2,., ; i r j 1,2,., )s ，可取 (1) 1 (|) j i p vu s 。将选定的 (1) (|) j i p v u 代入式（6.25），得到 (1) ( )j p v 。 (2) 将 (1) ( )j p v 代入式（6.24），得到 (2) (|) j i p v u 。 R(D) Dmax D S 0
(3）再将p(2)(y,lu）代入式（6.25)，得到p(2)(y）。(4)重复前面的步骤，计算出第k次和第k+1次的R(k)(D)和R(k+)(D)：p(k)(y, lu,)R(9(D)=ZZ p(u,)p((v, u,)log (6.26)p((v,)=j-lp((y, /u,)22p(lu,)p(k1(y,/u,) logPR(k+I)(D)=与(6.27)p(k(v,)台合(5)当R(k)(D)与R(k+1)(D)的差别小于预先给定的值，取 R(*)(D)或R(k+)(D)作为R(S)的近似值。(6）选略大一些的负数S2，重复上述选代过程，得到对应于S,的R(S,）。(7）重复上述过程，直到R(Smax）逼近零。(8）根据ST、S,、..、Smax，以及与之相对应的R(S)、R(S2)、..、R(Smax），可以作出R(S)曲线。根据R(D)函数的S参量表述理论，进而得到R(D)曲线。完成整个选代过程。199
199 (3) 再将 (2) (|) j i p v u 代入式（6.25），得到 (2) ( )j p v 。 (4) 重复前面的步骤，计算出第 k 次和第 k 1次的 ( ) ( ) k R D 和 ( 1) ( ) k R D ： ( ) () () ( ) 1 1 (|) ( ) ( ) ( | )log ( ) k r s k k j i i ji k i j j p vu R D pu p v u p v （6.26） 与 ( 1) ( 1) ( 1) ( 1) 1 1 (|) ( ) ( ) ( | )log ( ) k r s k k j i i ji k i j j p v u R D pu p v u p v （6.27） (5) 当 ( ) ( ) k R D 与 ( 1) ( ) k R D 的差别小于预先给定的值，取 ( ) ( ) k R D 或 ( 1) ( ) k R D 作为 1 R( ) S 的近似值。 (6) 选略大一些的负数 2 S ，重复上述迭代过程，得到对应于 2 S 的 2 R( ) S 。 (7) 重复上述过程，直到 max R S( )逼近零。 (8) 根据 1 S 、 2 S 、.、 Smax ，以及与之相对应的 1 R( ) S 、 2 R( ) S 、.、 max R S( )，可以作 出 R( ) S 曲线。根据 R( ) D 函数的 S 参量表述理论，进而得到 R( ) D 曲线。完成整个迭代过程