例5.5 某模型计算机共有7种不同的指令,如采用固定长操作码则操作码字段需-|||-要3位。已知各种指令在程序中出现的概率如表5.3所示,计算采用Huffman编码法的-|||-操作码平均长度,并计算固定长操作码和Huffman操作码的信息冗余量(以最短平均长-|||-度为标准)。-|||-表5.3 各种指令的使用频度-|||-I1 I2 I3 I4 Is I6 I7-|||-使用频度 0.45 0.30 0.15 0.05 0.03 0.01 0.01

考查要点：本题主要考查Huffman编码的构造方法、平均码长的计算，以及信息冗余量的比较。

解题核心思路：

1. Huffman编码构造：根据各指令的使用频度，构造Huffman树，确定每个指令的编码长度。
2. 平均码长计算：将各指令的编码长度与其概率相乘求和。
3. 信息冗余量计算：通过香农熵（最短平均长度）与实际平均码长的比值，计算冗余量；对比固定长和Huffman编码的冗余量。

破题关键点：

• 正确构造Huffman树：每次合并当前最小的两个概率，生成前缀编码。
• 香农熵的计算：需准确计算各指令的香农信息量之和。
• 冗余量公式应用：注意区分固定长和Huffman编码的平均码长。

1. Huffman编码构造

1. 排序概率：将指令按使用频度从小到大排列：0.01, 0.01, 0.03, 0.05, 0.15, 0.30, 0.45。
2. 合并最小概率：
   • 合并两个最小概率0.01和0.01，得到新节点0.02。
   • 依次合并0.02和0.03（0.05），0.05和0.05（0.10），0.10和0.15（0.25），0.25和0.30（0.55），最终合并0.55和0.45（1.0）。
3. 确定编码长度：根据合并顺序，编码长度依次为1位（I1）、2位（I2）、3位（I3）、4位（I4）、5位（I5）、6位（I6、I7）。

2. 平均码长计算

$A = 0.45 \times 1 + 0.30 \times 2 + 0.15 \times 3 + 0.05 \times 4 + 0.03 \times 5 + 0.01 \times 6 + 0.01 \times 6 = 1.97 \text{位}$

3. 香农熵（最短平均长度）

香农熵公式：
$H = -\sum p_i \log_2 p_i$
计算得：
$H = 0.45 \times 1.152 + 0.30 \times 1.737 + 0.15 \times 2.737 + 0.05 \times 4.322 + 0.03 \times 5.060 + 0.01 \times 6.644 \times 2 = 1.95 \text{位}$

4. 信息冗余量计算

• Huffman编码冗余量：
  $R = 1 - \frac{H}{A} = 1 - \frac{1.95}{1.97} \approx 1.0\%$
• 固定长冗余量：
  $R = 1 - \frac{H}{L} = 1 - \frac{1.95}{3} \approx 35\%$