3.4算术编码与LZ编码.pdf

3.5 算术编码 • Huffman编码虽然是最佳编码，但对于二元信 源，必须对二元信源的n次扩展信源进行编码，才 能使平均码长接近于信源熵，提高编码效率。当n 较大时编码过于复杂。 • 算术编码不同于Huffman编码，是非分组码。它 从全序列出发，考虑符号之间的依赖关系，采用 递推形式进行编码。算术编码无需计算所有长为L 的信源序列的分布。 3.5 算术编码 • Shannon-Fano-Elias码1968。算术编码 J.Rissanen 1976 • 直接对一个消息序列编码，可以达到渐进 最佳性能 • 算术编码中，信源符号与码字之间不存在 一一对应关系 • 码字是定义在一个介于0和1之间的实数 • 当消息的符号增加时，用于消息的间隔变 得更小，而表示间隔所需的信息单元变得 更多了 • 算术编码是JPEG和FAX的基础 3.5 算术编码 信源符号的分布函数(累积概率) a , p a , p a 0 k 1,2,..., K { ( ) ( ) (} ) k k k k −1 F a p a , k 2,...,K ,F a 0 ( ) ∑ ( )( ) ( ) k k 1 p a 将区间 分成了k个子区间，每个区间宽度为 ( ) i 1 k F a [0,1) { ( )} k 例题 信源符号 概率 初始子区间 4 a4 0.2 [0.81.0， ) 4 a3 0.4 [0.4，0.8) 3 3 a2 0.2 [0.2，0.4) 2 2 a1 0.2 [0，0.2) 1 1 3.5 算术编码 3.4.2 算术编码 消息序列的分布函数(累积概率) 编码序列