清华大学多媒体课件 (34)

4.3.3 算术编码,原理： 算术编码方法是将被编码的信息表示成实 数0和1之间的一个间隔。信息越长编码表示它 的间隙就越小，表示这一间隙所须二进位就越 多，大概率符号出现的概率越大对应于区间愈 宽，可用长度较短的码字表示；小概率符号出 现概率越小层间愈窄，需要较长码字表示。,信息源中连续的符号根据某 一模式生成概率的大小来减少间 隔。可能出现的符号要比不太可能出现的符号减少范围少，因此只增加了较少的比特位。,1.Huffman 编码原理,对出现频率较高的码分配短码字； 对出现频率较低的码分配长码字。 JPEG提供了参考Huffman码表。,2.自适应二进制算术编码,（1）基本工作原理 设编码初始化子区间为0，1 MPS与LPS分配如图所示： 设 大概率 Pe MPS（Most Probable Symbol） 小概率 Qe LPS（Least Probable Symbol） Pe=1-Qe,Qe,Pe,编码时，设置两个专用寄存器（C，A） 初始时：令 C 寄存器的值为子区域的起始位置 A 寄存器的值为子区域的宽度 (该宽度恰好是已输入符号串的概率),初始化时：C=0 A=1 随着被编码数据源输入，C和A的内容按以下规律修正： 当低概率符号LPS到来时： C=C A=AQe 当高概率符号MPS到来时： C=C+AQe A=APe=A（1-Qe）,0 为LPS Qe= 1/8 =（0.001）b 1 为MPS Pe= 7/8 =（0.111）b 初始状态： C=0 子区间起始位置 A=1 子区域宽度,例: 对11011111进行算术编码,算术编码原理图 书p117,11011111 1) 1 为MPS C=C+AQe =0+1 0.001=0.001 A=APe=1 0.111 =0.111,0.001,0.111,0,1,11011111 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,0,1,11011111 3) 0 为LPS C=C=0.001111 A=A Qe = 0.110001 0.001 =0.000110001,0.001111,0.000110001,0,1,头 0.0101尾 传送码字为 0101 解码： 按 Qe Pe分成两个子区间，判断被解码的码字落在哪个区间，并赋予对应符号：,头 0.010001111110111100000001 间隔 0.000011001001000010111111 尾 0.010101000111111111000000,+,设 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）,设 c=（0.0101）b 是被解码的值 初始值 A=1 Qe=0.001,当C落在Qe A -A之间，解码符号为D=1； C=C-QeA； A=A（1-Qe）,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.1110.111=0.110001,3） C= 0.000101 落在0-QeA之间，解码符号为D=0 C=C=0.000101 A=AQe=0.1100010.001=0.000110001,当C落在0-QeA之间，解码符号为 D=0； C=C A=QeA ；,算术解码原理图,算术编码的特点：,(1). 不需要码表； (2). 当信源概率比较接近时，建议使用算术编码。 (3). JPEG成员对多幅图进行算术编码效率可以提高5%。 JPEG扩展系统用算术编码代替Huffman。,