Module-2
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.
Introduction(Addition)
• Computers are built using tiny electronic switches, typically MOS
transistors.
• The state of these switches is expressed in binary (ON/OFF).
• To design arithmetic circuits, we need to work with binary numbers.
To design arithmetic circuits for use in computers, we need to work
with binary numbers.
• How do we represent numbers in binary?
• How do we carry out arithmetic operations in binary?
• How can we implement these operations efficiently in hardware?
Representation of Integers
• Unsigned Integers
• For an n-bit binary number, the range is from 0 to (2ⁿ - 1).
• Signed Integers
• 1's Complement (n-bit): Range is from -(2ⁿ⁻¹ - 1) to +(2ⁿ⁻¹ - 1).
• 2's Complement (n-bit): Range is from -2ⁿ⁻¹ to +(2ⁿ⁻¹ - 1).
• For both representations, subtraction can be performed using addition.
• 2's complement is the most widely used representation.
Subtraction Using 1's Complement
• How to compute A - B:
• Compute the 1's complement of B.
• Add the result to A: R = A + (1's comp of B).
• If there is an end-around carry:
• Add the carry back to the result (R = R + 1).
• The final result is positive.
• If there is no carry: The result is negative and is already in its 1's
complement form.
1's Complement Examples (4-bit)
• Example 1: 6 - 2
• 6 = 0110
• 1's complement of 2 (0010) = 1101
• 0110 + 1101 = 1 0011
• End-around carry is 1. Add it back: 0011 + 1 = 0100
• Result: +4
• Example 2: 3 - 5
• 3 = 0011
• 1's complement of 5 (0101) = 1010
• 0011 + 1010 = 1101
• No carry. The result is negative.
• 1101 is the 1's complement of 0010.
• Result: -2
Subtraction Using 2's Complement
• How to compute A - B:
• Compute the 2's complement of B.
• Add the result to A: R = A + (2's comp of B).
• If there is a final carry:
• Ignore the carry.
• The result is positive.
• If there is no carry:
• The result is negative and is already in its 2's complement form.
2's Complement Examples (4-bit)
• Example 1: 6 - 2
• 6 = 0110
• 2's complement of 2 (0010) = 1110
• 0110 + 1110 = 1 0100
• Ignore the carry.
• Result: +4
• Example 2: 3 - 5
• 3 = 0011
• 2's complement of 5 (0101) = 1011
• 0011 + 1011 = 1110
• No carry. The result is negative.
• 1110 is the 2's complement of 0010.
• Result: -2
Addition of Two Binary Digits (Bits)
• When two bits A and B are added, a sum (S) and carry (C) are
generated as per the following truth table:
Addition of Mul-bit Binary Numbers
• When two bits A and B are added, a sum (S) and carry (C) are
generated as per the following truth table:
0010110 1111110
0101011 0111111
0001001 0000001
0110100 1000000
At every bit position (stage), we require to add 3 bits:
• 1 bit for number A
• 1 bit for number B
• 1 carry bit coming from the previous stage
Addition of Mul-bit Binary Numbers
Various Implementations of Full Adder
Delay of a full adder
• Assume that the delay of all basic gates (AND, OR, NAND, NOR, NOT)
is δ.
• Delay for Carry = 3δ
• Delay for Sum = 6δ (AND-OR delay plus one inverter delay)
Parallel Adder Design
• Ripple carry adder
• Carry look-ahead adder
• Carry save adder
• Carry select adder
Ripple carry adder
• Cascade n full adders to create a n- bit parallel adder.
• Carry output from stage-i propagates as the carry input to stage-(i+1).
• In the worst-case, carry ripples through all the stages.
1111110 Carry
0111111 Number A
0000001 Number B
1000000 Sum S
How to Design a Parallel Adder?
• Observation:
• Computing A+B
• Let Xi = Bi
How to Design a Parallel Subtractor?
• Observation:
• Computing A-B is the same as adding the 2’s complement of B to A.
• 2’s complement is equal to 1’s complement plus 1.
• Let Xi = Bi’
Parallel Adder/Subtractor?
Carry look-ahead adder
Carry look-ahead adder
• Problem with Ripple Carry Adder: The propagation delay is
proportional to n because of the carry rippling sequentially through
each stage.
• Solution: Speed up the addition by generating the carry signals for all
stages in parallel.
• Benefit: Time complexity can be reduced from O(n) to O(1) for carry
generation.
• Trade-off: Hardware complexity increases rapidly with n.
Carry Generate and Propagate
• Consider the i-th stage of an adder:
• Carry Generate (Gᵢ): A carry is generated at stage i regardless of the
input carry.
• Gᵢ = Aᵢ ⋅ Bᵢ
• Carry Propagate (Pᵢ): An input carry Cᵢ is propagated to the output
carry Cᵢ₊₁.
• Pᵢ = Aᵢ ⊕ Bᵢ
• The output carry Cᵢ₊₁ can be expressed as:
• Cᵢ₊₁ = Gᵢ + Pᵢ ⋅ Cᵢ
Unrolling the Recurrence
• We can express the carry for any stage in terms of the initial carry C₀.
• C₁ = G₀ + P₀ ⋅ C₀
• C₂ = G₁ + P₁ ⋅ C₁ = G₁ + P₁(G₀ + P₀C₀) = G₁ + P₁G₀ + P₁P₀C₀
• C₃ = G₂ + P₂ ⋅ C₂ = G₂ + P₂G₁ + P₂P₁G₀ + P₂P₁P₀C₀
• And so on...
• This allows us to calculate all carries simultaneously, directly from the
inputs A, B, and C₀.
Design of a 4-bit CLA Adder
Design of a 4-bit CLA Adder
The 4-bit CLA Circuit
The 4-bit CLA Circuit
16-bit Adder Using 4-bit CLA Modules
The 4-bit CLA Circuit
• Solution:
• Use a second level of carry look-ahead mechanism to generate the input
carries to the CLA blocks in parallel.
• The second level of CLA generates C4, C8, C12 and C16 in parallel with two
gate delays (2δ).
• For larger values of n, more CLA levels can be added.
• Delay calculation of a 16-bit adder:
a) For original single-level CLA- 14δ
b) For modified two-level CLA: 10δ
