信息论与编码曹雪虹第4章课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《信息论与编码曹雪虹第4章课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息论 编码 曹雪虹第 课件
- 资源描述:
-
1、第4章信息率失真函数 本章主要讨论在信源允许一定失真情况下所需的最少信息率,从分析失真函数、平均失真出发,求出信息率失真函数R(D)。n4.1 平均失真和信息率失真函数n4.2 离散信源和连续信源的R(D)计算(1)“消息完全无失真传送消息完全无失真传送”的可实现性的可实现性n信道编码定理信道编码定理:无论何种信道,只要信息率无论何种信道,只要信息率R小于信小于信道容量道容量C,总能找到一种编码,使在信道上能以任意小,总能找到一种编码,使在信道上能以任意小的错误概率和任意接近于的错误概率和任意接近于C的传输率来传送信息。反之的传输率来传送信息。反之,若,若RC,则传输总要失真。,则传输总要失真
2、。n完全无失真传送不可实现:完全无失真传送不可实现:q实际的信源常常是连续的,信息率无限大,要无失实际的信源常常是连续的,信息率无限大,要无失真传送要求信息率真传送要求信息率R为无穷大;为无穷大;q实际信道带宽是有限的,所以信道容量受限制。要实际信道带宽是有限的,所以信道容量受限制。要想无失真传输,所需的信息率大大超过信道容量想无失真传输,所需的信息率大大超过信道容量RC。4.1.1 引引 言言4.1 基本概念有失真信源编码的意义有失真信源编码的意义(2)实际中允许一定程度的失真实际中允许一定程度的失真n 技术发展的需要技术发展的需要q随着科学技术的发展,数字系统应用得越来越广泛,随着科学技术
3、的发展,数字系统应用得越来越广泛,这就需要传送、存储和处理大量的数据。为了提高传这就需要传送、存储和处理大量的数据。为了提高传输和处理效率,往往需要对数据压缩,这样也会带来输和处理效率,往往需要对数据压缩,这样也会带来一定的信息损失。一定的信息损失。q人类社会已进入信息时代,信息爆炸的结果要求人们人类社会已进入信息时代,信息爆炸的结果要求人们解决如何对浩如烟海的数据有效的压缩,减少数据的解决如何对浩如烟海的数据有效的压缩,减少数据的存储容量存储容量(如各种数据库、电子出版物、多媒体娱乐如各种数据库、电子出版物、多媒体娱乐)、传输时间传输时间(如数据通信和遥测如数据通信和遥测)、或、或占有带宽占
4、有带宽(如多媒如多媒体通信、数字音频广播、高清晰度电视体通信、数字音频广播、高清晰度电视),要想方设法,要想方设法压缩给定消息压缩给定消息 集合占用的空间域、时间域和频率域资集合占用的空间域、时间域和频率域资源。源。4.1.1 引引 言言4.1 基本概念n实际生活中的需要实际生活中的需要q实际生活中,人们一般并不要求获得完全无失真的消息实际生活中,人们一般并不要求获得完全无失真的消息,通常只要求近似地再现原始消息,即允许一定的失真,通常只要求近似地再现原始消息,即允许一定的失真存在。存在。q例如打电话:即使语音信号有一些失真,接电话的人也例如打电话:即使语音信号有一些失真,接电话的人也能听懂。
5、人耳接收信号的带宽和分辨率是有限的。能听懂。人耳接收信号的带宽和分辨率是有限的。q放电影:理论上需要无穷多幅静态画面,由于人眼的放电影:理论上需要无穷多幅静态画面,由于人眼的“视觉暂留性视觉暂留性”,实际上只要每秒放映,实际上只要每秒放映24幅静态画面。幅静态画面。q有些失真没有必要完全消除。有些失真没有必要完全消除。4.1.1 引引 言言4.1 基本概念n限失真编码:信源编码经过译码后能保留应用要求的信息,允许信源有一定的失真。n那么在允许一定程度失真的条件下,能够把信那么在允许一定程度失真的条件下,能够把信源信息压缩到什么程度,也就是,允许一定程源信息压缩到什么程度,也就是,允许一定程度失
6、真的条件下,如何能快速的传输信息,这度失真的条件下,如何能快速的传输信息,这就是本章所要讨论的问题。就是本章所要讨论的问题。4.1 平均失真和信息率失真函数n4.1.1 失真函数n4.1.2 平均失真n4.1.3 信息率失真函数R(D)n4.1.4 信息率失真函数的性质4.1 平均失真和信息率失真函数 在实际问题中,信号有一定的失真是可以容忍的。在实际问题中,信号有一定的失真是可以容忍的。但是当失真大于某一限度后,信息质量将被严重损伤但是当失真大于某一限度后,信息质量将被严重损伤,甚至丧失其实用价值。要规定失真限度,必须先有,甚至丧失其实用价值。要规定失真限度,必须先有一个定量的失真测度。为此
7、可引入失真函数。一个定量的失真测度。为此可引入失真函数。1、失真函数信源信源编码信道编码信道信道译码信源译码信宿干扰 根据信道编码定理,我们可以把信道编码、信道和信道解码等价成是一个没有任何干扰的广义信道,这样收信者收到消息后,所产生的失真只是由信源编码带来的。我们也可以把信源编码和信源译码等价成一个信道。4.1.1 失真函数我们称此信道为我们称此信道为试验信道试验信道。现在我们要研究在给定允许失真的条件下,是否可以设现在我们要研究在给定允许失真的条件下,是否可以设计一种信源编码使信息传输率为最低。为此,我们首先计一种信源编码使信息传输率为最低。为此,我们首先讨论失真的测度。讨论失真的测度。信
8、源信源解码器信宿信源编码器 无噪信道试验信道4.1.1 失真函数失真函数定义 信源 经过信源编码后输出 对于每一对(xi,yj),指定一个非负函数 d(xi,yj)0 i=1,2,n j=1,2,m 称 d(xi,yj)为单个符号的失真函数.表示信源发出符号 xi ,接收端再现 yj 所引起的误差或失真.d越小表示失真越小:d(xi,yj)=0 无失真,d(xi,yj)0 有失真.,21nxxxX,21myyyY 常用的失真函数 1平方误差失真函数 d(xi,yj)=(xi-yj)2 2绝对误差失真函数 d(xi,yj)=|xi-yj|3相对误差失真函数 d(xi,yj)=|xi-yj|/|x
9、i|4误码失真函数 失真函数1,2,3用于连续信源,失真函数4用于离散信源,失真函数4也称Hanmming失真函数失真矩阵d n m 矩阵 其他其他10),(jiyxdji ),(),(),(),(1111mnnmyxdyxdyxdyxdd例例1:0(,)1ijd u vijij当uv当uv失真矩阵为:01.110.1.11.0D这种失真成为汉明失真在二元情况下:1001D例例2:删除信源:删除信源1mn0(,)1(1/2()ijijd u vijjni除j=n以外的所有i和所有j)所有对于二元删除信源n=2,m=301/2111/20D 失真函数的定义可以推广到序列编码情况,如果假定离散信源
10、输出符号序列X=(X1X2XlXL),其中L长符号序列样值xi(xi1xi2xilxiL),经信源编码后,输出符号序列Y=(Y 1Y 2Y lY L),其中L长符号序列样值yj(yj1yj2yjlyjL),则失真函数定义为:其中其中d(xil,yjl)是信源输出是信源输出L长符号样值长符号样值xi中的第中的第l个符号个符号xil时,编时,编码输出码输出L长符号样值长符号样值yj中的第中的第l个符号个符号yjl的失真函数。的失真函数。LljliljiLyxdLd1),(1),(yx4.1.2 平均失真平均失真 由于xi和yj都是随机变量,所以失真函数d(xi,yj)也是随机变量,限失真时的失真值
11、,只能用它的数学期望或统计平均值,因此将失真函数的数学期望称为平均失真平均失真,记为 nimjjiijinimjjijibadabpapbadbapD1111),()/()(),()(ix信源编码器信源编码器jy)(ijxyp 对于连续随机变量同样可以定义平均失真 dxdyyxdyxpDxy),(),(LllLljlilLDLyxdELD111),(1对于对于L长序列编码情况,平均失真为长序列编码情况,平均失真为 受信道容量的限制,实际应用中必须对信源进行压缩,应 1使其压缩后的信息传输率小于信道容量;2保证压缩所引入的平均失真 不超过预先给定的允许 失真度D;3在满足 D的前提下,使编码后的
12、信息率尽可能小.不等式 D 称为保真度准则DDDD4.1.3 信息率失真函数R(D)naaax,21信源编码器信源编码器nbbby,21XY假想信道假想信道将信源编码器看作信道将信源编码器看作信道4.1.3 信息率失真函数R(D)给出一个失真的限制值D,在满足平均失真 D的条件下,选择一种编码方法使信息率R尽可能小。信息率R就是所需输出的有关信源X的信息量。D试验信道 1有失真的信源编码器视作有干扰的信道(假想信道)2当信源已知(即P(X)已知)时,单个符号的失真度给定,选择一类假想信道,使得 D,这类假想信道称为 D 失真允许信道,或 D 失真允许试验信道.记为 PD=p(yi|xj):D;
13、i=1,2,n;j=1,2,m p(yi|xj)为信道的传递概率。凡满足保真度准则的这些试验信道称为D失真许可的试验信道。把所有D失真许可的试验信道组成一个集合PD。DD(1)D允许试验信道(2)信息率失真函数R(D)由于互信息取决于信源分布和信道转移概率分布,当p(xi)一定时,互信息I是关于p(yj/xi)的U型凸函数,存在极小值。因而在上述允许信道PD中,可以寻找一种信道pij,使给定的信源p(xi)经过此信道传输后,互信息I(X;Y)达到最小。该最小的互信息就称为信息率失真函数R(D),即);(min)(YXIDRDP对于离散无记忆信源,R(D)函数可写成 p(ai),i1,2,n 是
14、信源符号概率分布;p(bj/ai),i1,2,n,j1,2,m 是转移概率分布 p(bj),j1,2,m 是接收端收到符号概率分布。nimjjijijiPPbpabpabpapDRDij11)()/(log)/()(min)(例4-1-3 设信源的符号表为Aa1,a2,a2n,概率分布为p(ai)1/2n,i1,2,2n,失真函数规定为 即符号不发生差错时失真为0,一旦出错,失真为1,试研究在一定编码条件下信息压缩的程度。jijiaadji01),(4.1.4 信息率失真函数的性质1.R(D)函数的定义域 Dmin和R(Dmin)Dmin0 对于连续信源 )()0()(minXHRDR)()0
15、()(minxHRDRc (2)Dmax和R(Dmax)niijimjdpD1,2,1maxmin选择所有满足选择所有满足R(D)0中中D的最小值,定义为的最小值,定义为R(D)定义域定义域的上限的上限Dmax,即,即DDDR0)(maxmin因此可以得到因此可以得到R(D)的定义域为的定义域为max,0 DD Dmax是这样来计算的。R(D)0就是I(X;Y)0,这时试验信道输入与输出是互相独立的,所以条件概率p(yj/xi)与xi无关。即jjijijpypxypp)()/(求出满足条件 的D中的最小值,即,即mjniijijdppD11maxmin11mjjp nimjijjidppD11
16、此时平均失真为此时平均失真为从上式观察可得:在从上式观察可得:在j=1,m中,可找中,可找到到 值最小的值最小的j,当该,当该j对应的对应的pj1,而,而其余其余pj为零时,上式右边达到最小,这时为零时,上式右边达到最小,这时上式可简化成上式可简化成niijidp1niijimjdpD1,2,1maxmin (4.3)且且 (4.4)(4.5)证:证:1)定义域下界:定义域下界:对对x的每一取值的每一取值 ,令对应最小的,令对应最小的 条件概率条件概率p(bj|ai)为为1,其余条件概率为零,就得到其余条件概率为零,就得到Dmin。maxmin0DDDxyyxdxpD),(min)(minxy
17、yxdxpD),()(minmaxyxyxdxypxpD,),()|()(yxyyxdxypxp,),(min)|()(),(min),(yxdyxdyxyyxypyxdxp)|(),(min)(0),(min)(xyyxdxp)0),(yxdia(,)ijd a b1 R(D)的定义域为的定义域为 2)定义域上界:定义域上界:R(D)为平均互信息,所以为平均互信息,所以R(D)0。在较大范围内。在较大范围内 求极小值一定不大于在所含小范围内求的极小值,所求极小值一定不大于在所含小范围内求的极小值,所 以以D1D2=R(D1)R(D2),即,即R(D)是是D的非增函数。的非增函数。当当XY独立
18、时,独立时,R(D)I(X;Y)=0,当,当D继续增加,继续增加,R(D)仍然为仍然为0。所以,。所以,Dmax是使是使R(D)=0的最小平均失真。当的最小平均失真。当 x,y独立时,独立时,p(x,y)=p(x)p(y),有,有 由于由于 已给定,而且对不同已给定,而且对不同y,也可能有不同的值。所以,求也可能有不同的值。所以,求 ,并使对,并使对应的应的p(y)=1,其余为,其余为0。这样就可使平均失真最小。所。这样就可使平均失真最小。所以得到(以得到(4.5)式。)式。证毕。证毕。yxyxyxyxdxpypyxdypxpD,),()()(min),()()(minmax(),(,)p x
展开阅读全文