您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 质量控制/管理 > 第四章:算术编码..
第四章:算术编码算术编码:越来越流行(在很多标准中被采用)适合的场合:小字母表:如二进制信源概率分布不均衡建模与编码分开内容:算术编码的基本思想一些性质实现有限精度:区间缩放(浮点数/整数实现)计算复杂度:用移位代替乘法二进制编码自适应模型QM编码器:自适应二进制编码回顾:Huffman编码例1:信源的符号数目很少:0.10.9XabPX0ab1a=0,b=1回顾:扩展的Huffman编码例2:信源的符号的概率严重不对称:A={a,b,c},P(a)=0.95,P(b)=0.02,P(c)=0.03H=0.335bits/symbolHuffman编码:a0b11c10l=1.05bits/symbol冗余(Redundancy)=l-H=0.715bits/sym(213%!)问题:能做得更好吗?10abc01回顾:扩展的Huffman编码基本思想:考虑对两个字母序列而不是单个字母编码LetterProbabilityCodeaa0.90250ab0.0190111ac0.0285100ba0.01901101bb0.0004110011bc0.0006110001ca0.0285101cb0.0006110010cc0.0009110000l=1.222/2=0.611冗余=0.276bits/symbol(27%)回顾:扩展的Huffman编码该思想还可以继续扩展考虑长度为n的所有可能的mn序列(已做了32)理论上:考虑更长的序列能提高编码性能实际上:字母表的指数增长将使得这不现实例如:对长度为3的ASCII序列:2563=224=16M需要对长度为n的所有序列产生码本很多序列的概率可能为0分布严重不对称是真正的大问题:A={a,b,c},P(a)=0.95,P(b)=0.02,P(c)=0.03H=0.335bits/symboll1=1.05,l2=0.611,…当n=8时编码性能才变得可接受但此时|alphabet|=38=6561!!!算术编码(ArithmeticCoding)算术编码:从另一种角度对很长的信源符号序列进行有效编码对整个序列信源符号串产生一个唯一的标识(tag)直接对序列进行编码(不是码字的串联):非分组码不用对该长度所有可能的序列编码标识是[0,1)之间的一个数(二进制小数,可作为序列的二进制编码)概率复习随机变量:将试验的输出映射到实数用数字代替符号X(ai)=i,其中aiA(A={ai},i=1..n)给定信源的概率模型P概率密度函数(probabilitydensityfunction,pdf)累积密度函数(cumulativedensityfunction,cdf)iPXiPa11iiXikkFiPXkPa产生标识定义一一映射:ak[FX(k-1),FX(k)],k=1..m,FX(0)=0[FX(k-1),FX(k)]区间内的任何数字表示ak对2字母序列akaj编码对ak,选择[FX(k-1),FX(k)]然后将该区间按比例分割并选取第j个区间:00,..1,,1XXXFmiiFiF11,111XXXXXXXXFjFjFkFkFkFkFkFk将[0,1)分为m个区间:产生标识:例考虑对a1a2a3编码:A={a1,a2,a3},P={0.7,0.1,0.2)映射:a11,a22,a33cdf:FX(1)=0.7,FX(2)=0.8,FX(3)=1.0映射成实数A={a1,a2,…,am}对公平掷骰子的例子:{1,2,3,4,5,6}6..161kforkXPiXPiFiXPkXPaTXikiX211211125.022112XPXPTX75.0521541XPkXPTkX词典顺序(Lexicographicorder)字符串的词典顺序:其中表示“在字母顺序中,y在x的前面”n为序列的长度():12inXiiTPPyyxxyxxy词典顺序:例考虑两轮连续的骰子:输出={11,12,…,16,21,22,…,26,…,61,62,…,66}469.07251321121113xPxPxPTX注意:为了产生13的标识,我们不必对产生其他标识但是,为了产生长度为n的字符串的标识,我们必须知道比其短的字符串的概率这与产生所有的码字一样繁重!应该想办法来避免此事区间构造观察包含某个标识的区间与所有其他标识的区间不相交基本思想递归:将序列的下/上界视为更短序列的界的函数上述骰子的例子:考虑序列:322令u(n),l(n)为长度为n序列的上界和下界,则u(1)=FX(3),l(1)=FX(2)u(2)=FX(2)(32),l(2)=FX(2)(31)(2)32(11)...(16)(21)...(26)(31)(32)XFPPPPPPxxxxxx区间构造(2)32(11)...(16)(21)...(26)(31)(32)XFPPPPPPxxxxxx6661212112111,,iiiPkiPxkxiPxkPxiPxkwherexxxx(2)1132(1)(2)(31)(32)(2)(31)(32)XXFPxPxPPFPPxxxx1221(31)(32)(3)(1)(2)(3)(2)XPPPxPxPxPxFxx)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)(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产生标识通常,对任意序列x=x1x2…xn()()2nnXulTx()(1)(1)(1)()(1)(1)(1)()(1)kkkkkkXkXkkkulullluFxFxl只需知道信源的cdf,即信源的概率模型算术编码:编码和解码过程都只涉及算术运算(加、减、乘、除)产生标识:例考虑随机变量X(ai)=i对序列1321编码:3,1)(,1)3(,82.0)2(,8.0)1(,0,0)(kkFFFFkkFXXXXX1,0)0()0(ul8.0)1(0)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)kkkkkkXkXkkkulullluFxFxl解码标识AlgorithmInitializel(0)=0,u(0)=1.1.Foreachi,i=1..n•Computet*=(tag-l(k-1))/(u(k-1)-l(k-1)).2.Findthexk:FX(xk-1)t*FX(xk).3.Updateu(n),l(n)4.Ifdone--exit,otherwisegoto1.解码:例3,1)(,1)3(,82.0)2(,8.0)1(,0,0)(kkFFFFkkFXXXXX772352.01321XTAlgorithmInitializel(0)=0,u(0)=1.1.Computet*=(tag-l(k-1))/(u(k-1)-l(k-1)).2.Findthexk:FX(xk-1)t*FX(xk).3.Updateu(k),l(k)4.Ifdone--exit,otherwisegoto1.)1()()1()1()1()()1()1()1()(kXkkkkkXkkkkxFlullxFlulu8.0)1(0)0()1(8.00)0(772352.0010772352.0)0()0()0()1()0()0()0()1(**XXXXFluluFlullFtFt8.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.077408.07712.0772352.0**XXFtFt1131321321算术编码的唯一性和效率上述产生的标识可以唯一表示一个序列,这意味着该标识的二进制表示为序列的唯一二进制编码但二进制表示的精度可以是无限长:保证唯一性但不够有效为了保证有效性,可以截断二进制表示,但如何保证唯一性?答案:为了保证唯一性和有效性,需取小数点后l位数字作为信源序列的码字,其中注意:P(x)为最后区间的宽度,也是该符号串的概率符合概率匹配原则:出现概率较大的符号取较短的码字,而对出现概率较小的符号取较长的码字1log1()lPxx算术编码的唯一性和效率长度为n的序列的算术编码的平均码长为:()1()log1()1()log11()()log()2()22AnlPlPPPPPPPHXnHXxxxxxxxxx22nAAHnHXlnHXXlHXn算术编码的效率高:当信源符号序列很长,平均码长接近信源的熵实现迄今为止已有能工作的编码/解码算法假设实数(无限精度)最终l(n)和u(n)将集中到一起我们需要对字符串增量式编码观测:当区间变窄时1.[l(n),u(n)][0,0.5),或2.[l(n),u(n)][0.5,1),或3.l(n)[0,0.5),u(n)[0.5,1).先集中处理1.&2,稍后再讨论3实现编码器:一旦我们到达1.或2.,就可以忽略[0,1)的另一半还需要告知解码器标识所在的半区间:发送0
本文标题:第四章:算术编码..
链接地址:https://www.777doc.com/doc-3822236 .html