Untitled Document
利用哈夫曼树进行操作码编码的方法，又称为最小概率合并法。对于上面这个例子，具体的编码方法是：首先，把所有7条指令按照操作码在程序中出现的概率值，自左向右从排列好，每条指令是一各结点；然后，选取两个概率最小的结点合并成一个概率值是二者之和的新结点，并把这个新结点插入到其它还没有合并的结点中间；再在新的结点集合中选取两个概率最小的结点进行合并，如此继续进行下去，直至全部结点都合并完毕，最后得到一个根结点，根结点的概率值为1。
从图中可以看到，每个结点都有两个分支，分别用一位代码"0"和"1"表示。如果要得到某一条指令的操作码编码，可以从根结点开始，沿尖头所指方向，到达属于该指令的概率结点，把沿线所经过的代码组合起来得到这条指令的操作码编码。例如，要想得到概率值为0.15的指令的操作码编码，可以从概率值为1.00的根结点开始，沿箭头向右上方，到达概率值为0.55结点，于是得到第一位操作码"1"，继续向右上方，到达概率值为0.25结点，得到第二位操作码，也是"1"，最后沿向上的箭头，到达概率值为0.15的结点，得到最后一位操作码"0"，把所经过的代码组合起来得到概率值为0.15这条指令的操作码编码为"110"。
应当指出，采用上述方法形成的操作码编码并不是唯一的，只要将任意一个二叉结点上的"0"和"1"交换，就可以得到一组新的操作码编码。然而，无论怎样交换，操作码的平均长度是唯一的。
采用哈夫曼编码法所得到的操作码的平均长度为：
Pi表示第i种操作码在程序中出现的概率，Li表示第i种操作码的二进制位数，一共有n种操作码。
把具体数值代入，得到：
＝0.45×1＋0.30×2＋0.15×3＋0.05×4
＋0.03×5＋0.01×6＋0.01×6
＝1.97（位）
这种编码方法的信息冗余量很小，仅为：
与采用3位固定长操作码的信息冗余量35％相比要小得多。
2．扩展编码法
采用哈夫曼编码法能够使操作码得平均长度最短，信息的冗余量最小。然而，这种编码方法所形成得操作码很不规整。在上面这个例子中，7条指令就有6种不同长度的操作码。这样，既不利于硬件的译码，也不利于软件的编译。另外，它也很难与地址码配合，形成有规则长度的指令编码。
在许多处理机中，采用了一种折中的方法，称为扩展编码法。这种方法是由固定长操作码与哈夫曼编码法相结合形成的。
对于上一节中那个有7条指令的模型机的例子，如果采用扩展编码法编排操作码，可以有多种方法。如果要求把操作码最长不得超过5位，则可以采用1-2-3-5扩展编码法。如果要求把操作码最长不得超过4位，则可以采用2-4等长扩展编码法。编码结果如表3.3所示。
采用1-2-3-5扩展编码法的操作码最短平均长度为：
H＝0.45×1＋0.30×2＋0.15×3＋（0.05＋0.03＋0.01＋0.01）×5
＝2.00
信息冗余量为：
采用2-4等长扩展编码法的操作码最短平均长度为：
H＝（0.45＋0.30＋0.15）×2＋（0.05＋0.03＋0.01＋0.01）×4
＝2.20
信息冗余量为：
表3.3 模型机的操作码扩展编码法
指令序号
出现的概率
1-2-3-5扩展编码
2-4等长扩展编码
I1
0.45
0
00
I2
0.30
10
01
I3
0.15
110
10
I4
0.05
11100
1100
I5
0.03
11101
1101
I6
0.01
11110
1110
I7
0.01
11111
1111
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/96895.html
