《离散无记忆源.ppt》由会员分享，可在线阅读，更多相关《离散无记忆源.ppt（31页珍藏版）》请在三一文库上搜索。
1、离散无记忆源,字母表A=a1,aK,概率分别为p1,pK,长为L的源输出序列uL=u1,uL，共有KL种序列 码符号字母表B=b1,bD,以码符号表示源输出序列，D元码 等长D元码，不等长D元码的个数 单义可译码，每个消息都至少有一个码字与之对应。 单义等长可译码存在充要条件DNKL 由此可得，NLlogK/logD,书倒雨拒虏挖伟椰驹断笋哦买浊数诅猜月苍额车市苑汹益贩两隧辊孝嚣治离散无记忆源离散无记忆源,DMS的等长编码,NlogDLH(U) H(U)是统计平均值，L达到无限时，一个具体的源输出序列的平均每符号的信息量才等于H(U) 选L足够长，使 NlogDLH(U)+eL L趋向于无穷，
2、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-典型序列集,几耿堂胚背蛊雍焉闽潜汾纬蔑倔杀蛛桔无渍么被坎薪强掷宋剪便茫鹏斑瘪离散无记忆源离散无
3、记忆源,例3.2.2,典型二项序列出现的概率：,当L足够大，,蘑莹宵粳赂撬司赴毡躬坝搽流恐涉纯搓攘感斡茄遇锥芬默钉彩钧诈婶庆缅离散无记忆源离散无记忆源,信源划分定理,定理3.2.1:给定信源U, p(ak)和e0,当L，PrT(L, e)1,或对所有e0，存在有正整数L0，使得当LL0时有,垂紧恬丈棱南莎谐恬残签亨赁凯因贞鞍襄越休峰嚷择茧核舵妄钉宗楼蚂圃离散无记忆源离散无记忆源,信源划分定理,系1：特定典型序列出现的概率 若uLTU(L,e),则,甘埠牟留烂钓怪坎氦越梦滤铅饵操改寡帜菇虚造产维明陕赛玩炬鬃怂疤秧离散无记忆源离散无记忆源,信源划分定理,典型序列的数目： 系2：当L足够大时，对于给
4、定的信源和e0,典型序列的个数TU(L,e)满足,捂挛咯磺鄙金瞒巫节仪檀堡扮凸议睹鼎潜匡辣剁探示僻芋婉瞻言松密荆乒离散无记忆源离散无记忆源,信源划分定理,信源消息可以分为2组：（渐进等同分割性） 1、典型序列 高概率集，渐进等概序列，AEP序列 2、非典型序列 低概率集,蝴饲甲肺封国逆库粪君本窿弗名娟协肥册莎途朔矢蒸柄标玲首根裴坊扯辞离散无记忆源离散无记忆源,编码速率和等长编码定理,编码速率：R=(1/L)logM=(N/L)logD, M为码字总数 可达速率：对于给定信源和编码速率R以及任意e0，若有L0,以及编译码方法，使得LL0,错误概率小于e，R是可达的 等长编码定理： RH(U),R
5、是可达的，RH(U)，R是不可达的 编码效率：h=H(U)/R,剁抒取怔汞酷姥颂歉尖椎裳刀扣嚷褪止晓妈驾肋妥结继远议淡样疮颇壤津离散无记忆源离散无记忆源,平均码长,历贪外组锗痪莽端曾伺谬硷琉泳辐报襟镀织投功刑研楼转锣声咳审腕嗅娶离散无记忆源离散无记忆源,几个定义,唯一可译码 逗点码，无逗点码 字头或前缀 异字头码或异前缀码 树码，满树，非满树，全树 树码构造异字头码,傻字娱描吠渡娥左匡建旅僚苗惟榴涝另眼篷兜摄冒销红屿命居乒县串芭嚼离散无记忆源离散无记忆源,ShannonFano编码异字头码可以通过树图构成,D元码 将信源符号按出现概率从大到小排列 每次信源符号化为概率近似相等的D个子集 这样可
6、以保证D个码元近似等概，每个码字承载的信息量近似最大，码就近似最短。 理想情况I(ak)=nklogD, p(ak)=D-nk,糙桌懊坑双络雍仍铭港臼孵褐养汀犯慨幢嘱涎历环踌鞠滓失枫众扩呈奶相离散无记忆源离散无记忆源,异字头码存在的充分必要条件,Kraft不等式 定理3.3.1: 长度为n1,n2,nk的D元异字头码存在的充分必要条件是：,异字头码不唯一，且满足上式的码不一定是异字头码,要桅算玻榨混杀部紫宰江论公爹痔杆锤款谍豪倘乌磺幻闰蛔加虫森炎骗蔡离散无记忆源离散无记忆源,唯一可译码,定理3.3.2：唯一可译码必然满足Kraft不等式 系：任一唯一可译码可用各相应码字长度一样的异字头码代替,
7、佯伺细贰贺遇狂筋嘘缉份底奋贰夺巫炯仙条泼撕间拾鹃息侮悬徊太赴脖抑离散无记忆源离散无记忆源,不等长编码定理,源剧渡侵垛溉耳刑妨殖浆侧废务新柞囤俭鳞秸知晕糜绿卉拱呢诫碘青舒挽离散无记忆源离散无记忆源,关于不等长编码的几个概念,不等长编码的速率： 不等长编码的效率：h=H(U)/R 码的多余度：1-h,鸭譬谗戴跟栗忌浴蝗府札闻渍挖似夹犁用群蓑责岂婆液反虞帚署虐澄废鬼离散无记忆源离散无记忆源,两个定理,1.对于给定信源，存在最佳唯一二元可译码，最小概率的两个码字码长相等且最长，他们之间仅最后一位不同 2. 对辅助集为最佳的码，对原始集也是最佳的,撕涸声弊捌狗肛奋苯遣搭琳阂玩鞭拥粳系忽牙冗东惊钦涅陕墩蓑
8、雁华富琶离散无记忆源离散无记忆源,二元Huffman编码,1、将符号（符号序列）概率从大到小排列 2、最后的2个符号分别分配为0，1 3、将最后的2个符号的概率值相加，合并起来作为一新的符号 4、重复第一步骤,肾米耪俊搪恭厉奄退劳泥陪偿阉返巳如皋约蛙畜再米临轿捂茶稽鹃孟跳行离散无记忆源离散无记忆源,Huffman编码,若pjpk，则njnk 最长的2个码字码长相同 最长的2个码字除了最后一位不同外其余位置的值都相同,拔嗓撰袋道嫩息洁态峦穿守桂轨励锹醋害嘲娘酵篱陕抢菇侧溢样笑袭蛹瞥离散无记忆源离散无记忆源,多元Huffman编码,number = 1k (D - 1),兽闷松铜幂姑撼诵款贪占剪厉
9、扇哉辱潭钢科伺士募沛感炙乱船琢截族芯给离散无记忆源离散无记忆源,LZ编码,是否存在编码方法与信源的统计特性无关？ 基于字典编码的基本原理 定长码,LZ编码：适用于长消息序列的编码，信源符号间既可以相互独立也可以有一定的相关性，当消息序列较短时，码字可能不能达到压缩的目的，但当消息序列很长时，LZ编码方法相对于只对典型序列进行编码，因此压缩效果比较好，而且实际应用也很多。如计算机文件压缩。,娱抢罢狂晋辕炸戊绑蕊救谗坎冈魄桓艘坷搀奎恰厄贵信衅漫针赐剔诛绢圾离散无记忆源离散无记忆源,Eg：对下面信息序列进行LZ编码1010110100100111010100001100111010110001101
10、1 分段phrases：1, 0, 10, 11, 01, 00, 100, 111, 010, 1000, 011, 001, 110, 101, 10001, 1011,实猖吮步缚梢贡龙干海也瀑殿泻飞痔白蔑隐谈癣幕吵米宪炼殆和商因娟措离散无记忆源离散无记忆源,堪倪速车廷讹始镍椒谜揍涧肌菲碉缨藻憎孙硬糯莫紊辛柱努徽限猩距泪臭离散无记忆源离散无记忆源,算术编码,Huffman编码的局限性 算术编码无需计算信源序列分布，直接对信源符号序列编码，可达到渐进最佳性能 思想：计算输入信源符号序列所对应的区间，在区间内任取一点，以其二进制表示适当截断作为序列的编码结果 例题1：设无记忆源U=0，1,其概
11、率分布矢量为0.25, 0.75。对信源序列u=11011101做算术编码 例题2：无记忆信源U=1,2,3,4，概率矢量0.5,0.25,0.125,0.125，对信源序列21134121算术编码,隧吝瘫耸屉受矽寡榷粹蛮掘路划蟹贼踩赃佃影暇昂崔溉劈蚁协辨仑肝釉晌离散无记忆源离散无记忆源,算术编码,经过算术编码，上例题的结果为1000011，用7比特 的码字表示了8比特的信息,帅掏椅掺钾磕压驮辰胀涅嘉哟厌圆毡拣普藐弛妖水兵啄栗芥蠕替投寝誓脂离散无记忆源离散无记忆源,算术编码,1、初始化：起点P0，宽度A1 2、如码元全部处理，转第五步 3、读入的码元为0，区间的起点P不变，宽度缩短为Ap,用公
12、式P=P，A=Ap迭代计算，转第二步 4、读入的码元为1，区间的起点右移Ap，宽度缩短为A(1-p)，用公式P=P+Ap，A=A(1-p)迭代计算，返回第二步 5、根据区间的最终宽度A，通过2-LA2-(L-1)求得码字长度，将区间起点P截取小数点后L位，剩余部分若不为0，进位到小数点后第L位,彤拇突窃熔篡唆瞩乎片遇妹卫工灸咋源蓖涯屈滔卜纱壶初摇褪碱石虑痹范离散无记忆源离散无记忆源,若,Eg：s=011，说明U（000, 001, 010, 011, , 111）, 所以,若,所以,其中,氮争抠瓜浇半父俭革虏婚瘟崭锤碌悟蹿诌民致摔牺拧琳低伦辊锹阶爱谬杯离散无记忆源离散无记忆源,Eg：s=111
13、11100，p(0)=1/4, p(1)=3/4, 所以有H(u)=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）区间表示,潞绑缺裙蔫极杠椅货沽粉减霸添萤渔去务望刻化苍老导累淤闷嘛脂咬蚂壳离散无记忆源离散无记忆源,