信息论与编码第四章PPT讲稿.ppt

《信息论与编码第四章PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《信息论与编码第四章PPT讲稿.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息论与编码第四章*1第1页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码2第第4章章 限失真信源编码限失真信源编码n4.1平均失真和信息率失真函数平均失真和信息率失真函数n 4.1.1失真函数失真函数n 4.1.2平均失真平均失真n 4.1.3信息率失真函数信息率失真函数n 4.1.4信息率失真函数的性质信息率失真函数的性质n4.2离散信源和连续信源的计算离散信源和连续信源的计算n4.3限失真信源编码定理限失真信源编码定理n4.4常用信源编码方法简介常用信源编码方法简介n 4.4.1游程编码游程编码n 4.4.2算术编码算术编码n 4.4.3矢量量化矢量量化n

2、4.4.4预测编码预测编码n 4.4.5变换编码变换编码n习习 题题第2页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码3第第4章章 限失真信源编码限失真信源编码控制信息失真的原因控制信息失真的原因?n 在实际问题中，在实际问题中，信号有一定的失真是可信号有一定的失真是可以容忍的。以容忍的。但是当失真大于某一限度后，信但是当失真大于某一限度后，信息质量将被严重损伤，甚至丧失其实用价值。息质量将被严重损伤，甚至丧失其实用价值。要规定失真限度，必须先有一个定量的失真要规定失真限度，必须先有一个定量的失真测度。测度。例如：语音、图像例如：语音、图像第3页，共51页，编辑

3、于2022年，星期四*北京工商大学信息工程学院 信息论与编码44.1平均失真和信息率失真函数平均失真和信息率失真函数4.1.1失真函数失真函数 失真函数失真函数定义定义:信源编码信源编码Xx1x2xnYy1y2ym第4页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码54.1平均失真和信息率失真函数平均失真和信息率失真函数4.1.1失真函数失真函数n失真矩阵失真矩阵第5页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码64.1.1失真函数失真函数n例例设信源符号设信源符号X 0，1,编码器输出符号编码器输出符号Y 0,1,2,规定失真规定

4、失真函数为函数为 d(0,0)d(1,1)0;d(0,1)d(1,0)=1;d(0,2)d(1,2)0.5，求失真矩阵。，求失真矩阵。解:由式得失真矩阵由式得失真矩阵第6页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码74.1.1失真函数失真函数 (1)常用失真函数常用失真函数 均方失真：均方失真：绝对失真：绝对失真：相对失真：相对失真：误码失真：误码失真：说明说明:第7页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码84.1.1失真函数失真函数说明说明:(2)最常用的失真函数及其适用性最常用的失真函数及其适用性 均方失真函数、绝对失

5、真函数、相对失真函数适用于连续信源；误均方失真函数、绝对失真函数、相对失真函数适用于连续信源；误码失真适用于离散信源。码失真适用于离散信源。(3)失真函数困难性比较失真函数困难性比较 均方失真和绝对失真只与均方失真和绝对失真只与(xi-yj)有关，而不是分别与有关，而不是分别与xi及及yj有关，在数学处理上比较方便。有关，在数学处理上比较方便。第8页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码94.1.1失真函数失真函数 失真函数的定义的推广失真函数的定义的推广-序列编码序列编码 如果假定离散信源输出符号序列如果假定离散信源输出符号序列Xx1 x2xi xn，其

6、中，其中L长符号序列长符号序列X=X1X2 XL的取值设为的取值设为 xi=xi1 xi2 xiL，经信源编码后，接收端收到符号序，经信源编码后，接收端收到符号序列列Y=y1 y2yjym，其中，其中L长符号序列长符号序列yj=yj1 yj2 yjL 则失真函数定义为则失真函数定义为 式中式中d(xik,yjk)是信源输出第是信源输出第i个个L长符号长符号xi中的第中的第k个符号个符号xik，接收端收到第，接收端收到第j个个L长长符号符号yj中的第中的第k个符号个符号yjk的失真函数的失真函数。第9页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码104.1.2平均

7、失真平均失真失真矩阵失真矩阵信源编码信源编码Xx1x2xnYy1y2ym第10页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码114.1.2平均失真平均失真n平均失真平均失真 失真函数的数学期望称为平均失真。失真函数的数学期望称为平均失真。n对于连续随机变量的平均失真对于连续随机变量的平均失真连续随机变量的联合概率密度连续随机变量的联合概率密度第11页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码124.1.3信息率失真函数信息率失真函数n1.信息率失真函数信息率失真函数R(D)问题产生问题产生?对于对于信道容量为信道容量为C的信道传

8、输的信道传输信息传输率为信息传输率为R的信源时，的信源时，如果如果RC，就必须对信源压缩，使其压缩后信息传输率，就必须对信源压缩，使其压缩后信息传输率R小于小于信道容量信道容量C，但同时要保证压缩所引入的失真不超过预先规定的，但同时要保证压缩所引入的失真不超过预先规定的限度限度D。信息压缩问题就是对于给定的信源，在满足平均失真。信息压缩问题就是对于给定的信源，在满足平均失真 的前提下，使信息率尽可能小。的前提下，使信息率尽可能小。（举例语音）（举例语音）第12页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码134.1.3信息率失真函数信息率失真函数2 D允许信道（

9、允许信道（D允许的试验信道）允许的试验信道）对于离散无记忆对于离散无记忆信道信道(假想信道，实际上是信源编码假想信道，实际上是信源编码)3 信息率失真函数信息率失真函数R(D)n对于离散无记忆信源对于离散无记忆信源第13页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码144.1.3信息率失真函数信息率失真函数例例4-1-2 已知已知,编码器输入的概率分布为编码器输入的概率分布为:p(x)0.5，0.5，信道矩阵分别为信道矩阵分别为:求求:互信息。互信息。x1x2y1y20.60.4 0.20.8第14页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院

10、 信息论与编码154.1.3信息率失真函数信息率失真函数例例4-1-2 分析分析 p(x)0.5，0.5 x1x2y1y20.60.4 0.20.8第15页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码164.1.3信息率失真函数信息率失真函数n解解 (1)因因p(xiyj)p(xi)p(yj/xi)；n n n p(x1y1)=0.3，p(x1y2)0.2，n p(x2y1)=0.1，p(x2y2)0.4n n 因为因为p(yi)=n 所以所以p(y1)0.4，p(y2)0.6 x1x2y1y20.60.4 0.20.8第16页，共51页，编辑于2022年，星期

11、四*北京工商大学信息工程学院 信息论与编码174.1.3信息率失真函数信息率失真函数又因为又因为p(xi/yj)=p(xiyj)/p(yj)n 所以所以 p(x1/y1)=3/4,p(x1/y2)=1/3,n p(x2/y1)=1/4,p(x2/y2)=2/3 n 根据互信息公式代入可得根据互信息公式代入可得n n 比特比特/符号符号n 用用pij代入进行同样的运算可得代入进行同样的运算可得n I(X;Y)=0.397 比特符号比特符号 第17页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码184.1.3信息率失真函数信息率失真函数补充例补充例 已知已知,编码器输

12、入的概率分布为编码器输入的概率分布为:p(x)0.5，0.5，信道模型分别为信道模型分别为:求求:互信息、平均失真。互信息、平均失真。x1x2y1y20.990.01 0.010.09x1x2y1y211x1x2y1y20.90.1 0.10.9x1x2y1y20.60.4 0.40.6x1x2y1y20.50.5 0.50.5第18页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码194.1.3信息率失真函数信息率失真函数补充例补充例 编码器输入的概率分布为编码器输入的概率分布为:p(x)0.5，0.5 x1x2y1y211第19页，共51页，编辑于2022年，星

13、期四*北京工商大学信息工程学院 信息论与编码204.1.3信息率失真函数信息率失真函数补充例补充例 编码器输入的概率分布为编码器输入的概率分布为:p(x)0.5，0.5，x1x2y1y20.990.01 0.010.99第20页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码214.1.3信息率失真函数信息率失真函数补充例补充例 编码器输入的概率分布为编码器输入的概率分布为:p(x)0.5，0.5，x1x2y1y20.90.1 0.10.9第21页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码224.1.3信息率失真函数信息率失真函数补

14、充例补充例 编码器输入的概率分布为编码器输入的概率分布为:p(x)0.5，0.5，x1x2y1y20.60.4 0.40.6第22页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码234.1.3信息率失真函数信息率失真函数补充例补充例 编码器输入的概率分布为编码器输入的概率分布为:p(x)0.5，0.5，x1x2y1y20.50.5 0.50.5第23页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码244.1.3信息率失真函数信息率失真函数补充例补充例 总结总结 x1x2y1y20.50.5 0.50.5当信源固定，变动信道，这里指信源

15、编码的一种方式，当信源固定，变动信道，这里指信源编码的一种方式，信道转移概率可变。信道转移概率可变。第24页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码254.1.3信息率失真函数信息率失真函数补充例总结补充例总结 x1x2y1y20.990.010.010.09x1x2y1y211x1x2y1y20.90.1 0.10.9x1x2y1y20.60.4 0.40.6x1x2y1y20.50.5 0.50.51-pppI(X;Y)DR(D)第25页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码264.1.3信息率失真函数信息率失真函数

16、例例设信源的符号表为设信源的符号表为A=a1,a2,a2n,概率分布为概率分布为p(ai)1/2n，i1,2,2n，失真函数规定为，失真函数规定为由信源概率分布可求出信源熵为由信源概率分布可求出信源熵为设想采用下面的编码方案：设想采用下面的编码方案：等效试验信道第26页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码274.1.3信息率失真函数信息率失真函数例例设信源的符号表为设信源的符号表为A=a1,a2,a2n,概率分布为概率分布为p(ai)1/2n，i1,2,2n，失，失真函数规定为真函数规定为平均失真平均失真D为为等效试验信道第27页，共51页，编辑于202

17、2年，星期四*北京工商大学信息工程学院 信息论与编码284.1.3信息率失真函数n由该信道模型知，它是一个确定信道由该信道模型知，它是一个确定信道n由互信息公式可得由互信息公式可得 I(X;Y)=H(Y)-H(Y/X)=H(Y)n信道输出概率分布为信道输出概率分布为n所以概率分布为所以概率分布为n则输出熵则输出熵H(Y)为为第28页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码294.1.3信息率失真函数信息率失真函数信息率失真函数的意义：信息率失真函数的意义：在一定允许失真度在一定允许失真度D的条件下，用尽可能少的码符号来传送信的条件下，用尽可能少的码符号来传送

18、信源消息，以提高通信系统的可靠性源消息，以提高通信系统的可靠性。作业：作业：4-1本次课小结：本次课小结：1 失真函数失真函数 2 平均失真度平均失真度 3 信息率失真函数信息率失真函数第29页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码304.1.4信息率失真函数的性质信息率失真函数的性质1.R(D)函数的定义域 R(D)的定义域为D0，Dmax2.R(D)函数的下凸性和连续性3.R(D)函数的单调递减性例:R(D)在定义域内是下凸的,连续的。R(D)的单调递减性可以作如下理解：容许的失真度越大，所要求的信息率越小。第30页，共51页，编辑于2022年，星期四

19、*北京工商大学信息工程学院 信息论与编码314.1.4信息率失真函数的性质得出如下结论：nR(D)是非负的实数，即R(D)0。其定义域为0Dmax，其值为0H(X)。当DDmax时,R(D)0。nR(D)是关于D的下凸函数，因而也是关于D的连续函数。nR(D)是关于D的严格递减函数。第31页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码324.2离散信源和连续信源的计算某些特殊情况下R(D)的表示式为：率失真函数第32页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码334.2离散信源和连续信源的计算n例4.2.1设输入输出符号表为X=

20、Y=0，1，输入概率分布p(x)=p，1-p，0p1/2，失真矩阵为 求信息率失真函数R(D).解:简记 (1)按下式解方程 解得第33页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码344.2离散信源和连续信源的计算n(2)按下式解方程 解得n(3)得转移概率分布第34页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码354.2离散信源和连续信源的计算n(4)求s(s=log)第35页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码364.2离散信源和连续信源的计算n(5)计算R(D)，将上面各式代入，则有

21、(D)=H(p)-H(D)，p为参数第36页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码374.3限失真信源编码定理n限失真信源编码定理：设离散无记忆信源X的信息率失真函数R(D)，则当信息率RR(D)，只要信源序列长度L足够长，一定存在一种编码方法，其译码失真小于或等于D+，为任意小的正数；反之，若RR(D)，则无论采用什么样的编码方法，其译码失真必大于D。如果是二元信源，对于任意小的0，每一个信源符号的平均码长满足如下公式 在失真限度内使信息率任意接近R(D)的编码方法存在。第37页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码

22、384.4常用信源编码方法简介4.4.1游程编码n游程长度 在二元序列中，只有两种符号，即“0”和“1”，这些符号可连续出现，连“0”这一段称为“0”游程，连“1”这一段称为“1”游程。它们的长度分别称为游程长度L(0)和L(1).对于多元序列也存在相应的游程序列。例如m元序列中，可有m种游程。连着出现符号ar的游程，其长度L(r)就是“r”游程长度。n设有多元信源序列(x1，x2，xm1，y，y，y，xm1+1，xm1+2，xm2，y，y，其中x是含有信息的代码，取值于m元符号集A，可称为信息位；y是冗余位，它们可为全零，即使未曾传送在收端也能恢复。这样的序列可用下列两个序列来代替：111，

23、100，000111，111000和 x1，x2，xm1，xm1+1，xm1+2，xm2，前一个序列中，用“1”表示信息位，用“0”表示冗余位；后一个序列是取消冗余位后留下的所有信息位。第38页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码394.4.2算术编码n算术编码的基本思路 从全序列出发，将各信源序列的概率映射到0，1区间上，使每个序列对应这区间内的一点，也就是一个二进制的小数。n积累概率 则n例如有一序列S=011，这种三个二元符号的序列可按自然二进数排列，000，001，010，则S的积累概率为 P(S)=p(000)+p(001)+p(010)n如果

24、S后面接一个“0”，积累概率就成为 P(S0)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0101)=p(000)+p(001)+p(010)=P(S)信源的符号概率和积累概率第39页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码404.4.2算术编码如果S后面接一个“1”，则其积累概率是 P(S1)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0101)+p(0110)=P(S)+p(0110)=P(S)+p(S)p0上面两式可统一写作一般的递推公式序列的概率的公式 第40页，共5

25、1页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码414.4.2算术编码n实用中，采用积累概率P(S)表示码字C(S)，符号概率p(S)表示状态区间A(S)，则有n实际编码过程:先置两个存储器C和A，起始时可令 其中 代表空集。每输入一个信源符号，存储器C和A就按照上式更新一次，直至程序结束，就可将存储器C的内容作为码字输出。第41页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码424.4.2算术编码n例4.4.1有简单的四个符号a，b，c，d构成序列S=abda，各符号及其对应概率如表算术编解码过程如下:设起始状态为空序列，则A()=1，C(

26、)=0。表4-4-1各符号及其对元概率符号符号符号概率pi符号概率pi符号累积概率Pj符号累积概率Pjabcd0.100(1/2)0.010(1/4)0.001(1/8)0.001(1/8)0.0000.1000.1100.111第42页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码434.4.2算术编码算术码编码过程第43页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码444.4.2算术编码据递推公式的相反过程译出符号。具体译码顺序是后编的先译，故称为LIFO算术码，步骤如下：C(abda)=0.010111010,0.1)第一个符

27、号为a；放大至0,1):C(abda)20.101110.1,0.110)第二个符号为b；去掉累积概率Pb:0.10111-0.1=0.00111放大至0,1):0.00111 =0.1110.111,1)第三个符号为d去掉累积概率Pd：0.111-0.111=0放大至0,1)：0 =00,0.1)第四个符号为a。第44页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码454.4.3矢量量化n标量量化 连续信源进行编码的主要方法是量化，即将连续的样值x离散化成为yi，i=1,2,3,n。n设信源符号的取值区间为(a0，an)，即a0 xan，a0可为负无限，an可为

28、正无限，所以上述假设不失一般性。量化就是将上面的区间分成n个小区间，每个区间内定一个量化值yi，若各区间端点为ai-1和ai，必有 a0y1a1y2an-1ynann最佳标量量化就是在一定的n值时，选择各ai和yi以使失真最小。此时的信息率为 R=log n第45页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码464.4.3矢量量化n量化噪声 当一个样值x经量化后所产生的误差为也就是在信号值x上叠加了一个样值为 的噪声信号。n以语音信号量化常用的脉码调制(PCM)为例。设语音信号的准峰值为L，由于语音信号是双向性的，则其取值范围为-L,L。量化级数为n，量化级差为

29、2L/n，用中心值作为量化值yi。语音信号样值x的概率密度是负指数分布经推导计算(见参考文献2)可得信号功率与噪声功率之比即信噪比为第46页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码474.4.3矢量量化n压扩技术 综合考虑大、小功率的情况，将它们区别对待，即非均匀量化，小功率时量化级差小；大功率时量化级差大。这样就减小了小功率时的量化噪声，增大了大功率时的量化噪声。使得在较低的比特数编码时，既保证了小功率时的信噪比，又利用了大功率时信噪比的富余量。n矢量量化 在前面的最佳编码中可看到将离散信源的多个符号联合编码可提高效率。连续信源也是如此，当把多个信源符号联

30、合起来形成多维矢量，再对矢量进行标量量化时，自由度将更大，同样的失真下，量化级数可进一步减少，码率可进一步压缩。第47页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码484.4.4 预测编码n预测 就是从已收到的符号来提取关于未收到的符号的信息，从而预测其最可能的值作为预测值；并对它与实际值之差进行编码，达到进一步压缩码率的目的。n估计理论n预测指令n利用预测值来编码的方法 最佳估计:若估值与原物理量之间的均方误差最小 无偏估计:估值的数学期望等于原来的物理量一类是用实际值与预测值之差进行编码，也叫差值编码。一类方法是根据差值的大小，决定是否需传送该信源符号。第4

31、8页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码494.4.5 变换编码n变换编码 通过变换来解除或减弱信源符号间的相关性，再将变换后的样值进行标量量化，或采用对于独立信源符号的编码方法，以达到压缩码率的目的。n傅氏变换 设有函数f(t)，0tT，则 正交性 归一性 把f(t)展开为第49页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码504.4.5 变换编码nK-L变换 按均方误差最小准则来推算，可使变换后的随机变量之间互不相关。缺点是计算复杂，除了需测定相关函数和解积分方程外，变换时的运算也十分复杂.n离散变换 先对信源输出x(t)取样然后取N个样值形成一个N维矢量，对这矢量用矩阵进行变换，成为另一域内的N维矢量，以解除或减弱矢量内各分量的相关性。再对后一个分量进行标量量化或对矢量进行矢量量化来完成信源编码。第50页，共51页，编辑于2022年，星期四*北京工商大学信息工程学院 信息论与编码514.4.5 变换编码n变换和反变换写成矩阵形式分别为第51页，共51页，编辑于2022年，星期四