Transcript Document

Digital Logic Design
Lecture # 5
University of Tehran
Outline




Minterms and Maxterms
Simplification of a Function by KM
Minimization’s Effects on a Circuit
Timing Parameters of a Circuit
Minterms and Maxterms


We define a Minterm to be a product that contains all
variables of that particular switching function in
either complemented or non-complemented form.
A simpler shorthand form of representing a SSOP is
to use the number of the minterms that appear in
that representation. In the following example for
instance we could have written:
ab
c
0
00
01
11
10
0
0
0
1
0
1
2
1
1
6
1
3
4
0
7
1
5
w   m(1,3,4,5)
Minterms and Maxterms
(continued…)


We define a Maxterm to be a sum that contains all
variables of that particular switching function in
either complemented or non-complemented form.
Sometimes writing an expression in a POS form is
easier as seen in the following example:
w   m(1,2,3,5,6,7)
w   M (0,4)  (a  b  c).( a  b  c)
ab
c
0
00
01
11
10
0
1
1
0
0
1
2
1
1
6
1
3
4
1
7
1
5
Simplification of a Function by
KM


As said in the last lecture, in a karnaugh map, we
consider physically adjacent 1s to be boolean
adjacent terms too. This is our main concern in the
construction and use of a karnaugh map -keeping the
equality of physical adjacency and boolean
adjacency. Considering this equality, each two
adjacent boxes in the karnaugh map should only
differ in a single literal.
All of the above is exactly applied to maps with a
larger number of variables.
Simplification of a Function by
KM (continued…)

Example:
a
bc
a
b
c
F
0
0
0
0
0
1
2
0
1
0
1
0
1
1
3
4
0
0
1
0
1
1
0
5
6
7
1
1
1
0
1
1
1
0
1
1
1
0
0
0
00
0
1
0
0
0
4
bc
01
1
1
1
5
0
11
3
10
0
7
1
2
1
6
bc
}
bc+bc
Simplification of a Function by
KM (continued…)

Example:
a
b
c
F
0
0
0
1
0
0
1
1
0
0
1
1
0
0
1
0
1
0
0
1
1
1
0
1
0
1
0
0
1
1
1
1
a
00
01
1
0
bc
1
4
0
1
5
1
1
11
7
3
10
1
2
6
ac+ac
Simplification of a Function by
KM (continued…)


Observing the last example shows us that our
definition of physical adjacency doesn’t satisfy our
need, thus a small change is needed in this
definition. Hence from this point onwards we
consider the top and bottom rows of the map
adjacent (the first stands for the first and last
columns).
Note: There is no formal way to prove the resulted
expression is minimal but it can be visually observed
to be minimal.
Simplification of a Function by
KM (continued…)


Note: A standard SOP is unique for any given
function whereas a minimal SOP form may not be so.
Note: Karnaugh maps will only help with functions of
less that 7 variables.
Simplification of a Function by
KM (continued…)

We will now consider another example:
a
0
0

0
0
b
0
0
1
1
c
0
1
0
1
1
1
1
1
0
0
1
1
0
1
0
1
F
1
0
1
0
1
0
1
0
ab
c
0
00
01
1
0
1
1
2
0
1
11
1
6
0
3
10
1
4
0
7
a c + a c = c(a+a) = c
0
5
This example shows us that seeing 4 or 8 adjacent 1s
must also result in a combination that only has
variables that don’t differ in any of the corresponding
terms.
Simplification of a Function by
KM (continued…)

Let’s see another example of the last situation:
ab
c
0
00
01
11
10
1
1
0
0
0
1
2
1
1
1
3
w=a
6
4
0
7
0
5
Simplification of a Function by
KM (continued…)

Now we consider the simplification method for a
function of 4 variables. Pay attention to the example
in the next slide.
ab
bc
00
01
00
01
10
11
1
0
4
1
1
12
1
5
8
1
13
9
abc + ac + bd
1
11
3
7
1
15
10
1
11
1
2
6
14
1
10
Simplification of a Function by
KM (continued…)


The stars shown in the above karnaugh map show
that the particular map containing those stars would
be an essential choice, because those terms aren’t
covered by any other map.
In covering the 1s of a karnaugh map we look to
satisfy three aims:



Covering all minterms
Fewer maps
Larger maps (In order to cover more 1s in one map)
Simplification of a Function by
KM (continued…)

We will now see some definitions:



Implicant: Any term that it’s being one causes the
result of the function to be one, in other words
any term that implies a function. In a karnaugh
map, each 1 or combination of 1s is an implicant.
Prime Implicant: An implicant that is not included
in any larger implicant.
Essential Prime Implicant: A prime implicant that
covers at least one ‘1’ not covered by any other
prime implicant.
Simplification of a Function by
KM (continued…)


Note: When forming a minimized expression, first the
essential prime implicants are written and then the
prime implicants which have covered the 1s not
included by the EPIs are written.
We now apply the above to the following example:
ab
bc
00
01
*
0
00
01
1
1
*
1
4
12
8
1
5
13
9
3
7
1
11
10
10
11
*1
2
1
6
* 15* 1
*
bd +
11
1
14
bc
1
10
+ ad
Simplification of a Function by
KM (continued…)

The resulting circuit of the preceding example is a 2level network, as can be seen in the figure:
b
d
b
c
a
d
Simplification of a Function by
KM (continued…)

Two level networks are the most a karnaugh map can
minimize an expression to, while more minimization
may be done by the use of more boolean algebra.
This doesn’t necessarily mean the number of levels
will decrease but the number of transistors may. For
instance the three level network shown below uses
less transistors than the design shown in the last
example:
bd + bc + ad = bc + d(a+b)
b
c
a
b
d
Simplification of a Function by
KM (continued…)

To realize the expression b.d  b.c  a.d , using only
nand or nor gates, we use the following method:
b.d  b.c  a.d  bd .bc.a d
b
d
b
c
a
d
bd bcad bd bcad
b
d
b
c
a
d
Minimization’s Effects on a
Circuit



Minimization decreases our use of transistors.
Minimization affects circuit timing .
Minimization affects power consumption.
Timing Parameters of a Circuit

Consider the following structure:
1
a

b
c
a
vdd
vdd
0
0
b
1
1
0
c
In the situation where ‘a’ goes ‘1’, after a
considerable amount of time of it being ‘0’, the
capacitance on the pull-down will discharge through
the resistance of the first pull-down. An instance of
time in the exponential phase of this discharge will
come when the PMOS can no longer conduct a ‘1’ to
the output on ‘b’ and the NMOS transistor starts
conducting.
Timing Parameters of a Circuit
(continued…)

Now we consider 2 delay times, trise and tfall, for the
signals, the first being the time needed for a signal to
reach 90% of its total value from the instance it had
10% of that value and the second the time for
transition from 90% to 10%, as seen in the following
figure:
90%
10%
trise
tfall
Timing Parameters of a Circuit
(continued…)

Paying attention to the following figure, it is clear
that td is considered to be the time needed for the
output to reach 50% of its full amount from the
instance where the input has 50% of its full value.
t PHL  t PLH
td 
2
input
50%
output
50%
t
PLH
(time of propagation
from low to high)
t
PHL
(time of propagation
from high to low)
Timing Parameters of a Circuit
(continued…)

In practice, usually a delay time is considered for a
whole gate. For instance a 5ns delay for a NAND gate
would give.
a
1
a
w
5 ns
5 ns
w

Analog analysis of the mentioned matters may be
used where timing is a very important issue.