ReviewEssays.com - Term Papers, Book Reports, Research Papers and College Essays
Search

Booth's Multiplication Algorithm

Essay by   •  December 4, 2010  •  Study Guide  •  409 Words (2 Pages)  •  1,098 Views

Essay Preview: Booth's Multiplication Algorithm

Report this essay
Page 1 of 2

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

...

...

Download as:   txt (2.3 Kb)   pdf (57.2 Kb)   docx (9.7 Kb)  
Continue for 1 more page »
Only available on ReviewEssays.com