第10讲——算术编码与LZ编码.pdf

《第10讲——算术编码与LZ编码.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十讲算术编码与LZ编码算术编码•前面所讨论的无失真编码，都是建立在信源符号与码字一一对应的基础上，这种编码方法通常称为块码或分组码，此时信源符号一般是多元的。•如果要对二元序列进行编码，则需采用合并信源符号方法，把二元序列转换成多值符号，转换时二元符号之间的相关性不予考虑，转换后这些多值符号之间的相关性也不予考虑。这就使信源编码的匹配原则不能充分满足，编码效率一般不高。•为了克服这种局限性，需要跳出分组码范畴，从整个符号序列出发，采用递推形式进行编码。算术编码基本思想从整个符号序列出发，将各信源序列的概率映射到[0,1)区间上，然后选取区间内的一点（也就是一个二进制的

2、小数）来表示信源序列。设信源字母表为{a,a},概率p(a)=0.6,p(a)=0.4，1212将[0,1]按概率比例分为区间[0,0.6],[0.6,l]。00.61p(a1)p(a2)00.360.60.841p(aa)p(aa)p(aa)p(aa)11122122随着序列的长度不断增加,C所在区间的长度就越短,也就可以更加精确地确定C的位置累积概率设信源符号集A={a,a,…,a},其相应概率分布为p,p>012nii(i=1,2,…,n),定义信源符号的累积概率（分布函数）为r1Ppr=1,2,…,nPr[0,1)rii1P=0;P=p;P=p+p;…

3、121312pr=Pr+1-Pr0P1P2P3P4…1ppp…123二元序列的累积概率当A={0,1}二元信源时，P(0)=0;P(1)=p00P(0)P(1)1pp01引例设有二元序列S=011，求S的累积概率P(S)=p(000)+p(001)+p(010)二元序列的累积概率若S后面接00110P(S0)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0101)=p(000)+p(001)+p(010)=P(S)若S后面接10111P(S1)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0

4、101)+p(0110)=P(S)+p(0110)=P(S)+p(S)P1P(Sr)=P(S)+p(S)Pr二元序列的累积概率设符号序列S=011P(Sr)=P(S)+p(S)Pr0P(0)P(1)1pp01P(0)P(01)P(1)p(00)=p(0)Pp(01)1P(01)P(011)P(1)p(010)=p(01)Pp(011)1累积概率递推公式一般多元信源序列的累积概率递推公式P(S,a)P(S)p(S)Prr序列的概率(所对应区间的宽度)递推公式A(S,a)p(S,a)p(S)p(a)rrr累积概率递推计算累积概率递推公式P(S,a)P(S)p(S

5、)PrrA(S,a)p(S,a)p(S)p(a)rrr•实际中,求序列累积概率只需两个存储器,起始时可令:A(Φ)=1,C(Φ)=0每输入一个符号,存储器C和A就按照上式更新一次,直至符号输入完毕,这时存储器C的内容即为该序列的累积概率。注意：计算过程中,每输入一个符号只要进行乘法和加法运算。算术编码通过信源符号序列累积概率计算,把区间分割成许多小区间,不同的信源符号序列对应不同的区间为[P(S),P(S)+p(S))，可取小区间内的一点来代表这序列。将符号序列的累积概率写成二进位小数，取小数点后L位,若后面有尾数,就进位到第L位，即1LlogP(S)

6、L0.p(S)L若P(S)=0.10110001，L=3则C=0.110CP(S),P(S)p(S)算术编码的唯一可译性由码C的形成方法，可知CP(S)1L又Llog可知p(S)2p(S)LLP(S)p(S)P(S)2CCP(S)2由此可见C必在[P(S),P(S)p(S)),因而唯一可译。对于长序列，p(S)必然很小，L与概率倒数对数几乎相等，也就是说取整造成的差别很小，因而平均码长将接近于信源熵H(S)例题设二元无记忆信源S={0,1},p(0)=1/4,p(1)=3/4。S=11111100，对其做算术编码

7、。解：p(S=11111100)=p2(0)p6(1)=(1/4)2(3/4)6P(S)=p(00000000)+p(00000001)+p(00000010)+…+p(11111011)=1-p(11111111)-p(11111110)-p(11111101)-p(11111100)=1-p(111111)=1-(3/4)6=0.11010010011111010011Llog7p(S)从而得C=0.1101010，S的码字为1101010P(S0)P(S)P(S1)P(S)p(S)p(0)p(0)=(1/4)=