booth算法(补码乘法).doc

《booth算法(补码乘法).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、今天看到一种实现乘法的新算法——BOOTH算法，现在刚刚摸索到算法的本质，知道为什么这样做就可以实现乘法功能。废话少说，具体介绍如下：      布斯(Booth)算法是比较好的带符号数乘法的方法。它采用相加和相减的操作计算补码数据的乘积。Booth算法对乘数从低位开始判断，根据两个数据位的情况决定进行加法、减法还是仅仅移位操作。判断的两个数据位为当前位及其右边的位(初始时需要增加一个辅助位0)，移位操作是向右移动。   乘法过程中，被乘数相对于乘积的左移操作可表示为乘以2，设y=y0,yly2…yn为被乘数，x为乘数，每次循环中的运算可表示为对于x(yi+1-

2、yi)2^（n-i）项的加法运算(i=n，n-1，…，1，0)。这样，Booth算法所计算的结果 可表示为：(被乘数是两数相乘的后者，如A×B中的被乘数是A，但是这里貌似与这个没有关系)　　x×(0-yn)×2^0　　+x×(yn-yn-1)×2^1　　…　　+x×(y1-y0)×2^n　　=x×(-y0×2^n+y1×2^(n-1)+y2×2^(n-2)+……+yn×2^0)　　=x×y（这里切记一点y0是符号位）Booth算法表示如下表所示。在Booth算法中，操作的方式取决于表达式(yi+1-yi)的值，这个表达式的值所代表的操作为：　　0  无操作　　+

3、1  加x　　-1   减x　　Booth算法操作表示　　yiyi+1   操作     说明　　0  0       无       处于0串中，不需要操作　　0  1       加x     1串的结尾 　　1  0       减x     1串的开始 　　1  1      无       处于1串中，不需要操作例：用Booth算法计算2×(-3)。　　解：[2]补=0010，[-3]补=1101，在乘法开始之前，R0和R1中的初始值为0000和1101，R2中的值为0010。　　在乘法的第一个循环中，判断R1的最低位和辅助位为10，所以进入步骤1c，

4、将R0的值减去R2的值，结果1110送人R0，然后进入第二步，将R0和Rl右移一位，R0和R1的结果为1111、0110，辅助位为l。　　在第二个循环中，首先判断Rl的最低位和辅助位为0l，所以进入步骤1b，作加法，R0+R2=1111+0010，结果0001送入R0，这时R0R1的内容为00010110，在第二步右移后变为00001011，辅助位为0。　　在第三次循环中，判断位为10，进入步骤lc，R0减去R2，结果1110送入R0，R1不变；步骤2移位后R0和R1的内容为11110101，辅助位为1。　　第四次循环时，因两个判断位为11，所以不作加减运算，向

5、右移位后的结果为11111010，这就是运算结果(—6)。（结果result={R0,R1}）在每次移位都是{R0，R1}同时移位。用Booth补码一位乘法计算2×(-3)的过程　　循环　　步骤　　乘积 （R0, R1, P）　　初始值　　000011010　　第一次循环　　1c：减0010　　111011010　　2：右移1位　　111101101　　第二次循环　　1b：加0010　　000101101　　2：右移1位　　000010110　　第三次循环　　1c：减0010　　111010110　　2：右移1位　　111101011　　第四次循环　　1a：无操

6、作　　111101011　　2：右移1位　　111110101