Adder

Half Adder
X Y S C
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

2
 Full Adder

Truth table: Note:
X Y Z C S Z - carry in (to the current
0 0 0 0 0
0 0 1 0 1
position)
0 1 0 0 1 C - carry out (to the next
0 1 1 1 0
1 0 0 0 1
position)
1 0 1 1 0 S = Σm(1,2,4,7)
1 1 0 1 0
1 1 1 1 1 C = Σm(3,5,6,7)

Using K-map, simplified SOP form is:

C = XY + XZ + YZ
S = X'Y'Z + X'YZ'+XY'Z'+XYZ

Sum Carry
X 0 1 X 0 1
YZ YZ
00 0 1 4
00 0 0
0 4
0
01 1 0 01 0 1
1 5 1 5 Z
11 0 1 11 1 1
3 7 3 7
10 1 2
0 6 10 0 2 1 6
Full Adder Circuit

4
 Gate-level Design: Full Adder

Circuit for above formulae:
C = XY + (X⊕Y)Z
S = X⊕Y⊕Z

X (X⊕Y)
Y S

(XY)
C
Z
Full Adder made from two Half-Adders (+ OR gate).
4-bit Adder Circuit

But this is slow...

6
 K n-bit numbers can be added by cascading k n-bit adders.

xkn - 1 ykn - 1 x2n - 1 y2n - 1 xn y n xn - 1 y n - 1 x 0 y 0

cn
n-bit n-bit n-bit c
c kn 0
adder adder adder

s s( s s s s
kn - 1 k - 1) n 2n - 1 n n- 1 0

Each n-bit adder forms a block, so this is cascading of blocks.

Carries ripple or propagate through blocks, Blocked Ripple Carry Adder
 N bit Ripple carry adder
• Straight-forward design
• Simple circuit structure
• Easy to understand
• Most power efficient
• Slowest (too long critical path)
 Delays in the ripple carry adder
• This is called a ripple carry adder, because the inputs A0, B0 and CI “ripple”
leftwards until CO and S3 are produced.
• Ripple carry adders are slow!
– For an n-bit ripple carry adder
• Carry takes 2n gate delays
• Sum takes (2n-1) gate delays
– Imagine a 64-bit adder. The longest path would have 128 gates!

xk n - 1 yk n - 1 x2n - 1 y2n - 1 xn y n xn - 1 y n - 1 x 0 y 0

cn
n-bit n-bit n-bit c
c kn 0
adder adder adder

s s( s s s s
kn - 1 k - 1) n 2n - 1 n n- 1 0

9
 Binary Subtractor
• Subtraction is done by using complements

• A’s 2’s Complement = A’+1

• A-B= A + B’+1

10
•Recall X – Y is equivalent to adding 2’s complement of Y to X.
•2’s complement is equivalent to 1’s complement + 1.
•X – Y = X + Y + 1
•2’s complement of positive and negative numbers is computed similarly.

xn - 1 yn- 1 x1 y1 x0 y0

cn - 1 c1
cn FA FA FA 1

sn - 1 s1 s0
Most significant bit Least significant bit
(MSB) position (LSB) position
4-bit adder subtractor

12
Carry Lookahead adder
 A faster way to compute carry outs
• Instead of waiting for the carry out from all the
previous stages, we could compute it directly with a
two-level circuit, thus minimizing the delay.
• First we define two functions.
– The “generate” function gi produces 1 when
there must be a carry out from position i (i.e.,
when Ai and Bi are both 1).
g i = A iB i
– The “propagate” function pi is true when, if
there is an incoming carry, it is propagated (i.e,
Ai Bi Ci Ci+1
when Ai=1 or Bi=1, but not both).
0 0 0 0
p i = Ai ⊕ B i 0 0 1 0
0 1 0 0
• Then we can rewrite the carry out function:
0 1 1 1
ci+1 = gi + pici 1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
14
 A Note On Propagation
• We could have defined propagation as A + B instead of A ⊕ B
– As defined, it captures the case when we propagate but don’t generate
• I.e., propagation and generation are mutually exclusive
– There is no reason that they need to be mutually exclusive
– However, if we use ⊕ to define propagation, then we can share the XOR gate
between the production of the sum bit and the production of the propagation
bit

15
 Algebraic carry out
• Let’s look at the carry out equations for specific bits, using the general equation
from the previous page ci+1 = gi + pici:
c1 = g0 + p0c0

c2 = g1 + p1c1
= g1 + p1(g0 + p0c0)
= g1 + p1g0 + p1p0c0

c3 = g2 + p2c2
= g2 + p2(g1 + p1g0 + p1p0c0)
= g2 + p2g1 + p2p1g0 + p2p1p0c0

c4 = g3 + p3c3
= g3 + p3(g2 + p2g1 + p2p1g0 + p2p1p0c0)
= g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0c0

• These expressions are all sums of products, so we can use them to make a circuit
with only a two-level delay.

16
 4 bit Carry lookahead adder

Gate Delays 4 bit CLA

Gi, Pi = 1 gate delay Gate Delays 4 bit ripple carry
Ci = 3rd gate delay Ci = 8 gate delay
Si = 4th gate delay Si = 7 gate delay
 16 bit ripple carry adder using 4 bit Carry
lookahead adder

Gate Delays for 16 bit Gate Delays for 32 bit

1. Ripple Carry Adder 1. Ripple Carry Adder
Sum 31 Sum 63
Carry 32 Carry 64
2. CLA 2. CLA
G,P = 1 gate delay G,P = 1 gate delay
C4 = 3rd gate delay, C4 = 3rd gate delay,
C8 = 5th gate delay C8 = 5th gate delay
C12 = 7th gate delay C12 = 7th gate delay
C16 = 9th gate delay C 32 = 17th gate delay
(1 for g,p +2*8 for each 4 bit adder)
S15 = 10th gate delay
S32 = 18th gate delay
 High level Generator and Propagator function

4 CLA forms 16bit adder

Gate delays
G,P =1
GI,PI = 3rd gate delay
C4,C8,C12,C16 =5th gate delay
C12 to C15 = 7th gate delay
S15 = 8th gate delay
32 bit adder cascading two 16 bit Carry lookahead
adder

8 CLA form 32 bit adder

Gate Delay 32 bit adder

G,P =1
GI,PI = 3rd gate delay
C4,C8,C12,C16 =5th gate delay
C12 to C15 = 7th gate delay
GI,PI = 7 th gate delay
C20,24,28,32 = 9th gate delay

S31 = 10th gate delay

 64 bit Carry lookahead adder

Gate Delay
G,P =1
GI,PI = 3rd gate delay
GII,PII = 5 th gate delay
C16,C32,C48,C64 = 7th gate delay
C52,C56,C60 =9th gate delay
C61,C62,C63 = 11th gate delay

S63 = 12th gate delay

Overflow conditions

22
 Overflow conditions
Sequence of MIPS instructions can discover overflow - signed addition

23
 Overflow conditions
Sequence of MIPS instructions can discover overflow - unsigned addition

24