# Ch. 5.1

by user

on
49

views

Report

#### Transcript

Ch. 5.1
```SYEN 3330
Digital Systems
Chapter 5 – Part 1
SYEN 3330 Digital Systems
Jung H. Kim Chapter5-1 1
Binary addition is a frequently occurring
operation in computer systems.
In this section, we will:



Extend it to parallel binary addition using
ripple-carry, and

CLA.
SYEN 3330 Digital Systems
Chapter 5-1
Page 2
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
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
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
("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
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
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
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
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

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
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)
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:

Note: the carry out of Stage(i) becomes the carry in of
Stage(i+1).
SYEN 3330 Digital Systems
Chapter 5-1
Page 11
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.
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
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
By defining the
equations for the Full
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
1xxx Generate a carry out of
Look at the
1xxx stage(3).
following
1xxxx
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
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
```
Fly UP