Multiplication
Multiplication of unsigned numbers
Product of 2 n-bit numbers is at most a 2n-bit number.
Unsigned multiplication can be viewed as addition of shifted
versions of the multiplicand.
Multiplication of unsigned
numbers (contd..)
⚫ We added the partial products at end.
⚫ Alternative would be to add the partial products at each stage.
⚫ Rules to implement multiplication are:
⚫ If the ith bit of the multiplier is 1, shift the multiplicand and add the
shifted multiplicand to the current value of the partial product.
⚫ Hand over the partial product to the next stage
⚫ Value of the partial product at the start stage is 0.
Multiplication of unsigned numbers
Typical multiplication cell
Bit of incoming partial product (PPi)
jth multiplicand bit
ith multiplier bit ith multiplier bit
carry out FA carry in
Bit of outgoing partial product
(PP(i+1))
Combinatorial array multiplier
Combinatorial array multiplier
Multiplican
d
0 m3 0 m2 0 m1 0 m0
(PP0
) q0
0
PP p0
1 q1
0
PP p1
2 q2
0
PP p2
3 q3
0
,
p7 p6 p5 p4 p3
Product is: p7,p6,..p0
Multiplicand is shifted by displacing it through an array of adders.
Combinatorial array multiplier
(contd..)
⚫ Combinatorial array multipliers are:
⚫ Extremely inefficient.
⚫ Have a high gate count for multiplying numbers of practical size such as
32-bit or 64-bit numbers.
⚫ Perform only one function, namely, unsigned integer product.
⚫ Improve gate efficiency by using a mixture of
combinatorial array techniques and sequential
techniques requiring less combinational logic.
Sequential multiplication
⚫ Recall the rule for generating partial products:
⚫ If the ith bit of the multiplier is 1, add the appropriately shifted multiplicand
to the current partial product.
⚫ Multiplicand has been shifted left when added to the partial product.
⚫ However, adding a left-shifted multiplicand to an
unshifted partial product is equivalent to adding an
unshifted multiplicand to a right-shifted partial
product.
Sequential Circuit Multiplier
Register A (initially 0)
Shift right
an a0 q q
C - 1 n - 1 0
Multiplier Q
Ad d/Noadd
control
n-bit
Adder
MUX Control
sequencer
0 0
m m
n - 1 0
Multiplicand M
Signed Multiplication
Signed Multiplication
⚫ Considering 2’s-complement signed operands, what will happen to
(-13)×(+11) if following the same method of unsigned multiplication?
1 0 0 1 1 ( - 13)
0 1 0 1 1 ( + 11)
1 1 1 1 1 1 0 0 1 1
1 1 1 1 1 0 0 1 1
Sign extension
0 0 0 0 0 0 0 0
isshown in
blue 1 1 1 0 0 1 1
0 0 0 0 0 0
1 1 0 1 1 1 0 0 0 1 ( - 14 )
3
Sign extension of negative multiplicand.
Signed Multiplication
⚫ For a negative multiplier, a straightforward solution is
to form the 2’s-complement of both the multiplier and
the multiplicand and proceed as in the case of a
positive multiplier.
⚫ This is possible because complementation of both
operands does not change the value or the sign of the
product.
⚫ A technique that works equally well for both negative
and positive multipliers – Booth algorithm.
Basics of Booth’s Algorithm
The booth algorithm is a multiplication algorithm that allows us to multiply the
two signed binary integers in 2's complement, respectively.
It is also used to speed up the performance of the multiplication process.
It is very efficient too.
It works on the string bits 0's in the multiplier that requires no additional bit only
shift the right-most string bits and a string of 1's in a multiplier bit weight 2 k to
weight 2 m that can be considered as 2k+ 1 - 2m.
Flowchart of Booth’s Algorithm
Working of Booth’s Algorithm
1. Set the Multiplicand and Multiplier binary bits as M and Q, respectively.
2. Initially, we set the AC and Qn + 1 registers value to 0.
3. SC represents the number of Multiplier bits (Q), and it is a sequence counter that is continuously decremented
till equal to the number of bits (n) or reached to 0.
4. A Qn represents the last bit of the Q, and the Qn+1 shows the incremented bit of Qn by 1.
5. On each cycle of the booth algorithm, Qn and Qn + 1 bits will be checked on the following parameters as follows:
1. When two bits Qn and Qn + 1 are 00 or 11, we simply perform the arithmetic shift right operation (ashr) to
the partial product AC. And the bits of Qn and Qn + 1 is incremented by 1 bit.
2. If the bits of Qn and Qn + 1 is shows to 01, the multiplicand bits (M) will be added to the AC (Accumulator
register). After that, we perform the right shift operation to the AC and QR bits by 1.
3. If the bits of Qn and Qn + 1 is shows to 10, the multiplicand bits (M) will be subtracted from the AC
(Accumulator register). After that, we perform the right shift operation to the AC and QR bits by 1.
6. The operation continuously works till we reached n -1 bit in the booth algorithm.
7. Results of the Multiplication binary bits will be stored in the AC and QR registers.
Booth Algorithm
⚫ Consider in a multiplication, the multiplier is positive
0011110, how many appropriately shifted versions of
the multiplicand are added in a standard procedure?
0 1 0 1 1 0 1
0 0 +1 +1 + 1+1 0
0 0 0 0 0 0 0
0 1 0 1 1 0 1
0 1 0 1 1 0 1
0 1 0 1 1 0 1
0 1 0 1 1 0 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 1 0 1 0 1 0 0 0 1 1 0
Booth Algorithm
⚫ Since 0011110 = 0100000 – 0000010, if we use the
expression to the right, what will happen?
0 1 0 1 1 0 1
0+1 0 0 0- 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
2's complement of
1 1 1 1 1 1 1 0 1 0 0 1 1
the multiplicand
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 1 0 1
0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 1 0 0 0 1 1 0
Booth Algorithm
⚫ In general, in the Booth scheme, -1 times the shifted multiplicand is
selected when moving from 0 to 1, and +1 times the shifted
multiplicand is selected when moving from 1 to 0, as the multiplier
is scanned from right to left.
0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 1 0 0
0 +1 -1 +1 0 - 1 0 +1 0 0 - 1 +1 - 1 + 1 0 - 1 0 0
Booth recoding of a multiplier.
Booth Algorithm
0 1 1 0 1 (+13) 0 1 1 0 1
X1 1 0 1 0 (- 6) 0 - 1 +1 - 1 0
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 1 1
0 0 0 0 1 1 0 1
1 1 1 0 0 1 1
0 0 0 0 0 0
1 1 1 0 1 1 0 0 1 0 ( - 78)
Booth multiplication with a negative multiplier.
Booth Algorithm
Multiplier
Version of multi plicand
selected by biit
Bi i Bi i -1
t t
0 0 0 XM
0 1 +1 XM
1 0 –1 XM
1 1 0 XM
Booth multiplier recoding table.
Fast Multiplication
Bit-Pair Recoding of Multipliers
⚫ Bit-pair recoding halves the maximum number of
summands (versions of the multiplicand).
Sign extension Implied 0 to right of
1 1 1 0 1 0 0 LSB
0 0 −1 +1 −1 0
0 −1 −2
(a) Example of bit-pair recoding derived from Booth
recoding
Bit-Pair Recoding of Multipliers
Mu ltiplier bit-pair Multiplier bit on the Multiplicand
right selected at position
i +1 i i −1
0 0 0 0 X M
0 0 1 +1 X M
0 1 0 +1 X M
0 1 1 +2 X M
1 0 0 –2 X M
1 0 1 –1 X M
1 1 0 –1 X M
1 1 1 0 X M
(b) Table of multiplicand selection
decisions
Bit-Pair Recoding of Multipliers 0 1 1 0 1
0 - 1 +1 - 1 0
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 1 1
0 0 0 0 1 1 0 1
1 1 1 0 0 1 1
0 1 1 0 1 ( + 13) 0 0 0 0 0 0
× 1 1 0 1 0 (- 6) 1 1 1 0 1 1 0 0 1 0 ( - 78)
0 1 1 0 1
0 -1 -2
1 1 1 1 1 0 0 1 1 0
1 1 1 1 0 0 1 1
0 0 0 0 0 0
1 1 1 0 1 1 0 0 1 0
Figure 6.15. Multiplication requiring only n/2 summand2s3.
Carry-Save Addition of Summands
⚫ CSA speeds up the addition process.
P7 P6 P5 P4 P3 P2 P1 24P0
Carry-Save Addition of Summands(Cont.,)
P7 P6 P5 P4 P3 P2 P1 P0
Carry-Save Addition of
Summands(Cont.,)
⚫ Consider the addition of many summands, we can:
□ Group the summands in threes and perform carry-save addition on each
of these groups in parallel to generate a set of S and C vectors in one
full-adder delay
□ Group all of the S and C vectors into threes, and perform carry-save
addition on them, generating a further set of S and C vectors in one
more full-adder delay
□ Continue with this process until there are only two vectors remaining
□ They can be added in a RCA or CLA to produce the desired product
2. carry save addition of summands
⚫ Example 45 [M] x 43 [Q] = 2835 Conventional Method
2. carry save addition of summands
⚫More significant
reduction delay Using
Carry Save additio n
2. carry save addition of summands
⚫ Using Carry addition- Schematic representation
Integer Division
Two types
1. Restoring Division
2.Non- Restoring Division
Integer Division
1. Restoring Division
⚫ Figure 6.21 shows a logic circuit arrangement that implements restoring
division. Note its similarity to the structure for multiplication that was shown
in Figure 6.7. An n-bit positive divisor is loaded into register M and an n-bit
positive dividend is loaded into register Q at the start of the operation.
⚫ Register A is set to 0. After the division is complete, the n-bit quotient is in
register Q and the remainder is in register A. The required subtractions are
facilitated by using 2's-complement arithmetic. The extra bit position at
the left end of both A and M accommodates the sign bit during
subtractions.
Integer Division
1. Restoring Division
Quotient
Dividend
Divisor 00
Remainder
Integer Division
1. Restoring Division
Example-1 : Perform division of 18/3 using
Restoring Division Concept.
Integer Division
2. Non-Restoring Division
⚫ The restoring-division algorithm can be improved by avoiding the need for restoring A
after an unsuccessful subtraction. Subtraction is said to be unsuccessful if the result is
negative. Consider the sequence of operations that takes place after the subtraction
⚫ operation in the preceding algorithm. If A is positive, we shift left and subtract M, that is,
we perform 2A -M. If A is negative, we restore it by performing A +M, and then we shift it
left and subtract M. This is equivalent to performing 2A + M. The q0 bit
⚫ is appropriately set to 0 or 1 after the correct operation has been performed. We can
summarize this in the following algorithm for nonrestoring division.
⚫ Step 2 is needed to leave the proper positive remainder in A at the end of the n cycles of
Step l. The logic circuitry in Figure 6.21 can also be used to perform this algorithm. Note
that the Restore operations are no longer needed; and that exactly one Add or Subtract
operation is performed per cycle
Integer Division
⚫ 1. Non-Restoring Division
Example-2 : Perform division of 18/3 using
Non-Restoring Division Concept.
