Ch. 5.1

SYEN 3330
Digital Systems
Chapter 5 – Part 1
SYEN 3330 Digital Systems
Jung H. Kim Chapter5-1 1
Functional Blocks: Addition
Binary addition is a frequently occurring
operation in computer systems.
In this section, we will:

Develop a Half-Adder (HA) bit-wise
addition functional block,

Develop a Full-Adder (FA) bit-wise
addition block,

Extend it to parallel binary addition using
ripple-carry, and

Develop a faster Carry-Look-Ahead Adder
CLA.
SYEN 3330 Digital Systems
Chapter 5-1
Page 2
Functional Block: Half-Adder
A binary adder of one-bit width produces the following
values: X
0
0
1
1
+Y
+0
+1
+0
+1
CS
00
01
01
10
 A half adder adds two bits to produce a two-bit sum.
 The sum is expressed as a sum bit , S and a carry bit, C.
This can be expressed as a
combined Boolean function table
for S and C:

SYEN 3330 Digital Systems
X Y
C
S
0
0
1
1
0
0
0
1
0
1
1
0
0
1
0
1
Chapter 5-1
Page 3
Logic Simplification: Half-Adder
The K-Map for S, C is: S
This is a pretty trivial
map! By inspection,
we have:
X
C = XY
S = XY' + X'Y
[SOP]
or
S = (X'Y'+XY)'
= (X+Y)(X'+Y') [POS]
C
Y
0
11
12
3
X
Y
0
1
2
13
Note also that:
C = XY = (X'+Y')'
and that
S = XY (XOR)
These equations lead to several implementations.
SYEN 3330 Digital Systems
Chapter 5-1
Page 4
Five Implementations: Half-Adder
We can derive following sets of equations for a half-adder:
(d) S = (X+Y)(C')
(a) S = XY'+ X'Y
C = (X'+Y')' so C' = (X'+Y')
C = XY
(e) S = XY
(b) S = (X+Y)(X'+Y')
C = XY
C = XY
(c) S = (C+X'Y')'
C = XY
From above, (a), (b), and (e) are SOP, POS, and XOR
implementations for S.
In (c), the C function is used as a term in the AND-NOR
implementation of S, and in (d), the C' function is used in a
POS term for S.
SYEN 3330 Digital Systems
Chapter 5-1
Page 5
Implementations: Half-Adder
The most common halfadder implementation
("e") is shown below:
A NAND only
implementation (equivalent
to equation "d") is:
C
C
X
X
S
Y
S = XY
C = XY
G
SYEN 3330 Digital Systems
S
C
Y
S = (X + Y)C'
C = ((XY)')'
Co
Chapter 5-1
Page 6
Functional Block: Full-Adder
A full adder is similar to a half adder, but it makes
provisions for a carry-in bit from lower stages. Like the
half-adder, it computes a sum bit, S and a carry bit, C.
For a carry-in (Z) of
zero, it is the same as
the half-adder: 
For a carry- in
(Z) of one:
SYEN 3330 Digital Systems

Z
X
+Y
0
0
+0
0
0
+1
0
1
+0
0
1
+1
CS
00
01
01
10
Z
X
+Y
1
0
+0
1
0
+1
1
1
+0
1
1
+1
CS
01
10
10
11
Chapter 5-1
Page 7
Design: Full-Adder
Full-Adder Function Table: 
Full-Adder K-Map:
S
Y
0
X
X Y Z
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1
4
1
1
5
3
1
C
0
0
0
1
0
1
1
1
C
1
2
Y
0
X
7
6
4
1
1
Z
SYEN 3330 Digital Systems
S
0
1
1
0
1
0
0
1
5
1
1
3
7
Z
Chapter 5-1
Page 8
2
1
6
Design: Full-Adder
From the K-Map, we get:

The S function above turns out to be
the three-bit ExOR function (Odd
Function):

S = XY'Z'+X'Y'Z
+XYZ+X'YZ'
C = XY + XZ + YZ
S = (XY)Z
The Carry bit C will occur if both X
and Y are true (the sum is two), or if
the sum is one and a carry-in (Z)
occurs. Thus C can be re-written as:
C = XY + (XY)Z

The term XY is carry generate.
The term XY is carry propagate.
SYEN 3330 Digital Systems
Chapter 5-1
Page 9
Implementation: Full Adder
• Full Adder Schematic

Here X, Y, and Z, and C
(from the previous
pages) are A, B, Ci and
Co respectively. Also,
G= Generate and
P = Propagate.
G
A
Co
P
S
B
Ci
 Note: This is really a combination
G of a
3-bit odd function (for S = sum) and Carry logic:
(G = Generate) OR (P =Propagate AND Ci = Carry In)
 Co = G + PCi
A
SYEN 3330 Digital Systems
B
P
Chapter 5-1
Page 10
Co
S
Parallel Binary Adders
To make adders that add more than one bit, so we "bundle"
sets of logical signals together and build devices that operate
on the whole set in parallel.
Description
Subscript
3210
Name
0110
C(i)
1011
A(i)
0011
B(i)
Sum
1110
S(i)
Output
Carry
0011
C(i+1)
Example: 4 bit binary adder:
we wish to add an input
Input Carry
vector "A(3..0) " to "B(3..0)"
Augend
to get a sum S(3..0) thus:
Addend

Note: the carry out of Stage(i) becomes the carry in of
Stage(i+1).
SYEN 3330 Digital Systems
Chapter 5-1
Page 11
4-bit Ripple-Carry Binary Adder
• A four-bit Full Adder made from 4 single bit Full
Adders: 
A(3)
A(2)
A(1)
A(0)
B(3)
B(2)
B(1)
B(0)
C(4)
x
Co
y
FA
Ci
C(3)
S
S(3)
x
Co
y
FA
S
x
Co
y
FA
Ci
x
C(1)
Co
S
S(2)
Here FA is a FullAdder from before.
Each Full Adder looks
like this: 
SYEN 3330 Digital Systems
Ci
C(2)
y
FA
Ci
C(0)
S
S(1)
S(0)
G
Co
P
S
A
B
Ci
Chapter 5-1
Page 12
Carry Propagation & Delay
One potential problem with the addition of binary
numbers is the length of time to propagate the carry from
the least significant bit to the most significant bit.
The gate-level propagation path for a four-bit adder of the
last example:
A(3)
B(3)
A(2)
B(2)
C(3)
A(1)
B(1)
C(2)
A(0)
B(0)
C(1)
C(0)
C(4)
S(3)
S(2)
S(1)
S(0)
Note: The "long path" is from A(0) or B(0) though the
network to C(4) and S(3).
SYEN 3330 Digital Systems
Chapter 5-1
Page 13
Carry Look-Ahead
Given Stage(i) from a Full Adder, we know that there will be a
carry generated when A(i) = B(i) = "1", whether or not there
is a carry-in. Alternately, there will be a carry propagated if
the "Half-Sum" is "1" and a carry-in, C(i) occurs.
These two signal conditions
are called Generate denoted
as G(i), and Propagate
denoted as P(i) respectively
and are shown here: 
A(i)
B(i)
G(i)
P(i)
C(i)
SYEN 3330 Digital Systems
C(i+1)
S(i)
Chapter 5-1
Page 14
Carry Look-Ahead (Continued)
By defining the
equations for the Full
Adder in term of the
P(i) = A(i)B(i)
P(i) and G(i), we have:
G(i) = A(i)B(i)
And the output sum
S(i) and carry
S(i) = P(i)C(i)
C(i+1) is defined as:
C(i+1) = G(i) + P(i)C(i)
Starting the stage
numbering at zero,
C(4) = G(3) + P(3)G(2)
we have:
+ P(3)P(2)G(1)
Where C(0) is a carry in to the + P(3)P(2)P(1)G(0)
least significant bit.
+ P(3)P(2)P(1)P(0)C(0)
SYEN 3330 Digital Systems
Chapter 5-1
Page 15
Carry Look-Ahead (Continued)
1xxx Generate a carry out of
Look at the
1xxx stage(3).
following
1xxxx
"addition"
11xx Generate a carry out of the
examples, all of
01xx stage(2) and propagate it
which generate a
10xxx through the stage(3).
carry of 1 out of the 111x Generate a carry out of
001x stage(1) and propagate it
third stage:
100xx
1111
0001
1000x
1111
0000
10000
SYEN 3330 Digital Systems
through stage(2) and stage(3).
Generate a carry out of the
stage(0) and propagate it
through stage(1), stage(2), and
stage(3)..
Use a carry into stage(0) and
propagate it through stage(0),
stage(1), stage(2), and stage(3).
Chapter 5-1
Page 16
Group Carry Look-Ahead Logic
Figure 5-6 in the text shows how to implement a carry look-ahead
circuit for four bits. This could be extended to more than four bits.
In practice, though, it becomes more difficult to implement this over
more than a few bits. The concept can be extended another level by
considering a Group Generate (G_G) and Group Propagate (G_P)
logic condition:
G_G = G(3) + P(3)G(2) + P(3)P(2)G(1) + P(3)P(2)P(1)G(0)
G_P = P(3)P(2)P(1)P(0)
So we get:
C(4) = G_G + G_PC(0)
Thus, it is possible to have four, 4-bit adders use the same carry lookahead circuit as before to add 16 bits!
SYEN 3330 Digital Systems
Chapter 5-1
Page 17