Booth's Multiplication Algorithm
Essay by review • December 4, 2010 • Study Guide • 409 Words (2 Pages) • 1,025 Views
Booth's multiplication algorithm
Procedure
If x is the count of bits of the multiplicand, and y is the count of bits of the multiplier :
* Draw a grid of three lines, each with squares for x + y + 1 bits. Label the lines respectively A (add), S (subtract), and P (product).
* In two's complement notation, fill the first x bits of each line with :
o A: the multiplicand
o S: the negative of the multiplicand
o P: zeroes
* Fill the next y bits of each line with :
o A: zeroes
o S: zeroes
o P: the multiplier
* Fill the last bit of each line with a zero.
* Do both of these steps |y| (the Absolute Value of y) times :
1. If the last two bits in the product are...
 00 or 11: do nothing.
 01: P = P + A. Ignore any overflow.
 10: P = P + S. Ignore any overflow.
2. Arithmetically shift the product right one position.
* Drop the last bit from the product for the final result.
Example
Find 3 Ч -4:
* A = 0011 0000 0
* S = 1101 0000 0
* P = 0000 1100 0
* Perform the loop four times :
o P = 0000 1100 0. The last two bits are 00.
o P = 0000 0110 0. A right shift.
o P = 0000 0110 0. The last two bits are 00.
o P = 0000 0011 0. A right shift.
o P = 0000 0011 0. The last two bits are 10.
o P = 1101 0011 0. P = P + S.
o P
...
...