Publish on 28th October 2019
Category: Birds
0

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:00no arithmetic operation01add multiplicand to left half of product10subtract multiplicand from left half of product11no 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

0

Embed

Upload

Booth's Algorithm - CS Course Webpages