|
Kaleidoscope
Voodoo Child
Registered: 12/02/05
Posts: 674
Loc: the 28th dimension
Last seen: 16 years, 11 months
|
Booth's Algorithm for hardware multiplication?
#5359194 - 03/02/06 07:41 PM (17 years, 10 months ago) |
|
|
I have a midterm tommorow and I need to know how booth's algorithm works...and I don't understand when represented as binary math. Does anyone know how to represent this in MIPS 32 assembly language...I think I can figure it out in that form but straight math with ones and zero's makes very little sense to me. If anyone knows it or knows where I could find it in this form it would appreciated.
--------------------
Purple haze, all in my brain, lately things just don't seem the same. Actin' funny but I don't know why, 'scuse me while I kiss the sky.
|
Seuss
Error: divide byzero


Registered: 04/27/01
Posts: 23,480
Loc: Caribbean
Last seen: 2 months, 20 days
|
Re: Booth's Algorithm for hardware multiplication? [Re: Kaleidoscope]
#5360644 - 03/03/06 04:39 AM (17 years, 10 months ago) |
|
|
Booths' Algorithm is an optimization of the multiplication operator at the expensive of additional hardware.
Lets say you are trying to multiply two numbers in base ten, 47 x 99. We can rewrite this as 47 x (100-1) = 4700 - 47 = 4653. This is basically what Booths' does, but in binary.
Looking at a binary example:
N x 0111 = N x (1000 - 1)
Booths came up with a clever way to encode the far right side by adding in a new placeholder digit "-1". A "-1" is used when the current bit is a 1 and the previous bit is a 0. A "+1" is used when the current bit is a 0 and the the previous bit is a 1. "0" is used everywhere else. (Treat the 'missing' far right digit as a zero when translating... work out the following example, you will see what I mean.)
Going back to our binary example:
N x 0111 = N x (1000 - 1)
now becomes:
N x 0111 = N x (+1 0 0 -1)
The above expression, on the right, has spaces added between digits for clairity. The first "+1" and final "-1" are Booths placeholders, not a math operators. Remember, we took the 0111 from the left hand side, and applied the translation to come up with the expression on the right hand side.
Another example:
N x 001110110 = N x (0 +1 0 0 -1 +1 0 -1 0)
Ok, great, we translated the problem, but what does that get us? Quite a bit, actually. We know now whether the multiplier bit is a +1, -1, or 0. This solves the overflow problem because alternate adds and subtracts can never lead to an add overflow. We also don't have to do anything special with the MSB of the mutiplier as required by other multiplication implementations.
Using the translated encoding, a 0 means shift the partial product to the right, a +1 means to add the multiplicant to the partial product before shifting the partial product and a -1 means to subtract the multiplicant from the partial product before shifting the partial product.
-------------------- Just another spore in the wind.
|
Kaleidoscope
Voodoo Child
Registered: 12/02/05
Posts: 674
Loc: the 28th dimension
Last seen: 16 years, 11 months
|
Re: Booth's Algorithm for hardware multiplication? [Re: Seuss]
#5361163 - 03/03/06 10:58 AM (17 years, 10 months ago) |
|
|
ok, thanks that actually helps more than the code would!
--------------------
Purple haze, all in my brain, lately things just don't seem the same. Actin' funny but I don't know why, 'scuse me while I kiss the sky.
|
Seuss
Error: divide byzero


Registered: 04/27/01
Posts: 23,480
Loc: Caribbean
Last seen: 2 months, 20 days
|
Re: Booth's Algorithm for hardware multiplication? [Re: Kaleidoscope]
#5369841 - 03/06/06 04:34 AM (17 years, 10 months ago) |
|
|
Welcome. Good luck on your midterm. It has been a long time since I have done digital design work, and I miss it a lot. This kind of "took me back", so to speak.
-------------------- Just another spore in the wind.
|
|