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

第２５卷第３期　晋中学院学报　ｖｏ１．２５　Ｎｏ．３　２００８年６月　Ｊｏｕｒｎａｌ　ｏｆ　Ｊｉｎｚｈｏｎｇ　Ｕｒｔｉｖｅｒｓｉｔｙ　ＪＲ．　２００８　用ＢＯＯＴＨ算法改进的计算机定点乘法运算　陈苏豫　（商丘师范学院计算机科学系，河南商丘４７６０００）　摘要：普通的定点乘法运算算法简单易于理解，但是采用这种算法的计算机运算效率不　高，倘如采用ＢＯＯＴＨ算法可以在一定程度上提高计算机的运算效率．　关键词：ＢＯＯＴＨ；算法；定点乘法运算　中图分类号：ＴＰ３０１．６　文献标识码：Ａ　文章编号：１６７３—１８０８（２００８）０３—００９１—０３　目前常见的计算机组成原理本科教材中关于计算机乘法尤其是定点乘法运算采用的是普通移位相加　的算法逻辑，这种算法思想直接、简单，易于教师的讲解，同时也利于学生的接受．但是这种关于定点数的乘　法算法在现实运用中是有缺陷的．相对于普通移位相加算法来说，采用ＢＯＯＴＨ算法思想设计的乘法器不仅　所需硬件的数量更少而且执行效率也更高，可以说ＢＯＯＴＨ算法是一个比较好的关于定点乘法运算的算法．　１　ＢＯＯＴＨ算法的算法思想　普通移位相加算法从其基本实现方法来看，乘数的每一位都产生部分积，并且运算量较大．实际上当乘　数中某一位为０时，并不需要进行累加运算，所以累加器需要完成的累加次数（实际要生成的累加项的数　目）应该与乘数中值为１的位数相同．这样，如果能将乘数中值为１的位数减少，就可以减少所需要完成的　累加次数．ＢＯＯＴＨ算法的算法思想是让乘数近似于某个较大的整值，然后用这个整值数与被乘数的积减去　其对应这个整值数的补数与被乘数的乘积来进行计算，从而提高了乘法的运算效率．　１．１　ＢＯＯＴＨ算法的运算规则　ＢＯＯＴＨ算法最早是由ＢＯＯＴＨ夫妇提出来的，也称补码一位算法．其运算规则如下：　①符号位参与运算，运算的数均以补码表示．　②乘数末位增设附加位且初值为０．　③观察乘数最末两位：若是００执行部分积右移一位操作．若是０１执行部分积加［被乘数］补，结果右移　一位．若是１０执行部分积加［一被乘数］补，结果右移一位．若是１１也仅执行部分积右移一位．　④按照上述算法进行ｎ＋１（ｎ表示数据数值的位数不包括符号位在内）步操作，但第ｎ＋１步不再移位，　最终所得结果即为运算结果．　１．２　ＢＯＯＴＨ算法的硬件实现结构图　乘数和被乘数均以补码表示分别装入两个寄存器（Ｑ和Ｍ）中．因为是乘法运算还需一个寄存器（Ａ）并　且初始化为０，此寄存器与乘数寄存器一起用于存放最终的运算结果．不过还需一个１位寄存器，逻辑上位　于Ｑ寄存器的最低位（Ｑ０）的右边，命名为Ｑ／初始化也为０．乘法器工作时，控制逻辑每次读Ｑ０和Ｑ／两位．　若两位相同，则Ａ、Ｑ和Ｑ／寄存器的所有位向右移一位（Ｑ／被Ｑ０中的内容替代以此类推）．若两位不同，则　根据两位是０—１还是１—０来决定是Ａ寄存器是加上被乘数（Ｍ）再右移还是加上被乘数取负后的补码再右　移．另外要注意的是右移过程保留Ａ的最高位也就是Ａ寄存器中数据的符号位，其实Ａ寄存器的这种右移　【收稿日期］２００８—０２—２８　［作者简介］陈苏豫（１９８１一），男，河南商丘人，商丘师范学院计算机科学系，助教，硕士，研究方向：计算机原理、信息管理系统　开发．　・９１　・　维普资讯 http://www.cqvip.com 陈苏豫　用ＢＯＯＴＨ算法改进的计算机定点乘法运算　方式是寄存器中的算术移位方式．硬件结构图如下图所示：　被乘数　图１　ＢＯＯＴＨ算法的硬件组织结构图　从上述的算法规则中不难看出ＢＯＯＴＨ算法不是每一步均采用移位相加，所以减少了运算步骤，提高了　执行效率．不仅如此，在硬件设计方面，也仅用到了较少的寄存器便实现了定点数的乘法．　２　ＢＯＯＴＨ算法工作原理　ＢＯＯＴＨ算法优化乘法运算的原理并不复杂，而是源于二进制定点数本身的特点．假设有一正乘数，这　个数的两边是０，中间是１．例如０００１１１１０，对于任一个数Ｍ来说，　Ｍ＊（０００１１１１０）＝Ｍ＊（２４＋２３＋２２＋２　）　可以通过８次移位４次相加来实现．　但是如果我们观察出　２ｎ＋２ｎ一１＋…＋２ｎ—ｋ：２ｎ　ｌ一２ｎ—ｋ　也就是把乘数凑成一个较大的整数和一个补数差的形式，则　Ｍ＊（０００１１１１０）＝Ｍ＊（２５—２　）　表面上看是减少了乘数中１的个数，但从本质上说是减少了运算的步骤．通过被乘数的一次减法（相当　于加上被乘数取负后的补码）和一次加法运算来产生结果，当扫描到最末两位是１—０时执行减法，是０—１　时执行加法，是０—０或１—１仅移位不运算．可见本题通过两步运算操作即可得出结果而不是我们事先认　为的进行４次加法运算．这种策略扩展到乘数中有任意个１的情况依然适用．　对于最高位为数值位而非符号位的无符号数乘法运算，传统的移位相加算法和ＢＯＯＴＨ算法都能顺利　地完成，他们之间的区别仅仅是算法效率上的差别．但是对于负数参与的定点乘法运算，传统的移位相加算　法就不适用了．例如：１１（１０１１）乘以１３（１１０１）采用两种方法都能得出正确结果１４３（１０００１１１１），若认为１０１１　和１　１０１这两个数最高位为符号位，采用传统的移位相加算法得到的仍然是最高位为１的数１０００１　１　１　１，两个　负数的积仍是负数，显然这个结果显然是错误的．传统的改进做法是把符号位与数值位分别进行计算然后　再通过一步转换得出最终结果，而采用ＢＯＯＴＨ算法符号位参与运算不需要最后再做转换．对于操作数是负　数ＢＯＯＴＨ算法也能优化运算过程，推导过程如下：　假设ｘ是一个补码表示的负数，　Ｘ＝｛ｌｘｎ－２ｘ　一３…Ｘ１ｘｏ｝　其最高位为符号位，它的值可以表示成　Ｘ＝一２ｎ—ｌ＋Ｘｎ一２＊２“一ｚ＋Ｘｎ３＊２“一ｊ＋…一＋Ｘ１＊２　＋ｘｏ＊２ｌＵ　（１）　因为ｘ是负数所以ｘ的最左边的一位一定是１，假定最左的０在第ｋ位置上．ｘ可以表示为如下的形　式：　Ｘ＝｛１１１…１０ｘｋ一１Ｘｋ一２…ｘｌｘｏ｝　・（２）　９２・　维普资讯 http://www.cqvip.com 陈苏豫　用ＢＯＯＴＨ算法改进的计算机定点乘法运算　其值为　Ｘ＝一２“一　＋２“一２＋２ｋ＋　＋ｘｋ一　＊２ｋ一　＋…．．．＋ｘｏ＊２０　（３）　我们前面已知　２ｎ一２＋２ｎ一３＋…＋２　１：２ｎ一　一２　（４）　移项可得　一２ｎ一　＋２ｎ一　＋２ｎ一　＋…＋２　＝一２　（５）　（５）代入（３），得到　Ｘ：一２　＋　＋　一　＊２ｋ一　＋…＋ｘ０＊２０　（６）　从前面的推导很容易看出，从ｘ０起到最左的０的所有位也同样都能被适当处理．当算法扫描经过最左　的０而遇到Ｉ（Ｒ［Ｊ　２ｋ　）时，出现一个１０变化，于是一个减法发生（即一２ｋ　），而随后便不会进行任何的运算　了，仅作移位操作就能得到最终的结果．同理可知，倘如算法扫描１后遇到０即出现一个０１变化，就会做一　个加法运算，而如果是扫描遇到的是００或是１１则不运算直接移位即可．　例如让某数Ｍ乘以一６．假设字长８位，则一６的补码表示式为１１１１１０１０．由（１）可知　一６：一２７＋２６＋２５＋２４＋２３＋２　于是有　Ｍ＊（１１１１１０１０）＝Ｍ＊（一２７＋２６＋２５＋２４＋２３＋２　）　代入（６）式　Ｍ＊（１１１１１０１０）＝Ｍ＊（一２　＋２　）　即　Ｍ＊（１１１１１０１０）＝Ｍ＊（一２　＋２７—２　）　由上述等式可以看出：若采用ＢＯＯＴＨ算法则运算步骤减少到了３步，定点乘法运算的执行效率得以提　高．即便本方法存在最坏情况如乘数为１０１０…或者０１０１…的情况，ＢＯＯＴＨ算法虽然不能有效地减少运算步　骤，但是因为整个算法流程简单不需要对结果进行转换即可生成，在硬件的设计和实现上仍占有优势．　３结论　ＢＯＯＴＨ算法不仅适用整数的定点运算，而且适用负数的定点运算．另外在硬件实现方面，采用ＢＯＯＴＨ　算法思想设计的乘法运算器与普通移位相加算法设计的运算器相比需要的硬件设备更少，基于ＢＯＯＴＨ算　法思想设计的乘法器执行效率也更高．　［参考文献］　［１］白中英．计算机组成原理［Ｍ］．北京：科学出版社，２０００．　［２］白中英．计算机组成原理——试题，题度与试验［Ｍ］．北京：科学出版社，２００１．　［３］王爱英．计算机组成与结构［Ｍ］．北京：清华大学出版社，２００１．　［４］张基温．计算机组成原理教程一题解与试验指导［Ｍ］．北京：清华大学出版社，２００１　（责任编辑张莺）　・９３　・