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/45360.html
