《《算术编码与LZ编码》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《算术编码与LZ编码》PPT课件.ppt（27页珍藏版）》请在装配图网上搜索。
1、算术编码与LZ编码,第十讲,算术编码,前面所讨论的无失真编码，都是建立在信源符号与码字一一对应的基础上，这种编码方法通常称为块码或分组码，此时信源符号一般是多元的。 如果要对二元序列进行编码，则需采用合并信源符号方法，把二元序列转换成多值符号，转换时二元符号之间的相关性不予考虑，转换后这些多值符号之间的相关性也不予考虑。这就使信源编码的匹配原则不能充分满足，编码效率一般不高。 为了克服这种局限性，需要跳出分组码范畴，从整个符号序列出发，采用递推形式进行编码。,从整个符号序列出发，将各信源序列的概率映射到0,1) 区间上，然后选取区间内的一点（也就是一个二进制的小数）来表示信源序列。,算术编码基
2、本思想,设信源字母表为a1, a2,概率p(a1)=0.6, p(a2)=0.4， 将0,1按概率比例分为区间0,0.6,0.6,l。,p(a1),p(a2),0 0.6 1,0 0.36 0.6 0.84 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 -
3、 Pr,P1,p1,P2,P3,P4,1,p2,p3,0,当A=0,1二元信源时，P(0)= 0 ; 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
4、)+ p(0110),=P(S)+ p(0110),=P(S)+p(S)P1,二元序列的累积概率,P(Sr)=P(S)+p(S)Pr,0110,0111,P(0),0,P(1),1,p0,设符号序列S = 011,p1,P(0),P(1),p(00)=p(0)P1,P(01),p(01),P(01),P(1),P(011),p(010)=p(01)P1,p(011),二元序列的累积概率,P(Sr)=P(S)+p(S)Pr,二元信源符号序列的累积概率递推公式,信源符号序列所对应区间的宽度递推公式,累积概率递推公式,一般多元信源序列的累积概率递推公式,序列的概率公式,实际中,求序列累积概率只需两个
5、存储器,起始时可令: A() =1, C() = 0 每输入一个符号,存储器C和A 就按照上式更新一次,直至符号输入完毕,这时存储器C的内容即为该序列的累积概率。,累积概率递推公式,累积概率递推计算,注意：计算过程中,每输入一个符号只要进行乘法和加法运算。,通过信源符号序列累积概率计算,把区间分割成许多小区间,不同的信源符号序列对应不同的区间为P(S), P(S) + p(S) ，可取小区间内的一点来代表这序列。 将符号序列的累积概率写成二进位小数，取小数点后L位,若后面有尾数,就进位到第L位，即,算术编码,若P(S) = 0.10110001，L=3,则C = 0.110,算术编码的唯一可译
6、性,由码C的形成方法，,又,可知,可知,由此可见C必在,因而唯一可译。,对于长序列，p(S)必然很小，L与概率倒数对数几乎相等，也就是说取整造成的差别很小，因而平均码长将接近于信源熵H(S),设二元无记忆信源S=0,1,p(0)=1/4,p(1)=3/4。 S=11111100，对其做算术编码。,P(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.11
7、0100100111,从而得C = 0.1101010，S的码字为1101010,解：p(S=11111100) = p2(0)p6(1) = (1/4)2 (3/4)6,例 题,1101001,+,=,p(1)=3/4=(0.11)2,p(11)=(3/4)2=(0.1001)2,+,=,p(0)=(1/4)=2-2 p(S)p(0)p(S)右移2位,设无记忆信源U=a1,a2,a3,a4，其概率分布依次为 0.5,0.25,0.125,0.125，对信源序列 做算术编码。,解：,例 题,算术编码递推过程,a1, a2, a3 , a4 0.5,0.25,0.125,0.125,设无记忆信源
8、U=a1,a2,a3,a4，其概率分布依次为 0.5,0.25,0.125,0.125，对信源序列 做算术编码。,由算术编码递推表得C = 0. 100110111010000 ， 从而U的码字为1001101110100,解：,例 题,P(0),0,P(1),1,p(0),译码输出序列 011,p(1),P(0),P(1),p(00),P(01),p(01),P(01),P(1),P(011),p(010),p(011),算术编码译码,C,C,C,对二元算术码而言，其译码过程是一系列比较过程： 每一步比较 与 ，这里 为前面已译出的 序列串， 是序列串 对应的宽度， 是序列 的累 积概率值，
9、即为 对应区间的下界限， 是此区间 内下一个输入为符号“0”所占的子区间宽度。 译码规则为： 若 ，则译输出符号为“0”； 若 ，则译输出符号为“1”。,算术编码译码,算术编码的编码效率很高，当信源符号序列很长时，L很大时，平均码长接近信源熵。 从性能上来看，算术编码具有许多优点，它所需的参数较少、编码效率高、编译码简单，不象哈夫曼码那样需要一个很大的码表。算术编码在图像数据压缩标准（如JPEG）中得到广泛的应用。,算术编码,两位以色列研究者J. Ziv和A. Lempel独辟蹊径，完全脱离Huffman及算术编码的设计思路，创造出了一系列比Huffman编码更有效，比算术编码更快捷的通用压缩
10、算法LZ算法。,LZ编码,对于统计特性确知的平稳信源，已有huffman编码和算术编码高效编码方法，其平均码长可逼近信源的平均符号熵，而且实现困难不算太大，所以已进入实用。,要确知信源的统计特性相当困难。通用编码指在信源统计特性不知时，对信源进行编码，而且编码效率很高。,设输入信源符号序列为,尽可能取最少个相连的信源符号，并保证各段都不相同。,，其中,，编码时将此序列分成不同的段。,分段规则,则编码的码字由段号加后面一个符号组成。,设序列分段结果为,，若,则,或者说编码码字可用两个数段号i和符号序号r组成。,LZ78码,设U=a1, a2, a3, a4，信源序列为,按照分段规则，可以分为,符
11、号编码表,例 题,可以看出LZ78编码的编码方法非常简捷，译码也很简单，可以一边译码一边建立字典，无需传输字典本身。,当编码的信源序列较短时，LZ性能似乎会变坏，但是当序列增长时，编码效率会提高，平均码长会逼近信源熵。,例 题,符号编码,例 题,00000 00001 00110 01011 10010 00100 00011,码序列,可以看出LZ78编码的编码方法非常简捷，译码也很简单，可以一边译码一边建立字典，无需传输字典本身。,当编码的信源序列较短时，LZ性能似乎会变坏，但是当序列增长时，编码效率会提高，平均码长会逼近信源熵。,例 题,目前算法以及它们的各种变体几乎垄断了整个通用数据压缩领域，我们熟悉的WinZIP、WinRAR、gzip等压缩工具以及ZIP、GIF、PNG 等文件格式都是 LZ 系列算法的受益者。,作 业,3.7 3.12 3.14,本节小结,算术编码,LZ编码,编码方法（映射、选取）,（本节内容见课本73-79页）,基本思想,基本思想,编码方法,（字典）,
《算术编码与LZ编码》PPT课件.ppt
