信息论算术编码

第五章信源编码算术编码信源编码无失真信源编码限失真信源编码(常用)变长编码定理—最佳变长编码定长编码定理游程编码算术编码预测编码变换编码矢量量化哈夫曼编码方法费诺编码方法香农编码方法算术编码简介是非分组码的编码方法之一。它是从全序列出发，考虑符号间的依赖关系，即考虑符号间的相关性。经香农—费诺—哈夫曼编码推广而来的，直接对信号源符号序列进行编码输出。即时码，信源符号序列对应的累计概率区间是不重叠的。肯定也可以唯一译码。算术编码编码的基本思路：从全序列出发，将各信源序列的概率影射到[0，1]区间上，使每个序列对应这区间内的一点，也就是一个二进制的小数。这些点把[0，1]区间分成许多小段，每段的长度等于某一序列的概率。再在段内取一个二进制小数，其长度可与该序列的概率匹配，达到高效率编码的目的。算术编码如果信源符号集为A={a1，a2，……an}，已知的信源符号概率P=[p(a1)，p(a2)，……p(an)]=(p1，p2，……，pr，……，pn)，定义各符号的积累概率为：

由上式可得P1=0，P2=p1，P3=p1+p2，……且

pr=Pr+1—Pr算术编码由于Pr+1和Pr都是小于1的正数，可用[0,1]区间内的两个点来表示，则pr就是这两点间的小区间的长度，如图所示：0(P1)P2P3P4P5……1

……p1

p2p3p4算术编码有一序列S=011,

P(S)=p(000)+p(001)+p(010)，

P(S，0)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0101)

=p(000)+P(001)+P(010)=P(S)

P(S，1)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0101)+p(0110)

=P(S)+p(0110)=P(S)+p(S)p0算术编码由于单符号的累积概率为P0=0，P1=p0，所以上面两式可统一写作：

P(S，r)=P(S)+p(S)Pr，r=0，1推广到多元序列(m>2)，即可得一般递推公式：

P(S，ar)=P(S)+p(S)Pr，

以及序列概率公式：

p(S，ar)=p(S)pr算术编码码字的取得：

1.码字的长度：

代表大于或等于的最小整数。2.把积累概率P(S)写成二进位的小数，取其前L位;如果有尾数，就进位到第L

位，这样得到一个数C

。

算术编码实际应用中，采用累积概率P(S)表示码字C(S)，符号概率p(S)表示状态区间A(S)，则有：

算术编码例5—10有四个符号a，b，c，d构成简单序列S＝abda，各符号及其对应概率如下表，算术编解码过程如下：符号符号概率pi符号累积概率Pja0.100

(1/2)0.000b0.010

(1/4)0.100c0.001

(1/8)0.110d0.001

(1/8)0.111算术编码设起始状态为空序列

，则A()＝1，C(

)＝0。递推得：算术编码因此，C(a,b,d,a)即为编码后的码字010111。算术编码算术编码过程：（单位区间的划分表示）

a

b

c

d

A(a,b,d)

0(Pa)

pa

Pb

pb

Pc

pc

Pd

pd

1C(a,b,d)C(a,b)C(a)C(

)A(

)A(a)a

b

c

d

A(a,b)

a

b

c

d算术编码算术译码过程：

C(a,b,d,a)=0.010111<0.1

[0,0.1]第一个符号为a；放大至[0,1](×pa-1)：C(a,b,d,a)×21＝0.10111

[0.1,0.110]

第二个符号为b；

去掉累积概率Pb：0.10111-0.1=0.00111；放大至[0,1](×pb-1)：0.00111×22=0.111

[0.111,1]

第三个符号为d；

去掉累积概率Pd：0.111-0.111=0放大至[0,1](×pd-1)：0×24＝0

[0,0.1]四个符号为a；算术编码

算术编码优缺点：

算术编码从性能上看具有许多优点，特别是由于所需的参数很少，不象哈