第7章 限失真信源编码

信息论与编码理论

第7章限失真信源编码为什么允许存在失真连续信源其上有无穷多个点，但是传输时不可能传输无穷多个点，只能选择有限个点传输但是用有限精确表示无限是不可能的，失真必然存在离散信源信源符号的个数虽然是有限的，但有时为了提高压缩效果，需要减少符号个数例如{0.5,1.0,1.5,2.0,2.5,3.0}压缩为{1,2,3}，这必然引入失真信宿有时信宿不要求精确恢复消息，例如人眼、人耳等去掉信宿感觉不到的数据可以提高压缩比，不过这样也就带来了失真Lena.bmp118KLena.jpg25K7.1失真的度量

7.1.1失真函数和失真矩阵由于进行失真编码，因此发送的数据与接收的数据之间有差别设离散无记忆信源（限失真信源编码之前的数据）为接收端接收到的数据（限失真信源编码之后的数据）为因此可以定义失真函数(或单个符号失真度)为：d(ui,vj)≥0,i=1,2,…,n;j=1,2,…,m用来度量信源发出符号为ui，接收符号为vj时所引起的误差或失真失真矩阵信源U有n个符号，接收变量V有m个符号d(ui,vj)就有n×m个，可以排成矩阵形式，即：称为失真矩阵，是n×m阶矩阵汉明失真如果误码失真的常数值为1，则称为汉明失真失真矩阵举例【例】二元对称信源，信源U＝{0,1}，接收变量V＝{0,1}，在汉明失真定义下，失真函数为：d(0,0)＝d(1,1)＝0,d(0,1)＝d(1,0)＝1则失真矩阵为【例】设信源U＝{0,1},接收变量V＝{0,1,2}，失真函数为d(0,0)＝d(1,1)＝0,d(0,1)＝d(1,0)＝1,d(0,2)＝d(1,2)＝0.5则失真矩阵为【例】信源U＝{0,1,2},接收变量V＝{0,1,2},失真函数为d(ui,vj)＝(ui－vj)2由失真定义得d(0,0)＝d(1,1)＝d(2,2)＝0d(0,1)＝d(1,0)＝d(1,2)＝d(2,1)＝1d(0,2)＝d(2,0)＝4则失真矩阵为7.1.2序列失真

（N次扩展信源失真）信源序列失真度（或失真函数）定义为：S=s1s2…sN——信源的一个输出序列Y=y1y2…yN——信宿的一个接收序列sl——信源输出序列中的一个符号yl——信宿接收序列中的一个符号例若信源序列S=01,Y=02则d(S,Y)=(d(0,0)+d(1,2))/2=(0+0.5)/3=0.25又若信源序列S=11,Y=02则d(S,Y)=(d(1,0)+d(1,2))/2=(1+0.5)/2=0.757.1.3平均失真和保真度准则信源平均失真：ui——信源输出符号，i＝1，2，…，np(ui)——信源输出符号ui的概率vj——信宿接收符号，j＝1,2,…，mp(vj|ui)——信道传递概率含义：从总体上描述整个系统失真情况例信源U={0,1}，信宿V={0,1,2}信道失真矩阵则信源平均失真为保真度准则保真度准则指平均失真度不大于允许失真D，即：保真度准则体现了限失真信源编码中的“限”7.2信息率失真函数信息传输率R：平均每个码元携带的信息量试验信道BD：将编码过程看成一个信道，而且满足保真度准则失真越大编码后的数据能够提供的关于编码前的数据的信息量越小需要通过试验信道传输的信息量越小信息传输率越小因此，我们关注信息传输率的最小值而这个最小值又与允许的失真有关将这个信息传输率的最小值记作R(D)，这就是信息率失真函数即互信息越小关于率失真函数的说明从所有满足保真度准则的试验信道中找到一个条件概率，使平均互信息最小，其实质是选择（设计）一种编码方式，在满足保真度准则的条件下，使信息传输率最小，即保留的信息最少/失真最大，以达到压缩比最高当给定系统所允许的失真D之后，R(D)已经是信息传输率的最小值，不能再小了。如果再小，系统将不满足保真度准则的要求。7.2.2信息率失真函数

定义域及性质R(D)的定义域为0≤Dmin≤D≤DmaxDmin是允许的平均失真的最小值由于而其中的p(u)和d(u,v)是已知条件，因此所以对任意的ui，只要能够找到一个vj，使得取最小值，则此时的平均失真就是Dmin假设d(ui,v*)是d(ui,v1),…,d(ui,vm)中最小的那一个，则的最小值就是d(ui,v*)此时在p(ui,v1),…,p(ui,vm)中，只有p(ui,v*)=1，其他的均为0这就意味着使得平均失真取Dmin的信道（编码方法）也就确定了此时只要失真矩阵中每行有一个0，则Dmin=0。在实际应用中，一般Dmin=0。例则使允许失真达到Dmin的信道为例则使允许失真达到Dmin的信道为DmaxR(D)是关于D的下凸函数，并严格递减为什么求最小值？从图中可以看出，当D>Dmax时，R(D)也不再减小，仍然为0由于I(U,V)=0，因此此时的试验信道须满足：使得U和V无关，即p(v|u)=p(v)，一般取例则使允许失真达到Dmax的信道为R(D)函数的性质R(Dmin)≤H(U),R(Dmax)=0下凸连续单调递减7.2.3信息率失真函数和信道容量的关系只有当R(D)<C时，才能找到至少一个试验信道（即一种限失真信源编码方法）满足保真度准则的要求。7.2.4保真度准则下的信源编码定理定理7-1（限失真信源编码定理，香农第三定理）设R(D)为离散无记忆信源U的信息率失真函数，R为信息传输率，D为允许失真，则当信息率R>R(D)，只要信源序列长度L足够长，一定存在一种编码方法，其译码失真小于或等于D＋ε，ε为任意小的正数；反之，若R<R(D)，则无论采用什么样的编码方法，其译码失真必大于D。如果是二元信源，对于任意小的ε>0，每一个信源符号的平均码长满足如下公式：限失真信源编码定理的说明该定理说明在一定条件下满足保真度准则的编码方法是存在的，但并未给出编码步骤在给定允许失真D的情况下，所需信息率R的下限值，或信源信息压缩的下限值，就是R(D)7.3量化编码

7.3.1量化编码的主要作用连续信号离散信号的转换过程（A/D）：量化量化也是连续信源限失真编码的主要方法常用量化方法标量量化：各个样本值分别量化（零记忆量化）矢量量化量化关心的主要问题量化失真越小越好7.3.2均匀量化（线性量化）连续信源的取值范围为[a0,an]，将[a0,an]均分为n个子区间，取每个小区间的中点值作为量化值yi=(ai+1+ai)/2量化失真（量化误差）量化误差：e=x-yi均方误差：信噪比SNR（SignalNoiseRate）：7.3.3最优量化最优量化：使均方误差最小或者信噪比最大的量化如何得到最值？一阶导数为07.3.4矢量量化思想回想第二章讲到的算术编码和LZW编码，对信源序列进行编码，目的是提高编码效率受到这种思想的启发，矢量量化编码是对多个信源符号组成的矢量进行量化编码优点自由度更大码率可进一步压缩7.4预测编码

7.4.1基本原理有记忆信源：信源先后发出的消息符号之间彼此依存（信源相关性）例1：自然语言例2：数字图像我们、要、的、把、看、…碗、机、水、书、框、…基本原理预测编码的基本原理：根据已经得到的数据预测当前数据的值ûi（预测值），编码仅对预测值ûi和实际值ui之间的差（预测误差）ei=ui-ûi进行编码。为什么可以根据已经得到的数据预测当前数据的值？信源具有相关性因此预测编码只适合于有记忆信源，对无记忆信源来讲，预测编码起不到压缩的作用7.4.3DPCM编译码原理DPCM：差分脉冲编码调制（DifferentialPulse-CodeModulation）预测值：ûi=aui-1，其中a=1，a叫做预测系数编码：如果ei>0，则编码为1如果ei<0，则编码为0译码：如果码字为1，则增加一个固定的幅度Δ如果码字为0，则减少一个固定的幅度Δ如何提高DPCM的精度提高采样频率，同时减小Δ采样频率越高，相邻两个采样点之间的差别越小（相关性越强）7.5变换编码

7.5.1变换编码基本原理时域（空域）频域(1,2)空域数据频域数据基基时域频域变换时域频域变换例2Matlab源代码x=0:0.01:(4*pi);y0=5;y1=4*sin(x);y4=0.25*sin(8*x);ysum=y0+y1+y4;subplot(4,1,1);plot(x,y0);subplot(4,1,2);plot(x,y1);subplot(4,1,3);plot(x,y4);subplot(4,1,4);plot(x,ysum);4sin(x)0.25sin(8x)5+4sin(x)+0.25sin(8x)5空域数据sin(x)、sin(8x)：基540.25频域数据直流系数（分量）低频交流系数时域频域变换高频交流系数交流系数的值代表相应频率的能量，信号的能量主要集中在低频。（信号的能量为信号幅度的和，即积分值）低频表示信号的大体的趋势，高频表示信号的细节。7.5.2变换编码能够压缩信源的原因解除信号相关性，提高压缩效率传输时，只传输前面一部分低频系数，而舍弃后面的高频系数。540.25变换54压缩反变换编码译码9.5.3离散余弦（DCT）变换-3.0959-8.0022-1.86857.56435.43045.9623-4.9717-1.8566-0.148222.4009-4.58556.1522-1.2966-1.33085.9227-4.3259低频高频0.0166670.0066967-0.0043756-0.0262510.0014272-0.0048-0.00045128-0.017946-0.019903-0.00556390.00363880.031094-0.0067224-0.0139010.0045089-0.024418左上角数据