《第6章2 霍夫曼码、算术码和LZW码.doc》由会员分享，可在线阅读，更多相关《第6章2 霍夫曼码、算术码和LZW码.doc（7页珍藏版）》请在金锄头文库上搜索。
1、第6节 霍夫曼码1. 1952年霍夫曼(Huffman)提出的，是历史记录中第一个最优即时码。2. 二元霍夫曼码的构造方法：根据信源符号的概率自底向上地构造码树，步骤如下：（1） 将信源U的n个符号ui按概率p(ui)从大到小排列，构成码树的叶节点。（2） 将两个最小的概率值相加，构成二者的父节点。（3） 将所有没有父节点的概率值按从大到小重新排列。（4） 重复（2）与（3）直到根节点出现，即步骤（2）中两个概率值相加=1.例6-11 0.5， 0.25， 0.125， 0.125解：1）画出码树包括各节点对应的概率值。2）平均码长：2） 编码效率：3） 信源熵（信源的信息传输率）：4） 信源
2、的相对熵率（信源的信息传输效率）：3. 二分组霍夫曼码例6-12 0.7，0.3结论：对于“小消息信源”，必须用分组长度较大的霍夫曼码，才能获得较大的编码效率与较好的压缩效果。这是提高编码效率的重要途径。4. 最优分组码定义 1. 令S为一离散信源， 用一个新符号取代S中两个概率最小的信源符号，并把这两个最小概率合并为该新符号的概率，而其它信源符号及其概率不变，所得的信源S(1)称为信源S的（一次）缩减信源 ，并称S为S(1)的扩展信源。n-步缩减信源S(n). 2. 令C是信源S的一个即时码，其中有两个码字w与w长度最大且相等，用其最大真前缀替换C中的w与w所得的即时码C(1)称为C的（一次
3、）缩减码，并称C为C(1)的扩展码。与n-步缩减码分别记为和Cn。显然，信源每缩减一次，其符号总数减1；即时码每缩减一次其码字总数减1.引理1 令C为即时码，C(1)是码C的一个缩减码，则两个码的平均码长之间有如下关系： LC = L C(1) + p+p其中p与p分别是C中被合并的两个码字的概率。 证明 设S有q个符号，概率分别为pi，码C中对应的码字长为 li ，其中对应于概率p的码字长记为l，则 引理2 设C为某信源S的即时码，C1是码C的一个缩减码，则 C是最优码 C1是最优码。 证明 把码C1所对应的缩减信源记为S1，并设S1中的信源符号s是由S中两个信源符号合并而成。再令被合并的两
4、个信源符号的概率为p与p。由前面的引理3， LC = LC1 + p+ p (1)() 令D为S1的一个最优即时码，由前面的引理2，在S上存在D的扩展码D，从而由引理3得 LD = LD+ p+p (2)比较(1)与(2)，由C的最优性可得 LC1 LD，从而C1是最优码。 () 令E为S的一个最优即时码，由前面的定理4，E是正规码，从而在S1上存在缩减码E1，再由引理3得 LE = LE1+ p+p (3)比较(1)与(3)，由C1的最优性可得 LC LE ，从而C是最优码。 定理 二元分组码C是最优分组码，当且仅当，其码树是二分杈的，且C的每次缩减码都是“概率匹配码”。证明推论 霍夫曼码是
5、最优分组码。5. 讨论：同一个信源，不同分组的二元霍夫曼码相比较：分组长度越大，编码效率越高；编码效率随分组长度增加而增加，并趋向最大值1。6. 霍夫曼编码的不唯一性例6-13 平均码长相同，但码长方差不同，选择码长方差较小的一个，可使编码时输出码符号的速度更平稳。7. 多元霍夫曼码1）码树的构造方法类似于二元霍夫曼码的码树构造方法。2）码元数越大，编码效率小。8. 应用：传真、卫星通信、MP3程序设计2：构造二元霍夫曼码输入：一个概率分布。输出：该分布的熵。9. 变长分组码的缺点（1）码长不同导致信源编码器不能匀速输出码元符号，因此不能直接与信道连接。解决办法是添加缓冲寄存器。 （2）存在差
6、错扩散的问题。解决办法是使用纠错码提高数据的抗干扰能力。 （3）霍夫曼码的编译码都需要查找码本，码本太大的话，占用内存大且费时。因此，不能对太大的扩展信源进行编码。为进一步提高编码效率，需要改用非分组码，例如算术码、字典码。 （4）霍夫曼码属于概率匹配码，需要知道信源的统计特性，且不能适应信源概率变化。可改用具有自适应性的算术编码，或字典码。第7节 算术码仍设U为离散无记忆信源。1. 特点：1） 非分组码，全序列编码：是一个双射，可将任意长的信源序列编码为“一个”码字。2） 用信源序列S的累积概率F(S)的一个近似值作为S的码字，该近似值的长度由S的自信息量或概率p(S)确定。2. 累积概率注
7、意，累积概率值中不含p(S)。递推公式：(用树图说明)3. 累积概率区间长度相同的信源序列的累积概率有如下关系： 将单位区间0,1划分为若干不相交的小区间： 称为序列S的累积概率区间。 用树图说明各累积概率区间的包含与不相交关系。4. 编码方法基本思想：（1） 计算信源序列S的“累积概率”F(S)；（2） 计算S的码长 （3） 取码字，其中F(S)采用二进制表示。定义（近似运算）设x为两个二进制实数。近似值表达式 表示a是x的一个有理近似值，a共有k位二进制小数，且 注：满足上述近似关系的有理数a不唯一，即近似运算是多值函数。命题1. 近似运算是可计算的，即可以编程实现的。证明 可以编写一个C
8、语言程序实现该运算。 命题2. 任意实数相等关系x=y是不可判定的。算术码的编码方法：输入：信源序列 输出：一个码字。（1） 按信源符号的给定次序，计算各信源符号u的累积概率F(u)； （2） 令（3） 从i=1到i=n重复执行下面的赋值语句：（4） 计算码长；（5） 取码字，其中F(S)采用二进制表示。 注：取码长可以保证在教材所介绍的编码方法中，取码长为所取的码字为F(S)中L位小数，“若尾数不为0，则在末尾加1”。这样从数学上来说，也有但是，在计算机中很难判断尾数是否为0。因为随着序列长度增长，序列的概率越来越小，从而尾数越来越长，受到计算机存储空间的限制，长到一定程度时，必然被截断，从
9、而引入截断误差。例6-16 0.25，0.755. 唯一可译性命题1 由命题1知，长度相同的两个信源序列的码字是不同的。命题2 若S是T的前缀，则 证明 设T=Su，则 根据上述结果，用数学归纳法，可以证明该命题。 定理3 设信源符号概率都0.5，则算术码是唯一可译码。证明 设S与T是任意两个信源序列，只要证明即可。1）若S是T的前缀，则p(T) 0.5p(S)，从而LS+1LT ，故2）若S不是T的前缀，由命题2和命题1可得 6. 渐近最优性讨论： 算术码f:U*C限制在Un上是n分组码，记fn:UnC； fn的平均码长满足如下关系 其证明与信源编码定理的证明类似。因此，随着信源序列长度n不
10、断增长，fn的平均码长不断缩短，趋向信源熵，从而编码效率趋向1。所以，称算术码具有“渐近最优性”。因此，信源序列越长，算术码的压缩效果越好。问题：试比较同一个信源的算术码与霍夫曼码的优劣。7. 算术码的译码方法（1） 根据码字长计算p(S)所在的区间 ；（注：此步是对教材中的算法的补充，为步骤（5）做准备。）（2） 计算各信源符号的累积概率区间Iui，并令；（3） 判断A位于哪一个信源符号的累积概率区间，若，则翻译出符号u；（4） 计算新值；（5） 重复（3）、（4）直到.例6-17 对例6-16中所得的码字01010进行译码。8. 译码方法的正确性命题1. 由当且仅当ui是S的第一个符号。由
11、累积概率的递推公式可得，命题2. 若且，则 证明 由于，根据（1）可得 由于，第8节 LZW码1. 特点：（1） 自适应码，不需要知道信源符号的概率分布。（2） 字典码：在编码过程中，根据信源序列中出现的新的字符串（单词）构造一个字符串表（字典），用定长的单词序号作为该单词的码字。（3） 定长码，但编码对象长度不定。2. 编码方法（1） 将信源序列中的所有符号登记到字符串表中，并用其在字符串表中的序号作为每个符号的码字；（2） 读入信源序列的第一个字符，赋给“前缀变量”P；（3） 读入下一个字符，赋给“扩展变量”S;（4） 若S存入符号为空格，则输出P中字符串的码字，停止；否则执行（5）；（5） 若PS不在串表中，则将P对应的码字输出，并将PS存入串表，分配一个码字给该串，并将字符S赋给P取代中存放的字符串；否则，将PS赋给P；（6） 重复（3）。例6-18 对信源序列XYXYZYXYXYXXXXXXX进行LZW编码。3. 编码效率随码字长增加而趋向1.
