哈夫曼编码的平均长度_曼彻斯特编码1是从低到高吗

2024年 8月 6日下午1:21 • 激活谷笔记

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

哈夫曼编码的平均长度_曼彻斯特编码1是从低到高吗

相关推荐