[工学]04-多媒体数据压缩技术-第一部分.ppt

第四章 多媒体数据压缩技术 4.2.4 Shannon-Famo编码 1) 将给定符号按照其频率从大到小排序。对上例子，应该得到： a - 16 b - 7 c - 6 d - 6 e - 5 第四章 多媒体数据压缩技术 4.2.4 Shannon-Famo编码 2) 将序列分成上下两部分，使得上部频率总和尽可能接近下部频率总和。我们有： a - 16 b - 7 ----------------- c - 6 d - 6 e - 5 第四章 多媒体数据压缩技术 4.2.4 Shannon-Famo编码 3) 我们把第二步中划分出的上部作为二叉树的左子树，记 0，下部作为二叉树的右子树，记 1。 4) 分别对左右子树重复 2 ）、3） 两步，直到所有的符号都成为二叉树的树叶为止。 第四章 多媒体数据压缩技术 4.2.4 Shannon-Famo编码 2.164911221 熵 0.375 0.410545 0.410545 0.44005 0.528771 Pi*log2(1/pi) 2.275 Shannon-Fano编码平均码长 2.2 Huffman编码平均码长 3 3 2 2 2 Shannon-Fano编码码长 3 3 3 3 1 Huffman编码码长 111 110 10 01 00 Shannon-Fano编码结果 001 000 011 010 1 huffman编码结果 0.125 0.15 0.15 0.175 0.4 5/40 6/40 6/40 7/40 16/40 概率 　 e d c b a 信源符号 第四章 多媒体数据压缩技术 4.2.4 算术编码 算术编码（arithmetic coding AC）是利用0和1之间的间隔来表示信源序列(也称为消息)的一种方法。把整个消息看作一个单元，用一个半开区间[a,b)来表示一条消息，其中a和b都是0和1之间的实数。初始时，区间是[0,1)。随着消息长度的增加，区间的长度将缩小，而用来表示区间的位数将增加。 算术编码用到的参数：符号的概率。 信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。 算术编码器的编码过程： 第四章 多媒体数据压缩技术 4.2.4 算术编码 例：假设信源符号为{A, B, C, D}，这些符号的概率分别为{ 0.1, 0.4, 0.2, 0.3 }，根据这些概率可把间隔[0, 1）分成4个子间隔：[0, 0.1）, [0.1, 0.5）, [0.5, 0.7）, [0.7, 1），其中[x,y）表示半开放间隔，即包含x不包含y，如表4-1所示。 如果消息序列的输入为：CADACDB，其编码过程如下： [0.7,1） [0.5,0.7） [0.1,0.5） [0,0.1） 初始编码间隔 0.3 0.2 0.4 0.1 概率 D C B A 符号 第四章 多媒体数据压缩技术 4.2.4 算术编码 第四章 多媒体数据压缩技术 4.2.4 算术编码 BEGIN low=0.0; high=1.0;range=1.0; while (symbol != terminator) { get(symbol); low = low +range*range_low(symbol); high = low +range*range_high(symbol); range = high -low; } output a code so that low= code = high; END 第四章 多媒体数据压缩技术 4.2.4 算术编码 算术编码的解码： BEGIN get binary code and convert to decimal value = value (code); DO { find a symbol s so that Range_low(s) = value Range_high(s); output s; low = Range_low(s); high=Range_high(s); range = high -low; value = [value-low]/range; } until symbol s is a terminator END 第四章 多媒体数据压缩技术 4.2.4 算术编码 算术编码的解码： 解码器由编码输出值：0.5143876，可解得第一个字符为C，然后依次得到唯一解A,D,A,C,D,B。 第四章 多媒体数据压缩技术 4.2.4 算术编码 在算术编码中需要注意的几个问题： （1