ELE 4550 ASIC Technologies
Project Tutorial
Simple Shift-add Multiplier
0011 (Multiplicand) x 0111 (Multiplier) 0011
+ Disadvantage:
¾ number of addition depends on number of bits of multiplication which cannot be
reduced.
0011 0011 0000 .
00010101
Booth Multiplier
Compared to shift add multiplier, booth multiplier can reduce the number of multiplier in average. Here is its algorithm.
2’s complement representation of multiplier:
b=−2nbn+2n−1bn−1+2n−2bn−2+...+20b0
consider the term 2n, it can be rewritten as:
2n = 2n+1 – 2n
based on this property, we can recode every set bit in the multiplier as “+2 -1” for example:
0 0 1 1 1 1 0 0 +1 -1
(Multiplier)
+1 -1 +1 -1 +1 -1
0 1 0 0 0 -1 0 0
~ P. 1 ~
(recoded multiplier)
ELE 4550 ASIC Technologies
Project Tutorial
As shown above, less “1” in the recoded multiplier, this implied that less addition is needed.
Example: 6 x 14 = 84
0 0 0 0 0
(sign extension)
1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 1 1 0 . 0 0 1 0 1 0 1 0 0 (84)
Question: What is the worst case for booth multiplier?
x
0 0 1 1 0 (Multiplicand) 0 1 1 1 0 (Multiplier)
+1 0 0 -1 0 (recoded multiplier)
Hardware algorithm
MultiplicandZero- MultiplicandPartial ProductMultiplexerMultiplierAdderDFF
~ P. 2 ~
ELE 4550 ASIC Technologies
Project Tutorial
Radix -4 Modified Booth Algorithm
Can design n-bit synchronous multiplier that generates exactly n/2 partial products. Example
Note: The results must be obtained after a fixed cycles through the pipeline!!! Eg: 16*16bit Raix-4 booth multiplier can get the result after 8 cycles.
~ P. 3 ~
