《信息论与编码基础》课件 16算术编码

§6.2算术编码§6压缩编码方法1.引入2.编码3.解码4.讨论§6.2算术编码1.引入单符号变长编码:平均码长>=H是否有压缩方法，其编码平均码长可达到（趋向）信源熵？§6.2算术编码1.引入单符号变长编码（Huffman编码）码长取整数P=0.9，对应的理想码长应为log(1/0.9)=0.152位

21bit/0.152bit=6.58倍§6.2算术编码1.引入码长取小数？扩展信源编码K^N,K:信源字母表大小N:扩展块大小最好：N->§6.2算术编码1.引入1.00初始概率区间：0.50.750.875a1a2a3a4a1:0.5,a2:0.25,a3:0.125,a4:0.125一个例子：扩展信源下的概率区间：复杂1.00概率区间：0.50.750.875a1a1a1a2a1a3a1a4§6.2算术编码1.引入PeterElias1923~2001享年78岁Elias编码§6.2算术编码发展史Shannon,1948,MathematicaltheoryofcommunicationPeterElias,1963之前,私人通信;NAbramson,1963,Informationtheoryandcoding,NewYork:McGraw-Hill.p61.Elias码的第一次公开发表;Jorma

Rissanen,1976,杂志;RichardPasco,1976,博士论文,StanfordUniversity;Witten,ClearyandNeal,1987,NewZealand§6.2算术编码2.编码扩展信源编码：复杂能否只针对所出现的待编码的字符串编码？§6.2算术编码编码概率区间1：a1a3概率区间2：此小区间和待编码信源唯一地对应1.000.50.750.875a2概率区间0：a1:0.5,a2:0.25,a3:0.125,a4:0.125待编码信源：a2a1a3...一个例子：1.00初始概率区间：0.50.750.875a1a2a3a4仿照shannon码，检讨各步骤字符串

概率小区间的嵌套收缩是否需要对字符串的“联合概率”排序？是否限定对概率小区间的左端点编码？编码码长？－》shannon码的思路§6.2算术编码编码编码码长证明：编码的平均码长，可以趋向于信源熵注意符号的两套体系：字母表（标号）体系、字符串（时间）体系§6.2算术编码编码问题：位长不足字符串

概率小区间的嵌套收缩概率小区间的长度会很小处理位长不足以支持§6.2算术编码编码处理位长不足的例子“this$is$his$hat$is$it$his$hat$”字母表：A={ahist$}；出现频率：{256548}/30概率区间的划分：

ahist$0.0670.1670.2000.1670.1330.267[0,0.067，0.233，0.433，0.600,0.733,1.000]§6.2算术编码编码6位十进制symboll_nr_nd_nt0.6000000.7333330.133333h0.6088890.6311110.022222i0.6140740.6185190.004444s0.6160000.6167410.000741$0.6165430.6167410.000198i0.6165890.6166290.000040s0.6166060.6166130.000007$0.6166110.6166130.000002h0.6166110.6166120.000000

i0.6166110.6166120.000000s0.6166110.6166110.000000$0.6166110.6166110.000000……处理位长不足的例子§6.2算术编码编码§6.2算术编码编码处理位长不足的例子用20位十进制$0.616611490525855177000.616611490525855288000.00000000000000011102h0.616611490525855177000.616611490525855177000.00000000000000000000§6.2算术编码编码Symboll_nr_nd_nt0.6000000.7333330.133333h0.6088890.6311110.022222i0.6140740.6185190.004444s0.6160000.6167410.000741$ 0.6165430.6167410.000198i 0.6165890.6166290.000040s 0.6166060.6166130.000007$ 0.6166110.6166130.000002h 0.6166110.6166120.000000i 0.6166110.6166120.000000s 0.6166110.6166110.000000$ 0.6166110.6166110.000000……6位十进制问题：位长不足§6.2算术编码编码第二个时刻’th’l=0.608889r=0.631111r=0.311110l=0.088890左移一位，保持纯小数“位长不足”问题的解决§6.2算术编码编码获得当前小区间后，考察概率小区间左、右端点，从最高有效位开始，一旦发现两者的高有效位匹配，就发送之；概率小区间左、右端点随之而变，留出最低有效位给以后的计算所需要的精度。“位长不足”问题的解决§6.2算术编码编码增量输出小区间的扩展固定的有限精度的处理§6.2算术编码2.编码两个实际问题运算位长定点化算术编码基本思路信源单符号，概率；信源符号流，联合概率；用概率区间表达为概率区间的嵌套收缩；标识概率小区间位置，取概率小区间中的点编码输出；浮点值定点化，定点值输出；但处理不可能获得无限精度；在概率小区间左右端点值的高位相同时，放大概率小区间。§6.2算术编码编码§6.2算术编码编码算术编码的基本步骤1划分初始区间；2读入信源符号，在当前概率小区间上，得到嵌套收缩的新的概率小区间；3检查是否输出比特，小区间是否扩展；4回到2；§6.2算术编码2.编码例子a1:0.5,a2:0.25,a3:0.125,a4:0.125编码：a2a1a3...对照Huffman的情况§6.2算术编码2.编码例子2“this$is$his$hat$is$it$his$hat$”采用16bits精度，信源符号分布概率采取统计法

当编码完成后，输出73bits

30个字符，压缩后速率为2.433bits/symbol

Huffman编码需要2.53bit/symbol

信源熵2.483bits/symbol§6.2算术编码2.编码例子2“this$is$his$hat$is$it$his$hat$”Huffman编码需要2.53bit/symbol

信源熵2.483bits/symbol考虑剩余小区间尚需2bits编码，于是压缩后速率为2.500

bit/symbol

§6.2算术编码§6压缩编码方法1.引入2.编码3.解码

4.讨论§6.2算术编码3.解码先不考虑编码的“定点化、固定精度”，先考虑原理性编码（Elias码）所对应的解码。

§6.2算术编码3.解码字母表：A={ahist$}；概率：{256548}/30接收到码字0.616611490525…

概率区间的划分：

ahist$0.0670.1670.2000.1670.1330.267[0,0.067，0.233，0.433，0.600,0.733,1.000]§6.2算术编码3.解码第1拍的解码：容易code=0.616611490525…属于[0.600000,0.733333)区间，为‘t’

ahist$[0,0.067，0.233，0.433，0.600,0.733,1.000]§6.2算术编码3.解码第2拍code=0.616611490525…

ahist$[0,0.067，0.233，0.433，0.600,0.733,1.000]在前一时刻的字符（串）是“t”、即前一时刻的小区间是[0.600,0.733)的基础上，再进行小区间划分、数值位置的判断？否§6.2算术编码3.解码l(n)<=code(n)<r(n)c(i-1)<=[code(n)-l(n-1)]/d(n-1)<c(i)当前时刻的信息，被之前的信息“遮蔽”了希望去除之前的信息，只留下当前时刻的信息S(n)=[code(n)-l(n-1)]/d(n-1)§6.2算术编码3.解码第2拍code=0.616611490525…

ahist$[0,0.067，0.233，0.433，0.600,0.733,1.000]S=(code-0.6)/0.1333=0.1246属于[0.067,0.23)区间，为‘h’§6.2算术编码3.解码解码器的工作：(1) 保持状态（包括小区间左右端点、当前输入码字值）和编码器一致；(2) 码字值的转换、搜索；§6.2算术编码3.解码再考虑编码的“定点化、固定精度”等操作，解码端跟随之，即可。§6.2算术编码算术解码的基本步骤§6.2算术编码3.解码