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

第十讲 算术编码与LZ编码 算术编码 • 前面所讨论的无失真编码，都是建立在信源符号与码字一 一对应的基础上，这种编码方法通常称为块码或分组码， 此时信源符号一般是多元的。 • 如果要对二元序列进行编码，则需采用合并信源符号方法， 把二元序列转换成多值符号，转换时二元符号之间的相关 性不予考虑，转换后这些多值符号之间的相关性也不予考 虑。这就使信源编码的匹配原则不能充分满足，编码效率 一般不高。 • 为了克服这种局限性，需要跳出分组码范畴，从整个符号 序列出发，采用递推形式进行编码。 算术编码基本思想 从整个符号序列出发，将各信源序列的概率映射到[0,1) 区间上，然后选取区间内的一点（也就是一个二进制 的小数）来表示信源序列。 设信源字母表为{a , a },概率p (a )=0.6, p (a )=0.4 ， 1 2 1 2 将[0,1]按概率比例分为区间[0,0.6],[0.6,l]。 0 0.6 1 p (a ) p (a ) 1 2 0 0.36 0.6 0.84 1 p (a a ) p (a a ) p (a a ) p (a a ) 1 1 1 2 2 1 2 2 随着序列的长度不断增 加,C所在区间的长度就 越短,也就可以更加精确 地确定C的位置 累积概率 设信源符号集A={a ,a ,…,a }, 其相应概率分布为p , p 0 1 2 n i i (i=1,2, …,n), 定义信源符号的累积概率 （分布函数）为 r 1 P p r=1,2, …,n P [0,1) r  i r i 1 P = 0; P = p ; P = p +p ; … 1 2 1 3 1 2 p r = Pr+1 - Pr 0 P P P P 1 1 2 3 4 … p 1 p 2 p 3 … 二元序列的累积概率 当A={0,1}