quick_notes
quick_notes
Multiplication and Division
Date : 25/11/2024
Subject : #UE23CS251A
Shift and Add Multiplication
1. We need 4 registers:
C -> carry
M -> Multiplicand
A -> Accumulator
Q -> Multiplier
2. If the value of Q has q0 = 0 i.e. the Least Significant Bit
3. Then add A = A + M, if q0 ≠ 0 then no need to add
4. Right Shift 1-bit from carry flag to register Q
5. Repeat this process "n" number of times, where "n" is the number
of bits of multiplier/multiplicand
None of the above methods work for Signed Integer
Sign Extension Method
ONLY WORKS FOR +ive × −ive MULTIPLICATION
Similar to normal multiplication except when we get a partial
product we need to extend it from the left till we reach 2n (n -
> number of bits of multiplicand/multiplier)
We extend to the left with the MSB of the partial product
Booth Recoding
Bit i Bit i+1 Recoded Multiplier x Multiplicand
0 0 0 x M
quick_notes
Bit i Bit i+1 Recoded Multiplier x Multiplicand
0 1 +1 x M
1 0 -1 x M
1 1 0 x M
Example
Consider
MSB -> 11011011 <- LSB
First we add an imaginary 0 to the right of LSB
MSB -> 110110110 <- LSB
Now Start from LSB and compare consecutive digits
Imaginary newly added Bit is Bit (i)
and the Initial LSB is Bit (i-1)
Find the case from the table and recode it
Bit i = 1; Bit (i+1) = 0; therefore we recode that as -1
(if you do not remember table just do Bit (i+1) - Bit (i) you
will get the correct recode value. Eg: 0 - 1 = -1)
Then we move i one step back
Bit i = 1, But (i-1) = 1, therefore Recoded will be 0
Keep repeating this process and finally we get
Booth Recoded Value = 0 -1 +1 0 -1 +1 0 -1
We can see the value of the Binary doesn't change
11011011 -> -37
0 -1 +1 0 -1 +1 0 -1 -> multiply each weightage with their 2^x
conversion
=> 128(0) + 64(-1) + 32(+1) + 16(0) + 8(-1) + 4(+1) + 2(0) + 1(-1) =
-37
We use booth recoding to make our multiplier easier and reduce the
number of 1's
Okay Now there are some quality cases in Booth
Since our objective is to minimise the number of 1's, there can
be 3 types
Good, Average and Bad
Good -> 01111111 --when converted-> +1 0 0 0 0 0 0 -1
(Number of 1 decreases
Average is everything in between
quick_notes
Bad -> 01010101 --when converted->+1 -1 +1 -1 +1 -1 +1 -1
(Number of 1 increases)
To use this in multiplication
Convert the multiplier into booth recoding
And then multiply:
+1 x M => Normal Multiplication
-1 x M => Instead of putting the normal partial product, we
just add the 2's Complement of the Multiplicand
0 x M => Normal Multiplication
We also use Sign Extension while solving
Example
Booth Multipliers with Shift and Add
Performs both positive and negative multipliers uniformly
−
In this we have A, Q and a Q 1 register
A is initialised with 0's
Q is loaded with the Multiplier
The conditions are as follows
quick_notes
if Q
−
1 = 1 and Q
0
= 0, add A = A + M
if Q − 1 = 0 and Q 0 = 1, add A = A + (-M) => Here -M is
nothing but the 2's Complement of M
− 0 − 0
if Q 1 = 0 and Q = 0 or Q 1 = 1 and Q = 1, Do nothing
Right shit from A to Q
−
1
Do this for N-times
Example
Important
When we shift right in Booth Multiplier Shift and Add, we use
Sign Extension too
For example:
When we right shift and the MSB is 1, the empty space created in
the MSB after shifting will also be filled with 1. This is
unlike the usual Shift and Add and need to be kept in mind
see how here we add 1 to the MSB after shifting
quick_notes
Fast Multiplication (Bit Pair Recoding)
if we see carefully, in booth multiplier (+1 -1) and (0 +1) have
the same value
This is redundancy in the recoding which we can decrease, which
will in turn decrease the number of summands
We use Bit Pair recoding for this
In bit pair, we take 3 bits and get the value of it from the
lookup table
Easy way to remember table is to remember 0, +1, +1, +2; once we
reach the half way mark we flip the order and add a negative sign
for bit pair we extend the sign by 1-bit and also put an implied
zero at the end
So the number now becomes, 1110100
Now we can take triplets starting from the left
quick_notes
Performing Multiplication
When the encounter different numbers multiplication changes
0 -> just put 0's
+1 -> normal multiplication
-1 -> add the 2's complement of the multiplicand
-2 -> just like -1, take the 2's complement of the
multiplicand. But put a 0 to the right of the LSB and then
add that as a Partial Product
+2 -> just like +1, put a zero to the right of the LSB and
then add that as a Partial Product
Here he has converted multiplier first to booth and then to bit
pair, but we can do it directly from binary to bit pair also
Carry Save Addition
Division
Next : [[]]
