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