版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、:0.10.9XabP X0ab1a=0, b=110ab c01l = 1.222/2 = 0.611冗余 = 0.276 bits/symbol27%n但此时|alphabet| = 38 = 6561 ! iP XiP a 11iiXikkFiP XkP a 00,.1,1XXXFmiiFiF 11,111XXXXXXXXFjFjFkFkFkFkFkFkv将0, 1)分为m个区间:v对公平掷骰子的例子:1, 2, 3, 4, 5, 66.161kforkXP iXPiFiXPkXPaTXikiX2112111 25. 022112XPXPTX 75. 0521541XPkXPTkX (
2、):12inXiiTPPy y xxyxxy 469. 07251321121113xPxPxPTXv留意:v为了产生13的标识,我们不用对产生其他标识v但是,为了产生长度为n的字符串的标识,我们必需知道比其短的字符串的概率v这与产生一切的码字一样繁重!v应该想方法来防止此事(2)32(11).(16)(21).(26)(31)(32)XFPPPPPPxxxxxx (2)32(11).(16)(21).(26)(31)(32)XFPPPPPPxxxxxx6661212112111,iiiPkiP xk xiP xkP xiP xkwherex xxx(2)1132(1)(2)(31)(32)(
3、2)(31)(32)XXFP xP xPPFPPxxxx1221(31)(32)(3)(1)(2)(3)(2)XPPP xP xP xP xFxx)2()3()3(1XXFFxP)2()2()3()2(32)2(XXXXXFFFFF)2()1()1()1()2(XFlulu) 1 ()2()3()2(31)2(XXXXXFFFFF) 1 ()1()1()1()2(XFlull()()(3)( )(3)( )322 ,32133XXuFlF=()()(3)(2)(2)(2)322(31)(32)(31)(2)XXXXXFFFFF=+-()()(3)(2)(2)(2)321(31)(32)(31)
4、(1)XXXXXFFFFF=+-)2()2()2()2()3(XFlulu) 1 ()2()2()2()3(XFlull)2()2()3()2(32)2(XXXXXFFFFF)2()1()1()1()2(XFlulu ( )( )2nnXulTx( )(1)(1)(1)( )(1)(1)(1)()(1)kkkkkkXkXkkkulullluFxFxl只需知道信源的cdf,即信源的概率模型算术编码:编码和解码过程都只涉及算术运算加、减、乘、除3, 1)(, 1)3(,82. 0)2(, 8 . 0) 1 (, 0, 0)(kkFFFFkkFXXXXX1, 0)0()0(ul8 . 0) 1 (0
5、)0()0()0()0()1()0()0()0()1(XXFluluFlull18 . 0)3(656. 0)2()1()1()1()2()1()1()1()2(XXFluluFlull1377408. 0)2(7712. 0) 1 ()2()2()2()3()2()2()2()3(XXFluluFlull132()()(4)(1)(3)(3)(4)(3)(3)(3)( )0.7712(1)0.7735040XXllulFululF=+-=+-=1321(4)(4)13210.7723522XulT( )(1)(1)(1)( )(1)(1)(1)()(1)kkkkkkXkXkkkululllu
6、FxFxl3, 1)(, 1)3(,82. 0)2(, 8 . 0) 1 (, 0, 0)(kkFFFFkkFXXXXX772352. 01321 XTvAlgorithmvInitialize l(0) = 0, u(0) = 1.vCompute t*=(tag-l(k-1)/(u(k-1)-l(k-1).vFind the xk: FX(xk-1) t* FX(xk).vUpdate u(k), l(k)vIf done-exit, otherwise goto 1.) 1()()1()1()1()()1()1()1()(kXkkkkkXkkkkxFlullxFlulu 8 .0)1 (
7、0)0()1 (8 .00)0(772352.0010772352.0)0()0()0()1()0()0()0()1(*XXXXFluluFlullFtFt 8 .0)3(656.0)2()3(182.0)2(96544.008 .00772352.0)1()1()1()2()1()1()1()2(*XXXXFluluFlullFtFt77408.0)2(7712.0)1 ()2(82.08 .0)1 (808.0656.08 .0656.0772352.0)2()2()2()3()2()2()2()3(*XXXXFluluFlullFtFt)1 (8 .00)0(4 .07712.07740
8、8.07712.0772352.0*XXFtFt1131321321 1log1( )lPxx ( )1 ( )log1( )1 ( ) log1 1( ) ( )log( )2( ) 22AnlPlPPPPPPPH XnH X xxxxxxxxx 2 2 nAAHnH XlnH XXlH Xn算术编码的效率高:当信源符号序列很长,平均码长接近信源的熵nn与编码器坚持同步3, 1)(, 1)3(,82. 0)2(, 8 . 0) 1 (, 0, 0)(kkFFFFkkFXXXXX1, 0)0()0(ul(1)(0)(0)(0)(1)(0)(0)(0)(1)(1)(1)(1)(0)0(1)0.8
9、,)0,0.5),)0.5,1)XXllulFululFluluget next symbolInput: 1321Output: 6 . 0)5 . 08 . 0(2312. 0)5 . 0656. 0(2) 1 , 5 . 08 . 0,656. 08 . 0)3(656. 0)2()2()2()1()1()1()2()1()1()1()2(ulFluluFlullXXInput: -321Output: 1Input: -21Output: 1154816. 0)2(5424. 0) 1 ()2()2()2()3()2()2()2()3(XXFluluFlull6 . 0,312. 0)
10、2()2(ul09632. 05 . 054816. 020848. 05 . 05424. 02)3()3(ulInput: -1Output: 11019264. 009632. 021696. 00848. 02)3()3(ulInput: -1Output: 110038528. 019264. 023392. 01696. 02)3()3(ulInput: -1Output: 1100077056. 038528. 026784. 03392. 02)3()3(ulInput: -1Output: 11000154112. 0)5 . 077056. 0(23568. 0)5 . 0
11、6784. 0(2)3()3(ulInput: -1Output: 110001504256. 0) 1 ()3568. 054112. 0(3568. 03568. 0)0()3568. 054112. 0(3568. 0)4()4(XXFuFlInput: -1Output: 110001Output: 11000110v留意:0.1100011 = 2-1+2-2+2-6+2-7= 0.7734375 0.7712,0.77408n如何终了? )3(182.0)2(9570.008 .00765625.0*XXFtFt8 .0)3(656.0)2()1()1()1()2()1()1()1
12、()2(XXFluluFlullInput: 110001100000Output: 13Input:-10001100000 (左移)6 .0)5 .08 .0(2312.0)5 .0656.0(2)2()2(ul )2(82.08 .0)1 (8155.0312.06 .0312.0546875.0*XXFtFtInput: -10001100000 (0.546875)Output: 13254816.0)2(5424.0)1 ()2()2()2()3()2()2()2()3(XXFluluFlull09632. 05 . 054816. 020848. 05 . 05424. 02)3
13、()3(ulInput: -001100000 (左移)Input: -0001100000 (左移)(1)(1)0(10)000(10)0.80.8lu19264. 009632. 021696. 00848. 02)3()3(ulInput: -01100000 (左移)38528. 019264. 023392. 01696. 02)3()3(ulInput: -1100000 (左移)77056. 038528. 026784. 03392. 02)3()3(ulInput: -100000 (左移)504256. 0) 1 ()3568. 054112. 0(3568. 03568.
14、 0)0()3568. 054112. 0(3568. 0)4()4(XXFuFlInput: -100000*2*1000000.5,(0)00.8(1)XXtFtFOutput: 1321证明请见文献: Witten, Radford, Neal, Cleary, “Arithmetic Coding for Data Compression Communications of the ACM, vol. 30, no. 6, pp. 520-540, June 1987. timestimes0,1000111nn 1times0.5100nTCkCCkFnkCCXkii)()()(1(
15、 )(1)(1)(1)( )(1)(1)(1)1(1)1()1nnnnnnnnnnllulCC xTCululCC xTC( )(1)(1)(1)( )(1)(1)(1)()(1)kkkkkkXkXkkkulullluFxFxll=000, u=111, e3_count=0repeat x=get_symbol l=l+ (u-l+1)CC(x-1)/TC / lower bound update u=l+ (u-l+1)CC(x)/TC-1 / upper bound update while(MSB(u)=MSB(l) OR E3(u,l) / MSB(u)=MSB(l)=0 E1 re
16、scaling if(MSB(u)=MSB(l) / MSB(u)=MSB(l)=1 E2 rescaling send(MSB(u) l = (l1)+0 / shift left, set LSB to 0 u = (u0) send(!MSB(u) / encode accumulated E3 rescalings e3_count- endwhile endif if(E3(u,l) / perform E3 rescaling & remember l = (l1)+0 u = (u1)+1 complement MSB(u) and MSB(l) e3_count+ en
17、dif endwhileuntil donel=000, u=111, e3_count=0repeat x=get_symbol l=l+ (u-l+1)CC(x-1)/TC u=l+ (u-l+1)CC(x)/TC-1 while(MSB(u)=MSB(l) OR E3(u,l) if(MSB(u)=MSB(l) send(MSB(u) l = (l1)+0 u = (u0) send(!MSB(u) e3_count- endwhile endif if(E3(u,l) l = (l1)+0 u = (u1)+1 complement MSB(u) and MSB(l) e3_count
18、+ endif endwhileuntil donel=000, u=111, e3_count=0repeat x=get_symbol l=l+ (u-l+1)CC(x-1)/TC u=l+ (u-l+1)CC(x)/TC-1 while(MSB(u)=MSB(l) OR E3(u,l) if(MSB(u)=MSB(l) send(MSB(u) l = (l1)+0 u = (u0) send(!MSB(u) e3_count- endwhile endif if(E3(u,l) l = (l1)+0 u = (u1)+1 complement MSB(u) and MSB(l) e3_c
19、ount+ endif endwhileuntil done2)0(2)0()11111111(255)00000000(0ulfalse32)1(2)1(),()()11001011(203150402560)00000000(05002560EuMSBlMSBulInput: 1321Output: Input: -321Output: 1 1)()()11001011(203150502040)10100111(167504120402)2(2)2(uMSBlMSBull=000, u=111, e3_count=0repeat x=get_symbol l=l+ (u-l+1)CC(x
20、-1)/TC u=l+ (u-l+1)CC(x)/TC-1 while(MSB(u)=MSB(l) OR E3(u,l) if(MSB(u)=MSB(l) send(MSB(u) l = (l1)+0 u = (u0) send(!MSB(u) e3_count- endwhile endif if(E3(u,l) l = (l1)+0 u = (u1)+1 complement MSB(u) and MSB(l) e3_count+ endif endwhileuntil doneInput: -21Output: 110 1, 1)()()10010100(1481504114828)10
21、010010(1465040148282)3(2)3(e3_countuMSBlMSBul175)10000000(11)10010111(281000000001)01001110(151)10010111(11)11001011(78)01001110(01)10101011(22)2(2)2(322)2(22)2(xorxortrueulEule3_count = 1l=000, u=111, e3_count=0repeat x=get_symbol l=l+ (u-l+1)CC(x-1)/TC u=l+ (u-l+1)CC(x)/TC-1 while(MSB(u)=MSB(l) OR
22、 E3(u,l) if(MSB(u)=MSB(l) send(MSB(u) l = (l1)+0 u = (u0) send(!MSB(u) e3_count- endwhile endif if(E3(u,l) l = (l1)+0 u = (u1)+1 complement MSB(u) and MSB(l) e3_count+ endif endwhileuntil doneInput: -1Output: 1100 0)()(41)00101001(11)10010100(36)00100100(1)10010010(22)3(22)3(uMSBlMSBulInput: -1Outpu
23、t: 11000 0)()(83)01010011(11)00101001(72)01001000(1)00100100(22)3(22)3(uMSBlMSBulInput: -1Output: 110001 1)()(167)10100111(11)01010011(144)10010000(1)01001000(22)3(22)3(uMSBlMSBull=000, u=111, e3_count=0repeat x=get_symbol l=l+ (u-l+1)CC(x-1)/TC u=l+ (u-l+1)CC(x)/TC-1 while(MSB(u)=MSB(l) OR E3(u,l)
24、if(MSB(u)=MSB(l) send(MSB(u) l = (l1)+0 u = (u0) send(!MSB(u) e3_count- endwhile endif if(E3(u,l) l = (l1)+0 u = (u1)+1 complement MSB(u) and MSB(l) e3_count+ endif endwhileuntil doneInput: -1Output: 1100010 0)()(79)01001111(11)10100111(32)00100000(1)10010000(22)3(22)3(uMSBlMSBulInput: -1191)1000000
25、0(11)10011111(01000000001)01000000(),()(159)10011111(11)01001111(64)01000000(1)00100000(22)3(2)3(322)3(22)3(xorxortrueulEuMSBlMSBule3_count = 1l=000, u=111, e3_count=0repeat x=get_symbol l=l+ (u-l+1)CC(x-1)/TC u=l+ (u-l+1)CC(x)/TC-1 while(MSB(u)=MSB(l) OR E3(u,l) if(MSB(u)=MSB(l) send(MSB(u) l = (l1
26、)+0 u = (u0) send(!MSB(u) e3_count- endwhile endif if(E3(u,l) l = (l1)+0 u = (u1)+1 complement MSB(u) and MSB(l) e3_count+ endif endwhileuntil doneInput: -1Output: 1100010 false32)4(2)4(),()()10011000(152150401920)00000000(05001920EuMSBlMSBulv终了v通常,发送l(4): (00000000)2v但是 e3_count = 1,因此v在发送l(4)的第一个0
27、后发送1最后 output: 1100010010000000 Initialize l, u, t / t = first n bitsrepeat k=0 while( (t-l+1)TC-1)/(u-l+1) CC(k) k+ x = decode_symbol(k) l=l+ (u-l+1)CC(x-1)/TC u=l+ (u-l+1)CC(x)/TC-1 while(MSB(u)=MSB(l) OR E3(u,l) if(MSB(u)=MSB(l) / Perform E1/E2 rescaling of l,u,t l = (l1)+0 / add 0 to the right o
28、f l u = (u1)+1 / add 1 to the right of u t = (t1)+next_bit endif if(E3(u,l) / Perform E3 rescaling of l,u,t l = (l1)+0 u = (u1)+1 t = (t1)+next_bit complement MSB(u), MSB(l), MSB(t) endif endwhileuntil doneInitialize l, u, t repeat k=0 while( (t-l+1)CC(x-1)/TC CC(k) k+ x = decode_symbol(k) l=l+ (u-l
29、+1)CC(x-1)/TC u=l+ (u-l+1)CC(x)/TC-1 while(MSB(u)=MSB(l) OR E3(u,l) if(MSB(u)=MSB(l) l = (l1)+0 u = (u1)+1 t = (t1)+next_bit endif if(E3(u,l) l = (l1)+0 u = (u1)+1 t = (t1)+next_bit complement MSB(u), MSB(l), MSB(t) endif endwhileuntil doneInput: 1100010010000000 222)11000100(196)11111111(255)000000
30、00(0tul11382561501970*xktOutput: 1false322),()()11001011(20350402560)00000000(05002560EuMSBlMSBul33482031501970*xktOutput: 13Input: 1100010010000000 )()()11001011(203150502040)10100111(16750412040)10001001(222uMSBlMSBultInput: 1100010010000000 true322222),()()10010111(11)11001011()01001110(1)1010011
31、1()00010010(EuMSBlMSBultInput: 1100010010000000 falsexorxorxor3222222),()(175)10111001(1000000011)10010111(28)00011100(100000001)01001110(146)10010010(10000000)00010010(EuMSBlMSBultInitialize l, u, t repeat k=0 while( (t-l+1)CC(x-1)/TC CC(k) k+ x = decode_symbol(k) l=l+ (u-l+1)CC(x-1)/TC u=l+ (u-l+1
32、)CC(x)/TC-1 while(MSB(u)=MSB(l) OR E3(u,l) if(MSB(u)=MSB(l) l = (l1)+0 u = (u1)+1 t = (t1)+next_bit endif if(E3(u,l) l = (l1)+0 u = (u1)+1 t = (t1)+next_bit complement MSB(u), MSB(l), MSB(t) endif endwhileuntil done2240) 128175(150) 128146*xktOutput: 1322228148 40 50146(10010010)28148 41 501148(10010100)( )( )5luMSB lMSB u ,共 次v终了v已解码接纳到了预定数目的字符,或v接纳到EOTInitialize l, u, t repeat k=0 while( (t-l+1)CC(x-1)/TC CC(k) k+ x = decode_symbol(k) l=l+ (u-l+1)CC(x-1)/TC u=l+ (u-l+1)CC(x)/
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年高纯度丙烯酰胺及聚丙烯酰胺项目发展计划
- 肉粉销售合同范本
- 2024版标准农作物种子采购合同书
- 2024版个人房屋租赁合同范本-1
- 2024版合同评审控制程序5
- 2024版房屋买卖合同书(简易)
- 贵重物品押送合同协议
- 2024版广州劳务承包合同样本
- 酒水物流合同示范文本
- 钢铁厂半包装修合同样本
- 小学数学研讨课活动方案及流程
- 中国古建筑行业市场现状供需分析及市场深度研究发展前景及规划可行性分析研究报告(2024-2030)
- 2022年10月自考04741计算机网络原理试题及答案含解析
- 出镜记者现场报道的呈现技巧(修订版)
- EPC项目设计优化思路
- 智慧黑板采购投标方案(技术方案)
- 车辆维修保障方案
- 2024年低碳产业园路径与案例( PPT)
- 园长进班指导制度
- 全球公路建设的发展趋势
- 外出作业安全教育的课件
评论
0/150
提交评论