文档介绍：算术编码与LZ编码的区别
算术编码
前面所讨论的无失真编码，都是建立在信源符号与码字一一对应的基础上，这种编码方法通常称为块码或分组码，此时信源符号一般是多元的。
如果要对二元序列进行编码，则需采用合并信源符号方法，把二元序列转换成多值符号，转换时二元符号之间的相关性不予考虑，转换后这些多值符号之间的相关性也不予考虑。这就使信源编码的匹配原则不能充分满足，编码效率一般不高。
为了克服这种局限性，需要跳出分组码范畴，从整个符号序列出发，采用递推形式进行编码。
从整个符号序列出发，根据各信源序列的概率将信源序列映射到[0,1) 区间上，然后选取区间内的一点（也就是一个二进制的小数）来表示信源序列。
算术编码基本思想
设信源字母表为{a1, a2},概率p(a1)=, p(a2，
将[0,1]按概率比例分为区间[0,],[,l]。
p(a1)
p(a2)
0 1
0 1
p(a1a1)
p(a1a2)
p(a2a1)
p(a2a2)
随着序列的长度不断增加,C所在区间的长度就越短,精确地确定C的位置需要码长也不断增加
设信源符号集A={a1,a2,…,an}, 其相应概率分布为pi, pi >0 (i=1,2, …,n), 定义信源符号的累积概率（分布函数）为
P1= 0; P2= p1 ; P3= p1+p2 ; …
累积概率
r=1,2, …,n
pr = Pr+1 - Pr
P1
p1
P2
P3
P4
1
p2
p3
…
…
0
当A={0,1}二元信源时，P1=P(0)= 0 ; P2 = P(1)= p0
P(0)
P(1)
0
1
p0
p1
二元序列的累积概率
引例
设有二元序列S=011，求S的累积概率
P(S)=p(000)+ p(001)+ p(010)
若S后面接0
P(S0)=p(0000)+ p(0001)+ p(0010)+p(0011)+
p(0100)+ p(0101)
=p(000)+ p(001)+ p(010)
=P(S)
若S后面接1
P(S1)=p(0000)+ p(0001)+ p(0010)+p(0011)+
p(0100)+ p(0101)+ p(0110)
=P(S)+ p(0110)
=P(S)+p(S) p0
二元序列的累积概率
P(0)=0,P(1)=p0
P(Sar)=P(S) + p(S) Pr
S0=0110
S1=0111
p(Sar)=p(S) p(ar)
p(Sar)=p(S) p(ar)
P(Sar)=P(S) + p(S) Pr
P(0)
0
P(1)
1
p0
设符号序列S = 011
p1
P(0)
P(1)
p(00)=p(0)P(1)
P(01)
p(01)
P(01)
P(1)
P(011)
p(010)=p(01)P(1)
p(011)
二元序列的累积概率
P(Sar)=P(S)+p(S)Pr
累积概率递推公式
一般多元信源序列的累积概率递推公式
序列的概率(所对应区间的宽度)递推公式
实际中,求序列累积概率只需两个存储器,起始时可令:
A(Φ) =1, P(Φ) = 0
每输入一个符号,存储器P和A 就按照上式更新一次,直至符号输入完毕,这时存储器P的内容即为该序列的累积概率。
累积概率递推公式
累积概率递推计算
注意：计算过程中,每输入一个符号只要进行乘法和加法运算。
通过信源符号序列累积概率计算,把区间分割成许多小区间,不同的信源符号序列对应不同的区间为[P(S), P(S) + p(S)) ，可取小区间内的一点来代表这序列。
将符号序列的累积概率写成二进位小数，取小数点后L位,若后面有尾数,就进位到第L位，即
算术编码
若P，L=3
则C