第四章有限失真信源编码

1、第四章限失真信源编码第四章限失真信源编码n简介：和无失真编码比较，（失真和熵率值比较）熵压缩编码在的允许失真条件下，编码后的熵率压缩到最小（无译码器）（解释两种编码的必要性） 信息速率失真函数R(D): 是熵压缩编码的基础，把信息和失真两个度量可联系在一起，为信号处理中同时考虑两个因素提供可解。引入限失真的必要性n1） 失真在传输中是不可避免的;n2） 接收者（信宿）无论是人还是机器设备，都有一定的分辨能力与灵敏度，超过分辨能力与灵敏度的信息传送过程是毫无意义的;n3） 即使信宿能分辨、能判别，但对通信质量的影响不大，也可以称它为允许范围内的失真；n4） 我们的目的就是研究不同的类型的客观信源

2、与信宿，在给定的Qos要求下的最大允许（容忍）失真D，及其相应的信源最小信息率R(D).n5） 对限失真信源，应该传送的最小信息率是R(D)，而不是无失真情况下的信源熵H(U). 显然 H(U)R(D). 当且仅当 D=0时，等号成立；n6） 为了定量度量D，必须建立信源的客观失真度量，并与D建立定量关系；n7） R(D)函数是限失真信源信息处理的理论基础；本章节达到的目的本章节达到的目的n理解限失真信源编码在通信系统中的意义理解限失真信源编码在通信系统中的意义n了解失真测度的含义和基本方法了解失真测度的含义和基本方法n理解理解R(D)函数的概念、物理意义、性质函数的概念、物理意义、性质n了解

3、特殊情况下了解特殊情况下R(D)函数的计算方法函数的计算方法n了解了解R(D)函数在信道编码定理中的作用函数在信道编码定理中的作用n理解香农第三定理的物理意义及其实用意义理解香农第三定理的物理意义及其实用意义n了解香农三大定理的相互关系与比较情况了解香农三大定理的相互关系与比较情况本章研究内容本章研究内容n概述概述n失真的度量失真的度量n信息率失真函数信息率失真函数n限失真信源编码定理限失真信源编码定理n香农三大定理的关系和比较香农三大定理的关系和比较4.1:4.1:概述概述1n问题引出问题引出n无噪信道编码定理回顾无噪信道编码定理回顾n有噪信道编码定理回顾有噪信道编码定理回顾n存在的问题：存

4、在的问题：n实际需求特点实际需求特点n引出的研究内容引出的研究内容n本章节研究方法与顺序本章节研究方法与顺序4.1:4.1:概述概述2n无噪信道编码定理回顾：无噪信道编码定理回顾：n总可以找到一种输入分布（信源编码方法），使在总可以找到一种输入分布（信源编码方法），使在上，能够上，能够地传输信地传输信息。息。信源编码信源编码无噪无损信道无噪无损信道R=C;PE=0,最佳分布消息压缩冗余度最好地利用利用C4.1:4.1:概述概述3n有噪信道编码定理回顾：有噪信道编码定理回顾：n只要只要，总可以找到一种信道编码方法，使在信，总可以找到一种信道编码方法，使在信道上能够道上能够传输信息。传输信息。信源

5、编码信源编码信道信道R C; PE=,消息信道编码信道编码增加冗余度，最好地匹配信道特性4.1:4.1:概述概述4n存在问题存在问题n对于连续和模拟信源对于连续和模拟信源H(S)= n信道传输率信道传输率R=H(S)/n（比特（比特/码符号）码符号） R=R= n平均码长平均码长l=Hl=Hr r(S)=H(S)/logr(S)=H(S)/logr, l= , l= ,n实际上，因为实际上，因为B B有限，有限，C C一定有限，一定有限，RC,RC,及及l=l=均均不可能不可能4.1:4.1:概述概述5n实际需求特点：实际需求特点：n信宿对真实度的要求：信宿对真实度的要求：n实际语音信号：实际

6、语音信号：20Hz8KHz 人耳能够分辨：人耳能够分辨：300Hz3400Hzn图象色差：可达足够多图象色差：可达足够多 视觉分辨：视觉分辨：256级（黑白）已足够级（黑白）已足够n可以允许一定的失真度可以允许一定的失真度n完全保真完全保真没必要没必要4.1:4.1:概述概述6n引出的研究内容引出的研究内容n限失真的信源编码问题限失真的信源编码问题n允许一定的失真度下，能将信源信息压缩到什么允许一定的失真度下，能将信源信息压缩到什么程度？（最少需要多少比特才能在收端描述信程度？（最少需要多少比特才能在收端描述信源？）源？）n一定的信息传输率一定的信息传输率R下，允许的最大失真是多少？下，允许的

7、最大失真是多少？n相关问题相关问题n失真如何度量？失真如何度量？n率失真函数如何计算？率失真函数如何计算？4.1:4.1:概述概述7n研究方法：n抽象信道n虚拟试验信道4.1:4.1:概述概述8n方法：n抽象：将与讨论重点关系小的部分抽象n因为涉及信源编码，对信道进行抽象n信道编码信道信道译码 信道*n信道*可以略去n根据信道编码定理 信道*是一个没有干扰的广义信道，信宿收到信息的失真只来自于信源编码4.1:4.1:概述概述9n方法：n虚拟：将讨论重点虚拟细化n将限失真信源的编译码过程虚拟n信源编码信道* 信源译码 试验信道n可以用信道传递概率来描述限失真信源编译码前后的关系信源信源编码编码信

8、道信道编码编码信道信道信道译码译码信源信源译码译码信源信源信宿信宿信源信源编码编码信道*信源信源译码译码信源信源信宿信宿信源信源信宿信宿试验信道UVP(V|U)4.1:4.1:概述概述10n本章节讨论顺序本章节讨论顺序n从最简单的离散无记忆信源入手从最简单的离散无记忆信源入手n讨论失真的度量讨论失真的度量n讨论率失真函数的定义和性质讨论率失真函数的定义和性质n讨论在最简单的二进制对称离散信源和高斯连续信讨论在最简单的二进制对称离散信源和高斯连续信源条件下率失真函数源条件下率失真函数R(D)的计算方法的计算方法n讨论限失真信源编码定理讨论限失真信源编码定理n信息率失真理论的探讨及应用举例信息率失

9、真理论的探讨及应用举例n香农三大定理的关系和比较香农三大定理的关系和比较4.2:4.2:失真的度量1n失真度定义n平均失真度n保真度准则n试验信道4.2:4.2:失真的度量2n失真度定义n在U,V联合空间上定义： d（ui，vj），uiU，vjV 为U,V的失真测度。nd（ui，vj）有距离的概念n性质1：ui=vj时，d=0n性质2：min d=0n性质3：0d0, 0, ui vj 0, 0, ui=vj 汉明距离度量时：汉明距离度量时：dij= 1, 1, ui vjn连续信源：用失真函数描述。连续信源：用失真函数描述。d(u,v)=(u-v)2 =|u-v| 4.2:4.2:失真的度量

10、4n平均失真度平均失真度n单符号失真度：单符号失真度： d（ui，vj） 0，（，（i=1r，j=1s） 信源的失真矩阵可表示为：信源的失真矩阵可表示为： 共共rs个元素个元素),().,(.),().,(1111srrsvudvudvudvudD4.2:4.2:失真的度量5n平均失真度平均失真度n平均失真度：平均失真度： UU，V V是随机变量；是随机变量； d（ui，vj）也是随机变量）也是随机变量平均失真度：平均失真度： ),()|()(),()(),(,jijijiivuvuduvpupvuduvpvudED4.2:4.2:失真的度量6n平均失真度平均失真度nc.f :d &n

11、d：描述了某个信源符号通过传输后失真的大小：描述了某个信源符号通过传输后失真的大小 不同的信源符号，其不同的信源符号，其d不同。不同。n ：描述了某一个单符号信源在某一试验信道传输：描述了某一个单符号信源在某一试验信道传输 下的失真，它不仅与单个符号的下的失真，它不仅与单个符号的d有关，还与有关，还与 试验信道的统计特性有关。试验信道的统计特性有关。DD4.2:4.2:失真的度量7n平均失真度平均失真度nN维信源符号序列的平均失真度：维信源符号序列的平均失真度：此时此时D为一为一 rNsN阶的矩阵阶的矩阵与：与： d（u，v）、）、p(u)、p(v|u)、N均有关均有关Nljiijrisjil

12、lNNvudppvudEND111),()|()(),()()(ND4.2:4.2:失真的度量8n平均失真度n信源平均失真度n信源、信道均无记忆时：n信源平稳时：)(1NDDNNNllNNNllDDDND111)(序列中第l个分量的平均失真度)|()|(),()(ijijiiuvpuvpupupillDDlDNND)(DDN4.2:4.2:失真的度量9n保真度准则n给定D，若 D，则称此为保真度准则n对于序列信源，保真度准则为： NDD)(ND4.2:4.2:失真的度量10n试验信道：nP(v|u)不是实际的信道特性矩阵，在此相当于不同的编码方法，不同的编码方法， 不同。n定义：所有 D的试验

13、信道构成D失真许可的试验信道集合BDDD4.3:4.3:率失真函数1n问题引出问题引出n度量了失真，进一步关心的问题是：度量了失真，进一步关心的问题是：n一定的失真一定的失真D下，最小的信息传输率下，最小的信息传输率R是多少？是多少？n一定的失真一定的失真D下，收端再现信源需要的最低的平均信息量下，收端再现信源需要的最低的平均信息量是多少？是多少？n定义：（信息）率失真函数定义：（信息）率失真函数R(D) 对于对于N维序列信源：维序列信源：),(min)()|(VUIDRDBuvp),(min)()(VUIDRNDNDN4.3:4.3:率失真函数2n率失真函数的进一步解释率失真函数的进一步解释

14、n单位：比特单位：比特/信源符号（同互信息）信源符号（同互信息）n离散无记忆信源：离散无记忆信源：RN(D)=NR(D)nP(v|u)无实际信道含义，只代表不同编码方法无实际信道含义，只代表不同编码方法n求求R(D)就是在就是在D条件下，选择一种编码方法，使条件下，选择一种编码方法，使R最小。最小。n定义域：定义域：D 0,DmaxnR(D)的性质的性质：n凸状性凸状性n单调递减性单调递减性n连续性连续性4.3:4.3:率失真函数3n Dmax与R(Dmax)n定义当DDmax时，R(Dmax)=0n使R(Dmax)=0的p(v|u)不止一个n不同的p(v|u)有不同的 |R(D)=0n对我们

15、有意义的： 的最小值Dmax的p(v|u)n利用该p(v|u)求得使R(Dmax)=0时的DmaxnR=0时，U,V统计独立p(v|u)只是v的函数n则有： p(v|u)Q(v), Dmax=DDVUvQvudvQup,)(),()()(min)()(min),()()(min)()(vdvQvudupvQVvQVUvQDmaxDR(D)R(D)0R(D)=04.3:4.3:率失真函数4nR(D)的计算的计算n求解求解R(D)，-求求解互信息的解互信息的极小值极小值n互信息互信息I(X,Y)是条件转移概率的下凸函数是条件转移概率的下凸函数极小值极小值存在存在n一般情况下很难得到一般情况下很难得

16、到R(D)的的显函数显函数表达式，只能表达式，只能得到得到参量参量表达式表达式n具体计算很困难，一般利用计算机进行具体计算很困难，一般利用计算机进行迭代迭代计算计算n在一些在一些特殊特殊情况下，情况下，R(D)有显式解。有显式解。n举例(1)6.4 Property of R(D)nCalculation of R(D) of binary symmetric sourcenKnown conditions：二进制对称信源：二进制对称信源U=0,1，接收变量，接收变量V=0,1，允许的，允许的失真失真DnP(u)=，1 ， 1/21/2n汉明失真矩阵汉明失真矩阵0110DnSteps to s

17、olve：n求求D Dminmin = =0 0 n找到满足最小失真的试验信道找到满足最小失真的试验信道p(v|up(v|u),),得到得到R(0)R(0)n由汉明失真矩阵和失真度定义，计算最大允许的失真度由汉明失真矩阵和失真度定义，计算最大允许的失真度D Dmaxmax = = n由由D Dmaxmax，找到满足最大失真的试验信道，找到满足最大失真的试验信道p,p,并得到并得到R(DR(Dmaxmax) )n在一般条件下当在一般条件下当0DD0DR(D)时，存在一种时，存在一种信息传输率为信息传输率为R的信源编码，其平均失真度的信源编码，其平均失真度D+n思路：思路：n产生码书产生码书n选取

18、编译码方法选取编译码方法n计算失真度计算失真度n方法：方法：n产生码书：在产生码书：在Vn空间随机抽取空间随机抽取M=2nR个随机序列个随机序列vn编码方法：若存在与信源序列编码方法：若存在与信源序列u构成构成失真典型序列失真典型序列对的序列对的序列v(),则编码则编码uv(),否则编码否则编码uv(1)n译码：再现译码：再现v()n失真度计算：在所有随机码书和失真度计算：在所有随机码书和Un空间统计平均的基础上计算平均失真度空间统计平均的基础上计算平均失真度4.4:4.4:限失真信源编码定理限失真信源编码定理5n限失真信源编码定理的几点说明n只是一个存在性定理，没有构造方法n存在问题：n符合

19、实际信源的R(D)函数计算相当困难n信源统计特性的确切数学描述难得n符合主客观实际的失真测度难得nR(D)计算本身困难n即使求得了R(D)，还需研究最佳编码方法才能达到极限值R(D)。4.4:4.4:限失真信源编码定理限失真信源编码定理6n限失真信源编码定理的实用意义n如何进行限失真信源编码？n举例：nR（D）的实用意义n在允许一定失真的情况下，信源的R(D)函数可以作为衡量各种压缩编码方法性能优劣的一种尺度。n举例：n二进制无记忆对称信源n编译码：2121,1 , 0)(upU111101110111011100001000100010001 ,02876514321)( vuuuuvuuu

20、uUYCVUUf译码实际信道无噪无损信道传输0000 1111举例：结论nR=1/3（比特/信源符号）n该压缩编码方法下的信息传输率信息传输率nd(C)=1/4n该压缩编码方法下的平均失真nR(1/4)=1-H(1/4)=0.189(比特/信源符号）n失真失真1/4下，最小的信息传输率下，最小的信息传输率R是是0.189(比特/信源符号）nR(1/4)Rn在1/4失真度下，该压缩编码方法不是最佳的，或该信源还可以压缩4.5:4.5:香农三大定理的关系和比较香农三大定理的关系和比较1无失真信源编码定理无失真信源编码定理限失真信源编码定理限失真信源编码定理信源冗余度压缩编码信源的熵压缩编码无失真、

21、保熵有失真、熵压缩信源压缩的极限值：信源熵H(S)信源压缩的极限值：率失真函数R(D)存在性、构造性存在性定理4.4:4.4:香农三大定理的关系和比较香农三大定理的关系和比较2信道编码定理信道编码定理限失真信源编码定理限失真信源编码定理给定信道特性p=p(y|x)给定信源p=p(u)及失真测度d(u,v)对于假设的信源p=p(x)对于假设的试验信道p=p(v|u)寻求最优的信道编码C2寻求最优的限失真编码C3产生的误码率pe产生的最大失真D信道编码存在的条件RR(D)信道容量公式率失真函数公式存在符合条件的C2,使pe0存在符合条件的C3，使D量化它包括标量和矢量两种，这是重点讲标量量化1 标

22、量量化适用范围：连续无记忆信源2 标量量化的概念：连续信号量化K个若干可能离散值 举例：A/D采集版量化u量化概念量化概念uA/D中的量中的量化化u量化过程示量化过程示意图意图u一个量化实一个量化实例例 量化处理是使数据比特率下降的一个强有力的措施。 量化输入值动态范围很大，需要以多比特数表示一个数值，量化输出只能取有限个整数，称量化级。每个量化输入被强迫归一到与其接近的某个输出，即量化到某个级。量化处理总是把一批输入量化到一个输出级上，所以量化是个多对一的处理过程，量化中由信息丢失，或者说，会引起量化误差（量化噪声）。 模拟量经过A/D转换，得到二进制码的过程，就是脉冲编码调制（PCM）编码

23、过程，也称PCM编码。 A/D转换中的采样和量化分别是对时间和模拟量进行数字化的过程。量化n量化概念量化概念nA/D中的量中的量化化n量化过程示量化过程示意图意图n一个量化实一个量化实例例输入输入输出输出阈值阈值代表级代表级量化曲线量化曲线量化n量化概念量化概念nA/D中的量中的量化化n量化过程量化过程示意图示意图n一个量化实一个量化实例例 24位标准图像 8位（256色）标准图像量化n量化概念量化概念nA/D中的量中的量化化n量化过程示量化过程示意图意图n一个量化实一个量化实例例预测编码方法基本原理 从相邻数据之间有很强的相关性特点考虑，可以利用前面已经出现的数值，进行预测（估计），得到一个

24、预测值，将实际值与预测值求差，对这个差值信号进行编码、传送，这种编码方法即成为预测编码方法。预测编码最佳的预测编码：en=yn-un 最小有三种不同的标准：最小均方误差；最小平均绝对误差；最大零误差概率；DPCM基本原理转入f(i,j)e(i,j)量化器预测器预测器编码器解码器信道传输e(i,j)f(i,j)输出f(i,j)f(i,j)f(i,j)f(i,j)DPCM编、解码原理图预测编码 不带量化器的DPCM线性预测编码，属于无失真编码系统；带有量化器的DPCM线性预测编码，属于有失真编码系统。 DPCM线性预测系统是一个负反馈系统，对误差有收敛性。发送端与接收端之间的误差等于量化误差。 最

25、佳量化器的设计，可利用人眼的视觉可见度阈值和视觉掩蔽效应等生理特征，来确定量化器的级数和步距，使量化误差总处于人眼难以觉察的范围内，达到主观评定准则的要求。 最佳量化预测编码自适应预测编码ADPCM 自适应技术的概念是：预测器的预测系数和量化器的量化参数，能够根据图像的局部区域分布特点自动调整。 实践证明，ADPCM编、解码系统与DPCM编、解码系统相比，不仅能改善恢复图像的评测质量和视觉效果，同时还能进一步压缩数据。 ADPCM系统包括自适应预测，即预测系数的自适应调整和自适应量化，即量化器参数的自适应调整两部分内容。预测编码变换编码原理n定义：将空域图像信号映射变换到另一个正交矢量空间（变换域或频域），产生一批变换系数，对系数进行编码处理n原理：n信号