算术编码 | 学习笔记

开发者学堂课程【高校精品课-华中科技大学 -智能媒体计算：算术编码】学习笔记，与课程紧密联系，让用户快速学习知识。

课程地址：https://developer.aliyun.com/learning/course/811/detail/15684

算术编码

内容介绍：

一、算数编码思想

二、算数编码过程举例

三、算术编码需要注意的几个问题

一、算数编码思想

1. 算术编码在图像数据压缩标准(如 JPEG)中扮演了重要的角色

在图像压缩中只用一个实数表示，用0和1中的一个小数表示信源的符号，例如颜色值或者声音的样本。

其可以大幅度的压缩数据量，所以使用算数编码的压缩比很高

2.在算术编码中，消息用0到1之间的实数进行编码，算术编码用到两个基本的参数

（1）符号概率

（2）编码间隔

3.注意

编码的间隔取决于符号概率。

二、算数编码过程举例

例1：

假设信源符号为{00,01,10,11}，这些符号的概率分别为{0.1,0.4,0.2,0.3 }

根据这些概率可把间隔[0,1)分成4个子间隔:

[0,0.1)∶间隔为0.1

[0.1,0.5)∶间隔为0.4

[0.5,0.7)∶间隔为0.2

[0.7,1)：间隔为0.3

区间的间隔是概率值，可以用两个二进制表示，算数编码是用编码间隔去找到0到1之间的数。

先按照间隔将其分为4份，信源符号、概率和初始编码间隔的表格如下：

间隔图如下：

第一个符号为10

[0.5,0.7)是10，将[0.5,0.7)作为一个整体，将该区间进行分割，等比例的划分成4个区间，计算时可以将其分为10份。0.5到0.7的间隔是0.2，除以10为0.02，前面第一个编码空间占1份，也就是0.5到0.52，依此类推，可以把这4个区间开始和结束的值计算出来.

第二个符号为00

00位于该区间的第一段，区间为0.5到0.52，可以再将该区间等比例划分为4个。

第三个符号为11

区间为0.514到0.52，继续输入符号00，然后等比例分割，区间为0.5146到0.514。继续输入符号10，是从下面开始数的第三个子区间，然后等比例放大，区间为0.51442到0.5143.下一个为11，继续等比例分割，区间就为0.514384到0.51442。下一个符号为01，继续等比例分割，区间为0.5143876到0.514402.

假设将所有数编完了，输出的数，就是把该空间的上下两个数选择一个，通常选下面的这个为0.5143876作为前面编码的算数编码。

如下图：

也就是输入10 00 11 00 10 11 01用小数0.5143876表示。

如果还要输入，则继续按照前面的分割，结果是越后编码的数量越多，小数点后的位数越长。在 不影响区间的情况下可以适当的进行四舍五入，但是不能改变区间。

算数解码过程如下表格：

所以译码的过程是编码的过程反过来。

三、算术编码需要注意的几个问题

1. 由于实际的计算机精度不可能无限长，运算中会出现溢出问题

（1）多数机器都有16位、32位或者64位的精度

（2）可使用比例缩放方法解决

（目前多数计算机都有16位、32位，普遍都是64位，所以很大程度上避免了溢出出现的概率，但是将8k的图像整个的用算数编码编是不可能的，算数编码是把一幅图像划分一小块一小块的，例如8*8，现在变成了4*4的，甚至还有2*2的小块，2*2也就是4个像素，8*8也就是64个像素，随着小块的数量是有限的，溢出的问题会得到很好的解决）

还可以通过比例的缩放来解决溢出的问题，但是溢出本身从算数编码的方法来说是存在的。

2.算术编码器对整个消息只产生一个码字（在间隔[O，1)中的一个实数）,因此译码器在接收到表示这个实数的所有位之前不能进行译码

（1）一种对错误很敏感的编码方法（这时需要加一些错误保护）

（2）如果有一位发生错误就会导致整个消息译错