Transcript Basic Multiplication

Multiplication
Multiplier Notation
Partial Products
Logical-AND
Shift and Add Paradigm
Shift and Add Examples
Programmed Multiplication
Programmed Multiplication (cont.)
Hardware Shift and Add (right)
Hardware Shift and Add
Hardware Shift and Add (left)
Signed Number Multiplication
(positive case)
Signed Number Multiplication
(negative case)
Booth’s Recoding (or encoding)
• Developed for Speeding Up Multiplication in Early Computers
• When a Partial Product of 0 Occurs, Can Skip Addition and
Just Shift
• Doesn’t Help Multipliers Where Datapaths Go Through Adder
Such as Previous Examples
• Does Help Designs for Asynchronous Implementation or
Microprogramming Since Shifting is Faster Than Addition
• Variable Delay – Depends on Number of One’s in
• Booth Observed that a String of 1’s May be Replaced as:
2 2
j
j 1

i 1
2
2 2
i
j 1
2
i
Booth’s Recoding Example
xn xn-1
...
xi xi-1
...
x0 (0)
yi=xi-1 - xi
yn
...
xi
0
1
1
0
yi
xi-1
0
1
0
1
...
y0
Operation
shift only
shift only
subtract shift
addition shift
Comments
string of zeros
string of ones
beg. string of ones
end string of ones
EXAMPLE
0011110011(0)
0100010101
yi
0
0
-1
1
Booth’s Recoding
• Maps Words With Digit Set [0,1] to Those With [-1,1]
Sequential Multiplication
A
X
Y
(-1) Add –A
Shift
(+1) Add +A
Shift
(-1) Add –A
Shift
1011
1101
0111
0101
00101
1011
11011
111011
0101
001111
0001111
(-510)
(-310)
(recoded)
(+1510)
Booth Multiplier Example
Booth’s Recoding Drawbacks
• Number of add/sub Operations are Variable
• Some Inefficiencies
EXAMPLE
001010101(0)
011111111
• Can Use Modified Booth’s Recoding to Prevent
• Will Look at This in Later Class
Sign Extension
• Consider 6-bit 2’s Complement Number
s=0 Positive Value; s=1 Negative Value
• Show Sign Extension Works:
s s s s s p4 p3 p2 p1 p0
  s  29  s  28  s  27  s  26  s  25  p4  24  p3  23  p2  22  p1  21  p0  20
4
  s  2  s  (2  2  2  2 )   pi  2i
9
8
7
6
5
i 0
4
  s  2  s  (2  2 )   pi  2i
9
9
5
i 0
4
  s  2   pi  2i
5
i 0
• Definition of 2’s Complement
Sign Extension Example
A
X
Y
010110
001011
010101
11111101010
0000000000
111101010
00000000
0010110
000000
00011110010
(+2210)
(+1110)
(recoding)
(neg. A)
(0 A)
(neg. A)
(0 A)
(neg. A)
(0 A)
(24210)
Sign Extension Example
• Same Trick as Before, Complement Original Sign Bit
• Add 1 to Column 5
1
001010
100000
001010
100000
110110
100000
00011110010
(neg. A)
(0 A)
(neg. A)
(0 A)
(neg. A)
(0 A)
(24210)
Methods for Fast Multiplication
• Reduce
Number of Partial Products to be Added
– Group Multiplier Bits Together
– Higher Radix Multiplier
• Add the Partial Products Faster
Radix-r Shift and Add
Radix-4 Multiplication
• Shifter is Multi-bit
• No Longer a Simple AND of xi with a
• Need 4:1 MUX with 0, a, 2a, 3a as Inputs
Partial Product Selection
• 0, a and 2a are easy
• 3a=a+2a  Requies an Adder!
• Need a Way to Compute 3a Efficiently
Example With 3a Availability
Computing 3a
• One Way is to Precompute 3a and Store in Register Initially
• Another Way is When 3a Occurs Add -a
• Send Carry of 1 to Next into Next Radix-4 Digit of Multiplier
• Causes Incoming Multiple to be [0,4] Versus [0,3]
– 4 Because incoming carry to 112 Causes Digit 1002
• Multiples 0, 1, 2 Handled Easily
• Multiple 3 Converted to –1 With Outgoing Carry of 1
• Multiple 4 Converted to 0 With Outgoing Carry of 1
• Requires Extra Cycle of Computation Since MSD May Have Carry
Example With 3a Availability
Using Radices >4
• Could Also Use Radices of 8, 16, ...
• Bit Groupings of Size 3, 4, ...
• Multiple Generation Hardware Becomes More Complex
• Must Precompute 3a, 5a, 7a, ....
• Or Use 3a With a Carry Scheme
• Carry Scheme Converts Multipliers 5a, 6a, 7a
to –3a, -2a, -a, etc.
• Carry Digit in This Form Becomes a 1
Booth Recoding
• Modern Arithmetic Circuits DO NOT Apply
Booth Recoding Directly
• Useful in Understanding Higher-radix Versions of
Booth Recoding
• No Consecutive 1’s or –1’s Occur Using Previously Seen
Booth Recoding
• Booth Recoding in Radix-4 Results in the Following:
– Only Multiples of a or 2a are Required
– These are Easily Obtained Using Shifting and Complementation
Modified Booth Recoding
• Booth Recoding Results From xi and xi-1
• Radix-4 Multiplier Digits Implies Booth Recoding
Based on xi+1, xi and xi-1
• Similar to Classical Booth Recoding, Modified Booth
Recoding Encodes Multipliers into [-2,2]
Modified Booth Recoding
Example Modified Booth Recoding
Example Multiplication with MBR
Hardware MBR Example