30-03-2012, 11:32 AM
Booth's Algorithm Example
15765_booth algorithm (1).ppt (Size: 182 KB / Downloads: 300)
Points to remember
When using Booth's Algorithm:
You will need twice as many bits in your product as you have in your original two operands.
The leftmost bit of your operands (both your multiplicand and multiplier) is a SIGN bit, and cannot be used as part of the value.
Example
In the week by week, there is an example of multiplying 2 x (-5)
For our example, let's reverse the operation, and multiply (-5) x 2
The numerically larger operand (5) would require 3 bits to represent in binary (101). So we must use AT LEAST 4 bits to represent the operands, to allow for the sign bit.
Let's use 5-bit 2's complement:
-5 is 11011 (multiplier)
2 is 00010 (multiplicand)
Step 2 for each pass
Perform an arithmetic right shift (ASR) on the entire product.
NOTE: For X-bit operands, Booth's algorithm requires X passes.
Verification
To confirm we have the correct answer, convert the 2's complement final product back to decimal.
Final product: 11111 10110
Decimal value: -10
which is the CORRECT product of: