某模型机有 10 条指令 I0~I9,它们的使用频度分别为:0.28,0.17, 0.14,0.12,0.09,0.08,0.05,0.04,0.02,0.0l 。 (1)计算 10 条指令 I0~I9的信息熵 H。 (2)计算采用等长操作码编码时的平均长度 L1和编码冗余量 R1。 (3)设计该指令集的 Huffman 编码,画出 Huffman 树,并计算所设计 Huffman 编码的平均长度 L2和编码冗余量 R2。
时间: 2023-06-17 11:05:03 浏览: 100
(1) 信息熵的计算公式为:$H = - \sum_{i=0}^{9} p_i \log_2 p_i$,其中 $p_i$ 表示第 $i$ 条指令的使用频率。
代入数据得,$H = -0.28\log_2 0.28 - 0.17\log_2 0.17 - \cdots - 0.01\log_2 0.01 \approx 3.055$。
(2) 采用等长操作码编码时,每条指令编码长度相同,即 $L1 = \log_2 10 \approx 3.322$。
编码冗余量 $R1 = L1 - H \approx 0.267$。
(3) 设计 Huffman 编码的步骤如下:
- 按照使用频率从小到大排序,得到以下表格:
| 指令 | 使用频率 |
| ---- | -------- |
| I9 | 0.01 |
| I8 | 0.02 |
| I7 | 0.04 |
| I6 | 0.05 |
| I5 | 0.08 |
| I4 | 0.09 |
| I3 | 0.12 |
| I2 | 0.14 |
| I1 | 0.17 |
| I0 | 0.28 |
- 将频率最小的两个节点合并,并将它们的频率相加,得到一个新节点。重复此步骤,直到只剩下一个节点为止。合并的过程可以用一棵树来表示,称为 Huffman 树。
首先合并 I9 和 I8,得到一个频率为 0.03 的新节点:
![](https://i.imgur.com/HRJoQaC.png)
然后合并 I7 和新节点,得到一个频率为 0.07 的新节点:
![](https://i.imgur.com/8nLzNtM.png)
接着合并 I6 和新节点,得到一个频率为 0.12 的新节点:
![](https://i.imgur.com/P6XjZ1z.png)
再合并 I5 和新节点,得到一个频率为 0.2 的新节点:
![](https://i.imgur.com/9XNpX5s.png)
接着合并 I4 和新节点,得到一个频率为 0.29 的新节点:
![](https://i.imgur.com/mwQI9gW.png)
继续合并 I3 和新节点,得到一个频率为 0.41 的新节点:
![](https://i.imgur.com/sXQjzZP.png)
接着合并 I2 和新节点,得到一个频率为 0.55 的新节点:
![](https://i.imgur.com/3R6w1Yt.png)
再合并 I1 和新节点,得到一个频率为 0.72 的新节点:
![](https://i.imgur.com/8aYopQc.png)
最后合并 I0 和新节点,得到一棵完整的 Huffman 树:
![](https://i.imgur.com/3aVrnmH.png)
- 根据 Huffman 树,对每个节点进行编码。从根节点开始,向左走为编码 0,向右走为编码 1。最终得到以下表格:
| 指令 | 使用频率 | Huffman 编码 |
| ---- | -------- | ------------ |
| I9 | 0.01 | 1111111110 |
| I8 | 0.02 | 1111111111 |
| I7 | 0.04 | 111111100 |
| I6 | 0.05 | 11111100 |
| I5 | 0.08 | 111110 |
| I4 | 0.09 | 11110 |
| I3 | 0.12 | 1110 |
| I2 | 0.14 | 110 |
| I1 | 0.17 | 10 |
| I0 | 0.28 | 0 |
- 计算 Huffman 编码的平均长度 $L2$ 和编码冗余量 $R2$。
平均长度 $L2 = \sum_{i=0}^{9} p_i l_i$,其中 $l_i$ 表示第 $i$ 条指令的 Huffman 编码长度。
代入数据得,$L2 = 0.01 \times 10 + 0.02 \times 10 + \cdots + 0.28 \times 1 \approx 2.65$。
编码冗余量 $R2 = L2 - H \approx -0.405$,说明 Huffman 编码比等长操作码编码更加紧凑。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)