第6章2 霍夫曼码、算术码和LZW码.doc

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） 信源熵（信源的信

2、息传输率）：4） 信源的相对熵率（信源的信息传输效率）：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长度最大且相等，用其

3、最大真前缀替换 C 中的 w与 w所得的即时码 C(1)称为 C 的（一次）缩减码，并称 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，则 112()1qCiiCLplllp引理 2 设 C 为某信源 S 的

4、即时码， C1 是码 C 的一个缩减码，则 C 是最优码 C1 是最优码。 证明 把码 C1 所对应的缩减信源记为 S1，并设 S1 中的信源符号 s 是由 S 中两个信源符号合并而成。再令被合并的两个信源符号的概率为 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 上

5、存在缩减码 E1，再由引理 3 得 LE = LE1+ p+p (3)比较(1)与(3)，由 C1 的最优性可得 LC LE ，从而 C 是最优码。 定理 二元分组码 C 是最优分组码，当且仅当，其码树是二分杈的，且 C 的每次缩减码都是“概率匹配码” 。证明推论 霍夫曼码是最优分组码。5. 讨论：同一个信源，不同分组的二元霍夫曼码相比较：分组长度越大，编码效率越高；编码效率随分组长度增加而增加，并趋向最大值 1。6. 霍夫曼编码的不唯一性例 6-13 平均码长相同，但码长方差不同，选择码长方差较小的一个，可使编码时输出码符号的速度更平稳。7. 多元霍夫曼码1）码树的构造方法类似于二元霍夫曼码

6、的码树构造方法。2）码元数越大，编码效率小。8. 应用：传真、卫星通信、MP3程序设计 2：构造二元霍夫曼码输入：一个概率分布。输出：该分布的熵。9. 变长分组码的缺点（1）码长不同导致信源编码器不能匀速输出码元符号，因此不能直接与信道连接。解决办法是添加缓冲寄存器。 （2）存在差错扩散的问题。解决办法是使用纠错码提高数据的抗干扰能力。（3）霍夫曼码的编译码都需要查找码本，码本太大的话，占用内存大且费时。因此，不能对太大的扩展信源进行编码。为进一步提高编码效率，需要改用非分组码，例如算术码、字典码。 （4）霍夫曼码属于概率匹配码，需要知道信源的统计特性，且不能适应信源概率变化。可改用具有自适应

7、性的算术编码，或字典码。第 7 节 算术码仍设 U 为离散无记忆信源。1. 特点：1） 非分组码，全序列编码：是一个双射 ，可将任意长的*:0,1fU信源序列编码为“一个”码字。2） 用信源序列 S 的累积概率 F(S)的一个近似值作为 S 的码字，该近似值的长度由 S 的自信息量或概率 p(S)确定。2. 累积概率 |()()lexTSFp注意，累积概率值中不含 p(S)。递推公式：(用树图说明) ()FupFu3. 累积概率区间长度相同的信源序列的累积概率有如下关系：120()()1,miiiSSFp将单位区间0,1 划分为若干不相交的小区间：称 为序列 S 的累积概率区间。(), ()S

8、IS用树图说明各累积概率区间的包含与不相交关系。4. 编码方法基本思想：（1） 计算信源序列 S 的 “累积概率”F(S) ；（2） 计算 S 的码长log()1LpS（3） 取码字 ，其中 F(S)采用二进制表示。()C定义（近似运算）设 x 为两个二进制实数。近似值表达式 表示kaxa 是 x 的一个有理近似值，a 共有 k 位二进制小数，且2ax注：满足上述近似关系的有理数 a 不唯一，即近似运算 是(,)kx多值函数。命题 1. 近似运算 是可计算的，即可以编程实现的。(,)kx证明 可以编写一个 C 语言程序实现该运算。 命题 2. 任意实数相等关系 x=y 是不可判定的。算术码的编

9、码方法：输入：信源序列 12ns输出：一个码字。（1） 按信源符号的给定次序，计算各信源符号 u 的累积概率 F(u)； （2） 令 , ()0, ()1;SFpS（3） 从 i=1 到 i=n 重复执行下面的赋值语句：()();iips（4） 计算码长 ；log()1LpS（5） 取码字 ，其中 F(S)采用二进制表示。 ()LCF注：取码长 可以保证l(),()Sp在教材所介绍的编码方法中，取码长为 log()L所取的码字为 F(S)中 L 位小数， “若尾数不为 0，则在末尾加 1”。这样从数学上来说，也有 (),()CSFSp但是，在计算机中很难判断尾数是否为 0。因为随着序列长度增长

10、，序列的概率越来越小，从而尾数越来越长，受到计算机存储空间的限制，长到一定程度时，必然被截断，从而引入截断误差。例 6-16 0.25，0.755. 唯一可译性命题 1 1(), ()()2CSFSplog() 1 2() ()(). LALppSCSF A证 明 依 算 法 ， 显 然 。由 ， 得故 由命题 1 知，长度相同的两个信源序列的码字是不同的。命题 2 若 S 是 T 的前缀，则(), ()(), ()FpFSpS证明 设 T=Su，则 ();()()() ().SupSu根据上述结果，用数学归纳法，可以证明该命题。 定理 3 设信源符号概率都0.5，则算术码是唯一可译码。证明

11、设 S 与 T 是任意两个信源序列，只要证明 即可。()CST1）若 S 是 T 的前缀，则 p(T) 0.5p(S)，从而 LS+1L T ，故()C2）若 S 不是 T 的前缀，由命题 2 和命题 1 可得 ()6. 渐近最优性讨论： 算术码 f:U*C 限制在 Un 上是 n 分组码，记 fn:UnC； fn 的平均码长满足如下关系2()()HSL其证明与信源编码定理的证明类似。因此，随着信源序列长度 n 不断增长，f n 的平均码长不断缩短，趋向信源熵，从而编码效率趋向 1。所以，称算术码具有“渐近最优性” 。因此，信源序列越长，算术码的压缩效果越好。问题：试比较同一个信源的算术码与霍

12、夫曼码的优劣。7. 算术码的译码方法（1） 根据码字长计算 p(S)所在的区间 ；（注：此步是对教12, )L材中的算法的补充，为步骤（5）做准备。 ）（2） 计算各信源符号的累积概率区间 Iui，并令 ；()ACS（3） 判断 A 位于哪一个信源符号的累积概率区间，若 ，则翻译uI出符号 u；（4） 计算新值 ；()Fp（5） 重复（3） 、 （4）直到 .12(S), )L例 6-17 对例 6-16 中所得的码字 01010 进行译码。8. 译码方法的正确性命题 1. 由当且仅当 ui 是 S 的第一个符号。1(), ()iiCSFu由累积概率的递推公式可得， ()()(, (1)pFu

13、SF命题 2. 若 且1(), ()2Ap，()u则 1(), 2FSpS证明 由于 ，根据（1）可得 ()Au().AFS由于 ，()/() /2()()( /()(/2AFupSupuSFFSp第 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.