Transcript Karnaugh Maps - s3.amazonaws.com

Karnaugh Maps
Ellen Spertus
MCS 111
September 2, 2003
Big Picture
• Any number can be represented as 0s and 1s
• Functions can be represented as a table
• Any table of 0s and 1s can be interpreted as
a truth table
• Any truth table can be converted into a
boolean function
• We can implement boolean functions with
switches
2
Homework 1
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
f(A,B,C)
1
0
0
0
1
0
0
0
A
B
C
3
Sum of products form
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
f(A,B,C)
1
0
0
0
1
0
0
0
• Product refers to and (·)
• Sum refers to or (+)
4
Practice
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
f(A,B,C)
1
0
1
0
0
0
0
1
5
Homework 3: Nand is universal
• “Universal” means that you can build
any boolean function out of it
• You must be able to construct
– and
– or
– not
A
A
f1(A)
f3(A,B)
B
A
f2(A,B)
B
• All you need is nand gates!
6
Optimizing formulas
• Why is it better to have simpler
formulas?
• What makes one function simpler than
another?
• Given a truth table, is there a way to
automatically generate the simplest
possible function?
7
Building a Karnaugh map
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
f
1
0
1
0
0
0
0
1
C
A
B
0
0
0
1
1
1
1
0
0
1
8
Using a Karnaugh map
• Circle each horizontal/vertical region of
1s.
• Convert each term into a boolean
product (i.e., and the variables or their
negations together).
• Build a sum of the products (i.e., or the
products together).
9
Practice
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
f
0
0
1
1
1
0
1
1
C
A
B
0
0
0
1
1
1
1
0
0
1
10
Rules for Karnaugh maps
• Label each axis with a gray code, i.e., only
change one bit at a time.
• Regions can stretch horizontally or vertically.
• Each side of a region must be a power of 2
(e.g., 1, 2, or 4).
• For simplest formula, choose ________region
and make use of “don’t care”s.
• Regions may wrap around the edges.
• Practice with 4-input Karnaugh map…
11
Putting it together
• Definitions:
– An integer greater than 1 is prime if it has
no divisors besides 1 and itself.
– An integer greater than 1 is composite if it
is not prime.
• Let’s design a circuit that will tell
whether its 3-digit binary input is
composite or prime
• Result should be 0 for composite, 1 for
prime.
12
Big Picture
• Any number can be represented as 0s and
1s.
• Any table of 0s and 1s can be interpreted as
a truth table.
• We can implement boolean functions with
switches.
 Any truth table can be converted into a
boolean function.

13
4-variable Karnaugh map
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
f
1
1
0
0
1
0
1
1
0
0
0
1
1
0
1
0
A
CDB
0
0
0
1
1
1
1
0
00
01
11
10
14
n n prime?
A
B
C
f
0
1
2
3
4
5
6
7
15
Karnaugh map for primes
16
Lab 1
• Get familiar with your lab kit and logic
gates
• Build a full adder
• Make use of a 4-bit adder
• The voice of experience says:
– Read the directions carefully
– Draw your wiring diagram
properly
17
Wiring diagrams 1/2
• The drawing is neat, with straight
horizontal and vertical (not diagonal)
lines. (Use rulers and templates.)
• Chips are drawn not as rectangles but
in shapes that suggest their function.
• Chips are labeled with their part number
(e.g., LS283).
• Signal names (e.g., A3) appear inside
the chip, pin numbers outside.
18
Wiring diagrams 2/2
• The connections of the upper-right pin
to power and the lower-left pin to
ground are not shown.
• Inputs and outputs are clearly labeled
and grouped together.
• If colors are used, they should be used
logically and consistently.
19
inputs
S3 S2 S1 S0
S7 S6 S5 S4
14 12 3 5
A3 A2 A1 A0
9
11 15 2 6
B3 B2 B1 B0
Cout
C in
LS283
3
10
L3
2
13
L2
1
1
L1
7
0
4
L0
outputs
20