算数编码、解码
1赞算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。
给定事件序列的算术编码步骤如下：
（1）编码器在开始时将“当前间隔” [ L， H) 设置为[0，1)。
（2）对每一事件，编码器按步骤（a）和（b）进行处理
（a）编码器将“当前间隔”分为子间隔，每一个事件一个。
（b）一个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择子间隔对应于下一个确切发生的事件相对应，并使它成为新的“当前间隔”。
（3）最后输出的“当前间隔”的下边界就是该给定事件序列的算术编码。
编码：
设Low和High分别表示“当前间隔”的下边界和上边界，CodeRange为当前编码间隔的长度，LowRange(symbol)和HighRange(symbol)分别代表为了事件symbol分配的初始间隔下边界和上边界。上述过程的实现可用伪代码描述如下：
set Low to 0
set High to 1
while there are input symbols do
take a symbol
CodeRange = High – Low
High = Low + CodeRange *HighRange(symbol)
Low = Low + CodeRange * LowRange(symbol)
end of while
output Low
解码：
算术码解码过程用伪代码描述如下：
get encoded number
do
find symbol whose range straddles the encoded number
output the symbol
range = symbo.LowValue – symbol.HighValue
substracti symbol.LowValue from encoded number
divide encoded number by range
until no more symbols
算术编码器的编码解码过程可用例子演示和解释。
例1：假设信源符号为{A， B， C， D}，这些符号的概率分别为{ 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]，其中[x，y]表示半开放间隔，即包含x不包含y。上面的信息可综合在表03-04-1中。
表03-04-1 信源符号，概率和初始编码间隔
符号 A B C D
概率 0.1 0.4 0.2 0.3
初始编码间隔 [0， 0.1) [0.1， 0.5) [0.5， 0.7) [0.7， 1]
如果二进制消息序列的输入为：C A D A C D B。编码时首先输入的符号是C，找到它的编码范围是[0.5，0.7]。
High = Low（0） + CodeRange（1）*HighRange(symbol)（0.5）
Low = Low（0） + CodeRange（1） * LowRange(symbol)（0.7）
由于消息中第二个符号A的编码范围是[0， 0.1]，因此它的间隔就取[0.5， 0.7]的第一个十分之一作为新间隔[0.5，0.52]。
High = Low（0.5） + CodeRange（0.2）*HighRange(symbol)（0）
Low = Low（0.5） + CodeRange（0.2） * LowRange(symbol)（0.1）
依此类推，编码第3个符号D时取新间隔为[0.514， 0.52]，
High = Low（0.5） + CodeRange（0.02）*HighRange(symbol)（0.7）
Low = Low（0.5） + CodeRange（0.02） * LowRange(symbol)（1）
编码第4个符号A时，取新间隔为[0.514， 0.5146]，…。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如图03-04-1所示。
图03-04-1 算术编码过程举例
这个例子的编码和译码的全过程分别表示在表03-04-2和表03-04-3中。
表03-04-2 编码过程
从[0.5143876， 0.514402]中选择一个数作为输出：0.5143876
表03-04-3 译码过程
解码： 0.5<0.51439 <0.7 输出c
0 <{(0.51439-0.5)/(0.7-0.5)=0.07195}<0.1 输出a
0.7<{(0.07195-0)/(0.1-0)=0.7195}<1 输出d
以此类推；
在上面的例子中，我们假定编码器和译码器都知道消息的长度，因此译码器的译码过程不会无限制地运行下去。实际上在译码器中需要添加一个专门的终止符，当译码器看到终止符时就停止译码。
在算术编码中有几个问题需要注意：
·由于实际的计算机的精度不可能无限长，一个明显的问题是运算中出现溢出，但多数机器都有16、32或者64位的精度，因此这个问题可使用比例缩放方法解决。
·算术编码器对整个消息只产生一个码字，这个码字是在间隔[0，1]中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。
·算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。
算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地 进行修改，在编码期间估算信源符号概率的过程叫做建模。需要开发动态算术编码的原因是因为事先知道精确的信源概率是很难的，而且是不切实际的。当压缩消息 时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为确定编码器压缩效率的关键。
此外，在算术编码的使用中还存在版权问题。JPEG标准说明的算术编码的一些变体方案属于IBM， AT&T和Mitsubishi拥有的专利。要合法地使用JPEG算术编码必须得到这些公司的许可。
C源码;
1. clc,clear all;
2. symbol=['abc'];
3. pr=[0.4 0.4 0.2]; %各字符出现的概率
4. temp=[0.0 0.4 0.8 1.0];
5. orignal=temp;
6. in=input('input a string of abc:');
7. n=length(in);
8. %编码
9. for i=1:n
10. width=temp(4)-temp(1);
11. w=temp(1);
12. switch in(i)
13. case 'a'
14. m=1;
15. case 'b'
16. m=2;
17. case 'c'
18. m=3;
19. otherwise
20. error('do not input other character');
21. end
22. temp(1)=w+orignal(m)*width;
23. temp(4)=w+orignal(m+1)*width;
24. left=temp(1);
25. right=temp(4);
26. fprintf('left=%.6f',left);
27. fprintf(' ');
28. fprintf('right=%.6f\n',right);
29. end
30. encode=(temp(1)+temp(4))/2
31. %解码
32. decode=['0'];
33. for i=1:n
34. fprintf('tmp=%.6f\n',encode);
35. if(encode>=orignal(1)& encode<orignal(2))
36. decode(i)='a';
37. t=1;
38. elseif(encode>=orignal(2)& encode<orignal(3))
39. decode(i)='b';
40. t=2;
41. else
42. decode(i)='c';
43. t=3;
44. end
45. encode=(encode-orignal(t));
46. encode=encode/pr(t);
47. end
48. decode
