Module-3
Arithmetic Unit
Text Books
Computer Organization: C Hamacher, Z Vranesic, S Zaky:, Tata McGraw Hill, 5th Edition,
2011 .
Dr. Bhat Geetalaxmi Jairam
Professor,
ISE, NIE, Mysuru
A signed operand multiplication
• We now discuss multiplication of 2's-complement signed operands,
generating a double length product. The general strategy is still to
accumulate partial products by adding versions of the multiplicand as
selected by the multiplier bits.
• First, consider the case of a positive multiplier and a negative
multiplicand. When we add a negative multiplicand to a partial product,
we must extend the sign-bit value of the multiplicand to the left as far as
the product will extend.
A signed operand multiplication
• In Figure 6.8, for example, the 5-bit signed operand, -13,is the
multiplicand, and it is multiplied by +11,the multiplier, to get the 10-
bitproduct, -[Link] hardware discussed earlier can be used for
negative multiplicands if it provides for sign extension of the partial
products.
A signed operand multiplication
• Second: 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, called the Booth algorithm, is described next.
A signed operand multiplication
[Link] Booth Algorithm
• The Booth algorithm has two attractive features. First, it handles both positive
and negative multipliers uniformly. Second, it achieves some efficiency in the
number of additions required when the multiplier has a few large blocks of ls.
The speed gained by skipping over ls depends on the data. On average, the speed of
doing multiplication with the Booth algorithm is the same as with the normal
algorithm.
Fast Multiplication
We now describe two techniques for speeding up the multiplication operation.
• The first technique (bit-pair recoding) guarantees that the maximum number of
summands (versions of the multiplicand) that must be added is n/2 for n-bit
operands;
• The second technique reduces the time needed to add the summands.
[Link] pair recoding of multipliers
• A technique called bit-pair recoding halves the maximum number of summands. It
is derived directly from the Booth algorithm. Group the Booth-recoded multiplier
bits in pairs
Example:
As [-1 0] = -1x2 1 + 0x 2 0 = -2+0= -2
[ -1 +1] = -1x2 1 + 1x 2 0 = -2+1= -1
[0 0] = 0x2 1 + 0x 2 0 = 0+0= 0
[Link] pair recoding of multipliers
• Figure 6.l4b shows a table of the multiplicand selection decisions for all
possibilities.
[Link] pair recoding of multipliers
• Example
1. Using Boot Algo 2. Using Bit- Pair
2. Carry save addition of summands
1. Ripple –Carry Array
• Multiplication requires the addition of several summands. A technique called carry
save addition (CSA) speeds up the addition process. Consider the array for 4 x 4
multiplication shown in Figure 6.l6a.
• This structure is the general array shown in Figure 6.6, with the first row consisting
of just the AND gates that implement the bit products m3qo, m2qo, m1qo, and
moqo.
• Disadvantage: Carries ripple along the rows
1. Ripple- carry Array
• Ripple- carry Array
(a) Ripple carry array
2. carry save addition of summands
Generates S and C in parallel .
• Instead of letting the carries ripple along the rows.
• It can be "saved" and introduced into the next row, at the correct weighted
positions, as shown in Figure 6.16b. This frees up an input to three full adders in
the first row.
• These inputs are used to introduce the third summand bit products m2q2 , m 1q2,
and m0qz. Now, two inputs of each full adder in the second row are fed by sum
and carry outputs from the first row. The third input is used to introduce the bit
products m2q3, m1q3, and moq3 of the fourth summand.
• The high-order bit products m3q2 and m3q3 of the third and fourth summands are
introduced into there remaining free inputs at the left end in the second and third
rows. The saved carry bits and the sum bits from the second row are now added in
the third row to produce the final product bits.
2. carry save addition of summands
Advantage and steps:
• A more significant reduction in delay can be achieved as follows. Consider the addition
of many summands, as required in the multiplication of longer operands. 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.
• Next, we 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. We
continue with this process until there are only two vectors remaining.
• They can then be added in a ripple-carry or a carry-lookahead adder to produce the
desired product.
Ex. 13X 11 1m3 1m2 0m1 1m0
1q3 0q2 1q1 1q0More significant reduction in delay as follow
---------------------
1m3q0 1m2q0 0m1q0 1m0q0 A S 1C 1
1m3q1 1m2q1 0m1q1 1m0q1 X B
0m3q2 0m2q2 0m1q2 0m0q2 X X C
1m3q3 1m2q3 0m1q3 1m0q3 X X X D
S 2C 2
1 0 0 0 1 1 1 1
Example 1101
1011
1 1 0 1 A
1 1 0 1 X B
0 0 0 0 x x C
0 1 0 1 1 1 S1
0 1 0 0 0 C1
1 1 0 1 x x x D
1 1 0 1 1 1 1 S2
0 1 0 0 0 0 C2 binary addition along with carry
1 0 0 0 1 1 1 1
2. carry save addition of summands
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 addition
2. carry save addition of summands
• Using Carry addition- Schematic representation