第四章有限失真信源编码

第四章限失真信源编码简介：和无失真编码比较，（失真和熵率值比较）熵压缩编码在的允许失真条件下，编码后的熵率压缩到最小（无译码器）（解释两种编码的必要性）信息速率失真函数R(D):是熵压缩编码的基础，把信息和失真两个度量可联系在一起，为信号处理中同时考虑两个因素提供可解。引入限失真的必要性1）

失真在传输中是不可避免的;2）

接收者（信宿）无论是人还是机器设备，都有一定的分辨能力与灵敏度，超过分辨能力与灵敏度的信息传送过程是毫无意义的;3）

即使信宿能分辨、能判别，但对通信质量的影响不大，也可以称它为允许范围内的失真；4）

我们的目的就是研究不同的类型的客观信源与信宿，在给定的Qos要求下的最大允许（容忍）失真D，及其相应的信源最小信息率R(D).5）

对限失真信源，应该传送的最小信息率是R(D)，而不是无失真情况下的信源熵H(U).显然

H(U)≥R(D).当且仅当D=0时，等号成立；6）

为了定量度量D，必须建立信源的客观失真度量，并与D建立定量关系；7）

R(D)函数是限失真信源信息处理的理论基础；本章节达到的目的理解限失真信源编码在通信系统中的意义了解失真测度的含义和基本方法理解R(D)函数的概念、物理意义、性质了解特殊情况下R(D)函数的计算方法了解R(D)函数在信道编码定理中的作用理解香农第三定理的物理意义及其实用意义了解香农三大定理的相互关系与比较情况本章研究内容概述失真的度量信息率失真函数限失真信源编码定理香农三大定理的关系和比较§4.1:概述－1问题引出无噪信道编码定理回顾有噪信道编码定理回顾存在的问题：实际需求特点引出的研究内容本章节研究方法与顺序§4.1:概述－2无噪信道编码定理回顾：总可以找到一种输入分布（信源编码方法），使在无噪无损信道上，能够以信道容量C无误地传输信息。信源编码无噪无损信道R=C;PE=0,最佳分布消息压缩冗余度最好地利用C§4.1:概述－3有噪信道编码定理回顾：只要R<C，总可以找到一种信道编码方法，使在信道上能够以尽可能小的PE传输信息。信源编码信道R<C;PE=ε,消息信道编码增加冗余度，最好地匹配信道特性§4.1:概述－4存在问题对于连续和模拟信源H(S)=∞信道传输率R=H(S)/n（比特/码符号）R=

∞平均码长l=Hr(S)=H(S)/logr,l=∞,实际上，因为B有限，C一定有限，R<C,及l=∞均不可能§4.1:概述－5实际需求特点：信宿对真实度的要求：实际语音信号：20Hz~8KHz人耳能够分辨：300Hz~3400Hz图象色差：可达足够多视觉分辨：256级（黑白）已足够可以允许一定的失真度完全保真没必要§4.1:概述－6引出的研究内容限失真的信源编码问题允许一定的失真度下，能将信源信息压缩到什么程度？（最少需要多少比特才能在收端描述信源？）一定的信息传输率R下，允许的最大失真是多少？相关问题失真如何度量？率失真函数如何计算？§4.1:概述－7研究方法：抽象信道虚拟试验信道§4.1:概述－8方法：抽象：将与讨论重点关系小的部分抽象因为涉及信源编码，对信道进行抽象信道编码→信道→信道译码信道*信道*可以略去根据信道编码定理信道*是一个没有干扰的广义信道，信宿收到信息的失真只来自于信源编码§4.1:概述－9方法：虚拟：将讨论重点虚拟细化将限失真信源的编译码过程虚拟信源编码→信道*→信源译码试验信道可以用信道传递概率来描述限失真信源编译码前后的关系信源编码信道编码信道信道译码信源译码信源信宿信源编码信道*信源译码信源信宿信源信宿试验信道UVP(V|U)§4.1:概述－10本章节讨论顺序从最简单的离散无记忆信源入手讨论失真的度量讨论率失真函数的定义和性质讨论在最简单的二进制对称离散信源和高斯连续信源条件下率失真函数R(D)的计算方法讨论限失真信源编码定理信息率失真理论的探讨及应用举例香农三大定理的关系和比较§4.2:失真的度量－1失真度定义平均失真度保真度准则试验信道§4.2:失真的度量－2失真度定义在U,V联合空间上定义：d（ui，vj），ui∈U，vj∈V

为U,V的失真测度。d（ui，vj）有距离的概念性质1：ui=vj时，d=0性质2：mind=0性质3：0<d<∞§4.2:失真的度量－3失真度定义0,ui=vj

离散信源：用失真矩阵描述。dij=>0,ui≠

vj

0,ui=vj

汉明距离度量时：dij=1,ui≠

vj连续信源：用失真函数描述。d(u,v)=(u-v)2=|u-v|

§4.2:失真的度量－4平均失真度单符号失真度：d（ui，vj）≥0，（i=1~r，j=1~s）信源的失真矩阵可表示为：共r×s个元素§4.2:失真的度量－5平均失真度平均失真度：∵U，V是随机变量；∴d（ui，vj）也是随机变量平均失真度：

§4.2:失真的度量－6平均失真度c.f:d&d：描述了某个信源符号通过传输后失真的大小不同的信源符号，其d不同。：描述了某一个单符号信源在某一试验信道传输下的失真，它不仅与单个符号的d有关，还与试验信道的统计特性有关。§4.2:失真的度量－7平均失真度N维信源符号序列的平均失真度：此时D为一rN×sN阶的矩阵与：d（u，v）、p(u)、p(v|u)、N均有关§4.2:失真的度量－8平均失真度信源平均失真度信源、信道均无记忆时：信源平稳时：序列中第l个分量的平均失真度§4.2:失真的度量－9保真度准则给定D，若≤D，则称此为保真度准则对于序列信源，保真度准则为：≤ND§4.2:失真的度量－10试验信道：P(v|u)不是实际的信道特性矩阵，在此相当于不同的编码方法，不同的编码方法，不同。定义：所有≤D的试验信道构成D失真许可的试验信道集合BD§4.3:率失真函数－1问题引出度量了失真，进一步关心的问题是：一定的失真D下，最小的信息传输率R是多少？一定的失真D下，收端再现信源需要的最低的平均信息量是多少？定义：（信息）率失真函数R(D)

对于N维序列信源：§4.3:率失真函数－2率失真函数的进一步解释单位：比特/信源符号（同互信息）离散无记忆信源：RN(D)=NR(D)P(v|u)无实际信道含义，只代表不同编码方法求R(D)就是在D条件下，选择一种编码方法，使R最小。定义域：D∈[0,Dmax]R(D)的性质：凸状性单调递减性连续性§4.3:率失真函数－3Dmax与R(Dmax)定义当DDmax时，R(Dmax)=0使R(Dmax)=0的p(v|u)不止一个不同的p(v|u)有不同的|R(D)=0对我们有意义的：的最小值＝Dmax的p(v|u)利用该p(v|u)求得使R(Dmax)=0时的DmaxR=0时，U,V统计独立p(v|u)只是v的函数则有：p(v|u)＝Q(v),Dmax=DmaxDR(D)R(D)>0R(D)=0§4.3:率失真函数－4R(D)的计算求解R(D)，--求解互信息的极小值互信息I(X,Y)是条件转移概率的下凸函数极小值存在一般情况下很难得到R(D)的显函数表达式，只能得到参量表达式具体计算很困难，一般利用计算机进行迭代计算在一些特殊情况下，R(D)有显式解。举例(1)6.4PropertyofR(D)CalculationofR(D)ofbinarysymmetricsourceKnownconditions：二进制对称信源U={0,1}，接收变量V={0,1}，允许的失真DP(u)=[ω，1－ω]，ω≤1/2汉明失真矩阵Stepstosolve：求Dmin=0

找到满足最小失真的试验信道p(v|u),得到R(0)由汉明失真矩阵和失真度定义，计算最大允许的失真度Dmax=ω由Dmax，找到满足最大失真的试验信道p,并得到R(Dmax)在一般条件下当0<D<Dmax时，计算平均失真度=Pe选取一个信道，求互信息的最小值得到R(D)Verify：找到满足R(D)的试验信道，验证其正确性Analysisoftheresult：R(D)曲线分析6.4PropertyofR(D)0.40.5DR(D)(比特/符号）ω＝0.3ω＝0.1ω＝0.2ω＝0.5对于同一个D：信源分布越均匀，R(D)就越大，信源压缩的可能性越小反之，若信源分布越不均匀，即信源剩余度越大，R(D)就越小，压缩的可能性就越大。二进制对称信源的R(D)函数6.4PropertyofR(D)CalculationofR(D)ofGausssourceKnownconditions：高斯信源U，其均值为m，方差为σ2，接收变量V概密函数：失真函数：均方误差失真，即：Stepstosolve：计算平均失真度当≤D，求互信息求互信息的下限值得到包含有D和σ2的R(D)表达式讨论D和σ2比值不同时R(D)的取值Verify：找到满足R(D)的试验信道，验证其正确性Analysisoftheresult：R(D)曲线分析PropertyofR(D)0.00.81.0D/σ2R(D)(比特/自由度）当D＝σ2时，R(D)＝0。即：如果允许失真等于信源的方差，则只需用均值m来表示信源输出，而不需要传送信源的任何实际输出。当D＝0时，R(D)∞。即：在连续信源情况下，要毫无失真地传送连续信源必须要求信道具有无限大的容量。当D＝0.25σ2时,R(D)=1（比特/自由度）。即：允许均方误差小于或等于σ2/4时，连续信号的每个样本值最少需要用一个二元符号来传输。1.01.2高斯信源在均方误差准则下的R(D)函数Afourdimensionalsymmetricchannel,thesymbolreceivedis,itsdistortionmatrixis.Pleasecalculatethe,andthefunction,anddrawthegraphofittakingfourtofivepointswithit.Forn-dimensionalequalprobabilitysource,theratedistortionfunctionis.Inthisquestion,the.Sotheratedistortionfunctionis

.§4.4:限失真信源编码定理－1限失真信源编码定理限失真信源编码定理的证明限失真信源编码定理的实用意义§4.4:限失真信源编码定理－2限失真信源编码定理设R(D)为一离散无记忆平稳信源的信息率失真函数，并且有有限的失真测度。对于任意D≥0，ε＞0，δ＞0以及任意足够长的码长n，则一定存在一种信源编码C，其码字个数为:M=exp{n［R(D)+ε］}而编码后码的平均失真度:d(C)≤D+δ如果用二元编码，R(D)取比特为单位，则上式M可写成:M=2{n［R(D)+ε］}§4.4:限失真信源编码定理－3定理解释：对于任何失真度D≥0，只要码长n足够长，总可以找到一种编码C，使编码后每个信源符号的信息传输率:R′=logM/n=R(D)+ε即:R′≥R(D)而码的平均失真度d(C)≤D。在允许失真D的条件下，信源最小的、可达的信息传输率是信源的R(D)。§4.4:限失真信源编码定理－4限失真信源编码定理的证明问题：设有达到R(D)的试验信道p(v|u),要证明对于任意的R‘>R(D)时，存在一种信息传输率为R’的信源编码，其平均失真度≤D+δ思路：产生码书选取编译码方法计算失真度方法：产生码书：在Vn空间随机抽取M=2nR’个随机序列v编码方法：若存在与信源序列u构成失真典型序列对的序列v(ω),则编码uv(ω),否则编码uv(1)译码：再现v(ω)失真度计算：在所有随机码书和Un空间统计平均的基础上计算平均失真度§4.4:限失真信源编码定理－5限失真信源编码定理的几点说明只是一个存在性定理，没有构造方法存在问题：符合实际信源的R(D)函数计算相当困难信源统计特性的确切数学描述难得符合主客观实际的失真测度难得R(D)计算本身困难即使求得了R(D)，还需研究最佳编码方法才能达到极限值R(D)。§4.4:限失真信源编码定理－6限失真信源编码定理的实用意义如何进行限失真信源编码？举例：R（D）的实用意义在允许一定失真的情况下，信源的R(D)函数可以作为衡量各种压缩编码方法性能优劣的一种尺度。举例：二进制无记忆对称信源编译码：无噪无损信道传输举例：结论

R’=1/3（比特/信源符号）该压缩编码方法下的信息传输率d(C)=1/4该压缩编码方法下的平均失真R(1/4)=1-H(1/4)=0.189(比特/信源符号）失真1/4下，最小的信息传输率R是0.189(比特/信源符号）R(1/4)<R’在1/4失真度下，该压缩编码方法不是最佳的，或该信源还可以压缩§4.5:香农三大定理的关系和比较－1

无失真信源编码定理限失真信源编码定理信源冗余度压缩编码信源的熵压缩编码无失真、保熵有失真、熵压缩信源压缩的极限值：信源熵H(S)信源压缩的极限值：率失真函数R(D)存在性、构造性存在性定理§4.4:香农三大定理的关系和比较－2

信道编码定理限失真信源编码定理给定信道特性p=p(y|x)给定信源p=p(u)及失真测度d(u,v)对于假设的信源p=p(x)对于假设的试验信道p=p(v|u)寻求最优的信道编码C2寻求最优的限失真编码C3产生的误码率pe产生的最大失真D信道编码存在的条件R<C限失真信源编码存在的条件R>R(D)信道容量公式率失真函数公式存在符合条件的C2,使pe0存在符合条件的C3，使D’<D熵压缩编码重点介绍三种有代表性的方法1）量化标量量化矢量量化2）变换编码3）预测编码习惯上对把矢量量化和变换编码称为熵压缩分组编码，预测编码称为熵压缩树码前面提到就是允许一定D，把熵率压缩最小，即，使率失真函数最小。Dmin123RD1为直接矢量量化；2为先作变换，再L-M算法；３对其各分量直接用L-M算法结论：矢量量化是熵压缩分组编码的最有效方法如图①>②>③量化它包括标量和矢量两种，这是重点讲标量量化1

标量量化适用范围：连续无记忆信源2

标量量化的概念：连续信号量化K个若干可能离散值举例：A/D采集版量化量化概念A/D中的量化量化过程示意图一个量化实例量化处理是使数据比特率下降的一个强有力的措施。量化输入值动态范围很大，需要以多比特数表示一个数值，量化输出只能取有限个整数，称量化级。每个量化输入被强迫归一到与其接近的某个输出，即量化到某个级。量化处理总是把一批输入量化到一个输出级上，所以量化是个多对一的处理过程，量化中由信息丢失，或者说，会引起量化误差（量化噪声）。模拟量经过A/D转换，得到二进制码的过程，就是脉冲编码调制（PCM）编码过程，也称PCM编码。A/D转换中的采样和量化分别是对时间和模拟量进行数字化的过程。量化量化概念A/D中的量化量化过程示意图一个量化实例输入输出阈值代表级量化曲线量化量化概念A/D中的量化量化过程示意图一个量化实例24位标准图像8位（256色）标准图像量化量化概念A/D中的量化量化过程示意图一个量化实例预测编码方法基本原理从相邻数据之间有很强的相关性特点考虑，可以利用前面已经出现的数值，进行预测（估计），得到一个预测值，将实际值与预测值求差，对这个差值信号进行编码、传送，这种编码方法即成为预测编码方法。预测编码最佳的预测编码：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线性预测系统是一个负反馈系统，对误差有收敛性。发送端与接收端之间的误差等于量化误差。最佳量化器的设计，可利用人眼的视觉可见度阈值和视觉掩蔽效应等生理特征，来确定量化器的级数和步距，使量化误差总处于人眼难以觉察的范围内，达到主观评定准则的要求。

最佳量化预测编码自适应预测编码ADPCM自适应技术的概念是：预测器的预测系数和量化器的量化参数，能够根据图像的局部区域分布特点自动调整。实践证明，ADPCM编、解码系统与DPCM编、解码系统相比，不仅能改善恢复图像的评测质量和视觉效果，同时还能进一步压缩数据。ADPCM系统包括自适应预测，即预测系数的自适应调整和自适应量化，即量化器参数的自适应调整两部分内容。预测编码变换编码原理定义：将空域图像信号映射变换到另一个正交矢量空间（变换域或频域），产生一批变换系数，对系数进行编码处理原理：信号在时域描述时信息冗余度大，变换后，参数独立，去掉相关性，减少