1、主要内容主要内容 信源的失真测度信源的失真测度 信息率失真函数信息率失真函数 香农第三定理香农第三定理 限失真信源编码方法限失真信源编码方法无失真信源编码和有噪信道编码告诉我们：无失真信源编码和有噪信道编码告诉我们：l只要信道的信息传输速率小于信道容量，总能只要信道的信息传输速率小于信道容量，总能找到一种编码方法找到一种编码方法,使得在该信道上的信息传输的使得在该信道上的信息传输的差错概率任意小；差错概率任意小；l反之，若信道的信息传输速率大于信道容量，反之，若信道的信息传输速率大于信道容量，则不可能使信息传输差错概率任意小。则不可能使信息传输差错概率任意小。l但是，无失真的编码并非总是必要的
2、。但是，无失真的编码并非总是必要的。香农首先定义了信息率失真函数香农首先定义了信息率失真函数R(D)，并论述，并论述了关于这个函数的基本定理。了关于这个函数的基本定理。定理指出：在允许一定失真度定理指出：在允许一定失真度D D的情况下，信源的情况下，信源输出的信息传输率可压缩到输出的信息传输率可压缩到R(D)R(D)值，这就从理论上值，这就从理论上给出了信息传输率与允许失真之间的关系，奠定了给出了信息传输率与允许失真之间的关系，奠定了信息率失真理论的基础。信息率失真理论的基础。信息率失真理论是进行量化、数模转换、频带信息率失真理论是进行量化、数模转换、频带压缩和数据压缩的理论基础。压缩和数据压
3、缩的理论基础。1 1 失真度失真度 从直观感觉可知，若允许失真越大，信息传输率可从直观感觉可知，若允许失真越大，信息传输率可 越小；若允许失真越小，信息传输率需越大。越小；若允许失真越小，信息传输率需越大。所以信息传输率与信源编码所引起的失真所以信息传输率与信源编码所引起的失真(或误差或误差)是有关的。是有关的。首先讨论首先讨论失真的测度失真的测度。离散无记忆信源离散无记忆信源U，信源变量，信源变量Uu1,u2,ur，概率分布为概率分布为P(u)P(u1),P(u2),P(ur)。信源符号通过信道传输到某接收端，接收端的信源符号通过信道传输到某接收端，接收端的接收变量接收变量V v1,v2,v
4、s。对应于每一对对应于每一对(u,v)，我们指定一个非负的函数：，我们指定一个非负的函数：称为单个符号的失真度(或失真函数)。通常较小的d值代表较小的失真，而d(ui,vj)0表示没有失真。jijivudji)0(0),(若信源变量U有r个符号，接收变量V有s个符号，则d(ui,vj)就有rs个,它可以排列成矩阵形式，即：它为失真矩阵D，是 rs 阶矩阵。),(.),(),(:.:),(.),(),(),(.),(),(212221212111srrrssvudvudvudvudvudvudvudvudvudD须强调须强调:这里这里假设假设U U是信源，是信源，V V是信宿，那么是信宿，那么U
5、 U和和V V之间必之间必有信道。有信道。实际实际这里这里U U指的是原始的未失真信源，而指的是原始的未失真信源，而V V是指失真以后是指失真以后的信源。的信源。因此，从因此，从U U到到V V之间实际上是失真算法，所以这里的转移之间实际上是失真算法，所以这里的转移概率概率p(vp(vj j/u/ui i)是指一种失真算法，是指一种失真算法，有时又把有时又把p(vp(vj j/u/ui i)称为称为试验信道试验信道的转移概率，如图所示。的转移概率，如图所示。原始信源失真信源试验信道信道UVp(vj/ui)例例1 离散对称信源离散对称信源(r=s)。信源变量。信源变量Uu1,u2,ur，接收变量
6、接收变量V v1,v2,vs。定义单个符号失真度：。定义单个符号失真度：这种失真称为汉明失真。汉明失真矩阵是一方阵，对角线上的元素为零，即：jijijivuvuvud10),(rrD0.11:.:1.011.100110D 例例2 删除信源删除信源。信源变量。信源变量Uu1,u2,ur，接收变量，接收变量V v1,v2,vs(s=r+1)。定义其单个符号失真度为：。定义其单个符号失真度为：其中接收符号其中接收符号vs作为一个删除符号。作为一个删除符号。在这种情况下，意味着若把信源符号再现为删除符在这种情况下，意味着若把信源符号再现为删除符号号vs时，其失真程度要比再现为其他接收符号的失时，其失
7、真程度要比再现为其他接收符号的失真程度少一半。真程度少一半。则02111210Dsjjijivudji 2/110),(除j=s以外所有的j和i所有i 例例3 对称信源对称信源(s=r)。信源变量。信源变量Uu1,u2,ur，接收变，接收变量量V v1,v2,vs。失真度定义为：。失真度定义为：若信源符号代表信源输出信号的幅度值，这就是一种若信源符号代表信源输出信号的幅度值，这就是一种以方以方差表示的失真度差表示的失真度。它意味着幅度差值大的要比幅度差值小的所。它意味着幅度差值大的要比幅度差值小的所引起的失真更为严重，严重程度用平方来表示。引起的失真更为严重，严重程度用平方来表示。当当 r3时
8、，时，U0,1,2，V0,1,2，则失真矩阵为：，则失真矩阵为：2)(),(ijjiuvvud014101410D 上述三个例子三个例子说明了具体失真度的定义。一般情况下根据实际信源的失真，可以定义不同的失真和误差的度量。另外还可以按其他标准，如引起的损失、风险、主观感觉上的差别大小等来定义失真度d(u,v)。2 2 平均失真度平均失真度 信源 U 和信宿 V 都是随机变量，故单个符号失真度d(ui,vj)也是随机变量。显然，规定了单个符号失真度d(ui,vj)后，传输一个符号引起的平均失真，即信源平均失真度：在离散情况下，信源Uu1,u2,ur，其概率分布P(u)P(u1),P(u2),P(
9、ur)，信宿V v1,v2,vs。若已知试验信道的传递概率为P(vj/ui)时，则平均失其度为：),(),(vudEvudEDji),()/()(),()(11jirisjijiUVvuduvPuPvuduvPD 平均失真度平均失真度D不大于我们所允许的失真不大于我们所允许的失真D，即：，即：D D 称此为称此为保真度准则保真度准则。信源固定(给定P(u)，单个符号失真度固定时(给定d(ui,vj)，选择不同试验信道，相当于不同的编码方法，所得的平均失真度是不同的。凡满足保真度准则-平均失真度D D的试验信通称为-D失真许可的试验信道。把所有D失真许可的试验信道组成一个集合，用符号BD表示，即
10、：BD=P(vj/ui)：D D7.2 7.2 信息率失真函数信息率失真函数1 D失真许可信道7.2 7.2 信息率失真函数信息率失真函数2 2 信息率失真函数的定义信息率失真函数的定义 信源给定，且又具体定义了失真函数以后，总希望在满足一定失真的情况下，使信源传输给收信者的信息传输率R尽可能地小。即在满足保真度准则下，寻找信源必须传输给收信者的信息率R的下限值-这个下限值与D有关。从接收端来看，就是在满足保真度准则下，寻找再现信源消息所必须获得的最低平均信息量。而接收端获得的平均信息量可用平均互信息I(U;V)来表示，这就变成了在满足保真度准则的条件下，寻找平均互信息I(U;V)的最小值。寻
11、找平均互信息I(U;V)的最小值。而BD是所有满足保真度准则的试验信道集合，因而可以在D失真许可的试验信道集合BD中寻找一个信道P(vj/ui)，使I(U;V)取极小值。由于平均互信息I(U;V)是P(vj/ui)的U型凸函数，所以在BD集合中，极小值存在。这个最小值就是在D D的条件下，信源必须传输的最小平均信息量。即：);()(min)/(VUIDRDijBuvPR(D)-信息率失真函数或简称率失真函数。单位是奈特信源符号 或 比特信源符号 率失真函数给出了熵压缩编码可能达到的最小熵率与失真的关系，其逆函数称为失真率函数，表示一定信息速率下所可能达到的最小的平均失真。二、二、3 3 信息率
12、失真函数的性质信息率失真函数的性质 允许失真度D的下限可以是零，即不允许任何失真的情况。R(D)的定义域 且：minmax0DDDmin()min(,)yxDp xd x ymaxmin()(,)yxDp x d x yR R(D D)的定义域的定义域 率失真的定义域问题就是在信源和失真函数已知率失真的定义域问题就是在信源和失真函数已知的情况下的情况下,讨论允许讨论允许平均失真度平均失真度D D的的最小最小和和最大最大取取值问题。值问题。由于平均失真度是非负实数由于平均失真度是非负实数d d(x xi i,y yj j)的数学期望的数学期望,因此也是非负的实数因此也是非负的实数,即即 的的下界
13、是下界是0 0。w 允许平均失真度能否达到其下限值允许平均失真度能否达到其下限值0,0,与单个符号与单个符号的失真函数有关。的失真函数有关。DD,0R(D)R(D)的定义域的定义域D Dmin min 和和R R(D Dminmin)信源的最小平均失真度：信源的最小平均失真度：w 只有当失真矩阵的每一行至少有一个只有当失真矩阵的每一行至少有一个0 0元素时元素时,信源的信源的平均失真度平均失真度才能达到下限值才能达到下限值0 0。w 当当D Dmin min=0,=0,即信源不允许任何失真时即信源不允许任何失真时,信息率信息率至少应等于信源输出的平均信息量至少应等于信源输出的平均信息量信息熵。
14、信息熵。即即 R R(0)=(0)=H H(X X)min1()min(,)niijjiDp xd x yR(D)R(D)的定义域的定义域w 因为实际信道总是有干扰的因为实际信道总是有干扰的,其容量有限其容量有限,要无要无失真地传送连续信息是不可能的。失真地传送连续信息是不可能的。w 当允许有一定失真时当允许有一定失真时,R R(D D)将为有限值将为有限值,传送才传送才是可能的。是可能的。w 对于连续信源：对于连续信源：min0()lim()DR DR D R(D)R(D)的定义域为的定义域为DDminmin，D Dmaxmax 。通常通常D Dminmin=0=0，R R(D Dminmi
15、n)=)=H H(X X)当当 D DD Dmaxmax时时,R R(D D)=0)=0 当当 0 0 D DD Dmaxmax时时,0,0R R(D D)H H(X X)R(D)R(D)的定义域的定义域D Dmaxmax：定义域的：定义域的上限上限。D Dmaxmax是满足是满足R R(D D)=0)=0时所时所有的平均失真度中的有的平均失真度中的最最小值小值。w 由于由于I I(X,YX,Y)是非负函数是非负函数,而而R R(D D)是在约束条件下是在约束条件下的的I I(X,YX,Y)的最小值的最小值,所以所以R R(D D)也是一个非负函数也是一个非负函数,它的下限值是零。它的下限值是
16、零。R R(D D)0)0max()0minR DDDR(D)R(D)的定义域的定义域由于由于I I(X,YX,Y)=0)=0的充要条件是的充要条件是X X与与Y Y统计独立统计独立,即：即：)()|(jijypxypmax()()min()()(,)min()()(,)jjijijp yijjiijp yjiDp x p y d x yp yp x d x y max1,21min()(,)niijjmiDp x d x yR(D)R(D)的定义域的定义域 例例:设输入输出符号表为设输入输出符号表为X=Y=0,1,X=Y=0,1,输入概率输入概率分布分布p p(x x)=1/3,2/3,)=
17、1/3,2/3,失真矩阵失真矩阵 0110dw 求：求：D Dminmin 和和D Dmaxmax 31)31,32(min)032131,132031(minmin212,1maxjjijiijdpDw 失真矩阵的每一行至少有一个失真矩阵的每一行至少有一个0 0元素时元素时,D,Dminmin=0=0 例例:设输入输出符号表为设输入输出符号表为X=Y=0,1,X=Y=0,1,输入概率输入概率分布分布p p(x x)=1/3,2/3,)=1/3,2/3,失真矩阵失真矩阵 1212/1dw 求：求：D Dminmin 和和D Dmaxmax 1)1,23(min)132131,2322131(m
18、inmin212,1maxjjijiijdpD651322131),(min)(1minnijijiyxdxpD解：例 设试验信道输入符号集 ，各符号对应概率分别为)=1/3,1/3,1/3，失真矩阵如下所示，求 和 以及相应的试验信道的转移概率矩阵。123,a a aminDmaxD 123213321d123()min(1,2,3)()min(2,1,3)()min(3,2,1)p ap ap amin()min(,)yxDp xd x y 令对应最小失真度 的 ，其它为“0”，可得对应 的试验信道转移概率矩阵为(,)ijd a b(|)1jip baminD100(|)010001p y
19、 x max123123123min()(,)min()1()2()3,()2()1()2,()3()3()1yxDp x d x yp ap ap ap ap ap ap ap ap a 上式中第二项最小，所以令 ，可得对应 的试验信道转移概率矩阵为2()1p b13()()0p bp bmaxD010(|010010p y x R(D)是关于平均失真度D的下凸函数 设 为任意两个平均失真，则有：12,D D01a1212(1)()(1)()R aDa DaR Da R DR(D)是 区间上的连续和严格单调递减函数。由信息率失真函数的下凸性可知，R(D)在 上连续。又由R(D)函数的非增性，
20、R(D)是区间 上的严格单调递减函数。minmax(,)DDminmax(,)DDminmax(,)DD信息率失真函数的一般形状 定理 (保真度准则下的信源编码定理，香农第三定理)设R(D)为一离散无记忆信源的信息率失真函数，并且有有限的失真测度D。对于任意D ，以及任意长的码长n，一定存在一种信源编码C，其码字个数为 使编码后码的平均失真度 。0,0()2n R DMDD定理的含义是：只要码长n足够长，总可以找到一种信源编码，使编码后的信息传输率略大于(直至无限逼近)率失真函数R(D)，而码的平均失真度不大于给定的允许失真度，即：DD 由于R(D)为给定D前提下信源编码可能达到的下限，所以香
21、农第三定理即说明了：达到此下限的最佳信源编码是存在的。实际的信源编码(无失真编码或先限失真编码后无失真编码)的最终目标是尽量接近最佳编码，使编码信息传输率接近最大值log r，而同时又保证译码后能无失真地恢复信源的全部信息量H(S)或限失真条件下的必要信息量R(D)。编码后信息传输率的提高使每个编码符号能携带尽可能多的信息量，-使得传输同样多的信源总信息量所需的码符号数大大减少-使所需的单位时间传输信道单位时间信道容量Ct大大减少，或在Ct不变的前提下使传输时间大大缩短，从而提高了通信的效率。香农第三定理仍然只是个存在性定理，至于最佳编码方法如何寻找，定理中并没有给出，因此有关理论的实际应用有
22、待于进一步研究。如何计算符合实际信源的信息率失真函数R(D)?如何寻找最佳编码方法才能达到信息压缩的极限值R(D)?这是该定理在实际应用中存在的两大问题，它们的彻底解决还有赖于继续的努力。尽管如此，香农第三定理毕竟对最佳限失真信源编码方法的存在给出了肯定的回答，它为今后人们在该领域的不断深入探索提供了坚定的信心。逆定理不存在平均失真测度D，且 的任何信源编码，即对任意长的码长n的信源C，若码字个数为 ，一定有 。()2n R DM()D CD()RR D 该定理告诉我们：如果编码后平均每个信源符号的信息传输率R 小于信息率失真函数R(D)，就不能在保真度准则下再现信源的消息。联合有失真信源信道
23、编码定理联合有失真信源信道编码定理（信息传输定理）离散无记忆信源的S的信息率失真函数为R(D)，离散无记忆信道的信道容量C，若满足()CR D 则信源输出的信源序列能在此信道输出端重现，其失真小于等于D。()CRR D信息论信息论“三大定理三大定理”总结总结 香农信息论的三个基本概念香农信息论的三个基本概念信源熵、信道信源熵、信道 容量、信息率失真函数容量、信息率失真函数，都是临界值，是从理，都是临界值，是从理论上衡量通信能否满足要求的重要界限。论上衡量通信能否满足要求的重要界限。香农的三个基本编码定理香农的三个基本编码定理无失真信源编码定理、无失真信源编码定理、有噪信道编码定理、限失真信源编
24、码定理有噪信道编码定理、限失真信源编码定理，这是，这是三个理想编码的存在性定理。分别又称为香农第三个理想编码的存在性定理。分别又称为香农第一、第二、第三定理。一、第二、第三定理。虽然三个定理都指出理想编码是存在的，但如何虽然三个定理都指出理想编码是存在的，但如何寻找编码以及能否做到寻找编码以及能否做到“理想编码理想编码”，则完全是，则完全是另外一回事。正是后面两章另外一回事。正是后面两章信源编码信源编码或或信道编码信道编码所要讨论的问题。所要讨论的问题。限失真信源编码定理的实用意义限失真信源编码定理的实用意义例：01()1/21/2UP u 要对此信源进行无失真编码，每个信源符号必须用一个二元
25、符号来表示，信源的信息输出率为R=H=1。若允许失真存在，并定义失真函数为汉明失真，即0(,)1ijijuvd u vuv可以设想这样一种信源编码：121340000010000010100uuvuu562781111101111101011uuvuu无噪无损信道传输00001111这种编码方法，可以看成是一种特殊的试验信道1,()(/)0()jjijijivC vf uP vuvf u1()(),()Ud CP U d u f uN1 110 1 1 1 0 1 1 13 84 信息率为1/3，而平均失真为1/4，根据香农第三定理，若允许失真D=1/4时，总可以找到一种编码，使信息输出率达到
26、极限R(1/4)11()1()0.18944RH 香农第三定理是一个存在定理，至于如何寻找这种最佳编码方法并没有给出，在实际应用中，存在以下两方面的问题：1、符合实际信源的R(D)函数的计算相当困难。1）需要对实际信源的统计特性有确切的描述。2）需要对符合主客观实际的失真给予正确的描述。3）即使满足了前两条，R(D)的计算也比较困难2、即使求得很好的R(D)函数，还需要研究采取何种编 码方法才能达到极限值R(D)。目前，这两方面工作都有进展。根据数据在时间和空间上的相关性，图像中某一根据数据在时间和空间上的相关性，图像中某一像素的灰度值可以用其相邻的若干个像素来预测。将像素的灰度值可以用其相邻
27、的若干个像素来预测。将样本的实际值与预测值相减得到误差值，再对误差值样本的实际值与预测值相减得到误差值，再对误差值进行编码。进行编码。差分脉冲编码调制（差分脉冲编码调制（DPCM）最佳线性编码最佳线性编码DPCM系统中的图像降质系统中的图像降质 预测编码（预测编码（Prediction Coding）7.4 限失真信源编码方法DPCM：Differential Pulse Code Modulation（差分脉冲（差分脉冲编码调制）编码调制）每个像素可以根据前几个已知的像素值来做预测。因此每个像素可以根据前几个已知的像素值来做预测。因此在预测编码中，编码与传输的值并不是像素取样值本身，而在预测
28、编码中，编码与传输的值并不是像素取样值本身，而是这个取样值的预测值（也称估计值）与实际值之间的差值。是这个取样值的预测值（也称估计值）与实际值之间的差值。DPCM系统的原理框图系统的原理框图DPCMDPCM编码编码 mimnmnninxaxaxax1111nnnxxennneeq根据根据tn时刻以前已知时刻以前已知的的m 个取样值对个取样值对xn所作的预测值所作的预测值 预测系数预测系数预测阶数预测阶数预测误差信号预测误差信号量化器的量化误差量化器的量化误差量化器输出信号量化器输出信号 可见，接收端和发送端的误差由发送端量化器产生，可见，接收端和发送端的误差由发送端量化器产生，与接收端无关。接
29、收端和发送端之间误差的存在使得重建与接收端无关。接收端和发送端之间误差的存在使得重建图像质量会有所下降。因此，在这样的图像质量会有所下降。因此，在这样的DPCM系统中就存系统中就存在一个如何能使误差尽可能减少的问题在一个如何能使误差尽可能减少的问题。nnnnnnnnnnnnnqeeexxxexxxxx)()(输入信号输入信号接收端解码输出接收端解码输出预测编码的类型预测编码的类型 tn 时刻之前的样本值时刻之前的样本值X1,X2，XN-1与预测值之与预测值之间的关系呈现某种函数形式间的关系呈现某种函数形式。(1)线性预测：线性预测：11NiiiNXaX(2)非线性预测非线性预测 不满足上式不满
30、足上式 称为预测系数最佳线性编码最佳线性编码对于以前已知像素的选取方法，分为对于以前已知像素的选取方法，分为4种情况：种情况：（1）前值预测）前值预测（2）一维预测）一维预测（3）二维预测）二维预测（4）三维预测）三维预测取用现在像素取用现在像素xn的同一行扫描中前面的同一行扫描中前面最邻近像素最邻近像素x1预测预测xn，即，即xn的预测值的预测值等于等于x1。取用取用xn的同一行扫描中前几个已知像的同一行扫描中前几个已知像素值，如素值，如x1，x5等预测等预测xn。取用取用xn的同一行和前几行若干个已知的同一行和前几行若干个已知像素值预测像素值预测xn取用已知像素不但是前几行的而且还取用已知
31、像素不但是前几行的而且还包括前几帧的，称为三维预测。包括前几帧的，称为三维预测。最佳线性编码最佳线性编码最佳线性预测最佳线性预测 采用方均误差（采用方均误差（MSE）为极小值的准则来获得的）为极小值的准则来获得的DPCM，此时预测误差最小。，此时预测误差最小。关键：求出各个预测系数，使得预测误差最小。关键：求出各个预测系数，使得预测误差最小。)1,()1,1(),1(),(321nmfanmfanmfanmf例：例：一幅图像，设一幅图像，设f(m,n)点可用其他相邻像素来预测。点可用其他相邻像素来预测。),(),(),(nmfnmfnme最佳线性编码最佳线性编码22),(),(),(nmfnm
32、fEnmeE2321)1,()1,1(),1(),(nmfanmfanmfanmf 均方误差：均方误差：2),(nmeE为使为使 最小最小最佳线性编码最佳线性编码 解方程，求得解方程，求得a1，a2，a3，即为最佳线性预测系数。，即为最佳线性预测系数。预测时所选邻域越大，所选的像素数越多，则预预测时所选邻域越大，所选的像素数越多，则预测器就越复杂。一般邻近像素数不超过测器就越复杂。一般邻近像素数不超过4个。个。令：令：0),(0),(0),(232221nmeEanmeEanmeEa最佳线性编码最佳线性编码（3）如何求R(D)的定义域和值域 （2）平均失真 对给定信源q(x)进行压缩编码，不同的编码方法对应不同的实验信道，可用信道转移概率p(yx)来描述该实验信道，用概率分布 p(x y)=q(x)p(yx)对给定的失真测度求统计平均值就得到平均失真.（1）失真测度 可以理解为误码带来的代价，实际上发送同一符号而错成不同符号所带来的代价是不同的。本章介绍在允许一定失真条件下，对给定信源进行压缩编码,信息传输率可压缩的最低下界谓之率失真函数R(D)。重点讨论以下几个问题：小 结（5）香农第三定理保真度准则下的率失真编码定理，这是信息理论的重要定理之一。（4）求率失真函数R(D)本章通过两个例子讨论了两种特殊情况下R(D)的求法，在一般的离散无记忆情况下，可用书中介绍的参数法求解。
