Transcript Document

Digital Logic Design
Lecture # 4
University of Tehran
Outline






Review of Lecture # 3
Complex Gates
Capacitance and Resistance of a Transistor
Boolean Algebra
Decreasing the Use of Transistors in Overflow
Detector by the Boolean Algebra
Karnaugh Map
Review of Lecture # 3


Following up the last session, an inverter can be
represented in any of the following forms:
Quote: Different usages will require the bubble on
different sides of the gate.
Review of Lecture # 3
(continued…)

In each of the structures shown in the last session
for NAND, NOR and NOT gates, 2 main parts can be
defined. For instance in the NAND gate:
Pull up (pulls the output
of the gate to vdd)
vdd
w
a
b
Pull down (pulls the
output down to gnd)
Review of Lecture # 3
(continued…)

We prefer to use AND-OR gates instead of NANDNOR gates we constructed. These gates can be
constructed in the following manner:
AND

OR
As seen in the last slide, using the notation for the
inverter is preferable when we mean to cancel out
the two bubbles. This is mainly in order to increase
readability.
Review of Lecture # 3
(continued…)

Example: How many transistors will be used to
construct a three input AND?
Answer: 8, 6 for the three input NAND gate and
2 for the inverter needed after it.
Complex Gates

Gate structures we have seen so far have only
parallel or serial wiring in each of their pull up or pull
down structures. In complex gates, these two types
of wiring are mixed. In order to maintain the
complementary logic (CMOS), any series wiring in the
pull up structure must be parallel in the pull down
structure and vice versa.
Complex Gates (continued…)

Example: In the complex gate shown in the next
slide, it can be easily seen that whenever a=1 or b=1
and c=1, 0 will be pushed onto the output, thus we
have:
w  a  b.c
vdd
a
w
b
c
W=a+b.c
Complex Gates (continued…)

Logic in the last example can be shown in the
following manners:
c
b
a



1
c
b
a
2
Note: In the first representation, we consider a
complex gate which has only one pull up and one pull
down structure. In the second representation, we
consider 3 pull up and 3 pull down structures.
Complex gates are shown in the first manner.
These two structures mainly differ in their timings.
Capacity and Resistance of a
Transistor

If we consider the transistor structure as show below,
we can spot a capacitance and resistance potentially
showing itself in this structure:
Gate
Source
Drain
channel
Body
SiO2
Capacity and Resistance of a
Transistor (continued…)

The capacitance can be seen between the gate and
the body, while the resistance between the drain and
source will stand out very much when the channel
doesn’t exist in the off state. When the transistor is
on, a little resistance will still remain between the
drain and source.
Capacity and Resistance of a
Transistor (continued…)

When we use gates after each other for example in
the following figure, states can occur when the
change of the signals will effect the capacitance of
the transistors, causing them to be charged or
discharged. This change occurs in an exponential
time, because the capacitance of the NMOS transistor
makes an RC circuit with the resistance of the PMOS
transistor. These states occur mostly when we have
too many pull ups and downs structures after each
other. These structures will effect timing and energy
vdd
vdd
consumption in our circuit.
1
a
0
0
1
1
c
0
Boolean Algebra

Suppose two variables: a and b, which have only two
probable values: 1 and 0. To understand the Boolean
rules better, compare the variables with the switches
shown in the following circuits:
a
a
b
b
a.b
a+b
Boolean Algebra (continued…)

Boolean rules:
2) a.a  a
1)a  a
3)a  a  a
5) a  1  a
4)a.1  a
6)a.0  0
7) a  0  0
8) a.b  b.a
9) a  b  b  a
10)( a.b).c  a.(b.c)
11)( a  b)  c  a  (b  c)
12)a  (b.c)  (a  b).( a  c)
13)a.(b  c)  (a.b)  (a.c)
Boolean Algebra (continued…)
14) Duality: The dual of a true expression is also true
and can be formed by replacing and’s with or’s (and
vice versa), 0’s with 1’s (and vice versa).
15) Demorgan’s Law:
a.b  a  b


a  b  a.b
Precedence of operators:
1.not
2.and
3.or
Example:
a.b  c  a.b.c  (a  b).c
Decreasing the Use of Transistors
in Overflow Detector by the
Boolean Algebra

Returning to our discussion of constructing an
overflow detector, what we have done so far can be
analyzed as follows:
We started by writing an expression through our
analysis of the problem’s word description, and then
realized that expression by constructing the needed
gates of our primitives, the transistors. We reached a
realization uses 28 transistors.
b
s
a
2
2
8
6
8
2
v
Decreasing the Use of Transistors
in Overflow Detector by the
Boolean Algebra (continued…)


A question that arises here is weather or not we may
have decreased our use of transistors for this
structure by playing around with the expression
beforehand. Another thing to consider is that the
word description of a problem is not always simple
enough for us to hope of reaching a simplified
answer through it.
In our aim-minimization of the expression-we need to
have a knowledge of the algebra that rules in our
problem. We are using variables of 2 values thus our
need can be supplied by the use of Boolean algebra.
Decreasing the Use of Transistors
in Overflow Detector by the
Boolean Algebra (continued…)

Let us now see how close we have come to our goal.
v  a.b.c  a.b.c  a.b.c  a.b.c  a.b.c.a.b.c
b
s
a
2
2
6
4
v
6
2

In this new representation, we’ve used 22 transistors
instead of the 28 used in the first representation we
made.
Decreasing the Use of Transistors
in Overflow Detector by the
Boolean Algebra (continued…)


Manipulation of an expression will be a worthy act in
other phases of our work as it can be used to reduce
time and energy consumption in the circuit.
Example:
1)a  a.b  a.1  a.b  a.(1  b)  a.1  a
2)a  a.b  a.(b  b)  a.b  a.b  a.b  a.b 
a.b  a.b  a.b  a.b  a.(b  b)  b.(a  a ) 
ab
Decreasing the Use of Transistors
in Overflow Detector by the
Boolean Algebra (continued…)


Quote: using less transistors to realize a circuit
usually means less delay and power consumption
too.
Example:
F  x. y  y.z  x.z
If we realize the hardware directly from this
expression we will need 26 transistors. We will now
try to decrease this amount by using Boolean
algebra:
F  x.y  y.z.(x  x )  x.z  x.y  x.y.z  x.z.y  x.z
 x.y.1  x.y.z  x.z.y  x.z.1  x.y.(1  z) 
x.z.( 1  y)  x.y  x.z  x.y  x.z
Decreasing the Use of Transistors
in Overflow Detector by the
Boolean Algebra (continued…)

The last expression will only need 14 transistors to
realize.
Karnaugh Map


Using Boolean algebra for minimization causes it’s
own problem because of it mainly being a trial and
error process, and we can almost never be sure that
we have reached a minimal representation.
If we can form a graphical notation for our Boolean
algebra the insight need for the minimization will be
less vital in solving the problems.
Karnaugh Map (continued…)

We can come close to our aim by using a graphical
notation named Karnaugh Map shown as follows:
Karnaugh Map
a
b
0
0
1
0
0
1
2
0
1
Truth Table
0
1
3
a
0
b w
0 0
0
1 0
1
0 0
1
1 1
a
b
w
Karnaugh Map (continued…)

As it can be seen, each box of the Karnaugh map
corresponds t a row of the truth table and has been
numbered accordingly. In the following example, the
truth table and the Karnaugh map correspond in the
above mentioned manner:
Karnaugh Map
a
b
0
2
1
1
1
1
3
W=ab+ab+ab
p
1
0
0
1

0
Truth Table
a
0
b w
0 0
0
1 1
1
0 1
1
1 1
p
Sum of
Product
p
a
b
w
This form of representing w in the following example
is called a Sum of Product (SOP).
Karnaugh Map (continued…)

The expression w  a  b.c can also be considered a
sum of product, but the one shown before was a
Standard SOP. In standard SOP, the products are
obtained directly from the Karnaugh map or truth
table, so the SOP contains all of the variables of the
function.
Karnaugh Map (continued…)

When a function is written in standard SOP form, it
has been written with it’s smallest details. In the
expression w  a  b.c , the product ‘a’ is not in it’s
smallest detail, because it contains other terms as
well as can be seen from the truth table of the
function:
a
0
b
0
c
0
w
0
0
1
1
0
1
0
1
0
1
0
3
4
0
0
0
1
5
6
7
1
1
1
0
1
1
1
0
1
1
1
1
0
1
2
0
1
a
Karnaugh Map (continued…)


When attempting to minimize a function with Boolean
algebra, writing the expression in standard SOP form
will make the rest of the process easier.
For instance:
a.b  a.b  a.b  a.b  a.b  a.b  a.b 
a.(b  b )  b.(a  a )  a  b
Karnaugh Map (continued…)



Even by starting our process with a standard SOP
form, the insight needed for the next step is still
considerable (in the above example for instance, to
recognize what term needs to be added).
In Boolean algebra, we learnt that when two terms
differed in only one variable, that particular variable
could have been eliminated in both terms. These
terms are also called Boolean adjacent terms.
With paying attention to the structure of the
Karnaugh map, we can see that we may combine
physical adjacency and Boolean adjacency of the
products.
Karnaugh Map (continued…)

According to the facts mentioned in the two above
paragraphs, in order to use the Karnaugh maps for
minimizing a function, it’s enough to map the
physical adjacent 1’s in the Karnaugh map and write
the relative Boolean expressions of the maps as it’s
shown in the following example:
a
b
0
0
1
0
0
1
2
a+b
1
1
1
1
3
Karnaugh Map (continued…)

Note: The number of rows and columns of a map
must be equal to one of the powers of 2.