算术编码在图像数据压缩标准(如JPEG,JBIG)中扮演了重要的角色.在算术编码中,消息用0到1之间的实数进行编码,算术编码用到两个基本的参数：符号的概率和它的编码间隔.信源符号的概率决定压缩编码的效率,也决定编码过程中信源符号的间隔,而这些间隔包含在0到1之间.编码过程中的间隔决定了符号压缩后的输出.算术编码器的编

　　码过程可用下面的例子加以解释.

　　[例4.2]假设信源符号为{00,01,10,11},这些符号的概率分别为{0.1,0.4,0.2,0.3},根据这些概率可把间隔[0,1)分成4个子间隔：[0,0.1),[0.1,0.5),[0.5,0.7),[0.7,1),其中表示半开放间隔,即包含不包含.上面的信息可综合在表4-04中

　　.

　　表4-04信源符号,概率和初始编码间隔

　　符号

　　00

　　01

　　10

　　11

　　概率

　　0.1

　　0.4

　　0.2

　　0.3

　　初始编码间隔

　　初始编码间隔

　　[0,0.1)

　　[0.1,0.5)

　　[0.5,0.7)

　　[0.7,1)

　　如果二进制消息序列的输入为：10001100101101.编码时首先输入的符号是10,

　　找到它的编码范围是[0.5,0.7).由于消息中第二个符号00的编码范围是[0,0.1),因

　　此它的间隔就取[0.5,0.7)的第一个十分之一作为新间隔[0.5,0.52).依此类推,编码

　　第3个符号11时取新间隔为[0.514,0.52),编码第4个符号00时,取新间隔为[0.514,0

　　.5146),….消息的编码输出可以是最后一个间隔中的任意数.整个编码过程如图4-0

　　3所示.

　　图4-03算术编码过程举例

　　这个例子的编码和译码的全过程分别表示在表4-05和表4-06中.根据上面所举的例子,

　　可把计算过程总结如下.

　　考虑一个有M个符号的字符表集,假设概率,而.输入符号用表示,第个子间隔的范围用

　　表示.其中,和,表示间隔左边界的值,表示间隔右边界的值,表示间隔长度.编码步

　　骤如下：

　　步骤1：首先在1和0之间给每个符号分配一个初始子间隔,子间隔的长度等于它的概率,

　　初始子间隔的范围用[,)表示.令,和.

　　步骤2：L和R的二进制表达式分别表示为：

　　和

　　其中和等于“1”或者“0”.

　　比较和：①如果,不发送任何数据,转到步骤3；②如果,就发送二进制符号.

　　比较和：①如果,不发送任何数据,转到步骤3；②如果,就发送二进制符号.

　　…

　　这种比较一直进行到两个符号不相同为止,然后进入步骤3,

　　步骤3：加1,读下一个符号.假设第个输入符号为,按照以前的步骤把这个间隔分成如

　　下所示的子间隔：

　　令,和,然后转到步骤2.

　　表4-05编码过程

　　步骤

　　输入

　　符号

　　编码间隔

　　编码判决

　　1

　　10

　　[0.5,0.7)

　　符号的间隔范围[0.5,0.7)

　　2

　　00

　　[0.5,0.52)

　　[0.5,0.7)间隔的第一个1/10

　　3

　　11

　　11

　　[0.514,0.52)

　　[0.5,0.52)间隔的最后一个1/10

　　4

　　00

　　[0.514,0.5146)

　　[0.514,0.52)间隔的第一个1/10

　　5

　　10

　　[0.5143,0.51442)

　　[0.514,0.5146)间隔的第五个1/10开始,二个1/10

　　6

　　11

　　[0.514384,0.51442)

　　[0.5143,0.51442)间隔的最后3个1/10

　　7

　　01

　　[0.5143836,0.514402)

　　[0.514384,0.51442)间隔的4个1/10,从第1个1/10开始

　　8

　　从[0.5143876,0.514402中选择一个数作为输出：0.5143876

　　表4-06译码过程

　　步骤

　　步骤

　　间隔

　　译码符号

　　译码判决

　　1

　　[0.5,0.7)

　　10

　　0.51439在间隔[0.5,0.7)

　　2

　　[0.5,0.52)

　　00

　　0.51439在间隔[0.5,0.7)的第1个1/10

　　3

　　[0.514,0.52)

　　11

　　0.51439在间隔[0.5,0.52)的第7个1/10

　　4

　　[0.514,0.5146)

　　00

　　0.51439在间隔[0.514,0.52)的第1个1/10

　　5

　　[0.5143,0.51442)

　　10

　　10

　　0.51439在间隔[0.514,0.5146)的第5个1/10

　　6

　　[0.514384,0.51442)

　　11

　　0.51439在间隔[0.5143,0.51442)的第7个1/10

　　7

　　[0.51439,0.5143948)

　　01

　　0.51439在间隔[0.51439,0.5143948)的第1个1/10

　　7

　　译码的消息：10001100101101

　　[例3]假设有4个符号的信源,它门的概率如表4-07所示：