哈夫曼编码及平均编码长度_哈夫曼编码的平均码长

哈夫曼编码及平均编码长度_哈夫曼编码的平均码长Untitled Document利用哈夫曼树进行操作码编码的方法,又称为最小概率合并法。对于上面这个例子,具体的编码方法是:首先,把所有7条指令按照操作码在程序中出现的概率值,自左向右从排列好,每条指令是一各结点;然后,选取两个概率最小的结点合并成一个概率值

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

(0)
上一篇 2024年 9月 8日
下一篇 2024年 9月 8日

相关推荐

关注微信