算术编码统计编码.ppt

第四章第四章 统计编码统计编码  讲课内容：讲课内容：4. 1.      基本原理基本原理4. 2.      霍夫曼编码霍夫曼编码4. 3.      算术编码算术编码4. 4.       LZW编码编码 1【【【【例题例题例题例题】】】】假定用于通信的电文仅由假定用于通信的电文仅由假定用于通信的电文仅由假定用于通信的电文仅由 8  8 个字母个字母个字母个字母   a,b,c,d,e,f,g, ha,b,c,d,e,f,g, h组成组成组成组成,  , 各字母在电文中出现的频各字母在电文中出现的频各字母在电文中出现的频各字母在电文中出现的频率分别为率分别为率分别为率分别为   5 5,  , 2525,  , 3 3,  , 6 6,  , 1010,  , 1111,  , 3636,  , 4 4试为这 8  8 个字母个字母个字母个字母   1   1）设计定长码；）设计定长码；）设计定长码；）设计定长码；   2   2））））   设计不等长设计不等长设计不等长设计不等长 Huffman  Huffman 编码编码编码编码,  , 并给出该电文的总码数并给出该电文的总码数。

并给出该电文的总码数并给出该电文的总码数第四章第四章 统计编码统计编码对于定长编码对于定长编码对于定长编码对于定长编码,  , 电文的总码数为电文的总码数为电文的总码数为电文的总码数为3×1003×100＝＝＝＝300300位位位位 2第四章第四章 统计编码统计编码Huffman 编码编码3第四章第四章 统计编码统计编码Huffman Huffman 编码编码编码编码总码数总码数总码数总码数(  ( 4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + 3 * 10 +  3 * 11 + 2 * 36 + 4 * 4 = 2574 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + 3 * 10 +  3 * 11 + 2 * 36 + 4 * 4 = 257) )44.3 4.3 算算术编码术编码(Arithmetic Coding ) 一、问题的引入一、问题的引入 假假设设某某个个字字符符的的出出现现概概率率为为 80%，，该该字字符符事事实实上上只只需需要要 -log2(0.8) = 0.322 位位编编码码，，但但 Huffman 编码一定会为其分配一位编码一定会为其分配一位 0 或一位或一位 1 的编码。

的编码 难难道道真真的的能能只只输输出出 0.322 个个 0 或或 0.322 个个 1 吗吗？？54.3 4.3 算算术编码术编码(Arithmetic Coding ) 4.3.1 多元符号算术编码原理多元符号算术编码原理 4.3.2 自适应模型算术编码自适应模型算术编码 4.3.3 二进制算术编码二进制算术编码 4.3.4 二进制算术解码二进制算术解码 4.3.5 算术编码评价算术编码评价64.3 4.3 算算术编码术编码(Arithmetic Coding )它是一种非分组编码算法它是从全序列出发，采用递推形它是一种非分组编码算法它是从全序列出发，采用递推形式的连续编码它不是将单个的信源符号映射成一个码字，式的连续编码它不是将单个的信源符号映射成一个码字，而是将整个输入序列的符号依据它们的概率映射为实数轴上而是将整个输入序列的符号依据它们的概率映射为实数轴上区间区间[0 1)[0 1)内的一个小区间，再在该小区间内选择一个代表性内的一个小区间，再在该小区间内选择一个代表性的二进制小数，作为实际的编码输出的二进制小数，作为实际的编码输出 二、二、算术编码算术编码定义定义例如算术编码对某条信息的输出为例如算术编码对某条信息的输出为 1010001111，那么它表，那么它表示小数示小数 0.1010001111，也即十进制数，也即十进制数 0.64。

7 4.3.1 4.3.1 多元符号算术编码多元符号算术编码1)码字刷新：码字刷新：C(sai)=C(s)+P(ai)A(s)2)区间刷新：区间刷新：A(sai)=p(ai)A(s) 设输入符号串设输入符号串s取自符号集取自符号集S={a1,a2,a3,…,am}，， p(ai)={p1,p2,p3,…,pm}，，s后跟符号后跟符号ai扩展成符号串扩展成符号串sai，算，算术编码的迭代关系为术编码的迭代关系为: 符号累积概率：符号累积概率：初始条件：初始条件： 一、一、算术编码算术编码8 4.3.14.3.1多元符号算术编码多元符号算术编码当处理当处理ai时，区间时，区间A(s)宽度根据宽度根据ai出现概率出现概率p(ai)而而变窄，符号序列越长，相应的子区间越窄，编码的变窄，符号序列越长，相应的子区间越窄，编码的位数越多符号串每一步新扩展的码字位数越多符号串每一步新扩展的码字C(sai)都是都是由原符号串的码字由原符号串的码字C(s)与新区间宽度与新区间宽度A(sai)的算术的算术相加，相加，“算术码算术码”由此得名由此得名算术编码在传输任何信号算术编码在传输任何信号ai之前，信号的完整范围是之前，信号的完整范围是94.3.14.3.1多元符号算术编码多元符号算术编码例例题题1：：设设某某信信源源取取自自符符号号集集S={a,b,c,d,e,!}，，!表表示示编编码码结结束束，，各各符符号号概概率率和和初初始始子子区区间间如如下下，，设设待待编编码码的为的为“dead！！”，编码器和解码器的初值区间，编码器和解码器的初值区间[0，，1)表表1104.3.14.3.1多元符号算术编码多元符号算术编码编码第一个字符编码第一个字符d时时编码第二个字符编码第二个字符e时时 114.3.14.3.1多元符号算术编码多元符号算术编码编码第三个字符编码第三个字符a时时 依此类推，结果如下表依此类推，结果如下表 12最后在区间最后在区间[0.61804,0.6184)中任取一个代中任取一个代表性的小数，譬如表性的小数，譬如0.6183，转化成二进制，转化成二进制小数小数0.1001111，最后编码输出，最后编码输出1001111。

134.3.14.3.1多元符号算术编码多元符号算术编码编码144.3.14.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))15为了从码字中消除符号为了从码字中消除符号x的影响，解码器执行的影响，解码器执行                  Code:=(Code-LowRange(x))/Range的操作，的操作，Range是符号是符号x的子区间宽度表的子区间宽度表2总结了本例解码步骤。

总结了本例解码步骤字符字符低码字低码字范围范围d0.6183-0.4=0.2183/0.3=0.727667e0.727667-0.7=0.02767/0.2=0.13835a0.13835-0=0.13835/0.2=0.69175d0.69175-0.4=0.29175/0.3=0.9725!解码结束解码结束表表2 算术解码过程算术解码过程164.3.14.3.1多元符号算术编码多元符号算术编码 [ [例例2] 2] 假假设设信信源源符符号号为为{a, {a, b, b, c, c, d}d}，，这这些些符符号号的的概概率率分分别别为为{ { 0.1, 0.1, 0.4, 0.4, 0.2, 0.2, 0.3 0.3 } }，，对对输输入入消消息息序列序列cadacdb进行算术编码进行算术编码符号符号abcd 概率概率0.10.40.20.3 初始初始编码间编码间隔隔[0, 0.1)[0.1, 0.5)[0.5, 0.7)[0.7, 1) 解：根据这些概率可把间隔解：根据这些概率可把间隔[0, 1)[0, 1)分成分成4 4个子间个子间 隔：隔：[0, 0.1), [0.1, 0.5), [0.5, 0.7), [0, 0.1), [0.1, 0.5), [0.5, 0.7), [0.7, 1) [0.7, 1) 。

信息可综合在表中信息可综合在表中174.3.14.3.1多元符号算术编码多元符号算术编码编码时首先输入的符号是编码时首先输入的符号是编码时首先输入的符号是编码时首先输入的符号是c c c c，找到它的编码范围，找到它的编码范围，找到它的编码范围，找到它的编码范围是是是是[0.5, 0.7)[0.5, 0.7)[0.5, 0.7)[0.5, 0.7)由于消息中第二个符号由于消息中第二个符号由于消息中第二个符号由于消息中第二个符号a a a a的编码的编码的编码的编码范围是范围是范围是范围是[0, 0.1)[0, 0.1)[0, 0.1)[0, 0.1)，因此它的间隔就取，因此它的间隔就取，因此它的间隔就取，因此它的间隔就取[0.5, 0.7)[0.5, 0.7)[0.5, 0.7)[0.5, 0.7)的第一个十分之一作为新间隔的第一个十分之一作为新间隔的第一个十分之一作为新间隔的第一个十分之一作为新间隔[0.5, 0.52)[0.5, 0.52)[0.5, 0.52)[0.5, 0.52)依此类推，编码第此类推，编码第此类推，编码第此类推，编码第3 3 3 3个符号个符号个符号个符号d d d d时取新间隔为时取新间隔为时取新间隔为时取新间隔为[0.514, [0.514, [0.514, [0.514, 0.52)0.52)0.52)0.52)，，，，… … … … 。

消息的编码输出可以是消息的编码输出可以是消息的编码输出可以是消息的编码输出可以是最后一个间最后一个间最后一个间最后一个间隔中的任意数隔中的任意数隔中的任意数隔中的任意数   184.3.14.3.1多元符号算术编码多元符号算术编码194.3.2 自适应模型算术编码自适应模型算术编码 一、自适应模型问题引入？一、自适应模型问题引入？ 1 1 1 1、、、、静静静静态态模型如何模型如何模型如何模型如何实现实现？？？？ 对对对对信信信信息息息息 bccb bccb bccb bccb 中中中中只只只只有有有有两两两两个个个个字字字字符符符符，，，，概概概概率率率率分分分分布布布布为为为为 Pb Pb Pb Pb = = = = 0.50.50.50.5，，，，Pc Pc Pc Pc = = = = 0.50.50.50.5压压压压缩缩缩缩中中中中不不不不必必必必更更更更新新新新概概概概率率率率分分分分布布布布，，，，每每每每次次次次区区区区间间间间的的的的划划划划分分分分都都都都按按按按此此此此分分分分布204.3.2 自适应模型算术编码自适应模型算术编码2 2 2 2、静态模型缺点（即、静态模型缺点（即、静态模型缺点（即、静态模型缺点（即为为什么用自适什么用自适什么用自适什么用自适应应模型？）模型？）模型？）模型？）①①①①静静静静态态模型无法适模型无法适模型无法适模型无法适应应信息的多信息的多信息的多信息的多样样性性性性 必必必必须须消耗一定的空消耗一定的空消耗一定的空消耗一定的空间间保存静保存静保存静保存静态态模型模型模型模型统计统计出的概率分布出的概率分布出的概率分布出的概率分布 ②②②②静静静静态态态态模模模模型型型型需需需需要要要要在在在在压压压压缩缩缩缩前前前前对对对对信信信信息息息息内内内内字字字字符符符符的的的的分分分分布布布布进进进进行行行行统统统统计计计计，，，，这这这这一一一一统统统统计计计计过过过过程程程程将将将将消消消消耗耗耗耗大大大大量量量量的的的的时时时时间间间间，，，，使使使使得得得得本本本本来来来来就就就就比比比比较较较较慢慢慢慢的的的的算算算算术术术术编编编编码码码码压压压压缩缩缩缩更更更更加加加加缓慢。

缓慢③③③③对对对对较较较较长长长长的的的的信信信信息息息息，，，，静静静静态态态态模模模模型型型型统统统统计计计计出出出出的的的的符符符符号号号号概概概概率率率率是是是是该该该该符符符符号号号号在在在在整整整整个个个个信信信信息息息息中中中中的的的的出出出出现现现现概概概概率率率率，，，，而而而而自自自自适适适适应应应应模模模模型型型型可可可可以以以以统统统统计计计计出出出出某某某某个个个个符符符符号号号号在在在在某某某某一一一一局局局局部部部部的的的的出现概率或某个符号相对于某一上下文的出现概率出现概率或某个符号相对于某一上下文的出现概率出现概率或某个符号相对于某一上下文的出现概率出现概率或某个符号相对于某一上下文的出现概率 214.3.2 自适应模型算术编码自适应模型算术编码例例1：考虑某条信息中可能出现的字符仅有：考虑某条信息中可能出现的字符仅有 a b c 三三种，我们要压缩保存的信息为种，我们要压缩保存的信息为 bccb假设我们对假设我们对 a b c 三者在信息中的出现概率一无所知三者在信息中的出现概率一无所知（我们采用的是自适应模型），不妨设字符出现概（我们采用的是自适应模型），不妨设字符出现概率相等率相等 {Pa, Pb, Pc} = {1/3, 1/3, 1/3}二、自适应模型算术编码二、自适应模型算术编码224.3.2 自适应模型算术编码自适应模型算术编码{Pa, Pb, Pc} = {1/3, 1/3, 1/3}{Pa, Pb, Pc} = {1/4, 2/4, 1/4}第一个字符第一个字符 为为b234.3.2 自适应模型算术编码自适应模型算术编码第二个字符第二个字符 为为c接着出现接着出现 c，现在关注上，现在关注上一步中得到的一步中得到的 c 的区间的区间 0.5834 - 0.6667。

新添新添 c 后，三个字符的概率分布后，三个字符的概率分布 {Pa, Pb, Pc} = {1/5, 2/5, 2/5}我们用这个概率分布我们用这个概率分布划分区间划分区间 0.5834 - 0.6667244.3.2 自适应模型算术编码自适应模型算术编码第三个字符第三个字符 为为c划划分分 c 的的区区间间 0.6334 - 0.6667：：三三个个字字符符的的概概率率分分布布为为：： {Pa, Pb, Pc} = {1/6, 2/6, 3/6}254.3.2 自适应模型算术编码自适应模型算术编码最后一个字符最后一个字符b ，不用再做进一步的，不用再做进一步的划分了，上一步中得到的划分了，上一步中得到的 b 的区间为的区间为 0.6390 - 0.6501，在这个区间内随便选，在这个区间内随便选择一个容易变成二进制的数，例如择一个容易变成二进制的数，例如 0.64，将它变成二进制，将它变成二进制 0.1010001111，，去掉前面没有太多意义的去掉前面没有太多意义的 0 和小数点，和小数点，我们可以输出我们可以输出 1010001111 第四个字符第四个字符 为为b264.3.2 自适应模型算术编码自适应模型算术编码 三、自适应算术编码如何解压缩呢？三、自适应算术编码如何解压缩呢？ 解解压压缩缩之之前前我我们们仍仍设设三三个个字字符符的的概概率率相相等等，，并并得得出出第第一一幅幅分分布布图图。

先先在在二二进进制制流流数数据据前前面面加加上上 0 和和小小数数点点把把它它变变成成小小数数 0.1010001111，，也也就就是是十十进进制制 0.64发发现现 0.64 在在分分布布图图中中落落入入字字符符 b 的的区区间间内内，，我我们们立立即即输输出出字字符符 b，，并并得得出出三三个个字字符符新新的的概概率率分分布布类类似似压压缩缩时时采采用用的的方方法法，，我我们们按按照照新新的的概概率率分分布布划划分分字字符符 b 的的区区间间在在新新的的划划分分中中0.64 落落入入了了字字符符 c 的的区区间间，，则则输输出出字字符符 c同理类推，完成全部解压缩过程同理类推，完成全部解压缩过程 274.3.2 自适应模型算术编码自适应模型算术编码 如何解压缩呢？如何解压缩呢？b③ ccb284.3.2 自适应模型算术编码自适应模型算术编码 四、算术编码的精度？四、算术编码的精度？ 算算术术编编码码实实际际上上采采用用了了化化零零为为整整的的思思想想来来表表示示小小数数个个二二进进制制位位，，我我们们无无法法精精确确表表示示单单个个小小数数位位字字符符，，但但我我们们可可以以将将许许多多字字符符集集中中起起来来表表示示，，仅仅仅仅允允许许在在最最后后一一位位有有很很小的误差。

小的误差 我我们们每每输输入入一一个个符符号号，，都都对对概概率率的的分分布布表表做做一一下下调调整整，，并并将将要要输输出出的的小小数数限限定定在在某某个个越越来来越越小小的的区区间间范范围围内内对输出区间的限定是问题的关键所在对输出区间的限定是问题的关键所在294.3.34.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 寄存器的值为子区域的宽度寄存器的值为子区域的宽度3031例题例题1:设输入信源为设输入信源为11011111 ，对其编码，对其编码0为为 LPS,Qe= （（0.001））b;1为为MPS,Pe=（（0.111））b初始状态：初始状态：C=0, A=11) 1 为为MPS C=C+AQe =0+1  0.001=0.001 A=APe=1  0.111 =0.1114.3.34.3.3二进制算术编码二进制算术编码0.0010.11132 2) 1 为MPS C=C+AQe = 0.001 + 0.111 0.001=0.001111 A=APe= 0.111 0.111 =0.1100010.0011110.1100014.3.34.3.3二进制算术编码二进制算术编码3) 0 为LPS C=C=0.001111 ; A=A Qe = 0.110001 0.001=0.0001100010.0011110.00011000133 头头 <0.0101<尾尾 传送码字为传送码字为 0101头头   0.010001111110111100000001+     0.000011001001000010111111尾尾   0.010101000111111111000000编码过程4.3.3 4.3.3 二进制算术编码二进制算术编码34二进制解码：按二进制解码：按 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 4.3.4 二进制算术解码二进制算术解码351）） C’=0.0101      落在落在Qe A -A之间，解码符号为之间，解码符号为D=1       C’=C’-QeA=0.0101-0.001=0.0011    A=A（（1-Qe））=0.1112）） 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 4.3.4 二进制算术解码二进制算术解码36算算术术解解码码原原理理图图374.3.5 4.3.5 算术编码评价算术编码评价算术编码是一种非分组编码，编码方案众多，压缩效率最高。

算术编码是一种非分组编码，编码方案众多，压缩效率最高当信源符号概率接近时，建议用算术编码当信源符号概率接近时，建议用算术编码信源的每一个符号对应信源的每一个符号对应[0，，1）的一个子区间，该子区间的）的一个子区间，该子区间的长度等于对应符号的出现的概率长度等于对应符号的出现的概率 算术编码把信源算术编码把信源X的任一给定序列和的任一给定序列和[0，，1）的一个子区间）的一个子区间联系在一起，该子区间的长度等于这个序列的概率联系在一起，该子区间的长度等于这个序列的概率 算术编码比霍夫曼编码复杂，需要缓冲存储器，硬件实现难；算术编码比霍夫曼编码复杂，需要缓冲存储器，硬件实现难； 比分组码的误差扩散更严重，要求有高质量的信道，或采比分组码的误差扩散更严重，要求有高质量的信道，或采用检错重发的方式；用检错重发的方式； 概率大的符号对应区间大，描述所需比特少随着输入序概率大的符号对应区间大，描述所需比特少随着输入序列长度增加，平均编码所用比特数趋向信源熵列长度增加，平均编码所用比特数趋向信源熵 38The end! See you later! 39算术编码原理图40。