信息与编码信息与编码7-3.doc

东北电力大学 教案封皮 开课单位 理学院信息与 计算教研室 课程名称 信息与编码 授课教师 常志文 授课对象 信息与计算专业121 选用教材 信息论与编码 理论（沈世镒） 总学时 60 （含课内实验10学时） 课次 7 第3章 第4~6节huffman编码算法 教学目的 及要求 教学目的及要求： 要求学生掌握Hufman编码的原理及编码算法； 掌握Huffman编码的性能与编码定理。 教学重点 处理安排 教学重点： Huffman编码算法与性能； 处理安排： 结合Huffman编码原理与平均码长来说明。 教学难点 处理安排 教学难点： Huffman编码算法的实现； 处理安排： 通过不同基数的 Huffman编码实例说明编码时的首次压缩与概率插位的 方法。 教学方式、 方法 方式（手段）：多媒体； 方法：讲授法。 教学 内容 及时 间分 配 第一节课： Huffman信源编码算法； 45 分钟 第二节课： Huffman信源编码性能分析； 30分钟 3.6信源定长编码的编码定理。 15分钟 例题、练习 题 例题：给定信源在不同基数的下的 Hufman编码实例 作业、思考 题 作业：P73页3.9题。  内 容 备注 3. 4 Huffman信源编码算法 3.4.1 霍夫曼编码的实例分析 例3.4.1已给信源概率分布为 ^{0.14,0.20,0.18,0.13,0.10,0.06,0.05,0.03,0.01}, 信号字母表U ={0,1,2,3}，求信源的霍夫曼编码. 解. 1构造霍夫曼数据压缩表 (1)首先把概率分布 p的概率按降序排列，并把它们作为霍夫曼数 据压缩表的第一列，该列长度为a =9.第一列、第四列、第六列为码兀 ， 由实例说明 暂空. Huffman信源编 (2)把第一列的3个最小的概率相加，得到新的一列概率分布，重新按 码算法详细过程。 降序排列，成为霍夫曼数据压缩表中的第三列.这时第三列的长度为 7,相 加后的数为0.09,我们用方框标出. (3)把第三列的4个最小的概率相加，得到新的一列概率分布，重新 按降序排列，成为霍夫曼数据压缩表中的第五列.这时第五列的长度为 4, 相加后的数为0.38,我们用方框标出.这样霍夫曼数据压缩表构造，有关计 算与列表结果见表 3.4.1. 2.用霍夫曼数据压缩表构造霍夫曼编码表 (1)因霍夫曼数据压缩表 3.4.1的第五列的概率分布只有 4行,因此它 们的编码下好是0,1,2,3.把这4个数填入霍夫曼编码表的第六列 .因此，第 六列是一个码长为 1的编码. ⑵在第五列中，带方框概率为 0.38,它对应的第六列的编码为 0,而 0.38是由第三列的0.13,0.10,0.09,0.06这4个数相加而成.这样我们构造 第三列概率分布的编码为：第三列的0.13,0.10,0.09,0.06这4个数的编码 是在0.38的编码0后边延长1个数，它们分别为00,01,02,03. 第三列中0.24,0.20,0.18这3个数的编码与第五列的编码相同 ，仍为 1,2,3不变. 把 0.24,0.20,0.18, 0.13,0.10,0.09,0.06 这 7 个数的编码 1,2, 33, 00, 01, 02, 03列入霍夫曼编码表的第四列 . (1)在表的第三列中，带方框的概率为 0.09,它对应的第四列的编码 为02,而0.09是由第一列的 0.05,0.03,0.01这3个数相加而成.这 样我们构造第一列概率分布的编码为 第 列的前6个数的编码与第三码的编码疋在第三列的 0.09的编 码02后边延长1个数， 因此它分别为020,021,022. 把第一列个概率的编码列入霍夫曼编码表的第二列 .最终完成霍夫 曼编码表.各项计算结果见表 3.4.2. 3.4.2 霍夫曼编码的一般算法 下面考虑一般情形.令码字母表为 U={0,1/ ；r 1}. 信源概率分布 为P = ( P1,…,Pa ).对此我们构造霍夫曼码的运算步骤如下 . 简单情形下的霍夫曼编码 如果a乞r,那么我们称信源为简单情形下的编码 ?这时直接取每个 消息元的编码为信元。? 霍夫曼数据压缩表 (1)由a ■ r确定霍夫曼数据压缩表的行、 列数.如记2k+2是数据压 缩表的列数,那么k为使kr _ k ? 1乞a 的最大值,因此取 a -1 k =lnt( ),其中lnt(z)是正数z的整数部分，而数据压缩表的第 r -1 通过实际例子说 明k,及第一次压 缩分量个数。1,3,5, ,2k - 1,2k 1列的行数(或列的长度 通过实际例子说 明k,及第一次压 缩分量个数。 a, kr「k 1, (k「1)r「k 2, ,3r「2,2r「1,r. (341) 这时除了第1,3列之外，后一列比前一列的长度少 r -