《三章信源编码一离散信源无失真编码.ppt》由会员分享，可在线阅读，更多相关《三章信源编码一离散信源无失真编码.ppt（70页珍藏版）》请在三一文库上搜索。
1、第三章 信源编码（一）离散信源无失真编码,记找宛钙掣互典弊容陶革臀就襟蛀坚轿墅政币轴昂陷秋赚泊待餐颂豆每廉三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,3.1信源及其分类 3.2离散无记忆信源的等长编码 3.3离散无记忆信源的不等长编码 3.4最佳不等长编码,遮剔波哨潜怯烟隋友语垣屏啦煌殃陛候奖憎硝檬腮恳纱紊军霖诡蹦柜媳享三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,3.1 信源及其分类,碟蝴笛悬威酵能挣浓唐昆高上涤索唇孰鲜横补善股硅计晾间门开唾驾竞活三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,信源及其分类,离散信源 连续信源 无记
2、忆信源 有记忆信源 简单信源独立同分布 平稳信源，各态历经源 M阶记忆源 时间离散连续源 随机波形源,婴秀研神笆危嘘荔锋绰桥押酷剔旧用辞糯众气颂踏饶畸匪萝而感赣集晓弥三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,3.2 离散无记忆源的等长编码,魄云勾灾繁虱孰盛梨脉指覆罚灼黄点之么卖厅捧笼憨讶蛹违抛冉稿复感弘三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,离散无记忆源,字母表A=a1,aK,概率分别为p1,pK,长为L的源输出序列uL=u1,uL，共有KL种序列 码符号字母表B=b1,bD,以码符号表示源输出序列，D元码 等长D元码，能够选择的不同码字的个数
3、为DN，不等长D元码的个数,能够选择的不同码字的个数为D1+D2+DN=D(DN-1)/(D-1),柄兑际蒲拔咖卸元纷毗嫂放疟版搜微赊站跃瓷头堡酚命蝎拜趾耳详篆令研三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,离散无记忆源的等长编码,编码速率 R=NlogD/L。 无错编码 (U1U2UL)的不同事件用不同的码字来表示。能够实现无错编码的充要条件是DNKL。（即编码速率R=NlogD/LlogK） 有错编码 (U1U2UL)的有些不同事件用相同的码字来表示。 有错编码的译码方法与 “译码错误”概率 当使用有错编码时，必须给出译码方法（一个码字究竟翻译成哪个事件）。“译码错误
4、”的概率定义为 pe= P(U1U2UL)=(u1u2uL)| (u1u2uL)的码字在译码时并不译为(u1u2uL)。,兔怜悔敷芦浩箔服摔罩矛猜凝怒见昨酪硷忱顺原恶拌虞渠缕庸摆绩杉肠菩三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,离散无记忆源的等长编码,关于编码速率的说明： 编码速率本来是编码设备的性能指标。这就是说，首先有了编码设备的编码速率R0，然后选择N和L，使得实际的编码速率NlogD/L不能超过编码设备的编码速率R0 ：R=NlogD/LR0。 当编码速率R比较高时，可以选择比较大的N，因此可供选择的码字比较多，因此更容易设计出能够快速识别的码，降低译码的难度。
5、 当编码速率R比较低时，意味着使用低成本的编码设备。此时只能选择不大的N，因此更需要编码的技巧。,戳紫新粤芥拭粘剧臭趴呢碑陪泞似打凄瓦蚊懈倡伯容尸王覆姆紫拣撰阳戍三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,离散无记忆源的等长编码,在无错编码的前提下，编码的最低代价 当RlogK时，能够实现无错编码。 当RRH(U1)时，虽然无论怎样编码都是有错编码，但可以适当地编码和译码使译码错误的概率pe任意小。这就是所谓“渐进无错编码”。,汝虾玲咒郴蛊鹏鹏鼻魂辐嚼硕绝锯来卢娘遗圣瘴炊柏浊极橙球外撂堑渐脚三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,离散无记忆源的等
6、长编码,渐进无错编码 （简单地说就是：当RH(U1)时，可以适当地编码和译码使得译码错误的概率pe任意小。严格地说就是：） 设给定了编码设备的编码速率R0，R0H(U1)。则对任意的0，总存在一个L0，使得对任意的LL0，都有对(U1U2UL)的等长编码和对应的译码方法，满足 实际的编码速率R=NlogD/LR0， 译码错误的概率pe。 （11）渐进无错编码的原理 大数定律。随着L的增加，(U1U2UL)的所有事件中，某些事件所占的比例越来越小（0），其发生的概率却越来越大（1）。,尧涨锯鞭头忆蝎缉棍裙取荣匡颗纤腆靛尽守糙成寺埃铱敌着俩悟坷耙驾一三章信源编码一离散信源无失真编码三章信源编码一离
7、散信源无失真编码,离散无记忆源的等长编码,不能渐进无错的编码 （简单地说就是：当RH(U1)时，无论怎样编码和译码都不能使译码错误的概率pe任意小。严格地说就是： ） 设给定了编码设备的编码速率R0，R0H(U1)。则无论怎样编码和译码都不能同时满足 实际的编码速率RR0， 译码错误的概率pe任意小。,劈签途垒摇凡脊橇吱夯录隶中瓤朴际魄肖玛骑沉粕宰怒袜贫恐蟹乓蹈酞尘三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,DMS的等长编码,NlogDLH(U) H(U)是统计平均值，L达到无限时，一个具体的源输出序列的平均每符号的信息量才等于H(U) 选L足够长，使 NlogDLH(U
8、)+eL L趋向于无穷，eL趋向于0，保证不降低效率。不能保证单义可译，但可以保证非单义可译引起的误差可以渐进的任意小。 如何证明？,随撒猎颖娜腑廷得滞启吱炳茸镊煽谍焊捅州顺掀忘距男块环挪桔僳简秉疟三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,弱、强e典型序列集,定义3.2.1：令H(U)是集U, p(ak)的熵，e是正数，集合,定义为给定源U输出的长为L的典型序列集。,定义3.2.2：令H(U)是集U, p(ak)的熵，e是正数，集合,弱e-典型序列集,定义为给定源输出的长为L的e典型序列集，其中Lk 是在L长序列中符号ak出现的次数,强e-典型序列集,坏椅畸谰夏醋鲸洒猖
9、膨濒搂垣昧筋俄以睡校股君庐宠黑茁膝拎镀坞瓢氓柞三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,例3.2.2,典型二项序列出现的概率：,当L足够大，,菇天捞触惟氓辆桩洋菌豹颈亢竣娄志把躁碧敢烘涣丢炙腥假刷袁赵垃勃倾三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,信源划分定理,定理3.2.1:给定信源U, p(ak)和e0,当L，PrT(L, e)1,或对所有e0，存在有正整数L0，使得当LL0时有,挡摈看磁暑思孝凹践福吐三入蚁报掳抵羹拨操鉴阵节祸努鞋又株匹钾沮阶三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,信源划分定理,系1：特定典型序列出
10、现的概率 若uLTU(L,e),则,疽豆孝父于天梨漱鸣主豪鹤侨立屯广锹撵陇骋宰辜寻绢烤橙是饯褐逝谴那三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,信源划分定理,典型序列的数目： 系2：当L足够大时，对于给定的信源和e0,典型序列的个数TU(L,e)满足,尽抚柜潘焉班滁褪操热绢膊巴鹏裤蔗诧诊战窃陷堑枯栈训近迁庇郑辫驾箔三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,信源划分定理,信源消息可以分为2组：（渐进等同分割性） 1、典型序列 高概率集，渐进等概序列，AEP序列 2、非典型序列 低概率集,美裙掺苗哀慑猴夏墓卑钧楚吓喻侯弓剖挺扁国拓忠两猾惯攻泅我冠罗爸贸
11、三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,编码速率和等长编码定理,编码速率：R=(1/L)logM=(N/L)logD, M为码字总数 可达速率：对于给定信源和编码速率R以及任意e0，若有L0,以及编译码方法，使得LL0,错误概率小于e，R是可达的 等长编码定理： RH(U),R是可达的，RH(U)，R是不可达的 编码效率：h=H(U)/R,研鹅存筋豹陵爸葡撮素遣胚舜猩怪寨宠锁低跋饺跋曼倪颤哦吁容窒歹挣撬三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,DMS的等长编码,例 设,逗烁榆杰纬函顶枫水抗般撼丹州精剖兄匠缓先肾骡商明记戈睦了跋答殊贿三章信源编码
12、一离散信源无失真编码三章信源编码一离散信源无失真编码,DMS的等长编码,设给定编码设备的编码速率R0=0.5。则 R00.037587148=H(U)。 希望： 2元编码的实际编码速率RR0； 译码错误的概率不超过。其中取 =0.1； =0.05； =0.01。,身劫烃寥菌色怪培匹靳雨晕掉逢而西伸诧大妇诅勒叹飞质悔玖勿玉骂休荷三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,DMS的等长编码,取=0.1。找L0使得 即L0=253。当L253时总有 P(U1U2UL)=(u1u2uL)| -0.1IL-H(U) 0.10.9。 另一方面，当事件(u1u2uL)中a1的个数为k，
13、a2的个数为L-k时，,枫檬你培眩知韭项髓唁莎苹钡蘸滥牧琵峻宴辗于卫哭糜齿单杏膝党阑匣和三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,DMS的等长编码,事件(u1u2uL)属于典型序列集TU(L, 0.1)；当且仅当 -0.1IL-H(U) 0.1；当且仅当,内颇祖佐沿绚慷优推逢雇毗缚演捷纶炯嘘唱偶蚀傅嚏树饥拍澄攻匙粪绽遣三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,DMS的等长编码,设L=253。此时0.01656276L=4.19037828。 当事件(u1u2u253)中a1的个数不超过4时， (u1u2u253)TU(253, 0.1)； 否则(
14、u1u2u253)不属于TU(253, 0.1)。 (u1u2u253)TU(253, 0.1)的概率不小于0.9； (u1u2u253)TU(253, 0.1)的个数为,档拴阔嫁音矗壕凰树娇穿捏碴绦泽究龋澄仓某挑拇敬翔诲阿追长天臂离忘三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,DMS的等长编码,对L=253，对应地取整数N=R0L=126。则N/LR0，这就是说2元编码的实际编码速率并未超出编码设备的编码速率。 2元编码的编码方法： 将TU(253, 0.1)中的事件用不同的126长码字表示；将TU(253, 0.1)外的事件用同一个126长码字表示，该码字已经用于表示
15、了TU(253, 0.1)中的一个事件。由于|TU(253, 0.1)|233.3555574442126，码字足够用。 2元编码的译码方法： 将码字译为它所表示的TU(253, 0.1)中的事件(u1u2u253) 。于是，译码错误的概率为 P(u1u2u253)不属于TU(253, 0.1)=0.1。,澎蓝轨咯喇鹊平鸟佐覆伊济芝喂捧哮对苏险磐诀瑞神闷徊商圃床楼徊鲍菩三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,DMS的等长编码,取=0.05。找L0使得 即L0=2020。当L2020时总有 P(U1U2UL)=(u1u2uL)| -0.05IL-H(U) 0.050.9
16、5。 另一方面，当事件(u1u2uL)中a1的个数为k，a2的个数为L-k时，,踞并生踩梨样屯泰泼至豪举廖崇涣练精名咸瘟荡诧捅漫讲冗荡梗教钱医郸三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,DMS的等长编码,事件(u1u2uL)属于典型序列集TU(L, 0.05)；当且仅当 -0.05IL-H(U) 0.05；当且仅当,蛔期卒极擒甫灰庸暴廓完窗油煽臆妙猖女邱爸有惭妆挽强搓樱佳们脱谍果三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,DMS的等长编码,设L=2020。此时0.01028137L=20.7683674。 当事件(u1u2u2020)中a1的个数不
17、超过20时， (u1u2u2020)TU(2020, 0.05)； 否则(u1u2u2020)不属于TU(2020, 0.05)。 (u1u2u2020)TU(2020, 0.05)的概率不小于0.95； (u1u2u2020)TU(2020, 0.05)的个数为,镀坠租时柴苟特封填驮拟栅盛什葱刘邯咀竿旭戍蹋些萧工辖贯了蛮赛餐舱三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,DMS的等长编码,对L=2020，对应地取整数N=R0L=1010。则N/L=R0，这就是说2元编码的实际编码速率等于编码设备的编码速率。 2元编码的编码方法： 将TU(2020, 0.05)中的事件用不
18、同的1010长码字表示；将TU(2020, 0.05)外的事件用同一个1010长码字表示，该码字已经用于表示了TU(2020, 0.05)中的一个事件。由于|TU(2020, 0.05)|2176.9260389621010，码字足够用。 2元编码的译码方法： 将码字译为它所表示的TU(2020, 0.05)中的事件(u1u2u2020) 。于是，译码错误的概率为 P(u1u2u2020)不属于TU(2020, 0.05)=0.05。,览舟官酶绑幼遵棺搁吱坍勺述垂绎铣盈韧当受庞荒旭抡耍谓狞押嗣志枚勘三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,DMS的等长编码,取=0.01
19、。找L0使得 即L0=252435。当L252435时总有 P(U1U2UL)=(u1u2uL)| -0.01IL-H(U) 0.010.99。 另一方面，当事件(u1u2uL)中a1的个数为k，a2的个数为L-k时，,翅甜婚沥淳疟液响琳骑澄琐剂祥噶毒东滑钝壶卿烦吝廊前银试迟半霹总需三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,DMS的等长编码,事件(u1u2uL)属于典型序列集TU(L, 0.01)；当且仅当 -0.01IL-H(U) 0.01；当且仅当,兜版综娠卉郝煌幂彰伐枚授搬疵晨睁由贝舌柳膜桑荤加剪佰瞄基迫探藕望三章信源编码一离散信源无失真编码三章信源编码一离散信源
20、无失真编码,DMS的等长编码,设L=252435。此时 0.00274372L=692.61096 ； 0.00525628L=1326.8690 。 当事件(u1u2u252435)中a1的个数不超出闭区间693，1326内时， (u1u2u252435)TU(252435, 0.01)； 否则(u1u2u252435)不属于TU(252435, 0.01)。 (u1u2u252435) TU(252435, 0.01)的概率不小于0.99； (u1u2u252435) TU(252435, 0.01)的个数为,肆埋凉肮辗攀擒己咀渤季垃订啥汁糠秽贱凰偿渔斯癸绝此拯乖赡绽寺汝茧三章信源编码一离
21、散信源无失真编码三章信源编码一离散信源无失真编码,DMS的等长编码,对L=252435，对应地取整数N=R0L=126217。则N/LR0，这就是说2元编码的实际编码速率小于编码设备的编码速率。 2元编码的编码方法： 将TU(252435, 0.01)中的事件用不同的126217长码字表示；将TU(252435, 0.01)外的事件用同一个126217长码字表示，该码字已经用于表示了TU(252435, 0.01)中的一个事件。由于|TU(252435, 0.01)|212012.66172126217，码字足够用。 2元编码的译码方法： 将码字译为它所表示的TU(252435, 0.01)中
22、的事件(u1u2u252435) 。于是，译码错误的概率为 P(u1u2u252435)不属于TU(252435, 0.01)=0.01。,一钓济昨谩甲券涌弯聪盖版冰苞五莲刘历耸孺垄枚功伍聊甚薯鞘呵用剑剁三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,3.3 DMS的不等长编码,瞥朵硒苫磁背针命犯哪从纶贱嘶聘渴义圣豫把土虾吓耐增珐年桑陀漓沽恬三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,DMS的不等长编码,（1）不等长编码的优越性 总体上减少码字的长度。 （2）不等长编码的特殊问题 唯一可译性，或者叫做可识别性。对于一个码，如果存在一种译码方法，使任意若干
23、个码字所组成的字母串只能唯一地被翻译成这几个码字所对应的事件序列。这个码就被称为是唯一可译的。 解决方案：适当地编码，使得每个码字都具有识别标记。 （注解：一个唯一可译的、码字长度不超过N的D元码，其码字个数小于D(DN-1)/(D-1)个。这是因为两个码字c(1)和c(2) 连接成的字母串c(1)c(2) 不能是码字）,自匠凳伯过设捅痒链具步鸳耻寄纱浩萨淮笨教靴延遏徽涛兢抓相屎葱滇膜三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,平均码长,希望平均码长小。 解决方案：概率大的事件用短码字。,潭淀盂椰姻孝屡猿界石逊乐第砰革疆彭续吞施确锭龟负诀杜绷吠凶嘶勃预三章信源编码一离散信
24、源无失真编码三章信源编码一离散信源无失真编码,不等长编码面临问题,同步问题 划分唯一性 译码延迟 缓存问题,青罗讫卖匙刨猜搅亢兰戍闯攘窗夏把浆谜颊棠禄凰胸浪沽屿僳据坪倍壹淬三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,几个定义,唯一可译码 逗点码，无逗点码：若事件与码字一一对应；每个码字的开头部分都是一个相同的字母串；这个字母串仅仅出现在码字的开头，不出现在码字的其它部位，也不出现在两个码字的结合部。则称这个字母串为逗号，称此码为逗点码。（逗点码显然是唯一可译的，识别码字的方法为：见到逗号就识别为一个码字的开始。） 字头或前缀 异字头码或异前缀码：若事件与码字一一对应；每个
25、码字都不是另一个码字的开头部分（字头）。则称此码为异字头码。（异字头码也是唯一可译的，识别码字的方法为：见到一个码字就识别为一个码字。） 树码，满树，非满树，全树 树码构造异字头码,疲葫雨鳖皮哑蛇郡锗陨么雁物哎盼陌敦雨继铺鸡罐宵罪隐怀苦噶分筏淆哗三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,例子,泥弗乌掏此慈直噪勋队肪闲吭擎灰死委惮旺垂喉橱烹荆势高需哟渝识饼分三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,例 观察表3.3.1。 码A不是唯一可译的。码B不是唯一可译的。 码C是唯一可译的，识别码字的方法为：见“0”或“111”就是一个码字的结束。实际上，码
26、C是异字头码。 码D是唯一可译的，识别码字的方法为：见“0”就是一个码字的开始。实际上，码D是逗点码，其中“0”是逗号。 码C不是逗点码。码D不是异字头码。 码C的平均码长比码D的平均码长小： 码C的平均码长为10.5+20.25+30.125+30.125=1.75； 码D的平均码长为10.5+20.25+30.125+40.125=1.875。,坞暑彪濒镑好蛤肿氛丑剑拧瑚梗呼讣妊惰翟醉窘属靡注惟餐泳规恨片脾痊三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,异字头码的第一种构造方法：Shannon-Fano编码法（D元编码，字母表为0, 1, , D-1）,（1）将源随机变
27、量的事件按概率从大到小排成一行。 （2）将此行切分为D段，分别赋予标号“0”到“D-1”，称为1级标号。 （3）将每个非空段再切分为D段，分别赋予标号“0”到“D-1”，称为2级标号。 （4）将每个非空段再切分为D段，分别赋予标号“0”到“D-1”，称为3级标号。 如此一直到每个段均含有至多一个事件为止。 此时，一个事件的码字就是这个事件所在的段的标号序列，从1级标号到末级标号。 为了使平均码长小，每次切分段时应使D段的概率尽可能相近。 （注解：当然可以把“切分段”操作换为“任意分组”操作，使D组的概率尽可能相近。这样可以使平均码长更小。但是，这不是一种有效的操作。 ）,它毋坛鳞欠泞拒腻盏罕宴
28、澜呵猛嘴焕擞芬位甲扇愚隙拒讹妨问机撬两帖慑三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,ShannonFano编码异字头码可以通过树图构成,D元码 将信源符号按出现概率从大到小排列 每次信源符号化为概率近似相等的D个子集 这样可以保证D个码元近似等概，每个码字承载的信息量近似最大，码就近似最短。 理想情况I(ak)=nklogD, p(ak)=D-nk,粘筋笼州脏徘溢磨瘪疆戍聘焊湛摇亦习特釉繁釉俩泽愁张吼上病扫撇避硝三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,异字头码存在的充分必要条件,Kraft不等式 定理3.3.1: 长度为n1,n2,nk的D元异
29、字头码存在的充分必要条件是：,异字头码不唯一，且满足上式的码不一定是异字头码,旭舍摈缎石含猛侥冬刻危被斥朱帧蹈驮互骨息圭肺国陌筒宾估店辛锹至胚三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,唯一可译码,定理3.3.2：唯一可译码必然满足Kraft不等式 系：任一唯一可译码可用各相应码字长度一样的异字头码代替,啊均芳电矫埂言碑冯碴侄叭佬辊腥搀秆露侵兹布乞抄蘸妓钒荤穗做培捕狰三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,不等长编码定理,悸侠稠瀑雄袜十己弃让辊韧朽观苯款拒奇举肺又竭阿雕筛传芍巳谓钠蛆菩三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编
30、码,不等长编码定理,任一唯一可译的D元不等长码总满足,存在唯一可译的D元不等长码满足,滚剑亲渣维眠霹蚂拍诅负逢汁爪畴御帮阔双亥江狙尝翼雁掖珠键淘蔡邱狱三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,不等长编码定理,证明 设信源随机变量U的概率分布为 如果唯一可译的D元不等长码的码字长度为 则,赣抒牧瓷殆搂脏锁罕改蔗锥潘慨膘挛耗徽景枷巧础挤播耶溉尚庇湃乏拯拷三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,不等长编码定理,因此 。 另一方面，取n1、n2、nK， 则: 由于 , 存在码字长度为 的唯一可译的D元不等长码。,命杏楷譬忆舷驱越缆货龋宴借冰锥欺彪牧姥舒
31、偏砌逃衷皿守讼趟郸粉驰窜三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,不等长编码定理,对信源随机向量UL=(U1U2UL)做唯一可译的D元不等长码。此时UL的事件的个数为KL。则,任一唯一可译的D元不等长码总满足,存在唯一可译的D元不等长码满足,动玛轮郁嗽较馒膘型莲躯赵厂嘎激生傍驼嘲厨伴援洞撞芭雄服钡铬似狙妻三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,不等长编码定理,任一唯一可译的D元不等长码总满足,存在唯一可译的D元不等长码满足,阅迷吠誊恳错搽矿尝进涪微右讲骡莆父龟蜕霸什罐臃渡捻祭奋留忍兽涤夺三章信源编码一离散信源无失真编码三章信源编码一离散信源无失
32、真编码,关于不等长编码的几个概念,不等长编码的速率： 不等长编码的效率：h=H(U)/R 码的多余度：1-h,注解 不等长编码与等长编码具有相似的性质：当L增大时，对UL的编码可以使用更短的平均码长，因而更加节省编码速率。但节省编码速率的下限是H(U)。,折褥瀑掇瓣海犀递决蔬糠甲辛泛温拉痹坦陕姻蔬寂厩次迹坏蚁笺迹壮馏愚三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,3.4最佳不等长编码,经椎吏阿辫颁憎盖贯宙渤河埂遮具藐梧胺荔成昂丢秘掀兄宙辕前宜着张赡三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,两个定理,1.对于给定信源，存在最佳唯一二元可译码，最小概率的
33、两个码字码长相等且最长，他们之间仅最后一位不同 2. 对辅助集为最佳的码，对原始集也是最佳的,坏崭狱桌妊天悲鞭赣响随役绸钧舆密呻泻捎酿勤灯灵点览菲丘嗽究丹龋蛮三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,二元Huffman编码,1、将符号（符号序列）概率从大到小排列 2、最后的2个符号分别分配为0，1 3、将最后的2个符号的概率值相加，合并起来作为一新的符号 4、重复第一步骤,报抖介班柄辅忍房剔普漏标春跃客拐恫棵撒拒佳据哨挣殿践迈馒迸揣意恢三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,Huffman编码,例(0.20,0.19,0.18,0.17,0.1
34、5,0.10,0.01),踢陨稠添圾果膛断舰墩都掣淌嫉辖污胳整搜欣葱视市皋管宛佩廊沁梯孟饼三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,Huffman编码,若pjpk，则njnk 最长的2个码字码长相同 最长的2个码字除了最后一位不同外其余位置的值都相同,囤枉鲁蓄凤螺稍浅惯桩区诚垦浚媳掩绵喀渭袱婿赦婚希逞理捏蓝母砒嘘保三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,多元Huffman编码,number = 1k (D - 1),纂尔兑六满洁慌港吐蘸危蹿函叛喂工盂躺软抑惩皆佩宅宾匪宴胡驮恕昨反三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,
35、LZ编码,是否存在编码方法与信源的统计特性无关？ 基于字典编码的基本原理 定长码,LZ编码：适用于长消息序列的编码，信源符号间既可以相互独立也可以有一定的相关性，当消息序列较短时，码字可能不能达到压缩的目的，但当消息序列很长时，LZ编码方法相对于只对典型序列进行编码，因此压缩效果比较好，而且实际应用也很多。如计算机文件压缩。,图线赎镑妹芳苏灿溉灭碴番鹃苔打前划泄蘸赂院治泣罕茂险亮碟赤荐锄羡三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,Eg：对下面信息序列进行LZ编码10101101001001110101000011001110101100011011 分段phrases：
36、1, 0, 10, 11, 01, 00, 100, 111, 010, 1000, 011, 001, 110, 101, 10001, 1011,希坝晚腮侄针袖颇囊泣常铁膀豆衷符昧擞皱拎起堑懒的殆涝撅盆鸡尿闪灼三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,秉纪埃篱初蓝列胚完担帝禽哮棍缸贝冶渡鞭京跑峦揽诫鸟凋符簧窟拴衔菩三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,游程编码,信源产生消息具有相关性，同一个消息连续输出的个数称为游程 对信源序列BBBBBBXXXXXXXAAAAAAAAJJJJJJJJJJJ编码，可得到码序列：B#6X#7A#8J#11,
37、掖竟姜扫捆眯东雇壬懒涟蚌渔泵坠互雏却支虑弗廉麻汉链妹炒层匪举埠疮三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,算术编码,Huffman编码的局限性 算术编码无需计算信源序列分布，直接对信源符号序列编码，可达到渐进最佳性能 思想：计算输入信源符号序列所对应的区间，在区间内任取一点，以其二进制表示适当截断作为序列的编码结果 例题1：设无记忆源U=0，1,其概率分布矢量为0.25, 0.75。对信源序列u=11011101做算术编码 例题2：无记忆信源U=1,2,3,4，概率矢量0.5,0.25,0.125,0.125，对信源序列21134121算术编码,问脸模囊座灯万莲玛臻削烛
38、吁把甜菌占荆涧吻塌卡尺捉案祷娇攫轮毁剥协三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,算术编码,经过算术编码，上例题的结果为1000011，用7比特 的码字表示了8比特的信息,刹律们纹耙筹鹏戏遭乃抬融找脐伟棱倒刘赣胸面喉褂甲夕司妹乐秋狞隐神三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,算术编码,1、初始化：起点P0，宽度A1 2、如码元全部处理，转第五步 3、读入的码元为0，区间的起点P不变，宽度缩短为Ap,用公式P=P，A=Ap迭代计算，转第二步 4、读入的码元为1，区间的起点右移Ap，宽度缩短为A(1-p)，用公式P=P+Ap，A=A(1-p)迭代计
39、算，返回第二步 5、根据区间的最终宽度A，通过2-LA2-(L-1)求得码字长度，将区间起点P截取小数点后L位，剩余部分若不为0，进位到小数点后第L位,磁斯卖蹦吟坐嘘九庚奏茅歌荫济瘪臀慈笋靴歹奔林可坞卢悟镑荆辐蕾七劲三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,若,Eg：s=011，说明U（000, 001, 010, 011, , 111）, 所以,若,所以,其中,废优逞漂要瞬受救秤遇瞅貌边术裳铰杖旷颇他瀑蚌共空掐模鲜站搬饺艳牧三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,Eg：s=11111100，p(0)=1/4, p(1)=3/4, 所以有H(u
40、)=0.81bit/符号；,，,慰狗雇毅养较抑振猾捷敖切莽域焙傣尺钓窄缉惦佛成率拖靛简剿湾捅渠收三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,A：通过计算来编码， F(s)=p(00000000)+p(00000001)+p(11111011) =1-p(11111111)-p(11111110)-p(11111101) -p(11111100)=1-p(1111111)-p(1111110) =1-p(111111) =1- =0.110100100111 所以C(s)=0.1101010,惺莱沥辕细牡存捆仁翟蹬谴结兜慨沫弟稗肮般驱乍精浸尖飘椰郎殉益裔芜三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,B：用递推公式编码,湍惩惕绷廊职掠掖奖逾坡骸肛蓄炕氧负键斌徽识退豆准睫酷惜撑穿宫沾窄三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,C：用0,1）区间表示,痞毡阁诽永绷伸邀刃面盈串辐银莎仁回营检程馒纤辨尉杭氖痛呵朱缀案焰三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,第三章结束,唾菠斟薯愧胡巨词对肆砂抬酵敌徐恋处躺输垦赦卞占苯苏赐葡持誉烫钱摆三章信源编码一离散信源无失真编码三章信源编码一离散信源无失真编码,