How does Booth's algorithm work?

[saeddawoud]

Hello
How does Booth's algorithm work? I mean why some times we subtract the intermmediate product and some times we add it??!!
Regards

 

[sam536]

Re: hello


How Booths Algorithm Works ?

In two's complement multiplication B x A, the value A is

A = -2^{31} A_31 + 2^{30} A_30 + ... + 2 A_1 + A0.

The pair (A_i, A_{i-1}) and their difference, and operation are as follows
#===================================
A_i A_{i-1} (A_{i-1} - A_i) action
#====================================
0 0 0 do nothing
0 1 +1 add B (shifted)
1 0 -1 subtract B (shifted)
1 1 0 do nothing

So the value computed by Booth's algorithm is
(0 - A_0) * B
+ (A_0 - A_1) * B * 2
+ (A_1 - A_2) * B * 2^2
...
+ (A_29 - A_30) * B 2^30
+ (A_30 - A_31) * B * 2^31

After some simplification, the above expression reduce to
B * (A_0 + 2 * A_1 + ... + 2^30 * A_30 - 2^31 * A_31)
= B * A.
which is exactly the product of B and A.


Based on the above calculations, its directly used the partial products and these basic algortihm is modified to radix-2/4 modified Booths /recoder algorithms.

Best of Luck...

Regards,
Sam