CS 2204: Digital Circuits
Lecture 6
Minimization using k-maps
Consider the truth table:
1
1
0
1
Can we speed this up?
K = “Karnaugh”
k-map
First re-arrange your truth table as 2-d “map”
1
1
0
1
1
1 1
0
k-map
1
1 1
0
More examples
1 1
0 0
1 0
0 1
0 0
0 1
3-variable k-maps
Combination rules
1
11
1
1
1
11
1
4-variable k-map
Cubes of size 2, 4, and 8
are possible. Any cube can
be expressed as the product
of the variables that are
common across all the
minterms in the cube
Example 1
1
11
1
1 1
Example 2
1
1
1 1 1
1 1
1 1 1
Example 3
1
1 1 1
1 1
1 1
Example 4
1
1 1 1
1 1
1
1
1
1
From sop to pos
We can also write f in “product-of-sum”
form as follows
Each entry of a
truth-table is also
associated with a
“max-term.” E.g.
A Boolean function f can
be written as the
“product” of maxterms
over rows for which f=0
Example pos form
Example pos form
Implementation using and/or gates
Implementation using NAND and NOR GATES
On real silicon chips we can only implement NAND (NOT-AND)
and NOR (NOT-OR) gates, along with NOT gates. We would
implement AND gates using NAND followed by NOT. Likewise, we
would implement OR gates using NOR followed by NOT.
Transitioning between gates
FRom and-or to NAND-NOR Boolean logic netlists
Another example (with POS form)
Not gates can be designing using Nands or Nors
exercise
Implement using ONLY NOR gates