SSE3061: Digital System Design

Lecture 9.

Tae Hee Han: than@skku.edu

Semiconductor Systems Engineering
Sungkyunkwan University

Agenda
 Computer Arithmetic I
 Addition
 Number System

2
Overview
 Binary Addition
 Full Adder Revisited
 Ripple Carry
 Carry-select adder
 Carry-lookahead adder
 Subtraction

Computer Number Systems

 We all take positional notation for granted
 Dk−1 Dk−2 …D0 represents Dk−1Bk−1 + Dk−2Bk−2 + …+ D0 B0 where B ∈ { 0, …,
B−1 }
 Example: 200410, 11012 = 1310 = 0D16
 We all understand how to compare, add, subtract these numbers
 Add each position, write down the position bit and possibly carry to the next
position
 Computers represent finite number systems
 How do they efficiently compare, add, sub?
 How do we reduce it to networks of gates and FFs?
 Where does it break down?
 Manipulation of finite representations doesn’t behave like same operation on
conceptual numbers

4
Unsigned Numbers - Addition

+15 +0
Example: 3 + 2 = 5
+14 1111 0000 +1
1110 0001
+13 Unsigned binary addition
+2
1101 + 0010 Is just addition, base 2
+12 1100 0011 +3 Add the bits in each position and carry

+11 1011 0100 +4 1

+10
1010 0101 0011
+5
1001 0110 + 0010
+9 1000 0111 +6
0101
+8 +7

How do we build a combinational logic circuit to perform addition?

 Start with a truth table and go from there

Binary Addition: Half Adder

Ai 0 1 Ai
Ai Bi Sum Carry 0 1
Bi Bi
0 0 0 0 0 0 1 0 0 0
0 1 1 0
1 0 1 0 1 0
1 1 0 1
1 1 0 1

Sum = Ai Bi + Ai Bi Carry = Ai Bi
= Ai ⊕ Bi

Half-adder Schematic

But each bit position may have a carry in…

6
Full-Adder

1
0011 A B CI S CO AB
Co Cin
0 0 0 0 0 CI 00 01 11 10
+ 0010 B 0 0 1 1 0
0 0 1 0 1
0 1 0 1 0 S
0101 A 0 1 1 0 1 1 1 0 1 0
1 0 0 1 0
S 1 0 1 0 1
1 1 0 0 1 AB
1 1 1 1 1 CI 00 01 11 10
0 0 0 1 0
CO
1 0 1 1 1
S = CI ⊕ A ⊕ B

CO = B⋅CI + A⋅CI + A⋅B = CI⋅(A + B) + A⋅B

Now we can connect them up to do multiple bits…

7

Ripple Carry

A3 B3 A2 B2 A1 B1 A0 B0

+ + + +

S3 C3 S2 C2 S1 C1 S0

8
Delay in the Ripple Carry Adder
Critical delay: the propagation of carry from low to high order stages
@0
A @1
@N+1
@0
late B
CO
arriving CI @N+2
signal @N
two gate delays
@0 to compute CO
@1
@0

C0
A0 S0 @1
0
B0 C1 @2
4-stage adder
A1 S1 @3
1
B1 C2 @4

A2 S2 @5
2
B2 C3 @6

A3 S3 @7
3 final sum and carry
B3 C4 @8

Ripple Carry Timing

Critical delay: the propagation of carry from low to high order stages
S0, C1 Valid S1, C2 Valid S2, C3 Valid S3, C4 Valid

1111 + 0001
Worst-case
addition

T0 T2 T4 T6 T8

T0: Inputs to the adder are valid

T2: Stage 0 carry out (C1) 2 delays to compute sum

T4: Stage 1 carry out (C2) but the last carry not ready
until 6 delays later
T6: Stage 2 carry out (C3)

T8: Stage 3 carry out (C4)

10
Carry Select Adder
b7 a7 b6 a6 b5 a5 b4 a4 0 b3 a3 b2 a2 b1 a1 b0 a0
c0

FA

s3 s2 s1 s0
c8 0 b7 a7 b6 a6 b5 a5 b4 a4 1
1

FA

1 0 1 0 1 0 1 0

s7 s6 s5 s4

In this case:
T = Tripple_adder / 2 + TMUX
COST = 1.5 × COSTripple_adder+ (n+1) × COSTMUX

11

If we extend the bit-width…

A 16-bit carry-select adder with a uniform block size of 4

A 16-bit carry-select adder with a variable size

12
What really happens with the carries
b0 a0
c7 c6 c5 c4 c3 c2
c0
FA

s7 s6 c1 s0
A B Cout S Carry action
Ai
0 0 0 Cin kill Gi
Propagate Bi
0 1 Cin ~Cin
1 0 Cin ~Cin propagate
Ai
Pi
1 1 1 Cin generate
Bi

Carry Generate Gi = Ai ⋅ Bi must generate carry when A = B = 1

Carry Propagate Pi = Ai ⊕ Bi carry in will equal carry out here

All generates and propagates in parallel at first stage. No ripple.

13

Carry-Lookahead Adder Logic

Carry Generate Gi = Ai Bi must generate carry when A = B = 1

Carry Propagate Pi = Ai ⊕ Bi carry in will equal carry out here

Sum and Carry can be re-expressed in terms of generate/propagate:

Si = Ai ⊕ Bi ⊕ Ci = Pi ⊕ Ci Ci
Si
Pi
Ci+1 = Ai Bi + Ai Ci + Bi Ci

= Ai Bi + Ci (Ai + Bi)
Gi
= Ai Bi + Ci (Ai ⊕ Bi)
Ci Ci+1
= Gi + Ci Pi Pi

14
All Carries in Parallel

Reexpress the carry logic for each of the bits:

C1 = G0 + P0 C0

C2 = G1 + P1 C1 = G1 + P1 G0 + P1 P0 C0

C3 = G2 + P2 C2 = G2 + P2 G1 + P2 P1 G0 + P2 P1 P0 C0

C4 = G3 + P3 C3 = G3 + P3 G2 + P3 P2 G1 + P3 P2 P1 G0 + P3 P2 P1 P0 C0

Each of the carry equations can be implemented in a two-level

logic network

Variables are the adder inputs and carry-in to stage 0!

15

CLA Implementation
Ai
Pi @ 1 gate delay
Adder with Propagate and
Bi
Generate Outputs
Si @ 2 gate delay
Ci

Gi @ 1 gate delay Increasingly complex logic

C0 C0 C0
P0 C1 P0 P0
P1 P1
G0
P2 P2
P3
G0
P1 G0
C0
P2 P1
P0
P2
P1
G1 C3 P3
G0 P2
C2 G1
P1
P2
G1 G2 P3
C4
G2
P3

G3

16
How do We Extend this to Larger Adders?

A15-12 B15-12 A11-8 B11-8 A7-4 B7-4 A3-0 B3-0

4 4 4 4 4 4 4 4

4 4 4 4

S15-12 S11-8 S7-4 S3-0

 Faster carry propagation

 4 bits at a time
 But still linear
 Can we get to log?
 Compute propagate and generate for each adder BLOCK

17

CLA – in blocks
 “Group” propagate and generate signals:
pi
cin
gi
pi+1
gi+1
P = pi pi+1 … pi+k
G = gi+k + pi+k gi+k−1 + … + (pi+1pi+2 … pi+k)gi

pi+k
gi+k cout

 P true if the group as a whole propagates a carry to cout

 G true if the group as a whole generates a carry
Cout = G + PCin
 Group P and G can be generated hierarchically

18
 c0
c0
a0 p,g
b0 ci p=a⊕b
s0 P,G ai g = ab
c1 c0
a1 bi p,g
b1 si s = p ⊕ ci
s1
c2
ci+1
a2 ci+1 = g + cip
b2
s2
c3 c0
a3
b3 8-bit Carry Lookahead Adder
s3 c4
P,G
a4
b4
s4 c8
c5 c0 cin
a5
b5 P = PaPb
s5 Pa,Ga G = Gb + GaPb
c6
a6 P,G
b6 Pb,Gb Cout = G + cinP
s6
c7
a7 cout
b7
s7

19

Trade-offs in Combinational Logic Design

 Time vs. Space Trade-offs
 Doing things fast requires more logic and thus more space
 Example: carry lookahead logic

 Simple with lots of gates vs. complex with fewer

 Arithmetic Logic Units

 Critical component of processor datapath
 Inner-most “loop” of most computer instructions

20
So What About Subtraction?

+15 +0  Develop subtraction

+14 1111 0000 +1 circuit using the same
+13
1110 0001
+2
process
1101 − 0010
 Truth table for each bit
+12 1100 +3
0011 slice
+11 1011 0100 +4  Borrow in from slice of
+10
1010 0101 lesser significance
+5
1001 0110  Borrow out to slice of
+6
+9 1000 0111 greater significance
+8 +7
 Very much like carry chain

21

Finite Representation?

+15 +0  What happens when

+14 1111 0000 +1 𝑁 ?
1110 0001
+13 − +2  Overflow
1101 0010

+12 1100 +3  Detect?

0011
 Carry out
+11 1011 0100 +4
1010 0101
 What happens when
+10 +5
1001 0110
?
+9 1000 0111 +6  Negative numbers?
+8 +7  Borrow out?

22
Number Systems (1/2)
 Desirable properties:
 Efficient encoding (2n bit patterns. How many numbers?)
 Positive and negative
 Closure (almost) under addition and subtraction
 Except when overflow
 Representation of positive numbers same in most systems
 Major differences are in how negative numbers are represented
 Efficient operations
 Comparison: =, <, >
 Addition, Subtraction
 Detection of overflow
 Algebraic properties?
 Closure under negation?
 A == B iff A – B == 0

23

Number Systems (2/2)

 Three Major schemes:
 sign and magnitude
 1’s complement
 2’s complement
 (excess notation)

24
Sign and Magnitude
-7 +0
-6 1111 0000 +1
1110 0001 Example: N = 4
-5 +2 +
1101 0010
-4 1100 0011 +3 0 100 = + 4

-3 1011 0100 +4 1 100 = - 4

1010 0101
-2 +5 -
1001 0110
-1 1000 0111 +6
-0 +7
High order bit is sign: 0 = positive (or zero), 1 = negative

Remaining low order bits is the magnitude: 0 (000) thru 7 (111)

Number range for n bits = +/− 2n−1 − 1

Representations for 0?

Operations: =, <, >, +, − ???

25

1’s Complement (algebraically)

N is positive number, then N is its negative for 1's complement

N = (2n − 1) − N 𝟐𝟒 = 𝟏𝟎𝟎𝟎𝟎

𝟏 = 𝟎𝟎𝟎𝟎𝟏
Example: 1's complement of 7
𝟏𝟏𝟏𝟏

 𝟕 = −(𝟎𝟏𝟏𝟏)

𝟏𝟎𝟎𝟎
−7 in 1's comp.

Bit manipulation:

simply complement each of the bits

0111  1000

26
1’s Complement on the Number Wheel
-0 +0
-1 1111 0000 +1
1110 0001
-2 +2 +
1101 0010
-3 1100 0011 +3 0 100 = + 4

-4 1011 0100 +4 1 011 = - 4

1010 0101
-5 +5 -
1001 0110
-6 1000 0111 +6
-7 +7
Subtraction implemented by addition & 1's complement.
Sign is easy to determine.
Closure under negation. If A can be represented, so can −A.
Still two representations of 0!
If A == B then is A − B == 0 ?
Addition is almost clockwise advance, like unsigned.
27

2’s Complement number wheel

−𝟏 +𝟎
−𝟐 1111 0000 +𝟏
1110 0001
−𝟑 +𝟐 +
1101 0010

like 1's comp −𝟒 1100 0011 +𝟑 𝟎 𝟏𝟎𝟎 = +𝟒

except shifted −𝟓 1011 𝟏 𝟏𝟎𝟎 = −𝟒
one position
0100 +𝟒
1010
clockwise −𝟔 0101
+𝟓 
1001 0110
−𝟕 1000 0111 +𝟔
−𝟖 +𝟕
Easy to determine sign (0?).
Only one representation for 0.
Addition and subtraction just as in unsigned case.
Simple comparison: A < B iff A − B < 0.
One more negative number than positive number.
- one number has no additive inverse
28
2’s Complement (algebraically)

N* = 2n − N 24 = 10000

Example: 2’s complement of 7 sub 7 = 0111

1001 = repr. of −7

Example: 2’s complement of −7 24 = 10000

sub −7 = 1001

0111 = repr. of 7
Bit manipulation:
2’s complement: take bitwise complement and add one
0111  1000 + 1  1001 (representation of −7)

1001  0110 + 1  0111 (representation of 7)

29

How is addition performed in each

number system?
Operands may be positive or negative

30
Sign Magnitude Addition

Operand have same sign: unsigned addition of magnitudes

4 0100 −4 1100
result sign bit is the
same as the operands’ +3 0011 + (−3) 1011
sign
7 0111 −7 1111

Operands have different signs:

subtract smaller from larger and keep sign of the larger

4 0100 −4 1100
−3 1011 +3 0011
1 0001 −1 1001

31

1’s Complement Addition

Perform unsigned addition, then add in the end-around carry

4 0100 −4 1011
+3 0011 + (−3) 1100
7 0111 −7 10111
End-around carry 1

1000

4 0100 −4 1011
−3 1100 +3 0011
1 10000 −1 1110

End-around carry 1

0001

32
2’s Complement Addition

4 0100 −4 1100
Perform unsigned addition and
+3 0011 + (−3) 1101
discard the carry out.
7 0111 −7 11001

Overflow?

4 0100 −4 1100
−3 1101 +3 0011
1 10001 −1 1111

Simpler addition scheme makes 2’s complement the most common

choice for integer number systems within digital systems

33

2’s Complement Number Wheel

−𝟏 +𝟎
−𝟐 1111 0000 +𝟏
1110 0001
−𝟑 +𝟐 +
1101 0010
−𝟒 1100 0011 +𝟑 𝟎 𝟏𝟎𝟎 = +𝟒

−𝟓 1011 0100 +𝟒 𝟏 𝟏𝟎𝟎 = −𝟒

1010
−𝟔 0101
+𝟓 
1001 0110
−𝟕 1000 0111 +𝟔
−𝟖 +𝟕

 where 
 when

34
2’s Comp: ignore the Carry-out

 when
M* + N = (2n − M) + N = 2n + (N − M)

Ignoring carry-out is just like subtracting 2n

 where 𝑛1

(− M) + (− N) = M* + N* = (2n − M) + (2n − N)
Carry-out
= 2n − (M + N) + 2n

After ignoring the carry, this is just the right 2’s complement
representation for 

35

2’s Complement Overflow

How can you tell an overflow occurred?
Add two positive numbers to get a negative number or two
negative numbers to get a positive number

-1 +0 -1 +0
-2 1111 0000 +1 -2 1111 0000 +1
1110 0001 1110 0001
-3 +2 -3
1101 1101 +2
0010 0010
-4 -4
1100 0011 +3 1100 0011 +3
-5 1011 -5 1011
0100 +4 0100 +4
1010 1010
-6 0101 -6 0101
1001
+5 +5
0110 1001 0110
-7 1000 0111 +6 -7 1000 +6
0111
-8 +7 -8 +7

5 + 3 = −8! −7 − 2 = +7!
36
2’s Comp. Overflow Detection (4-bit case)
0111 1000
5 0101 −7 1001
3 0011 −2 1100
−8 1000 7 10111
Overflow Overflow

0000 1111
5 0101 −3 1101
2 0010 −5 1011
7 0111 −8 11000
No overflow No overflow

Overflow occurs when carry-in to sign does not equal carry-out

37

2’s Complement Adder/Subtractor

A − B = A + (−B) = A + B + 1

38
Summary (1/2)
 Circuit design for unsigned addition
 Full adder per bit slice
 Delay limited by Carry Propagation
 Ripple is algorithmically slow, but wires are short

 Carry select
 Simple, resource-intensive
 Excellent layout
 Carry look-ahead
 Excellent asymptotic behavior
 Great at the board level, but wire length effects are significant
on chip

39

Summary (2/2)
 Digital number systems
 How to represent negative numbers
 Simple operations
 Clean algorithmic properties

 2’s complement is most widely used

 Circuit for unsigned arithmetic
 Subtract by complement and carry in
 Overflow when  of sign-bit is 1

40