信息论-第4章《无失真信源编码》_第1页
信息论-第4章《无失真信源编码》_第2页
信息论-第4章《无失真信源编码》_第3页
信息论-第4章《无失真信源编码》_第4页
信息论-第4章《无失真信源编码》_第5页
已阅读5页,还剩56页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1 01 001 0001 00001 000001 0000001 0000000S1 s2 s3 s4 s5 s6 s7 s8000 001 010 011 100 101 110 111,00001 001 0000001 0000000 01 0000000 0001 000001 0001 00000015 3 7 7 2 7 4 6 4 7,1,将信源产生的全部信息无损地发送给信宿,这种信源编码称无失真信源编码。编码过程由编码器实现。4.1 编码器,第四章 无失真信源编码,r,编码器数学模型,2,1、编码器构成: 输入: 信源符号集 S=(s1,s2, sq),由q个符号组成 码符号集 X=(x1,x2xr),由r个符号组成 输出: 代码组C=(w1, w2,wq),由q个码字组成 其中, 称为码字,li称为码字长度,2、编码器的作用: 将信源符号集S中的符号si,i=1,2,q 变换成由码符号集X中的码元xj , j=1,2,r 组成的长度为li的一一对应的码字 码字 的集合称为代码组C。,3,3、码分类: 根据代码组C中码字的长度固定长度码:(定长码)代码组C中所有码字的长度相同。 可变长度码:(变长码)代码组C中码字的长度不相同。,10,晴 阴 雨 雪,0.40.30.20.1,1*0.4+2*0.3+3*0.2+3*0.1=1.9,4,4、码奇异性: 非奇异码:代码组C中所有码字都不相同。 奇异码: 代码组C中有相同的码字。,5,4.2 即时码与唯一可译码 1、分组码定义: 信源符号集S中的每一个符号si都映射成一个固定的码字wi,这种码称为分组码。2、分组码性质:,(1) 奇异性: 非奇异性是分组码正确译码的必要条件。,6,(2) 唯一可译性: 如果一个分组码对于任意有限的整数N,其N次扩展码均为非奇异码,则称之为唯一可译码 。不仅要求不同的码字表示不同的信源符号,而且还进一步要求对由信源符号构成的消息序列进行编码时,在接收端仍能正确译码,而不发生混淆。,7,唯一可译码是正确译码的充要条件。,11101100110001011010101001010001001100101001001001000100011000101000100100010001,00010000001,8,唯一可译码判别准则 如果一个分组码对于任意有限的整数N,其N次扩展码均为非奇异码,则此码为唯一可译码。首先由原始码集合S0,构造集合S1,S2, 、S1的构造: 若 ,且 ,则后缀A放入S1中。 、Sn(n1)的构造: 将S0和Sn-1中的元素进行比较 , 若 , 或 ,且 ,则A放入Sn中。,9,命题 码集合S0是唯一可译码的充要条件是S1,S2,中没有一个含有S0的元素。,bb,cde,de,10,例: S0=a,c,abb,cee, bbcde是否唯一可译码。,ee,例: a b b c d e,(3) 即时码: 无需考虑后续的码符号,即可以从码符号序列中译出码字,这样的唯一可译码为即时码。例如:C1=1,10,100,1000是唯一可译码,但非即时码C2=1,01,001,0001是唯一可译码,也是即时码,码前缀: 设 为一个码字,对于任意的1j l , 称码字wi的前j个元素 为码字wi的前缀。,例如,码1000的前缀有1,10,100, 1000,11,即时码存在充要条件: 唯一可译码成为即时码的充要条件是其中任意一个码字不是其他码字的前缀。,如果没有一个码字是其他码字的前缀,则在接收到一个相当于一个完整码字的码符号序列后,便可立即译码,而无需考虑其后的代码符号。 若设Wi是Wj的前缀,则在收到相当于Wi的码符号序列后,还不能判定它是一个完整的码字;若想正确译码,还必须参考后续的码符号。这与即时码的定义相矛盾。,例如: C=1,10,100,1000是唯一可译码,但非即时码 C=1,01,001,0001是唯一可译码,也是即时码,12,13,如何构造即时码?,14,15,16,17,每个节点可以有0,1,2,3,4五个分支,那么小鸟的位置可以用1010来描述。,只要是树枝顶端,编码就不会是其他位置的一部分(前缀)。,即时码可用树图来构造,树图中自根部经过一个分枝到达r个节点称为一阶节点。二阶节点的可能个数为r2个,一般n阶节点有rn个。若将从每个节点发出的r个分枝分别标以0,1,2,r-1,则每个n级节点需要用n个r元数字表示。,树图最顶部的节点称为树根;树枝的尽头称为节点;,18,每个节点生出的树枝数目等于码符号数r。,若有q个信源符号,在码树上就要选择q个终端节点,相应的r元基本符号表示就是码字。这样构造出来的码称为树码。若树码的各个分枝都延伸到最后一级端点,则此时将共有rn个码字,这样的码树称为整树,否则称为非整树。,指定某个n阶节点为终端节点,表示一个信源符号,则该节点就不再延伸,相应的码字即为从树根到此端点的分枝标号序列,其长度为n。因为从树根到每一个终端节点所走的路径均不相同,故一定满足即时码对前缀的限制。,19,树根码字起点树枝数码的进制数终止节点码字节数码长非满树变长码满树等长码,00011011,000102101112202122,010110111,将码与码树建立一一对应关系,20,r-l,唯一可译码存在充要条件,21,码长为1,可表示r个符号,每个符号占用全部号码资源的1/r;码长为2,可表示r2个符号,每个符号占用全部号码资源的1/r2;码长为l,可表示rl个符号,每符号占用全部号码资源的1/rl,即r-l。,克拉夫特不等式和麦克米伦不等式 设信源符号集为S = (s1, s2, , sq,),码符号集 为X = (x1, x2, , xr),对信源进行编码,代码组 为C = (w1, w2, ,wq),相应码长分别 l1, l2, lq, 即时码存在(唯一可译码存在)的充要条件为:,克拉夫特证明不等式为即时码存在的充要条件; 麦克米伦证明不等式为唯一可译码存在的充要条件。,22,4.3 定长码 一唯一可译定长码 1、简单信源S 信源S存在唯一可译定长码的条件为: 其中,q是信源符号个数; r是码符号集中码符号个数; l是简单信源S定长编码的码长。 表明唯一可译定长码的最短码长为,S1S2Sq,l=101,l=200011011,l=3000001010011100101110111,r=2,l=40000000100100011010001010110011110001001101010111100110111101111,23,2、信源S的N次扩展信源 N次扩展信源SN存在唯一可译定长码的条件为: 其中,qN是扩展信源符号个数; L是扩展信源SN定长编码的码长。,、l 是对原始信源进行定长编码的码长; 、L/N是N次扩展信源平均每个原始符号的码长; 、仅考虑了信源符号数,没考虑信源熵的不同。,24,3、定长编码条件的含义 定长唯一可译码存在的条件 即 l 是进行定长编码每个信源符号需要的码元个数 logr是一个码元符号平均所能携带的最大信息量,l logr是l个码元符号平均所能携带的最大信息量; logq是具有q个符号的离散信源一个符号平均具有的最大信息量; 存在唯一可译码(无失真); 能否考虑信源熵不同,实现,25,26,logr,logr,logr,货主X平均每天发货量H(x)logq。为了保证X的货顺利运走,每天需要车厢数,27,logr,logr,logr,货主X平均每天发货量H(x)logq。可否每天预留车厢数,28,logr,logr,logr,若当N个货主的货物一起发送时,若N足够多,可保证运不走的货物概率少于。,29,logr,logr,logr,若当N足够多时,可保证运不走的概率趋近于1。,二定长信源编码定理 1、定理设离散无记忆信源为 其信源熵为H(S), 其N次扩展信源SN为,用码符号集X=(x1,x2, xr)对SN进行长度为L的等长编码,对于0,0,只要满足 则当N足够大时,必可使译码错误小于。 反之,若 则当N足够大时,译码错误概率趋于1 。,30,证:、扩展信源SN有qN个符号 、每个符号都给一个码字,需要满足 、将SN分成两个互补集合,、集合 中 称为典型序列,若共有M个,则,31,32,、仅对典型序列进行编码,需要 M取上限有,、集合 中 没有编码,译码将出错,当N足够大时,译码错误概率,即集合 发生的概率小于。,自信息量,、集合 中 称为典型序列,若共有M个,则,33,自信息量,方差反映了随机变量的取值与平均值的偏离程度。,34,车贝晓夫不等式,相互独立的随机变量,35,、集合 中 没有编码,译码将出错,当N足够大时,译码错误概率,即集合 发生的概率小于。,36,根据方差定义推导出,2、定理 设有离散无记忆信源,熵为H(S) ,若对信源的长为N的符号序列进行定长编码,设码字是从r个码符号集中选取L个码元构成,对于 0 只要满足 则当N足够大时,可实现译码错误概率任意小的等长编码,近似无失真编码。,反之,若 满足 则当N足够大时,译码错误概率趋于1。,37,3、信源编码效率 (1) 编码速率:对于定长编码,编码速率定义为 编码速率R是原始信源一个符号对应的码元所能携带的最大信息量;当R H(S)时,可以实现无失真传输 。 (2) 编码效率:,38,相当于每天给货主X预留的装货量,实际装货量/预留的装货量,即预留车厢的利用率。,(3) 最佳编码效率: 对于给定的 0,最佳编码效率为 当要求译码错误概率 时,N应满足 将 用表示,,39,一般来说:当N有限时,高传输效率的等长码往往要引入一定的失真和错误,不能象变长码那样可以实现真正的无失真编码。,例:设有一简单离散信源,对其进行近似于无失真的等长编码,若要求其编码效率为96%,差错率低于10-5,试求符号联合编码长度N=?,解:编码效率:,信源序列长度需要4100万个符号,才能达到要求,不现实.,40,4.4 变长码 变长码无需N很大就能实现高效率的无失真信源编码; 变长码必须是唯一可译码才能实现无失真编码;变长码是唯一可译码的充要条件: (1)非奇异码 (2)任意有限次扩展码是非奇异码 若想即时译码,变长码须是即时码。,41,主要信源编码方法 1、匹配编码:概率大的信源符号,代码长度短; 概率小的信源符号,代码长度长。 2、变换编码:从一种空间变换成另一空间,再进行编码。 3、识别编码:对有标准形状的文字、符号和数据编码。 4、预测编码,42,同一信号可以有不同的表示方式,变换编码,国家标准信息交换汉字编码,位置总数9494个,利用区位的代号来编码汉字。,北 1717辈 1718背 1719贝 1720钡1721倍 1722,预测编码根据是较小的数据编码比特率较低。编码1,2,3,4和编码1,2,3,4,5,6比较思路由前面的样本对编码样本进行预测,仅编码预测误差,如果预测误差较小(典型情况),那么可由较低的平均比特率表示样本。使预测误差最小的预测方法最好。举例H264空间预测编码时间预测编码,1、码平均长度 离散无记忆信源为 编码后的码字为 码字长度分别为 因为是唯一可译码,si和wi一一对应,所以 则码字平均长度为,变长信源编码定理,46,、li是第i个码字的长度,必须是整数; 、 是变长编码后,一个信源符号平均所需要的码元个数,可以是小数; 、编码后信道的信息传输率R是一个码元携带的信息量H(X),即,对于给定的信源H(S),编码后 越小,信道的信息传输率R越大。我们希望 越小越好。,最小值能达到吗?如何达到 ?香农第一定理,47,2、定理 对于熵为H(S)的离散无记忆信源 用码符号集 对该信源进行编码, 则一定存在一种编码方式构成唯一可译码,其平均码长 满足,48,(1)唯一可译码的最短码长为 。,当选择 时,平均码长达到下界;,49,此时,,(2)一定存在平均码长小于 的唯一可译码。,若 不是整数,可取的最小值为,此时,,3、紧致码 对应一给定的信源和一给定的码符号集,若有一种唯一可译码,其平均长度 小于等于所有其它唯一可译码,则称这种码为紧致码,或最佳码。 信源变长编码的核心问题是寻找紧致码;紧致码是平均码长最短的唯一可译码,但紧致码不一定只有一个。,50,、紧致码最短码长为 。、达到下界的唯一可译码是紧致码; 、紧致码的平均码长不一定达到下界;,4、变长无失真信源编码定理(香农第一定理) 设离散无记忆信源 其信源熵为H(S),它的N次扩展信源SN为,扩展信源熵为H(SN),,51,用码符号集X=(x1,xr)对SN 编码,则总可以找到一种编码方法,构成唯一可译码,使信源S中的一个信源符号所需要的码字平均长度满足,当 时, , 是 对应的码字长度,52,、 是扩展信源SN编码后,一个符号 对应的平均码长; 是原始信源S一个符号 对应的平均码长; 、 是原始信源S编码后,一个符号 对应的平均码长; 、 和 都是信源S一个符号Si所需的平均码元个数 是信源扩展后编码,得到的平均码长 是信源编码后,得

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论