Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Karnaugh Maps
Objectives
This section presents a technique for simplifying logical
expressions
...

Show how to use Karnaugh maps to derive minimal sumof-products and product-of-sums expressions
...


Reading Assignment
Sections 2
...
7 from the text

Elec 326

1

Karnaugh Maps

Karnaugh Map Definitions
A Karnaugh map is a two-dimensional truth-table
...
e
...

A B Z
0 0 0
0 1 1
1 0 1
1 1 0
Truth Table

0

1

Z A
0
B
0 0

1

0

1

Z

A

B

1

1
1
0

Type 2 Map

Type 1 Map

Two-Variable Maps
AB C Z
0 00 0
0 01 1
0 10 1
0 11 0
1 00 1
1 01 0
1 10 0
1 11 1
Truth Table

Z

Z A
B,C
0
00 0

0
1

0

0
B

1

1

1

0

1
1

01

A

1

0

11

0

1

10

1

0

C

Type 1 Map

Type 2 Map

Three-Variable Maps
Elec 326

2

Karnaugh Maps

1

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

Z
0
0
0
1
0
1
1
1
0
1
1
1
1
1
1
1

D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1

Z

Z A,B
C,D
00 01 11 10
00 0 0 1 0

A
0

1

0

1

1

1

1

1

1

1

0

C

0

0

1

1

1

01 0

1

1

1

11 1

1

1

1

10 0

D

1

1

1

B
Type 1 Map

Type 2 Map

Four-Variable Maps

Truth Table

Elec 326

3

Karnaugh Maps

The interpretation of a type 1 map is that the rows or
columns labeled with a variable correspond to region
of the map where that variable has value 1
...


1

Elec 326

1
2
3

1

1
4

01

1

5

01 1

5

13 9

11

3

7

11 3

7

15 11

10

Z A
0
B
0 0

Z A
B,C
0
00 0

Z A,B
C,D
00 01 11 10
00 0 4 12 8

2

6

10 2

6 14 10

4

Karnaugh Maps

2

Exercise: Plot the following expression on a Karnaugh map
...

This is due to the use of a Gray code (one in which adjacent
numbers differ in only one position) to label the edges of a type 2
map
...


Note that squares at opposite ends of the same row or
column also have this property (i
...
, their associated
numbers differ in exactly one position)
...
,2k rectangles all
of whose binary numbers agree in (k-2),(k-3),(k4),
...

Z

A
0

0

0

0
C

0
1

1

0

0

1

1

0

0

0

0

0

D

B

Z=
=
=
=
=
=

Elec 326

m5 + m7 + m13 + m15
A'•B•C'•D + A'•B•C•D + A•B•C'•D + A•B•C•D
(A'•C' + A'•C + A•C' + A•C) • (B•D)
(A'•(C' + C) + A•(C' + C)) • (B•D)
(A' + A) • (B•D)
B•D

8

Karnaugh Maps

4

Basic Karnaugh Map Groupings for Three-Variable
Maps
...

Z7

A

Z8

Z9

A

A

Z10

A

1
1

1
C

1

D

A

Z12

C

1

1

1

D

B
A

Elec 326

1

1

1

Z14

1

A
1

D

C

1

D

C

1

1
B

B

10

D

B
A

1

1

C
B

1

Z13

1
1

1

C

B

B
Z11

D

C

D
C

1

D
1

1
B

Karnaugh Maps

5

Z15

Z16

A

Z17

A

A

1

1

1

D

1

C

1

1

1

1

C

1

1

C

B

1

1

1

1

1

1

1

1

1

1
D

C

C

B

Elec 326

1

1

1
B

11

1

A
1

D

C

1

Z20

A
1

D

B

Z19

A
1

1

1

B

Z18

1

1

D

1

1

1

1

1

1

1

D

1
B

Karnaugh Maps

Rules for Grouping:
The number of squares in a grouping is 2i for some i such
that 1 ≤ i ≤ k
...


Resulting Product Terms:
If X is a variable that has value 0 in all of the squares in the
grouping, then the literal X' is in the product term
...

If X is a variable that has value 0 for some squares in the
grouping and value 1 for others, then neither X' nor X are
in the product term
...


Z

A
0

1

0

0

0
C

loop 1

Z

1

1

0

1

1

1

0

0

1

1

0

A

1

1

0

1

1

1

1

0

1

1

loop 2

1

1

C

0

1

D

0

1

B

D

B

Violates Rule 1

Violates Rule 2

Elec 326

13

Karnaugh Maps

In order to minimize the resulting logical expression,
the groupings should be selected as follows:
Identify those groupings that are maximal in the sense that
they are not contained in any other possible grouping
...

A distinguished 1-cell is a cell that is covered by only one prime
implicant
...


Use the fewest possible number of maximal groupings
needed to cover all of the squares marked with a 1
...
Non-minimal
Product Terms

#3

1

1

C

1

0

#4
D

Z

#2

1

A

#2

1

#1

1

1

1

1

1

1

1

0

1

C

0

0

D

1

0

0

0

#4

B

D
#1

B

b
...
Minimal
Grouping

a
...
Z = B•D+A•B'•C'+A'•B•C'+A'•C•D+A'•B'•D'
c
...
W3 = C'D+AC'+BC+A'B'D'
b
...

X

Y

A

1

1

1

1

0

1

1

0

1

0

0

0

0

1

0

0

0

B

1

1

0

1

A

0

1

1

D

0

0

1

0

0

1

D

0
1

C

C

B

X = A•B + A'•B'•D' + A'•B'•C + B•C•D'
Y = A'•C' + A•C•D' + A•B•C + B•C'•D'

Elec 326

16

Karnaugh Maps

8

Minimal Product-Of-Sums Expressions
Merging Adjacent Product Terms
...


Resulting Sum Terms:
If variable X has value 0 for all squares in the group, then
the literal X is in the sum term
...

If variable X has value 0 for some squares in the group and
value 1 for the others, then that variable does not appear in
the sum term
...


Elec 326

18

Karnaugh Maps

9

Examples:
Z B'+C+D

A

C

1

0

0

1

0

A+D'

0

1

1

0

0

1

1

1

1

1

0

D

A'+B+C'+D

B

Z = (A+D')•(B'+C+D)•(A'+B+C'+D)
Z1

Z2

A

A

1

1

1

1

0

1

1

0
C

0
1

1

0

0

0

0

0

0

1

1

1

0

0

0

0

1

0

1

1

1

0

0

1

D
C

B

D

B

Z1 = (A+B'+D)•(B+C+D')•(A+B+D')
Z2 = D'•(A+B')•(B'+C')
Elec 326

19

Karnaugh Maps

Comparison of Sum-of-Products and Product-ofSums Expressions
...

X

X

A
1

1

1

0

0

1

1

1

0

0

1

1

0

0

0

1

1

1

1

1

1

A

1

0

0

B
D
1

0

0

1

1

0

D

0
0

C

C

B

X = B•D' + A•C' + A•D' + B•C'

Y = (B' + D') • (A' + C')

Elec 326

21

Karnaugh Maps

Don't Care Entries
Assignment of Values to Don't Care Entries
...

ΣA,B,C(0,d1,d3,4,5) and ΠA,B,C(d1,2,d3,6,7)
ΣA,B,C(6,7,8,d10,d11,d12,d13,d14,d15)
ΠA,B,C(0,1,2,3,4,5,9,d10,d11,d12,d13,d14,d15)

Elec 326

23

Karnaugh Maps

Five- and Six-Variable Maps
Five-Variable Maps
...

Z

B

B

1

0

1

0

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

D

0

0

B' •C' • E'

0

0

0

0

1

0

0

0

C

E
B•E

C
A

Z = B'•C'•E'+B•E
Z

B

B

0

1

1

0

0

1

1

0
D

0
1

1

0

0

1

1

0

1

1

1

0

0

1

1

1

1

1

0

0

0

0

1

1

C

E

C
A

A'B'D + CE + ABD + BD'E'

Elec 326

26

Karnaugh Maps

13

Z

B

B

0

1

0

0

0

0

0

0

1

1

1

0

1

1

1

0

1

1

1

0

1

1

1

0

D

0

0

1

0

0

0

1

1

C

E

C
A

Z = (B+C)•(B+E•(A'+D+E)•(A+C+E)
Z

B

B

0

1

0

d

d

d

d

0
D

d
d

1

0

0

0

1

0

d

d

1

1

d

d

d

d

d

d

1

1

1

1

1

1

C

E

C
A

Z = B•C + D

Elec 326

27

Karnaugh Maps

Timing Hazards
Exercise: Draw a timing diagram for the following
circuit assuming an equal unit delay for each gate
...

The spike is due to the gate delay and the fact that not
every path from on input to the output is the same length
...

A
Z
0

S

1

1

0

0

0

1

1

B

The hazard occurs when the output is 1 before and after the
transition
...
The spike occurs if it is possible for
the first to turn off before the second turns on
...
The hazard occurs in making a transition
from one square to the other
...
On the Karnaugh map
this is a loop covering the two adjacent one squares
...
Its only purpose is
to prevent the hazard
...

It is not possible to get a 1 spike from a 2-level AND-OR
network by changing only one variable
...
If the signal Z
above is not used during the transition, then we don't
care if it has a spike
...

Therefore, if we can make sure that any spikes occur
at some other time, they will not be a problem

---