无失真信源编码_第1页
无失真信源编码_第2页
无失真信源编码_第3页
无失真信源编码_第4页
无失真信源编码_第5页
已阅读5页,还剩58页未读 继续免费阅读

下载本文档

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

文档简介

第三章 无失真信源编码,3.1 编码的相关概念3.2 定长编码定理3.3 变长编码定理3.4 最佳编码,无失真信源编码,为什么要对进行编码?1.信源发出的消息符号可能不适合信道的传输,将信源发出的消息符号转换为适合信道传输的符号。2.信源消息确定后,提高通信的有效性-信源编码。3.提高通信的可靠性 , 编码具有发现错误或纠正错误的抗干扰能力-信道编码 。4.提高通信的安全性-加密编码。,3.1 编码的相关概念,3.1.1 信源编码的定义3.1.2 信源编码的研究方法3.1.3 编码相关概念3.1.4 唯一可译码的存在条件,编码的相关概念,信源编码的定义信源编码定义:指定能够满足信道特性/适合于信道传输的符号序列/码序列,来代表信源输出的消息。完成编码功能的器件称为编码器。离散信源输出的码序列离散信源输出的消息是由一个个离散符号组成的随机序列信源符号序列;X=(X1X2XlXL) Xlx1,x2,xi,xn信源编码就是把信源输出的随机符号序列变成码序列。Y=(Y1Y2YkYK) Yky1,y2,yj,ym,信源编码的研究方法,研究方法研究信源编码时,将信道编码和译码看成是信道的一部分,而突出信源编码;,信道,信源编码的研究方法,研究信道编码时,将信源编码和译码看成是信源和信宿的一部分,而突出信道编码。,信源,信宿,信源编码的研究方法,讨论无失真信源编码可以先不考虑抗干扰问题,所以它的数学模型比较简单,如图所示。,编码相关概念,码元和码字码元(符)集:信道可传输的基本符号的集合, 记为Y; 设 Y 有m个符号:Y=y1,y2,ym,其中yi称为码元或码符。m 元信道: 可传输m个基本符号的信道;二元信道: 可传输 2个基本符号的信道。这是一种最常用的信道, 基本符号常用 0 , 1 表示。码字: 由码元组成的序列称为码字,记为Yi 。码字Yi的码元个数 Ki 称为Yi的码长。所有码字Yi的码长 Ki 均相等称为定长码。码字Yi的码长 Ki不全相等称为变长码。,编码相关概念,编码与译码信源编码:将信源符号xi或符号序列X按一种规则映射成码字Yj的过程。无失真编码:信源符号到码字的映射必须一一对应。译码:从码符号到信源符号的映射。码表:所有映射规则的集合。,编码相关概念,许用码和禁用码许用码字:信源的符号xi或符号序列X与码字Yj定义了对应关系的码字。禁用码字:信源的符号xi或符号序列X与码字Yj未定义对应关系的码字。许用码字的全体称为码集。,编码相关概念,分组码(块码)分类按码字的码长分类定长码:码集中所有码字的码长相等。变长码:码集中所有码字的码长不全相等。按信源符号与码字对应关系分类非奇异码:信源符号与码字是一一对应的。奇异码:信源符号与码字不是一一对应的。,编码相关概念/分类,按译码唯一性分类唯一可译码:对于多个码字组成的有限长码流,只能唯一地分割一个个的码字。唯一可译码又称为单义码。唯一可译码在传输过程中不需要同步码。 非唯一可译码:对有限长码流,不能唯一地分割一个个的码字。例:码流 100111000 码1:x10 x210 x311 可分割10, 0, 11, 10, 0, 0码2:x11 x210 x311 则无法唯一分割,编码相关概念/分类,按译码的即时性分类非即时码:接收端收到一个完整的码字后,不能立即译码;还需要等到下一个码字开始接收后才能判断是否可以译码。即时码:接收端收到一个完整的码字后,就能立即译码;即时码又称为非延长码或异前缀码。例:非即时码 ,码流 01001100 x10 x201 x311 译码为 x2, x1, x1, x3, x1, ?即时码,码流 01001100 x10 x210 x311 译码为 x1, x2, x1, x3, x1, x1,结论:即时码指的是码集任何一个码不能是其他码的前缀,即时码必定是唯一可译码, 唯一可译码不一定是即时码。,编码相关概念/分类/举例,例:码1:显然不是惟一可译码。x2和x4对应于同一码字“11”,码1本身是一个奇异码。码2:是非奇异码,不是惟一可译码。当收到一串码符号“01000”时,可将它译成“x4 x3 x1”,也可译为“x4x1x3”, “x1x2x3”或“x1x2x1x1”等,这种码从单个码字来看虽然不是奇异的,单从有限长的码序列来看,它仍然是一个奇异码。码3:虽然是惟一可译码,但它要等到下一个“1”收到后才能确定码字的结束,译码有延时。码4:既是惟一可译码,又没有译码延时。码字中的符号“1”起了逗点的作用,故称为逗点码。,前缀条件码/异前置码/异字头码/逗点码/即时码/非延长码:如果一个码的任何一个码字都不是其它码字的前缀。,唯一可译码的存在条件,码树图码树图: 用码树来描述给定码集各码字的方法。码树图有树根、树枝、节点:一般中间节点(一级节点、二级节点 )用表示, 终端节点用表示。传输m个基本符号信道的码可用。例:二元(进制)码树,x11 x201 x3001,唯一可译码的存在条件/码树图,如果节点过多,也可以用如下方法表示码树图。,唯一可译码的存在条件/码树图,用码树图构造码的方法在树的生长过程中,中间节点生出树枝,各树枝标出相应的码元;为了清晰起见相同码元的树枝方向相同,终端节点表示信源符号; 从树根到终端节点所经过的树枝旁的码元按经过的顺序组成的序列构成码字。用码树图构造即时码的条件如果表示信源符号的终端节点不再延伸,即信源符号都在终端节点上,这样构造的码满足即时码条件。,唯一可译码的存在条件,前提条件:非奇异码唯一可译码存在定理:设n为信源符号或信源符号序列个数,m 为码元个数或进制数,Ki 为信源各符号或信源符号序列对应的码长; 则唯一可译码存在的充分和必要条件是满足Kraft不等式:注意:Kraft不等式是一个存在定理,不是唯一可译码的判定定理。如果n 、m、Ki 满足该不等式, 则存在唯一可译码如果是唯一可译码, 则n 、m、Ki 必定满足该不等式。,唯一可译码的存在条件,例:设二进制码树中Xx1,x2,x3,x4,K1=1,K2=2,K3=2,K4=3,应用上述判断定理,可得,因此,不存在满足这种Ki的唯一可译码,用树码进行检查如图所示。,唯一可译码的存在条件,信息率若信源输出符号序列长度L1变换成由KL个符号组成的码序列/码字变换要求:能够无失真或无差错地从Y恢复X,同时传送Y时所需要的信息率最小。,唯一可译码的存在条件/信息率,Yk有m种可能值,能编成的码字个数所以平均每个符号输出的最大信息量为logm,KL长码字最大信息量为KLlogm。用该码字表示长度为L的信源序列,则送出一个信源符号所需要的信息率平均为,所谓信息率最小,就是找到一种编码方式使KLlogm/L最小。,几个问题:信息率最小为多少时,才能无失真译码?若小于这个信息率是否还能无失真译码?,3.2 定长编码定理,3.2.1 平均码长和编码有效性3.2.2 定长编码定理,平均码长和编码有效性,平均码长单符号信源空间,其中信源符号 xi 对应的码字为Yi (i = 1, 2, , n),码字Yi 对应的码长为 Ki(i = 1, 2, , n ) 。所有的Ki相等为定长码,记为K, 不相等时为变长码。单符号对应变长码的平均码长,码符/信源符号,平均码长和编码有效性/平均码长,符号序列信源空间XL其中XL是X的L次扩展。信源符号序列 对应的码字为Yi (i = 1, 2, , nL),码字Yi 对应的码长为 Ki(i = 1, 2, , nL) 。符号序列对应变长码的平均码长,码符/信源符号序列,码符/信源符号,平均码长和编码有效性/编码效率,编码效率(码率)定义:平均一个码符所携带的平均信息量称为编码效率,记作;,平均码长和编码有效性,例:信源空间 H(X) = - ( 1/2 log1/2+1/4 log1/4+1/8 log1/8+1/8 log1/8 ) =1.75 bit/消息信源符号个数为n=4,二元码符0 , 1, 码符个数为m=2,Ki为信源各符号对应的码字长, 且满足Kraft不等式。 定长码: K1= K2= K3= K4=2 2-2+2-2+2-2+2-2=1 码字: Y1=00 , Y2=01 , Y3=10 , Y4=11编码效率= H(X)/K=1.75 2 = 0.825,平均码长和编码有效性/举例,变长码: K1=1, K2=2, K3=3, K4=3 满足不等式:2-1+2-2+2-3+2-3=1 码字: Y1=0 , Y2=10 , Y3=110 , Y4=111方案1 : x10,x210,x3110,x4111 =11/2+21/4+31/8+31/8=1.75 码符/信源符号= 1.75 1.75 = 1方案2 : x1111,x2110,x310,x40 = 31/2+31/4+21/8+11/8 =2.625 码符/信源符号= 1.75 2.625 = 0.667,平均码长和编码有效性,讨论1:为什么定长码的编码效率小于1,而变长码的编码效率能达到1?原因:因为H(X)=1.75,是个小数,而定长码的码长不可能为小数,所以编码效率小于1。除非H(X)为整数。但变长码的平均码长可以为小数,可能等于H(X)。,平均码长和编码有效性,讨论2:编码后码字集合确定,符号对应的码字长度不同,为什么编码效率不同?原因:不同符号的先验概率不同,对应的码字长度不同,计算出的平均码长也不同,编码效率也就不同。总结:一般情况下,变长编码的编码效率可能达到1;对于变长编码,若概率大的符号对应短码,概率小的符号对应长码,编码效率越高;反之越低。这也是后面最佳编码的思路。,定长编码定理,定理:由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1X2XlXL,可用KL个符号(每个符号有m种可能值)进行定长编码。对任意0,0,只要 则当L足够大时,必可使译码差错小于;反之,当 时,译码差错一定是有限值,而当L足够大时,译码几乎必定出错。,定长编码定理,定理中的公式改写成表明:不等式左边表示长为KL的码字能载荷的最大信息量,右边代表长为L的信源序列平均携带的信息量。所以定长编码定理告诉我们:只要码字传输的信息量大于信源携带的信息量,总可实现几乎无失真编码。,定长编码定理,信源熵HL(X)就是一个界限/临界值。当编码器输出的信息率超过这个临界值时,就能无失真译码,否则就不行。信源编码定理从理论上说明了编码效率接近于1,即 的理想编码器的存在性,代价是在实际编码时取无限长的信源符号(L)进行统一编码。只要足够小,就可实现几乎无失真译码;若足够小,编码效率就接近于1。说明:定长编码定理是在平稳无记忆离散信源的条件下论证的,但它同样适用于平稳有记忆信源,只是要求有记忆信源的极限熵和极限方差存在即可。对于平稳有记忆信源,定理中的熵应改为极限熵。,定长编码定理,定长编码 L 计算随机变量I(xi);I(xi)的数学期望M I(xi) ,即H(X) ;I(xi)的方差 2(X);符号序列长度L;已知编码效率和译码错误概率。,定长编码定理,例:设单符号信源模型为信源熵为:H(X)=2.55(比特/符号)自信息方差为:2(x)=1.323若要求编码效率为90%,即译码差错率为=10-6,则由此可见:在差错率和效率要求都不苛刻的情况下,就必须有1600多万个信源符号一起编码,技术实现非常困难。,3.3 变长编码定理,变长编码定理,单个符号变长编码定理:若一离散无记忆信源的符号熵为H(X),每个信源符号用m进制码元进行变长编码,一定存在一种无失真编码方法,其码字平均长度K满足下列不等式,变长编码定理/单符号,证明:若 xi 按如下不等式取所对应码字的码长为Ki ,若 为整数 , 则上述不等式左边取等号。 故可得:,变长编码定理/单符号,所有码字长度满足Kraft不等式。,如何降低平均码长:1、减少信源熵H(X)2、增加信道码元数m,变长编码定理,离散平稳无记忆序列变长编码定理:对于平均符号熵为HL(X)的离散平稳无记忆信源,必存在一种无失真编码方法,使平均信息率K满足不等式:证明:信源 X 的 L 次扩展信源XLXL 的信源熵为H(XL) bit/L个信源符号XL 所对应码字的码长 码符/L个信源符号,变长编码定理/证明,编码效率的下界:,码的剩余度:,变长编码定理/举例,例:设单符号信源模型为其信息熵为:H(X)=2.55(比特/符号)这里m=2,log2m=1要求90%,则,结论:与定长编码相比,对同一信源,要求编码效率都达到90%时,变长编码只需L=4进行编码,而等长码则要求L大于1.6875107。用变长编码时,L不需要很大就可以达到相当高的编码效率而且可实现无失真编码。,变长编码定理/举例,例:设离散无记忆信源的概率空间为其信源熵为L=1定长码:x10,x21,则K=1 编码效率:=H(X)/K = 0.811L=2XL x1x1 x1x2 x2x1 x2x2 p(XL) 9/16 3/16 3/16 1/16H(XL)=1.622 bit/2个符号,变长编码定理/举例,定长码 XL 00 01 10 11KL = 2码符/2个信源符号编码效率:= H(XL)/KL =H(X)/K = 0.811变长码 Y 0 10 110 111 Ki 1 2 3 3 = 1 9/16+2 3/16 + 3 3/16 +3 1/16 = 27/16 = 1.6875 码符/ 2个信源符号编码效率:=H(X)/K = 0.81132/27=0.961 当 L=3 =0.985 L=4 =0.991,采用扩展信源提高编码效率带来的问题: 1.码表迅速扩大;2.需求内存大;3.译码延时。,变长编码定理,信息传输效率平均信息率R:平均每个码元所含有的信息量。单位: bit/码元码元传输率/码元速率(RB) : 每秒钟传输码元的数目。单位: 波特(B) 码元时间长度(TB) : TB= 1/RB单位: 秒(s) 平均信息传输率(Rt):平均每秒钟传输的信息量。 单位: bit/sRt = R / TB,3.4 最佳编码,3.4.1 香农编码3.4.2 费诺编码3.4.3 哈夫曼编码,最佳编码,最佳码:能载荷一定信息量, 且码字的平均码长最短, 可分离的码字集合。编码思路:对概率大的信息符号编以短码;对概率小的信息符号编以长码。目的:使平均码字长度最短。这种编码方法称为统计编码/熵编码/概率匹配编码。,最佳编码,香农编码若单个字符xi按如下不等式取所对应码字的码长为Ki当m=2时, log2m =1,则,香农编码,编码方法: (1)将信源符号消息按其出现概率的大小依次排序。 p(x1) p(x2) p(xn)(2)按如下不等式取所对应码字的码长为Ki。(3)计算第个 i 消息的累加概率, 以便获得唯一可译码;(4)将累加概率变换为二进制数;(5)取二进制数的小数点后 Ki 位作为符号消息的二进制码字。,香农编码/举例,例:xi x1 x2 x3 x4 x5 x6 x7 p(xi) 0.20 0.19 0.18 0.17 0.15 0.10 0.01编码过程,香农编码/举例,信源熵:H(X) = 2.61 bit/符号平均码长编码效率,费诺编码,编码方法: (1)将信源符号消息按其出现概率的大小依次排列。p(x1) p(x2) p(xn)(2)将依次排列的信源符号按其概率分为两大组 , 使两个组的概率之和近似相等 , 并对各组赋予一个码元0和1。(3)按(2)方法将每一大组再分为两组 , 各组再赋予一个码元0和1。 (4)如此重复 , 直至每个组只剩一个信源符号为止。(5)信源符号所对应的码字即为Fano 码,费诺编码/举例,例:xi x1 x2 x3 x4 x5 x6 x7 p(xi) 0.20 0.19 0.18 0.17 0.15 0.10 0.01编码过程,费诺编码/举例,信源熵:H(X) = 2.61 bit/符号平均码长编码效率,哈夫曼编码,编码方法:(1)将信源符号消息按其出现概率的大小依次排序。p(x1) p(x2) p(xn)(2)取两个概率最小的符号分别配以0和1 , 并将这两个概率相加作为新字母的概率,与未分配的字母重新

温馨提示

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

评论

0/150

提交评论