Booth's Algorithm - CS Course Webpages

Booth's Algorithm Example
Points to remember
When using Booth's Algorithm:You will need twice as many bits in yourproductas you have in your original twooperands.Theleftmost bitof your operands (both your multiplicand and multiplier) is a SIGN bit, and cannot be used as part of the value.
To begin
Decide which operand will be themultiplierand which will be themultiplicandConvert both operands totwo's complementrepresentation using X bitsX must be at least one more bit than is required for the binary representation of the numerically larger operandBegin with a product that consists of the multiplier with an additional X leading zero bits
Example
In the week by week, there is an example of multiplying2 x (-5)For our example, let's reverse the operation, and multiply (-5) x 2The 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 is11011(multiplier)2 is00010(multiplicand)
Beginning Product
The multiplier is:11011Add 5 leading zeros to themultiplierto get thebeginning product:00000 11011
Step 1 for each pass
Use theLSB(least significant bit)and theprevious LSBto determine the arithmetic action.If it is the FIRST pass, use0as the previous LSB.Possible arithmetic actions:00no arithmetic operation01add multiplicand to left half of product10subtract multiplicand from left half of product11no arithmetic operation
Step 2 for each pass
Perform anarithmetic right shift(ASR) on the entire product.NOTE: For X-bit operands, Booth's algorithm requires X passes.
Example
Let's continue with our example of multiplying (-5) x 2Remember:-5 is11011(multiplier)2 is00010(multiplicand)And we added 5 leading zeros to themultiplierto get thebeginning product:00000 11011
Example continued
Initial Product andprevious LSB00000 110110(Note: Since this is the first pass, we use 0 for the previous LSB)Pass 1, Step 1: Examine the last 2 bits00000 110110The last two bits are10, so we need to:subtract themultiplicandfrom left half of product
Example: Pass 1 continued
Pass 1, Step 1: Arithmetic action(1)00000(left half of product)-00010(mulitplicand)11110(uses a phantom borrow)Place result intoleft halfof product1111011011 0
Example: Pass 1 continued
Pass 1, Step 2: ASR(arithmetic shift right)Before ASR11110 11011 0After ASR11111 01101 1(left-most bit was 1, so a 1 was shifted in on the left)Pass 1 is complete.
Example: Pass 2
Current Product andprevious LSB11111 011011Pass 2, Step 1: Examine the last 2 bits11111 011011The last two bits are11, so we do NOT need to perform an arithmetic action --just proceed to step 2.
Example: Pass 2 continued
Pass 2, Step 2: ASR(arithmetic shift right)Before ASR11111 01101 1After ASR11111 10110 1(left-most bit was 1, so a 1 was shifted in on the left)Pass 2 is complete.
Example: Pass 3
Current Product andprevious LSB11111 101101Pass 3, Step 1: Examine the last 2 bits11111 101101The last two bits are01, so we need to:add themultiplicandto the left half of the product
Example: Pass 3 continued
Pass 3, Step 1: Arithmetic action(1)11111(left half of product)+00010(mulitplicand)00001(drop the leftmost carry)Place result intoleft halfof product0000110110 1
Example: Pass 3 continued
Pass 3, Step 2: ASR(arithmetic shift right)Before ASR00001 10110 1After ASR00000 11011 0(left-most bit was 0, so a 0 was shifted in on the left)Pass 3 is complete.
Example: Pass 4
Current Product andprevious LSB00000 110110Pass 4, Step 1: Examine the last 2 bits00000 110110The last two bits are10, so we need to:subtract themultiplicandfrom the left half of the product
Example: Pass 4 continued
Pass 4, Step 1: Arithmetic action(1)00000(left half of product)-00010(mulitplicand)11110(uses a phantom borrow)Place result intoleft halfof product1111011011 0
Example: Pass 4 continued
Pass 4, Step 2: ASR(arithmetic shift right)Before ASR11110 11011 0After ASR11111 01101 1(left-most bit was 1, so a 1 was shifted in on the left)Pass 4 is complete.
Example: Pass 5
Current Product andprevious LSB11111 011011Pass 5, Step 1: Examine the last 2 bits11111 011011The last two bits are11, so we do NOT need to perform an arithmetic action --just proceed to step 2.
Example: Pass 5 continued
Pass 5, Step 2: ASR(arithmetic shift right)Before ASR11111 01101 1After ASR11111 10110 1(left-most bit was 1, so a 1 was shifted in on the left)Pass 5 is complete.
Final Product
We have completed 5 passes on the 5-bit operands, so we are done.Dropping theprevious LSB, the resultingfinal productis:11111 10110
Verification
To confirm we have the correct answer, convert the 2's complementfinal productback to decimal.Final product:11111 10110Decimal value:-10which is the CORRECT product of:(-5) x 2