Binary Multiplication Booth's Algorithm

Binary Multiplication Booth's Algorithm


Booth's algorithm provides for binary signed multiplication.


Some points:

1.) The product needs twice as many bits as the original 2 operands

2.) The leftmost bits in the operands are the signed bits and cannot be used as part of the value


Some methods -


RSC ( Right-Shift Curculant ) means simply shifting all bits in a binary array to the right 1 bit position each and move

the last bit in the shifted bit array to the beginning of the array.


Example:

10110

After RSC,

01011


RSA ( Right-Shift Arithmetic ) means you add 2 binary numbers together and shift the result to the right by 1 bit and also

add the first bit of the addition result to the beginning of the result.


Example:

0100

+0110

------

1010

Now add the first bit ( "1" here ) to the beginning:

11010


Now use booth's algorithm to perform signed multiplication of (-5) * 2.


1.) 00101 = 5 and 2's complement for -5 is 11010 + 1 = 11011

2.) 2 is 00010


For each pass ( For X-Bit operands, Booth's algorithm requires X passes ) there are 2 major steps:


Step 1:

So the multiplier is 11011 ( -5 ). Add 5 leading zeros the

this multiplier to get the first or beginning product. Use the least significant

bit and the previous least significant bit to determine which arithmetic action

to take. On the very first pass, the LSB is 0.


Possible arithmetic actions are:

a.) 00 -> No action

b.) 01 -> Add multiplicand to left half of product

c.) 10 -> Subtract multiplicand from left half of product ( Add 2's complement )

d.) 11 -> No action


Step 2:

Perform a RSA ( Right Shift Arithmetic ) on the entire product


Pass 1.) PRODUCT = 00000 11011 LSB = 0 [ 00000 11011 0 ]

Pass 1 Step 1.) Last 2 bits are 10 so subtract multiplicand ( 00010 ) from left half of product

so 11101+1 = 11110 ( which is 2's complement of 2 ) added to 00000 is

00000 + 11110 = 11110 , so entire product is now 11110 11011 0

Pass 1 Step 2.) Left most bit is 1 so add that to the beginning after shift

so now it becomes 11111 01101 1


Pass 2.) PRODUCT = 11111 01101 LSB = 1 [ 11111 01101 1 ]

Pass 2 Step 1.) Last 2 bits are 11 so no arithmetic step needed

Pass 2 Step 2.) Left most bit is 1 so add that to the beginning after shift

so now it becomes 11111 10110 1


Pass 3.) PRODUCT = 11111 10110 LSB = 1 [ 11111 10110 1 ]

Pass 3 Step 1.) Last 2 bits are 01 so add multiplicand to left half of product

so 11111 + 00010 = 00001 so entire product is now 00001 10110 1

Pass 3 Step 2.) Left most bit is 0 so add that to the beginning after shift

so now it becomes 00000 11011 0


Pass 4.) PRODUCT = 00000 11011 LSB = 0 [ 00000 11011 0 ]

Pass 4 Step 1.) Last 2 bits are 10 so subtract multiplicand ( 00010 ) from left half of product

so 00000 + 11110 = 11110, so entire product is now 11110 11011 0

Pass 4 Step 2.) Left most bit is 1 so add that to the beginning after shift

so now it becomes 11111 01101 1


Pass 5.) PRODUCT = 11111 01101 LSB = 1 [ 11111 01101 1 ]

Pass 5 Step 1.) Last 2 bits are 11 so do nothing in Step 1

Pass 5 Step 2.) Left most bit is 1 so add that to the beginning after shift

so now it becomes 11111 10110 1


At this point we have completed 5 passes on 5-bit operands so the multiplication is done.


Drop the previous LSB and the final product is:

11111 10110


This equates to:

(Negative) 00000 01001 + 1

which is 01010 = -10


So 5 * -2 = -10


Hope this was helpful.





















ClassyBits 2016