四章算术编码.ppt
《四章算术编码.ppt》由会员分享,可在线阅读,更多相关《四章算术编码.ppt(66页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、四章算术编码 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望回顾:Huffman编码n例1:信源的符号数目很少n 0ab1a=0,b=1回顾:扩展的Huffman编码n例2:信源的符号的概率严重不对称:nA=a,b,c,P(a)=0.95,P(b)=0.02,P(c)=0.03nH=0.335 bits/symbolnHuffman编码:a0b11c10nl=1.05 bits/symboln冗余(Redundancy)=l-H=0.715 bits/sym(21
2、3%!)n问题:能做得更好吗?10ab c01回顾:扩展的Huffman编码n基本思想:n考虑对两个字母序列而不是单个字母编码LetterLetterProbabilityProbabilityCodeCodeaaaa0.90250.90250 0abab0.01900.0190111111acac0.02850.0285100100baba0.01900.019011011101bbbb0.00040.0004110011110011bcbc0.00060.0006110001110001caca0.02850.0285101101cbcb0.00060.0006110010110010cc
3、cc0.00090.0009110000110000l=1.222/2=0.611冗余=0.276 bits/symbol(27%)回顾:扩展的Huffman编码n n该思想还可以继续扩展该思想还可以继续扩展n n考虑长度为考虑长度为n n的所有可能的的所有可能的m mn n 序列序列(已做了已做了3 32 2)n n理论上:考虑更长的序列能提高编码性能理论上:考虑更长的序列能提高编码性能n n实际上:实际上:n n字母表的指数增长将使得这不现实字母表的指数增长将使得这不现实n n例如:对长度为例如:对长度为3 3的的ASCIIASCII序列:序列:2562563 3=2=22424=16M=
4、16Mn n需要对长度为需要对长度为n n的的所有所有序列产生码本序列产生码本n n很多序列的概率可能为很多序列的概率可能为0 0n n分布严重不对称是真正的大问题:分布严重不对称是真正的大问题:n nA A=a,b,c,P(a)=0.95,P(b)=0.02,P(c)=0.03 =a,b,c,P(a)=0.95,P(b)=0.02,P(c)=0.03 n nH H=0.335=0.335 bits/symbolbits/symboln nl l1 1=1.05,=1.05,l l2 2=0.611,=0.611,n n当当n n=8=8时编码性能才变得可接受时编码性能才变得可接受n n但此时
5、但此时|alphabet|=3|alphabet|=38 8=6561=6561!算术编码(Arithmetic Coding)n n算术编码:从另一种角度对很长的信源符号序列进行有效算术编码:从另一种角度对很长的信源符号序列进行有效编码编码n n对整个序列信源符号串产生一个唯一的标识(对整个序列信源符号串产生一个唯一的标识(tag tag)n n直接对序列进行编码(不是码字的串联):直接对序列进行编码(不是码字的串联):非分组码非分组码n n不用对该长度所有可能的序列编码不用对该长度所有可能的序列编码n n标识是标识是0,1)0,1)之间的一个数(二进制小数,可作为序列之间的一个数(二进制小
6、数,可作为序列的二进制编码)的二进制编码)概率复习 n n随机变量:随机变量:n n将试验的输出映射到实数将试验的输出映射到实数n n用数字代替符号用数字代替符号n nX X(a ai i)=)=i i,其中其中 a ai i A A(A A=a ai i,i i=1.=1.n n)n n给定信源的概率模型给定信源的概率模型Pn n概率密度函数(概率密度函数(probability density function,probability density function,pdfpdf)n n累积密度函数(累积密度函数(cumulative density function,cumulativ
7、e density function,cdfcdf)产生标识n n定义一一映射:定义一一映射:n na ak k F FX X(k k-1),-1),F FX X(k k),k k=1.=1.m m,F FX X(0)=0(0)=0n n F FX X(k k-1),-1),F FX X(k k)区间内的任何数字表示区间内的任何数字表示 a ak kn n对对2 2字母序列字母序列a ak k a aj j编码编码n n对对a ak k ,选择,选择 F FX X(k k-1),-1),F FX X(k k)n n然后将该区间按比例分割并选取第然后将该区间按比例分割并选取第j j个区间:个区间
8、:v将0,1)分为m个区间:产生标识:例n考虑对a1a2a3编码:n nA A=a1,a2,a3,P P=0.7,0.1,0.2)n映射:a1 1,a2 2,a3 3ncdf:FX(1)=0.7,FX(2)=0.8,FX(3)=1.0映射成实数n nA=a a1 1,a a2 2,a am m v对公平掷骰子的例子:1,2,3,4,5,6词典顺序(Lexicographic order)n n字符串的词典顺序:n n其中其中 表示表示“在字母顺序中,在字母顺序中,y y在在x x的前面的前面”n nn n 为序列的长度为序列的长度词典顺序:例n n考虑两轮连续的骰子:考虑两轮连续的骰子:n n
9、输出输出=11,12,16,21,22,26,61,62,66=11,12,16,21,22,26,61,62,66v注意:为了产生13的标识,我们不必对产生其他标识=但是,为了产生长度为n的字符串的标识,我们必须知道比其短的字符串的概率这与产生所有的码字一样繁重!应该想办法来避免此事区间构造n n观察观察n n包含某个标识的区间与所有其他标识的区间不相交包含某个标识的区间与所有其他标识的区间不相交n n基本思想基本思想n n递归:将序列的下递归:将序列的下/上界视为更短序列的界的函数上界视为更短序列的界的函数n n上述骰子的例子:上述骰子的例子:n n考虑序列:考虑序列:3 2 23 2 2
10、 n n令令u u(n)(n),l,l(n)(n)为长度为为长度为n n序列的上界和下界,则序列的上界和下界,则u u(1)(1)=F FX X(3),l(3),l(1)(1)=F FX X(2)(2)u u(2)(2)=F FX X(2)(2)(32),l(32),l(2)(2)=F FX X(2)(2)(31)(31)区间构造区间构造产生标识n n通常,对任意序列通常,对任意序列x x=x x1 1x x2 2x xn n只需知道信源的cdf,即信源的概率模型算术编码:编码和解码过程都只涉及算术运算(加、减、乘、除)产生标识:例n考虑随机变量X(ai)=i n对序列1 3 2 1编码:11
11、31321321解码标识nAlgorithmnInitialize l(0)=0,u(0)=1.1.For each i,i=1.nCompute t*=(tag-l(k-1)/(u(k-1)-l(k-1).2.Find the xk:FX(xk-1)t*FX(xk).3.Update u(n),l(n)4.If done-exit,otherwise goto 1.解码:例vAlgorithmInitialize l(0)=0,u(0)=1.1.Compute t*=(tag-l(k-1)/(u(k-1)-l(k-1).2.Find the xk:FX(xk-1)t*FX(xk).3.Upd
12、ate u(k),l(k)4.If done-exit,otherwise goto 1.1131321321算术编码的唯一性和效率n上述产生的标识可以唯一表示一个序列,这意味着该标识的二进制表示为序列的唯一二进制编码n但二进制表示的精度可以是无限长:保证唯一性但不够有效n为了保证有效性,可以截断二进制表示,但如何保证唯一性?n答案:为了保证唯一性和有效性,需取小数点后l位数字作为信源序列的码字,其中n注意:P(x)为最后区间的宽度,也是该符号串的概率n符合概率匹配原则:出现概率较大的符号取较短的码字,而对出现概率较小的符号取较长的码字算术编码的唯一性和效率n长度为n的序列的算术编码的平均码长
13、为:算术编码的效率高:当信源符号序列很长,平均码长接近信源的熵实现n n迄今为止迄今为止 0,1);:0,0.5)=0,1);E E1 1(x)=2x(x)=2xn nE E2 2:0.5,1)=0,1);:0.5,1)=0,1);E E2 2(x)=2(x-0.5)(x)=2(x-0.5)n n注意:在缩放过程中我们丢失了最高位注意:在缩放过程中我们丢失了最高位n n但这不成问题但这不成问题我们已经发送出去了我们已经发送出去了n n解码器解码器n n根据根据0/10/1比特并相应缩放比特并相应缩放n n与编码器保持同步与编码器保持同步标识产生:带缩放的例子n考虑随机变量X(ai)=i n对序
14、列1 3 2 1编码:Input:1321Output:Input:-321Output:1标识产生:带缩放的例子Input:-21Output:11Input:-1Output:110Input:-1Output:1100Input:-1Output:11000标识产生:带缩放的例子n nEOT:EOT:n nl l(n)(n),u,u(n)(n)区间内的任何一个区间内的任何一个数字数字n n在此选在此选 0.5 0.51010=0.1=0.12 2Input:-1Output:110001Input:-1Output:110001Input:-1Output:110001Output:11
15、000110v注意:0.1100011=2-1+2-2+2-6+2-7=0.7734375 0.7712,0.77408增量式标识解码n n我们需要增量式解码n n如:网络传输如:网络传输n n问题n n如何开始?如何开始?n n必须有足够的信息,可以对第一个字符无歧义解码必须有足够的信息,可以对第一个字符无歧义解码 接收到的比特数应比最小标识对应的区间更小接收到的比特数应比最小标识对应的区间更小n n怎样继续?怎样继续?n n一旦有一个非歧义的开始,只要模拟编码器即可一旦有一个非歧义的开始,只要模拟编码器即可n n如何结束?如何结束?标识解码:例n n假设码字长为假设码字长为6 6n n输入
16、:输入:110001110001100000100000n n0.1100010.1100012 2=0.765625=0.7656251010n n第第1 1位:位:1 1Output:Output:1 1Input:110001100000Output:13Input:-10001100000(左移)Input:-10001100000(0.546875)Output:132Input:-001100000(左移)Input:-0001100000(左移)此时解码最后一个符号此时解码最后一个符号标识解码:例Input:-01100000(左移)Input:-1100000(左移)Input
17、:-100000(左移)Input:-100000Output:1321第三种情况:E3n n回忆三种情况回忆三种情况1.1.l l(n)(n),u,u(n)(n)0,0.5):E 0,0.5):E1 1:0,0.5)=0,1);E:0,0.5)=0,1);E1 1(x)=2x(x)=2x2.2.l l(n)(n),u,u(n)(n)0.5,1):E 0.5,1):E2 2:0.5,1)=0,1);E:0.5,1)=0,1);E2 2(x)=2(x-0.5)(x)=2(x-0.5)3.3.l l(n)(n)0,0.5),u 0,0.5),u(n)(n)0.5,1):0.5,1):E E3 3(
18、x)=?(x)=?n nE E3 3 缩放缩放n nE E3 3:0.25,0.75)=0,1);E:0.25,0.75)=0,1);E3 3(x)=2(x-0.25)(x)=2(x-0.25)n n编码编码n nE E1 1=0,E=0,E2 2=1,E=1,E3 3=?=?n n注意:注意:n nE E3 3 E E3 3 E E1 1=E=E1 1 E E2 2 E E2 2 n nE E3 3 E E3 3 E E2 2=E=E2 2 E E1 1 E E1 1 n n规则:规则:记录记录E E3 3 连续的次数,并在输出下一个连续的次数,并在输出下一个E E2 2/E/E1 1 之之
19、后后发送该次数发送该次数证明请见文献:Witten,Radford,Neal,Cleary,“Arithmetic Coding for Data Compression”Communications of the ACM,vol.30,no.6,pp.520-540,June 1987.第三种情况:E3整数实现n假设码字长度为n,则nni=长度为TotalCount(TC)的序列中字符i出现的次数n累积计数:CC 整数实现nMSB(x)=Most Significant Bit of xnLSB(x)=Least Significant Bit of xnSB(x,i)=ith Signif
20、icant Bit of xnMSB(x)=SB(x,1);LSB(x)=SB(x,m)nE3(l,u)=(SB(l,2)=1&SB(u,2)=0)l=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 rescaling if(MSB(u)=MSB(l)/MSB(u)=MSB(l)=1 E2 resca
21、ling 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=(u 2=28 8 x 50/1 x 50/1=最小最小 n n=8=8 (2 (28 8=256)=256)l=000,u=111,e3_count=0repeat x=get_symbol l=l+(u-l+1)CC(x-1)/TC u=l
22、+(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 done整数编码器:例l=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
23、)/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:1321Output:Input:-321Output:1 整数编码器:例l=000,u=111,e3_count=0repeat x=get_symbol l=l+(u-l+1)CC
24、(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+endif endwhileuntil doneInput:-21Output:110 e3_count=1整数编码器:例l=000,u=111,e3_count=0repeat x=get_sy
25、mbol 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+endif endwhileuntil doneInput:-1Output:1100 Input:-1Output:11000 Input:-1Output:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算术 编码
限制150内