Booth算法(数学专业术语)
温馨提示:这篇文章已超过458天没有更新,请注意相关的内容是否还可用!
Booth算法
数学专业术语
比较好的带符号数乘法的方法是布斯(Booth)算法。它采用相加和相减的操作计算补码数据的乘积。Booth算法对乘数从低位开始判断,根据两个数据位的情况决定进行加法、减法还是仅仅移位操作。判断的两个数据位为当前位及其右边的位(初始时需要增加一个辅助位0),移位操作是向右移动。
中文名 | Booth算法 |
外文名 | Booth |
所属学科 | 数学 |
适用领域 | 信息科学 |
方法 | 操作计算补码数据的乘积 |
基本内容
在上例中,第一次判断被乘数0110中的最低位0以及右边的位(辅助位0),得00;所以只进行移位操作;第二次判断0110中的低两位,得10,所以作减法操作并移位,这个减法操作相当于减去2a的值;第三次判断被乘数的中间两位,得11,于是只作移位操作;第四次判断0110中的最高两位,得01,于是作加法操作和移位,这个加法相当于加上8a的值,因为a的值已经左移了三次。
一般而言,设y=y0,yly2…yn为被乘数,x为乘数,yi是a中的第i位(当前位)。根据yj与yi+1的值,Booth算法表示如下表所示,其操作流程如下图所示。在Booth算法中,操作的方式取决于表达式(yi+1-yi)的值,这个表达式的值所代表的操作为:
0无操作
+1加x
-1减x
Booth算法操作表示
yiyi+1操作说明
00无处于0串中,不需要操作
01加x1串的结尾
10减x1串的开始
11无处于1串中,不需要操作
乘法过程中,被乘数相对于乘积的左移操作可表示为乘以2,每次循环中的运算可表示为对于x(yi+1-yi)2^31-i项的加法运算(i=3l,30,…,1,0)。这样,Booth算法所计算的结果可表示为:
x×(0-y31)×2^0
+x×(y31-y30)×2^1
+x×(y30-y29)×2^2
…
+x×(y1-y0)×2^31
=x×(-y0×231+y1×2^30+y2×2^29+y31×2^0)
=x×y
举例
例:用Booth算法计算2×(-3)。
解:补=0010,补=1101,在乘法开始之前,R0和R1中的初始值为0000和1101,R2中的值为0010。
在乘法的第一个循环中,判断R1的最低位和辅助位为10,所以进入步骤1c,将R0的值减去R2的值,结果1110送人R0,然后进入第二步,将R0和Rl右移一位,R0和R1的结果为11110110,辅助位为l。
在第二个循环中,首先判断Rl的最低位和辅助位为0l,所以进入步骤1b,作加法,R0+R2=1111+0010,结果0001送入R0,这时R0R1的内容为00010110,在第二步右移后变为00001011,辅助位为0。
在第三次循环中,判断位为10,进入步骤lc,R0减去R2,结果1110送入R0,R1不变;步骤2移位后R0和R1的内容为111101011,辅助位为1。
第四次循环时,因两个判断位为11,所以不作加减运算,向右移位后的结果为11111010,这就是运算结果(—6)。
这个乘法的过程描述如下表所示,表中乘积一栏表示的是R0、R1的内容以及一个辅助位P,黑体字表示对两个判断位的判断。
用Booth补码一位乘法计算2×(-3)的过程
循环
步骤
乘积(R0,R1,P)
0
初始值
000011010
第一次循环
1c:减0010
111011010
2:右移1位
111101101
第二次循环
1b:加0010
000101101
2:右移1位
000010110
第三次循环
1c:减0010
111010110
2:右移1位
111101011
第四次循环
1a:无操作
111101011
2:右移1位
111110101
4.补码两位乘
补码两位乘运算规则是根据补码一位乘的规则,把比较yiyi+1的状态应执行的操作和比较yi-1yi的状态应执行的操作合并成一步,便可得出补码两位乘的运算方法。
补码两位乘法运算规则如下
判断位yi-1yiyi+1
操作内容
000
补=2-2补
001
补=2-2{补+补}
010
补=2-2{补+补}
011
补=2-2{补+2补}
100
补=2-2{补+2补}
101
补=2-2{补+补}
110
补=2-2{补+-x}补}
111
补=2-2补
由上表可见,操作中出现加2补和加2补,故除右移两位的操作外,还有被乘数左移一位的操作;而加2补和加2补,都可能因溢出而侵占双符号位,故部分积和被乘数采用三位符号位。
例:补=0.0101,补=1.0101求:补。
解:求解过程如下表所示。其中乘数取两位符号位即11.0101,补=1.1011取三符号位为111.1011。
部分积
乘数
说明
000.0000
+000.0101
1101010
判断位为010,加补
000.0101
000.0001
+000.0101
0111010
→2位
判断位为010,加补
000.0110
000.0001
+111.1011
01
1001110
→2位
判断位为110,加补
111.1100
1001
最后一步不移位,得补
故补=1.11001001
可见,与补码一位乘相比,补码两位乘的部分积多取一位符号位(共3位),乘数也多取一位符号位(共2位),这是由于乘数每次右移2位,且用3位判断,故采用双符号位更便于硬件实现。可见,当乘数数值位为偶数时,乘数取2位符号位,共需作n/2次移位,最多作n/2+1次加法,最后一步不移位;当n为奇数时,可补0变为偶数位,以简化逻辑操作。也可对乘数取1位符号位,此时共作n/2+1次加法和n/2+1次移位(最后一步移一位)。
对于整数补码乘法,其过程与小数乘法完全相同。为了区别于小数乘法,在书写上可将符号位和数值位中间的“.”改为“,”即可。
再补充一道例子,增加一下理解。呵呵
例1.37设被乘数M=0111(7),乘数Q=0011(3),相乘过程如下:(其中的①②……是我自己加上去的)
AQQ-1
①000000110初始值
②100100110A=A-M
③110010011右移(第1次循环)
④111001001右移(第2次循环)
⑤010101001A=A+M
⑥001010100右移(第3次循环)
⑦000101010右移(第4次循环)
乘法运算结束后,所得结果共8位,A寄存器中是乘积的高位部分,Q寄存器中是乘积的低位部分,即乘积=0010101=(21)(十进制)
例1.38设被乘数M=0111(7),乘数Q=1101(-3),相乘过程如下:
AQQ-1
000011010初始值
100111010A=A-M
110011101右移(第1次循环)
001111101A=A+M
000111110右移(第2次循环)
101011110A=A-M
110101111右移(第3次循环)
111010111右移(第4次循环)
乘积=11101011=(-21)(十进制)
其中的移位是循环移位.
被乘数n位要移位3次.
参考资料
1. booth算法什么时候结束·四川便利网