第七章：信息率失真函数与限失真信源编码

第七章：信息率失真函数与限失真信源编码定理本章研究内容•概述•失真的度量•信息率失真函数•限失真信源编码定理•限失真信源编码定理应用•实用型信源编码•香农三大定理的关系和比较§7.1:概述－1•无噪信道编码定理回顾：–总可以找到一种输入分布（信源编码方法），使在无噪无损信道上，能够以信道容量C无误地传输信息。信源编码无噪无损信道R=C;PE=0,最佳分布消息压缩冗余度最好地利用C限：平均码长最小值Hr(S)每个码符号平均能够携带的最大信息量§7.1:概述－2•有噪信道编码定理回顾：–只要RC，总可以找到一种信道编码方法，使在信道上能够以尽可能小的PE传输信息。增加冗余度，最好地匹配信道特性限：信息传输率最大值C每个信道符号平均能够携带的最大信息量信源编码信道RC;PE=ε,消息信道编码§7.1:概述－3•存在问题–对于连续和模拟信源H(S)=∞•信道传输率R=H(S)/n（比特/码符号）R=∞•平均码长l=Hr(S)=H(S)/logr,l=∞,–实际上，因为B有限，C一定有限，RC§7.1:概述－4•实际需求特点：–信宿对真实度的要求：•实际语音信号：20Hz~8KHz人耳能够分辨：300Hz~3400Hz•图象色差：可达足够多视觉分辨：256级（黑白）已足够–可以允许一定的失真度•完全保真没必要§7.1:概述－5•引出的研究内容–限失真的信源编码问题•允许一定的失真度下，能将信源信息压缩到什么程度？（最少需要多少比特才能在收端描述信源？）•一定的信息传输率R下，可能达到的最小的平均失真是多少？–相关问题•失真如何度量？•率失真函数如何计算？§7.1:概述－6•方法：–抽象：将与讨论重点关系小的部分抽象•因为涉及信源编码，对信道进行抽象•信道编码→信道→信道译码信道*•研究失真影响时，“信道*”可以忽略–根据信道编码定理：信道*是一个没有干扰的广义信道，信宿收到信息的失真只来自于信源编码§7.1:概述－7•方法：–虚拟：将讨论重点虚拟细化•将限失真信源的编译码过程虚拟•信源编码过程→信道*→信源译码过程试验信道•可以用信道传递概率来描述限失真信源编译码前后的关系信源编码信道编码信道信道译码信源译码信源信宿信源编码信道*信源译码信源信宿信源信宿试验信道UVP(V|U)§7.2:失真的度量－1•失真度定义•平均失真度•保真度准则•试验信道§7.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：0d∞§7.2:失真的度量－3•失真度定义0,ui=vj–离散信源：用失真矩阵描述。dij=0,ui≠vj0,ui=vj汉明距离度量时：dij=1,ui≠vj–连续信源：用失真函数描述。d(u,v)=(u-v)2=|u-v|§7.2:失真的度量－4•平均失真度–单符号失真度：d（ui，vj）≥0，（i=1~r，j=1~s）信源的失真矩阵可表示为：共r×s个元素),().......,(..),().......,(1111srrsvudvudvudvudD§7.2:失真的度量－5•平均失真度–平均失真度：∵U，V是随机变量；∴d（ui，vj）也是随机变量平均失真度：),()|()(),()()],([,jijijiivuvuduvpupvuduvpvudED§7.2:失真的度量－6•平均失真度–confer:d&•d：描述了某个信源符号通过传输后失真的大小，不同的信源符号，其d不同。•：描述了某一个单符号信源在某一试验信道传输下的失真，它不仅与单个符号的d有关，还与试验信道的统计特性有关。DD§7.2:失真的度量－7•平均失真度–N维信源符号序列的平均失真度：此时D为一rN×sN阶的矩阵与：d（u，v）、p(u)、p(v|u)、N均有关NljiijrisjillNNvudppvudEND111),()|()()],([)()(ND§7.2:失真的度量－8•平均失真度–N维信源符号序列信源平均失真度–信源、信道均无记忆时：–信源平稳时：)(1NDDNNNllNNNllDDDND111)(序列中第l个分量的平均失真度)|()|(),()(ijijiiuvpuvpupupillDDlDNND)(DDN§7.2:失真的度量－9•保真度准则–给定D，若≤D，则称此为保真度准则–对于序列信源，保真度准则为：≤NDD)(ND§7.2:失真的度量－10•试验信道：–P(v|u)不是实际的信道特性矩阵，在此相当于不同的编码方法，编码方法不同，不同。–定义：所有≤D的试验信道构成D失真许可的试验信道集合BDDD§7.3:率失真函数－1•问题引出–度量了失真，进一步关心的问题是：•一定的失真D下，最小的信息传输率R是多少？•一定的失真D下，收端再现信源需要的最低的平均信息量是多少？•定义：（信息）率失真函数R(D))},({min)()|(VUIDRDBuvp)},({min)()(VUIDRNDNDN对于N维序列信源：§7.3:率失真函数－2•率失真函数的进一步解释–单位：比特/信源符号（同互信息）–离散无记忆信源：RN(D)=NR(D)–P(v|u)无实际信道含义，只代表不同编码方法–求R(D)就是在D条件下，选择一种编码方法，使R最小。–定义域：D∈[0,Dmax]–R(D)的性质：•凸状性•单调递减性•连续性一般情况下:Dmin=0,R(Dmin)=H(U)(有条件)当D≥Dmax时，R(D)=0;而当DminDDmax时，H(U)R(D)0.minmin()(|)(,)ijiijijDpupvuduv7.3：删除信道，求21012110DminD()min(|)(,)ijiijijpupvuduv()min(,)iijjipuduv§7.3:率失真函数－3§7.3:率失真函数－4•Dmax与R(Dmax)DDDmaxDR(D)R(D)0R(D)=0定义当DDmax时，R(Dmax)=0使R(Dmax)=0的p(v|u)不止一个不同的p(v|u)有不同的对我们有意义的：具有最小的的p(v|u)利用该p(v|u)求得使R(Dmax)=0时的DmaxR=0时，U,V统计独立p(v|u)只是v的函数,则有：p(v|u)＝P(v)例：二元信源,计算。12()0.40.6UuuPUmaxD00D§7.3:率失真函数－5max,min()()(,)UVDpupvduv()'()min()()(,)min()()pvVUpvVpvpuduvpvdvmin()(,)VUpuduv§7.3:率失真函数－6•R(D)的计算–求解R(D)，--求解互信息的极小值–互信息I(X,Y)是条件转移概率的下凸函数极小值存在–一般情况下很难得到R(D)的显函数表达式，只能得到参量表达式–具体计算很困难，一般利用计算机进行迭代计算§7.3:率失真函数－7•二进制对称信源的R(D)计算–已知条件：二进制对称信源U={0,1}，接收变量V={0,1}，允许的失真D•P(u)=[ω，1－ω]，ω≤1/2•汉明失真矩阵0110D§7.3:率失真函数－8–求解步骤：•由Dmin=0，找到满足最小失真的试验信道p(v|u),得到R(0)•由汉明失真矩阵和失真度定义，计算最大允许的失真度Dmax•由Dmax，找到满足最大失真的试验信道p,并得到R(Dmax)•在一般条件下当0DDmax时，计算平均失真度•选取一个信道，使＝D，求互信息•求互信息的下限值得到R(D)–验证：找到满足R(D)的试验信道，验证其正确性–结果分析：R(D)曲线分析DD§7.3:率失真函数－90.10.20.40.60.81.00.10.20.30.40.5DR(D)(比特/符号）ω＝0.3ω＝0.1ω＝0.2ω＝0.5对于同一个D：信源分布越均匀，R(D)就越大，信源压缩的可能性越小反之，若信源分布越不均匀，即信源剩余度越大，R(D)就越小，压缩的可能性就越大。二进制对称信源的R(D)函数DDDHHDR00)()()(等概信源的信息率失真函数。信源输出符号集，等概分布，输出符号集，失真函数定义为12,,...,rUuuu12,,...,rVvvv0(,),1,2,...,1ijijduvijrij()loglog(1)()RDrDrHD§7.3:率失真函数－10()loglog(1)()RDrDrHD0.00.20.40.60.81.02.03.0)(DRD8r4r2r§7.3:率失真函数－11•高斯信源的R(D)计算–已知条件：高斯信源U，其均值为m，方差为σ2，接收变量V•概密函数：•失真函数：均方误差失真，即：–求解步骤：•计算平均失真度•当≤D，求互信息•求互信息的下限值得到包含有D和σ2的R(D)表达式•讨论D和σ2比值不同时R(D)的取值–验证：找到满足R(D)的试验信道，验证其正确性–结果分析：R(D)曲线分析DD]exp[)(222)(21muup2)(),(vuvud§7.3:率失真函数－12当D＝σ2时，R(D)＝0。即：如果允许失真等于信源的方差，则只需用均值m来表示信源输出，而不需要传送信源的任何实际输出。当D＝0时，R(D)∞。即：在连续信源情况下，要毫无失真地传送连续信源必须要求信道具有无限大的容量。当D＝0.25σ2时,R(D)=1（比特/自由度）。即：允许均方误差小于或等于σ2/4时，连续信号的每个样本值最少需要用一个二元符号来传输。0.00.20.40.60.81.0D/σ2R(D)(比特/自由度）1.21.40.20.40.60.81.01.2高斯信源在均方误差准则下的R(D)函数22122log()0DDRDD§7.4:限失真信源编码定理－1•限失真信源编码定理•限失真信源编码定理的证明•限失真信源编码定理的实用意义§7.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)+ε］}§7.4:限失真信源编码定理－3•定理解释：–对于任何失真度D≥0，只要码长n足够长，总可以找到一种编码C，使编码后每个信源符号的信息传输率:R′==R(D)+ε即:R′≥R(D)而码的平均失真度d(C)≤D。–在允许失真D的条件下，信源最小的、可达的信息传输率是信源的R(D)。logMn§7.4:限失真信源编码定理－4•限失真信源编码定理的证明•问题：–设有达到R(D)的试验信道p(v|u),要证明对于任意的R‘R(D)时，存在一种信息传输率为R’的信源编码，其平均失真度≤D+δ•思路：–产生码书–选取编译码方法–计算失真度•方法：–产生码书：在Vn空间随机抽取M=2nR’个随机序列v–编码方法：若存在与信源序列u构成失真典型序列对的序列v(ω),则编码uv(ω),否则编码uv(1)–译码：再现v(ω)–失真度计算：在所有随机码书和Un空间统计平均的基础上计算平均失真度§7.4:限失真信源编码定理－5•限失真信源编码定理的几点说明–只是一个存在性定理，没有构造方法–存在问题：•符合实际信源的R(D)函数计算相当困难–信源统计特性的确切数学描述难得–符合主客观实际的失真测度难得–R(D)计算本身困难•即使求得了R(D)，还需研究最佳编码方法才能达