Module-3
Computer Arithmetic
Contents
• Integer Addition and Subtraction
• Ripple carry adder
• Carry look-ahead adder
• Carry save adder
• Carry select adder
• Multiplication
• Shift-and-Add,
• Booth Multiplier,
• Carry save multiplier
• Division - Non restoring and restoring techniques.
• Floating point arithmetic
• Decimal arithmetic operations
• BCD Adder, BCD Subtraction.
Multiplication of Signed Numbers
•We can extend the basic shift-and-add multiplication method to handle signed numbers.
• One important difference:
– Required to sign-extend all the partial products before they are added.
- Recall that for 2’s complement representation, sign extension can be done by replicating
the sign bit any number of times.
0101 = 0000 0101 = 0000 0000 0000 0101 = 0000 0000 0000 0000 0000 0000 0000 0101
1011 = 1111 1011 = 1111 1111 1111 1011 = 1111 1111 1111 1111 1111 1111 1111 1011
An Example: 6-bit 2’s complement multiplication
Note: For n-bit multiplication, since we are
generating a 2n bit product, overflow can never
occur.
Booth’s Algorithm for Signed
Multiplication
In the conventional shift-and-add multiplication as
discussed, for n-bit multiplication, we iterate n times.
• Add either 0 or the multiplicand to the 2n-bit par al
product (depending on the next bit of the multiplier).
• Shift the 2n-bit partial product to the right.
• Essentially we need n additions and n shift operations.
• Booth’s algorithm is an improvement whereby we can
avoid the additions whenever consecutive 0’s or 1’s are
detected in the multiplier.
– Makes the process faster.
Booth’s Algorithm for Signed Multiplication
We inspect two bits of the multiplier (Qi, Qi-1) at a time.
– If the bits are same (00 or 11), we only shift the partial product.
– If the bits are 01, we do an addition and then shift.
– If the bits are 10, we do a subtraction and then shift.
• Significantly reduces the number of additions / subtractions.
• Inspecting bit pairs as mentioned can also be expressed in terms of Booth’s
Encoding.
• Use the symbols +1, -1 and 0 to indicate changes w.r.t. Qi and Qi-1.
• 01 ->+1,
• 10-> -1,
• 00 or 11 -> 0.
• For encoding the least significant bit Q0, we assume Q -1 = 0
Examples of Booth encoding:
The last example illustrates the worst case for Booth’s multiplication (alternating 0’s
and 1’s in multiplier).
• In the illustrations, we shall show the two multiplier bits explicitly instead of showing the
encoded digits.
• Booth’s Algorithm: A ± M for Positive & Negative M
• Key Rule
• A - M → A + (2’s complement of M)
• A + M → A + M (direct addition)
• Works the same for positive and negative M (sign encoded in bits).
Binary Binary
Stored M (2’s A - M (Decimal A + M (Decimal
M sign operation in operation in
comp) meaning) meaning)
hardware hardware
Example: 00101 A + 11011 (2’s
Positive M A−5 A+5 A + 00101
(+5) comp of M)
Example: 10110 A − (−10) = A + A + 01010 (2’s
Negative M A + (−10) A + 10110
(−10) 10 comp of M)
Bit-Pair Recoding of Booth’s Multiplication
• A technique that halves the maximum number of summands; derived
directly from the Booth’s algorithm.
• If we group the Booth-coded multiplier digits in pairs, we observe:
▪ (+1, -1): (+1, -1) * M = 2 * M – M
▪ (0, +1):= M (0, +1) * M = M
• We need a single addition instead of a pair of addition & subtraction.
• Other similar rules can be framed..
• Every equivalent recoded pair has at
least one 0.
• Worst-case number of additions or
subtractions is 50% of the number of
multiplier bits.
• Reduces the worst-case time required
for multiplication.
Carry Save Multiplier
• We have seen earlier how carry save adders (CSA) can be used to add
several numbers with carry propagation only in the last stage.
• The partial products can be generated in parallel using n2 AND gates.
• The n partial products can then be added using a CSA tree.
• Instead of letting the carries ripple through during addition, we save
them and feed it to the next row, at the correct weight positions.