哈夫曼编码

列：假设某模型机共有7条指令，使用频度如图所示。

指令	使用频度	指令	使用频度
I1	0.15	I5	0.05
I2	0.03	I6	0.3
I3	0.4	I7	0.03
I4	0.04

1）若操作码用定长码表示，求操作码的码长、信息源熵H和信息冗余率。

2）采用哈夫曼编码，构造哈夫曼树，并求操作码平均码长和信息冗余率。

3）采用扩展操作码编码，求操作码平均码长和信息冗余率。

相关公式：

1. H：信息源商或者说最小冗余率

2. 信息冗余率=$\frac{平均码长-H}{平均码长}$

3. 平均码长=$\sum_{i=1}^n{pi*li}$；n是有多少条指令，pi是平度,li是哈夫曼编码之后的一个长度

4. 画哈夫曼树时：

   1. 从小到大按顺序排列频度
   2. 原始频度排最下面一行，
   3. 完成图后，标左1右0，

解1：

7个指令向上2的指数倍，定长码：$log_2{8}=3$

信息源熵$H=-\sum_{i=1}^7pi*log_2{pi}\approx2.17$

信息冗余率=$\frac{3-2.17}{3}\approx28\%$

解2：

指令	频度	哈夫曼操作码	哈夫曼码长
I3	0.4	0	1
I6	0.3	10	2
I1	0.15	110	3
I5	0.05	11100	5
I4	0.04	11101	5
I2	0.03	11110	5
I7	0.03	11111	5

平均码：$=\sum_{i=1}^7pi*li=0.4*1+0.3*2+0.15*3+(0.05+0.04+0.03+0.03)*5=2.2$

信息冗余率：$H=\frac{2.2-2.17}{2.2}\approx{1.36\%}$

解3：

指令	频度	哈夫曼操作码	哈夫曼码长	扩展码	扩展码长
I3	0.4	0	1	00	2
I6	0.3	10	2	01	2
I1	0.15	110	3	10	2
I5	0.05	11100	5	1100	4
I4	0.04	11101	5	1101	4
I2	0.03	11110	5	1110	4
I7	0.03	11111	5	1111	4

1. 前三个频度较高的指令，用2($log_24=2$)位二进制表示，留出11作为扩展码，参与剩下频度编码

平均码长：$\sum_{i=1}^7pi*li=(0.4+0.3+0.15)*2+(0.05+0.04+0.03+0.03)*4=1.7+0.6=2.3$

信息冗余率：$\frac{2.3-2.17}{2.3}\approx5.6\%$

延伸阅读