Booth提出补码乘法公式新变形
•Booth一位乘(每次乘一位)
已知[X]补和[Y]补,求[X*Y]补
[X*Y]补=-[X]补*(y31*231)+[X]补*(y30*230)++[X]补*(y1*21)+[X]补*(y0*20)
当yi取值0/1时,有
[X]补*(yn*2n)=[X]补*(yn*2n+1)-[X]补*(yn*2n)
[X]补*(ya-yb)=[X]补*ya-[X]补*yb
得
[X*Y]补=[X]补*(y30-y31)*231+[X]补*(y29-y30)*230++[X]补*(y-1-y0)*20
•每次循环公式相同,最高位不需额外处理,仍需N次循环
•Booth两位乘(每次乘两位)
对(-y31*231+y30*230++y1*21+y0*20)进行变换
(-y31*231+y30*230++y1*21+y0*20)
=(y29+y30-2*y31)*230+(y27+y28-2*y29)*228++(y1+y2-2*y3)*22+(y-1+y0-2*y1)*20
•每次循环公式相同,最高位不需额外处理,只需N/2次循环
两位乘电路
[X]补表示为x7x6x5x4x3x2x1x0
•部分积表示为p7p6p5p4p3p2p1p0+c
•补码减法=按位取反再+1
•注意左移的处理方式
Booth算法的串行实现
•以二位一乘为例,32位定点乘法需要把16个数相加
•可以用一个加法器加15次,需要15个时钟周期