第四章：算术编码

第四章：算术编码算术编码：越来越流行（在很多标准中被采用）适合的场合：小字母表：如二进制信源概率分布不均衡建模与编码分开内容：算术编码的基本思想一些性质实现有限精度：区间缩放（浮点数/整数实现）计算复杂度：用移位代替乘法二进制编码自适应模型QM编码器：自适应二进制编码回顾：Huffman编码例1：信源的符号数目很少:0.10.9XabPX0ab1a=0,b=1回顾：扩展的Huffman编码例2：信源的符号的概率严重不对称：A={a,b,c},P(a)=0.95,P(b)=0.02,P(c)=0.03H=0.335bits/symbolHuffman编码：a0b11c10l=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.03H=0.335bits/symboll1=1.05,l2=0.611,…当n=8时编码性能才变得可接受但此时|alphabet|=38=6561!!!算术编码（ArithmeticCoding）算术编码：从另一种角度对很长的信源符号序列进行有效编码对整个序列信源符号串产生一个唯一的标识（tag）直接对序列进行编码（不是码字的串联）：非分组码不用对该长度所有可能的序列编码标识是[0,1)之间的一个数（二进制小数，可作为序列的二进制编码）概率复习随机变量：将试验的输出映射到实数用数字代替符号X(ai)=i,其中aiA(A={ai},i=1..n)给定信源的概率模型P概率密度函数（probabilitydensityfunction,pdf）累积密度函数（cumulativedensityfunction,cdf）iPXiPa11iiXikkFiPXkPa产生标识定义一一映射：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,,1XXXFmiiFiF11,111XXXXXXXXFjFjFkFkFkFkFkFk将[0,1)分为m个区间：产生标识：例考虑对a1a2a3编码：A={a1,a2,a3},P={0.7,0.1,0.2)映射：a11,a22,a33cdf:FX(1)=0.7,FX(2)=0.8,FX(3)=1.0映射成实数A={a1,a2,…,am}对公平掷骰子的例子：{1,2,3,4,5,6}6..161kforkXPiXPiFiXPkXPaTXikiX211211125.022112XPXPTX75.0521541XPkXPTkX词典顺序（Lexicographicorder）字符串的词典顺序：其中表示“在字母顺序中，y在x的前面”n为序列的长度():12inXiiTPPyyxxyxxy词典顺序：例考虑两轮连续的骰子：输出={11,12,…,16,21,22,…,26,…,61,62,…,66}469.07251321121113xPxPxPTX注意：为了产生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)XFPPPPPPxxxxxx区间构造(2)32(11)...(16)(21)...(26)(31)(32)XFPPPPPPxxxxxx6661212112111,,iiiPkiPxkxiPxkPxiPxkwherexxxx(2)1132(1)(2)(31)(32)(2)(31)(32)XXFPxPxPPFPPxxxx1221(31)(32)(3)(1)(2)(3)(2)XPPPxPxPxPxFxx)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(ul8.0)1(0)0()0()0()0()1()0()0()0()1(XXFluluFlull18.0)3(656.0)2()1()1()1()2()1()1()1()2(XXFluluFlull1377408.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解码标识AlgorithmInitializel(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)(kkFFFFkkFXXXXX772352.01321XTAlgorithmInitializel(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()(kXkkkkkXkkkkxFlullxFlulu8.0)1(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(**XXXXFluluFlullFtFt77408.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**XXFtFt1131321321算术编码的唯一性和效率上述产生的标识可以唯一表示一个序列，这意味着该标识的二进制表示为序列的唯一二进制编码但二进制表示的精度可以是无限长：保证唯一性但不够有效为了保证有效性，可以截断二进制表示，但如何保证唯一性？答案：为了保证唯一性和有效性，需取小数点后l位数字作为信源序列的码字，其中注意：P(x)为最后区间的宽度，也是该符号串的概率符合概率匹配原则：出现概率较大的符号取较短的码字，而对出现概率较小的符号取较长的码字1log1()lPxx算术编码的唯一性和效率长度为n的序列的算术编码的平均码长为：()1()log1()1()log11()()log()2()22AnlPlPPPPPPPHXnHXxxxxxxxxx22nAAHnHXlnHXXlHXn算术编码的效率高：当信源符号序列很长，平均码长接近信源的熵实现迄今为止已有能工作的编码/解码算法假设实数（无限精度）最终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