Booth提出补码乘法公式新变形
• Booth一位乘(每次乘一位)
已知[X]补和[Y]补,求[X*Y]补
[X*Y] 补 = - [X] 补 *(y 31 *2 31 ) [X] 补 * (y 30 *2 30 ) ...... [X] 补 * (y 1 *2 1 ) [X] 补 * (y 0 *2 0 )
当y i 取值0/1时,有
[X] 补 * (y n *2 n ) = [X] 补 * (y n *2 n 1 )-[X] 补 * (y n *2 n )
[X] 补 *(y a -y b ) =[X] 补 *y a - [X] 补 * y b
得
[X*Y] 补 = [X] 补 *(y 30 -y 31 ) *2 31 [X] 补 * (y 29 -y 30 ) *2 30 ...... [X] 补 *(y -1 -y 0 ) *2 0
• 每次循环公式相同,最高位不需额外处理,仍需N次循环
• Booth两位乘(每次乘两位)
对(-y 31 *2 31 y 30 *2 30 ...... y 1 *2 1 y 0 *2 0 )进行变换
(-y 31 *2 31 y 30 *2 30 ...... y 1 *2 1 y 0 *2 0 )
= (y 29 y 30 -2*y 31 ) *2 30 (y 27 y 28 -2*y 29 ) *2 28 ...... (y 1 y 2 -2*y 3 ) *2 2 (y -1 y 0 -2*y 1 ) *2 0
• 每次循环公式相同,最高位不需额外处理,只需N/2次循环
两位乘电路
[X]补表示为x 7 x 6 x 5 x 4 x 3 x 2 x 1 x 0
• 部分积表示为p 7 p 6 p 5 p 4 p 3 p 2 p 1 p 0 c
• 补码减法 = 按位取反再 1
• 注意左移的处理方式
Booth算法的串行实现
• 以二位一乘为例,32位定点乘法需要把16个数相加
• 可以用一个加法器加15次,需要15个时钟周期
