算术编码专题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不当之处，请联系本人或网站删除。,【,例题,】,假定用于通信的电文仅由 8 个字母,a,b,c,d,e,f,g,h,组成,各字母在电文中出现的频率分别为,5,25,3,6,10,11,36,4,。试为这 8 个字母,1）设计定长码；2）设计不等长 Huffman 编码,并给出该电文的总码数。,第四章 统计编码,对于定长编码,电文的总码数为3100300位,1,第四章 统计编码,Huffman 编码,2,第四章 统计编码,Huffman 编码,总码数(,4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4=257,),3,4.3,算术编码(,Arithmetic Coding,),一、问题的引入,假设某个字符的出现概率为 80%，该字符事实上只需要-log,2,(0.8)=0.322 位编码，但 Huffman 编码一定会为其分配一位 0 或一位 1 的编码。,难道真的能只输出 0.322 个 0 或 0.322 个 1 吗,？,4,4.3,算术编码(,Arithmetic Coding,),4.3.1 多元符号算术编码原理,4.3.2 自适应模型算术编码,4.3.3 二进制算术编码,4.3.4 二进制算术解码,4.3.5 算术编码评价,5,4.3,算术编码(,Arithmetic Coding,),它是一种非分组编码算法。它是从全序列出发，采用递推形式的连续编码。它不是将单个的信源符号映射成一个码字，而是将整个输入序列的符号依据它们的概率映射为实数轴上区间0 1)内的一个小区间，再在该小区间内选择一个代表性的二进制小数，作为实际的编码输出。,二、,算术编码,定义,例如算术编码对某条信息的输出为 1010001111，那么它表示小数 0.1010001111，也即十进制数 0.64。,6,4.3.1 多元符号算术编码,1)码字刷新：C(sa,i,)=C(s)+P(a,i,)A(s),2)区间刷新：A(sa,i,)=p(a,i,)A(s),设输入符号串s取自符号集S=a,1,a,2,a,3,a,m,，p(a,i,)=p,1,p,2,p,3,p,m,，s后跟符号a,i,扩展成符号串sa,i,，算术编码的迭代关系为:,符号累积概率：,初始条件：,一、,算术编码,7,4.3.1多元符号算术编码,当处理a,i,时，区间A(s)宽度根据a,i,出现概率p(a,i,)而变窄，符号序列越长，相应的子区间越窄，编码的位数越多。符号串每一步新扩展的码字C(sa,i,)都是由原符号串的码字C(s)与新区间宽度A(sa,i,)的算术相加，“算术码”由此得名。,算术编码在传输任何信号a,i,之前，信号的完整范围是,8,4.3.1多元符号算术编码,例题1：设某信源取自符号集S=a,b,c,d,e,!，!表示编码结束，各符号概率和初始子区间如下，设待编码的为“dead！”，编码器和解码器的初值区间0，1),表1,9,4.3.1多元符号算术编码,编码第一个字符,d,时,编码第二个字符,e,时,10,4.3.1多元符号算术编码,编码第三个字符,a,时,依此类推，结果如下表,11,最后在区间0.61804,0.6184)中任取一个代表性的小数，譬如0.6183，转化成二进制小数0.1001111，最后编码输出1001111。,12,4.3.1多元符号算术编码,编码,13,4.3.1多元符号算术编码,二、,算术解码,解码器首先输入符号及区间，重构,表1,.然后输入其余码字。比如第一个数字是“6”，解码器立即知道是形如0.6的数字。该数字位于d的子区间0.4,0.7)中，所以第一个符号就是d。然后从该数字中减去d子区间的低端值0.4，再除以d子区间宽度0.3，以消除符号d对码字的影响。结果是0.727667，告诉解码器下一个符号是e(因为e的子区间是0.7,0.9)。,14,为了从码字中消除符号x的影响，解码器执行,Code:=(Code-LowRange(x)/Range,的操作，Range是符号x的子区间宽度。表2总结了本例解码步骤。,字符,低码字,范围,d,0.6183-0.4=0.2183,/0.3=0.727667,e,0.727667-0.7=0.02767,/0.2=0.13835,a,0.13835-0=0.13835,/0.2=0.69175,d,0.69175-0.4=0.29175,/0.3=0.9725,!,解码结束,表2 算术解码过程,15,4.3.1多元符号算术编码,例2 假设信源符号为a,b,c,d，这些符号的概率分别为 0.1,0.4,0.2,0.3，对,输入消息序列cadacdb进行算术编码。,符号,a,b,c,d,概率,0.1,0.4,0.2,0.3,初始编码间隔,0,0.1),0.1,0.5),0.5,0.7),0.7,1),解：根据这些概率可把间隔0,1)分成4个子间 隔：0,0.1),0.1,0.5),0.5,0.7),0.7,1)。信息可综合在表中。,16,4.3.1多元符号算术编码,编码时首先输入的符号是c，找到它的编码范围是0.5,0.7)。由于消息中第二个符号a的编码范围是0,0.1)，因此它的间隔就取0.5,0.7)的第一个十分之一作为新间隔0.5,0.52)。依此类推，编码第3个符号d时取新间隔为0.514,0.52)，。消息的编码输出可以是,最后一个间隔中的任意数,。,17,4.3.1多元符号算术编码,18,4.3.2 自适应模型算术编码,一、自适应模型问题引入？,1,、,静态模型如何实现？,对信息 bccb 中只有两个字符，概率分布为 Pb=0.5，Pc=0.5。压缩中不必更新概率分布，每次区间的划分都按此分布。,19,4.3.2 自适应模型算术编码,2,、静态模型缺点（即,为什么用自适应模型？）,静态模型无法适应信息的多样性,必须消耗一定的空间保存静态模型统计出的概率分布,静态模型需要在压缩前对信息内字符的分布进行统计，这一统计过程将消耗大量的时间，使得本来就比较慢的算术编码压缩更加缓慢。,对较长的信息，静态模型统计出的符号概率是该符号在整个信息中的出现概率，而自适应模型可以统计出某个符号在某一局部的出现概率或某个符号相对于某一上下文的出现概率。,20,4.3.2 自适应模型算术编码,例1：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的信息为 bccb。,假设我们对 a b c 三者在信息中的出现概率一无所知（我们采用的是自适应模型），不妨设字符出现概率相等 Pa,Pb,Pc=1/3,1/3,1/3,二、自适应模型算术编码,21,4.3.2 自适应模型算术编码,Pa,Pb,Pc=1/3,1/3,1/3,Pa,Pb,Pc=1/4,2/4,1/4,第一个字符 为b,22,4.3.2 自适应模型算术编码,第二个字符 为c,接着出现 c，现在关注上一步中得到的 c 的区间 0.5834-0.6667。新添 c 后，三个字符的概率分布 Pa,Pb,Pc=1/5,2/5,2/5我们用这个概率分布划分区间 0.5834-0.6667,23,4.3.2 自适应模型算术编码,第三个字符 为c,划分 c 的区间 0.6334-0.6667：三个字符的概率分布为：Pa,Pb,Pc=1/6,2/6,3/6,24,4.3.2 自适应模型算术编码,最后一个字符b，不用再做进一步的划分了，上一步中得到的 b 的区间为 0.6390-0.6501，在这个区间内随便选择一个容易变成二进制的数，例如 0.64，将它变成二进制 0.1010001111，去掉前面没有太多意义的 0 和小数点，我们可以输出 1010001111。,第四个字符 为b,25,4.3.2 自适应模型算术编码,三、自适应算术编码如何解压缩呢？,解压缩之前我们仍设三个字符的概率相等，并得出第一幅分布图。先在二进制流数据前面加上 0 和小数点把它变成小数 0.1010001111，也就是十进制 0.64。发现 0.64 在分布图中落入字符 b 的区间内，我们立即输出字符 b，并得出三个字符新的概率分布。类似压缩时采用的方法，我们按照新的概率分布划分字符 b 的区间。在新的划分中0.64 落入了字符 c 的区间，则输出字符 c。同理类推，完成全部解压缩过程。,26,4.3.2 自适应模型算术编码,如何解压缩呢？,b,c,c,b,27,4.3.2 自适应模型算术编码,四、算术编码的精度？,算术编码实际上采用了化零为整的思想来表示小数个二进制位，我们无法精确表示单个小数位字符，但我们可以将许多字符集中起来表示，仅仅允许在最后一位有很小的误差。,我们每输入一个符号，都对概率的分布表做一下调整，并将要输出的小数限定在某个越来越小的区间范围内。,对输出区间的限定是问题的关键所在,。,28,4.3.3二进制算术编码,一、基本工作原理,设编码初始化子区间为0，1)MPS与LPS分配如图,大概率 Pe MPS（Most Probable Symbol）,小概率 Qe LPS（Least Probable Symbol）Pe=1-Qe,设置（C，A）,令,C=0 A=1,C 寄存器的值为子区域的起始位置,A 寄存器的值为子区域的宽度,29,30,例题1:设输入信源为11011111，对其编码,0为 LPS,Qe=（0.001）b;1为MPS,Pe=（0.111）b,初始状态：C=0,A=1,1)1 为MPS,C=C+AQe=0+1,0.001=0.001,A=APe=1,0.111,=0.111,4.3.3二进制算术编码,0.001,0.111,31,2)1 为MPS,C=C+AQe=,0.001,+0.111,0.001=0.001111,A=APe=0.111,0.111,=0.110001,0.001111,0.110001,4.3.3二进制算术编码,3)0 为LPS,C=C=,0.001111,;A=A Qe=0.110001,0.001,=0.000110001,0.001111,0.000110001,32,头 0.0101尾,传送码字为 0101,头 0.010001111110111100000001,+0.000011001001000010111111,尾 0.010101000111111111000000,编码过程,4.3.3 二进制算术编码,33,二进制解码：按 Qe Pe分成两个子区间，判断被解码的码字落在哪个区间，并赋予对应符号；,设 c=（0.0101）b 是被解码的值,初始值 A=1 Qe=0.001,当c落在0-QeA之间，解码符号为 D=0；,C=C；A=QeA；,当c落在Qe A-A之间，解码符号为D=1；,C=C-QeA；A=A（1-Qe）,4.3.4 二进制算术解码,34,1）C=0.0101 落在Qe A-A之间，解码符号为D=1,C=C-QeA=0.0101-0.001=0.0011 A=A（1-Qe）=0.111,2）C=0.0011 落在Qe A-A之间，解码符号为D=1,C=C-QeA=0.0011-0.000111=0.000101,A=A（1-Qe）=0.111,0.111=0.110001,3）C=0.000101 落在0-QeA之间，解码符号为D=0,C=C=0.000101 A=AQe=0.110001,0.001=0.000110001,4.3.4 二进制算术解码,35,算术解码原理图,36,4.3.5 算术编码评价,算术编码是一种非分组编码，编码方案众多，压缩效率最高。当信源符号概率接近时，建议用算术编码。,信源的每一个符号对应0，1）的一个子区间，该子区间的长度等于对应符号的出现的概率。,算术编码把信源X的任一给定序列和0，1）的一个子区间联系在一起，该子区间的长度等于这个序列的概率。,算术编码比霍夫曼编码复杂，需要缓冲存储器，硬件实现难；,比分组码的误差扩散更严重，要求有高质量的信道，或采用检错重发的方式；,概率大的符号对应区间大，描述所需比特少。随着输入序列长度增加，平均编码所用比特数趋向信源熵。,37,The end!See you later!,38,算术编码原理图,39,