您好,欢迎来到爱问旅游网。
搜索
您的当前位置:首页用BOOTH算法改进的计算机定点乘法运算

用BOOTH算法改进的计算机定点乘法运算

来源:爱问旅游网
维普资讯 http://www.cqvip.com

第25卷第3期 晋中学院学报 vo1.25 No.3 2008年6月 Journal of Jinzhong Urtiversity JR. 2008 用BOOTH算法改进的计算机定点乘法运算 陈苏豫 (商丘师范学院计算机科学系,河南商丘476000) 摘要:普通的定点乘法运算算法简单易于理解,但是采用这种算法的计算机运算效率不 高,倘如采用BOOTH算法可以在一定程度上提高计算机的运算效率. 关键词:BOOTH;算法;定点乘法运算 中图分类号:TP301.6 文献标识码:A 文章编号:1673—1808(2008)03—0091—03 目前常见的计算机组成原理本科教材中关于计算机乘法尤其是定点乘法运算采用的是普通移位相加 的算法逻辑,这种算法思想直接、简单,易于教师的讲解,同时也利于学生的接受.但是这种关于定点数的乘 法算法在现实运用中是有缺陷的.相对于普通移位相加算法来说,采用BOOTH算法思想设计的乘法器不仅 所需硬件的数量更少而且执行效率也更高,可以说BOOTH算法是一个比较好的关于定点乘法运算的算法. 1 BOOTH算法的算法思想 普通移位相加算法从其基本实现方法来看,乘数的每一位都产生部分积,并且运算量较大.实际上当乘 数中某一位为0时,并不需要进行累加运算,所以累加器需要完成的累加次数(实际要生成的累加项的数 目)应该与乘数中值为1的位数相同.这样,如果能将乘数中值为1的位数减少,就可以减少所需要完成的 累加次数.BOOTH算法的算法思想是让乘数近似于某个较大的整值,然后用这个整值数与被乘数的积减去 其对应这个整值数的补数与被乘数的乘积来进行计算,从而提高了乘法的运算效率. 1.1 BOOTH算法的运算规则 BOOTH算法最早是由BOOTH夫妇提出来的,也称补码一位算法.其运算规则如下: ①符号位参与运算,运算的数均以补码表示. ②乘数末位增设附加位且初值为0. ③观察乘数最末两位:若是00执行部分积右移一位操作.若是01执行部分积加[被乘数]补,结果右移 一位.若是10执行部分积加[一被乘数]补,结果右移一位.若是11也仅执行部分积右移一位. ④按照上述算法进行n+1(n表示数据数值的位数不包括符号位在内)步操作,但第n+1步不再移位, 最终所得结果即为运算结果. 1.2 BOOTH算法的硬件实现结构图 乘数和被乘数均以补码表示分别装入两个寄存器(Q和M)中.因为是乘法运算还需一个寄存器(A)并 且初始化为0,此寄存器与乘数寄存器一起用于存放最终的运算结果.不过还需一个1位寄存器,逻辑上位 于Q寄存器的最低位(Q0)的右边,命名为Q/初始化也为0.乘法器工作时,控制逻辑每次读Q0和Q/两位. 若两位相同,则A、Q和Q/寄存器的所有位向右移一位(Q/被Q0中的内容替代以此类推).若两位不同,则 根据两位是0—1还是1—0来决定是A寄存器是加上被乘数(M)再右移还是加上被乘数取负后的补码再右 移.另外要注意的是右移过程保留A的最高位也就是A寄存器中数据的符号位,其实A寄存器的这种右移 【收稿日期]2008—02—28 [作者简介]陈苏豫(1981一),男,河南商丘人,商丘师范学院计算机科学系,助教,硕士,研究方向:计算机原理、信息管理系统 开发. ・91 ・ 维普资讯 http://www.cqvip.com 陈苏豫 用BOOTH算法改进的计算机定点乘法运算 方式是寄存器中的算术移位方式.硬件结构图如下图所示: 被乘数 图1 BOOTH算法的硬件组织结构图 从上述的算法规则中不难看出BOOTH算法不是每一步均采用移位相加,所以减少了运算步骤,提高了 执行效率.不仅如此,在硬件设计方面,也仅用到了较少的寄存器便实现了定点数的乘法. 2 BOOTH算法工作原理 BOOTH算法优化乘法运算的原理并不复杂,而是源于二进制定点数本身的特点.假设有一正乘数,这 个数的两边是0,中间是1.例如00011110,对于任一个数M来说, M*(00011110)=M*(24+23+22+2 ) 可以通过8次移位4次相加来实现. 但是如果我们观察出 2n+2n一1+…+2n—k:2n l一2n—k 也就是把乘数凑成一个较大的整数和一个补数差的形式,则 M*(00011110)=M*(25—2 ) 表面上看是减少了乘数中1的个数,但从本质上说是减少了运算的步骤.通过被乘数的一次减法(相当 于加上被乘数取负后的补码)和一次加法运算来产生结果,当扫描到最末两位是1—0时执行减法,是0—1 时执行加法,是0—0或1—1仅移位不运算.可见本题通过两步运算操作即可得出结果而不是我们事先认 为的进行4次加法运算.这种策略扩展到乘数中有任意个1的情况依然适用. 对于最高位为数值位而非符号位的无符号数乘法运算,传统的移位相加算法和BOOTH算法都能顺利 地完成,他们之间的区别仅仅是算法效率上的差别.但是对于负数参与的定点乘法运算,传统的移位相加算 法就不适用了.例如:11(1011)乘以13(1101)采用两种方法都能得出正确结果143(10001111),若认为1011 和1 101这两个数最高位为符号位,采用传统的移位相加算法得到的仍然是最高位为1的数10001 1 1 1,两个 负数的积仍是负数,显然这个结果显然是错误的.传统的改进做法是把符号位与数值位分别进行计算然后 再通过一步转换得出最终结果,而采用BOOTH算法符号位参与运算不需要最后再做转换.对于操作数是负 数BOOTH算法也能优化运算过程,推导过程如下: 假设x是一个补码表示的负数, X={lxn-2x 一3…X1xo} 其最高位为符号位,它的值可以表示成 X=一2n—l+Xn一2*2“一z+Xn3*2“一j+…一+X1*2 +xo*2lU (1) 因为x是负数所以x的最左边的一位一定是1,假定最左的0在第k位置上.x可以表示为如下的形 式: X={111…10xk一1Xk一2…xlxo} ・(2) 92・ 维普资讯 http://www.cqvip.com 陈苏豫 用BOOTH算法改进的计算机定点乘法运算 其值为 X=一2“一 +2“一2+2k+ +xk一 *2k一 +…...+xo*20 (3) 我们前面已知 2n一2+2n一3+…+2 1:2n一 一2 (4) 移项可得 一2n一 +2n一 +2n一 +…+2 =一2 (5) (5)代入(3),得到 X:一2 + + 一 *2k一 +…+x0*20 (6) 从前面的推导很容易看出,从x0起到最左的0的所有位也同样都能被适当处理.当算法扫描经过最左 的0而遇到I(R[J 2k )时,出现一个10变化,于是一个减法发生(即一2k ),而随后便不会进行任何的运算 了,仅作移位操作就能得到最终的结果.同理可知,倘如算法扫描1后遇到0即出现一个01变化,就会做一 个加法运算,而如果是扫描遇到的是00或是11则不运算直接移位即可. 例如让某数M乘以一6.假设字长8位,则一6的补码表示式为11111010.由(1)可知 一6:一27+26+25+24+23+2 于是有 M*(11111010)=M*(一27+26+25+24+23+2 ) 代入(6)式 M*(11111010)=M*(一2 +2 ) 即 M*(11111010)=M*(一2 +27—2 ) 由上述等式可以看出:若采用BOOTH算法则运算步骤减少到了3步,定点乘法运算的执行效率得以提 高.即便本方法存在最坏情况如乘数为1010…或者0101…的情况,BOOTH算法虽然不能有效地减少运算步 骤,但是因为整个算法流程简单不需要对结果进行转换即可生成,在硬件的设计和实现上仍占有优势. 3结论 BOOTH算法不仅适用整数的定点运算,而且适用负数的定点运算.另外在硬件实现方面,采用BOOTH 算法思想设计的乘法运算器与普通移位相加算法设计的运算器相比需要的硬件设备更少,基于BOOTH算 法思想设计的乘法器执行效率也更高. [参考文献] [1]白中英.计算机组成原理[M].北京:科学出版社,2000. [2]白中英.计算机组成原理——试题,题度与试验[M].北京:科学出版社,2001. [3]王爱英.计算机组成与结构[M].北京:清华大学出版社,2001. [4]张基温.计算机组成原理教程一题解与试验指导[M].北京:清华大学出版社,2001 (责任编辑张莺) ・93 ・ 

因篇幅问题不能全部显示,请点此查看更多更全内容

热门图文

Copyright © 2019-2025 awee.cn 版权所有 湘ICP备2023022495号-5

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务