题目
某机有10条指令,使用频度分别为:0.01、0.15、0.12、0.07、0.08、0.13、0.15、0.03、0.17、0.09。(1)求等长操作码编码的平均码长;(2)构造Huffman树;(3)写出Huffman的一种编码,并计算其平均码长;(4)只有两种码长,求平均码长最短的扩展操作码编码及其平均码长。
某机有10条指令,使用频度分别为:0.01、0.15、0.12、0.07、0.08、0.13、0.15、0.03、0.17、0.09。
(1)求等长操作码编码的平均码长;
(2)构造Huffman树;
(3)写出Huffman的一种编码,并计算其平均码长;
(4)只有两种码长,求平均码长最短的扩展操作码编码及其平均码长。
题目解答
答案
(1)10条指令的等长操作码的平均码长是[log210]+1位,即4位。
(2)构造Huffman树如下图所示。
(3)Huffman编码(不唯一)为
使用频度 编码
0.01 00000
0.03 00001
0.07 0001
0.08 010
0.09 011
0.12 001
0.13 100
0.15 101
0.15 110
0.17 111
平均码长为
=3.15位。
=3.15位。(4)扩展操作码编码(不唯一)为
使用频度 扩展码
0.01 0000
0.03 0001
0.07 0010
0.08 0011
0.09 010
0.12 011
0.13 100
0.15 101
0.15 110
0.17 111
平均码长为=3.19位。
=3.19位。