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