CSCE 211: Digital Logic Design Chin-Tser Huang [email protected] University of South Carolina Chapter 3: The Karnaugh Map Karnaugh Map (K-map)

The algebraic simplification method in Ch. 2 is not systematical and does not tell us whether the result is a minimum We introduce the Karnaugh map, a graphical approach to finding suitable product terms for use in SOP expressions Particularly useful for problems of three or four variables 09/15/2015

3 Introduction to the K-map K-map consists of one square for each possible minterm in a function A two-variable map has 4 squares A three-variable map has 8 squares

A four-variable map has 16 squares 09/15/2015 4 Example: Two-Variable Kmap The upper right square correspond to A = 1, B = 0, i.e. minterm 2 of f(A, B) 09/15/2015

5 Example: Three-Variable Kmap Notice that the last two columns are not in numeric order! By organizing the map this way, the minterms in adjacent squares can be combined using the adjacency property P9a. ab + ab = a 09/15/2015 6

Example: Four-Variable Kmap 09/15/2015 7 Plot a Function on the Kmap Two ways to do it

Use minterms and plot each square corresponding to each minterm Put the function in SOP form and plot each of the product terms How to plot the function F = AB + AC + ABC ? 09/15/2015 8

Implicant An implicant of a function is a product term that can be used in an SOP expression for that function From the point of view of the map, an implicant is a rectangle of 1, 2, 4, 8, (any power of 2) 1s. That rectangle may not include any 0s.

09/15/2015 9 Implicant Example The implicants of F are Minterms ABCD ABCD ABCD ABCD ABCD ABCD

ABCD 09/15/2015 Groups of 2 ACD BCD ACD BCD ABC ABD Groups of 4 CD

10 Prime Implicant A prime implicant is an implicant that (from the point of view of the map) is not fully contained in any one other implicant. An essential prime implicant is a prime implicant that includes at least one 1 that is not included in any other prime implicant. 09/15/2015 11

Why Prime Implicants? The purpose of the map is to help us find minimum SOP expressions The only product terms we need to consider are prime implicants Essential prime implicants are the prime implicants that must be used in any minimum SOP expression

09/15/2015 12 Minimum SOP using K-map We will start with the most isolated 1s on the map The 1s with the fewest (or no) adjacent squares with 1 in it

09/15/2015 13 Map Method 1 1. 2. Find all essential prime implicants. Circle them on the map and mark the minterm(s) that make them essential with an asterisk (*). Do this by examining each 1 on the map that has not already been circled. It is usually quickest to

start with the most isolated 1s, that is, those that have the fewest adjacent squares with 1s in them. Find enough other prime implicants to cover the function. Do this using two criteria: a. Choose a prime implicant that covers as many new 1s (that is, those not already covered by a chosen prime implicant). b. Avoid leaving isolated uncovered 1s. 09/15/2015 14 Example 1

minimum f = yz + wyz + wxz 09/15/2015 all prime implicants 15 Example 2 Find the minimum SOP expression for xyz + xyz + xyz + xyz + xyz 09/15/2015 16

Example 2 x y + x y + x z 09/15/2015 x y + x y + y z 17 Example 3: Dont be greedy Bad

move! minimum G = ABC + ACD + ABC + ACD 09/15/2015 18 Dont Cares When there are dont cares: An implicant is a rectangle of 1, 2, 4, 8, 1s or Xs A prime implicant is a rectangle of 1, 2, 4, 8, 1s or Xs not included in any one larger rectangle. Thus, from the

point of view of finding prime implicants, Xs (dont cares) are treated as 1s. An essential prime implicant is a prime implicant that covers at least one 1 not covered by any other prime implicant (as always). Dont cares (Xs) do not make a prime implicant essential. 09/15/2015 19 Example 1 minimum

other p.i.s F = BD + ACD + ABC 09/15/2015 20 Example 2 g1 = xz + wyz + wyz + wxy g2 = xz + wyz + xyz + wxy 09/15/2015 g3 = xz + wyz + xyz + wyz

21 Example 3 g1 = cd + ab + bd + acd g2 = cd + ab + bd + abc 09/15/2015 g3 = cd + ab + ad + abc 22 Finding Minimum Product of

Sums Expression Finding a minimum product of sums expression requires no new theory. The following approach is the simplest: 1. 2. 3. Map the complement of the function. (If there is already a map for the function, replace all 0s by 1s, all 1s by 0s and leave Xs unchanged.) Find the minimum sum of products expression for the complement of the function (using the techniques of the

last two sections). Use DeMorgans theorem (P11) to complement that expression, producing a product of sums expression. 09/15/2015 23 Example f(a, b, c, d) = m(0, 1, 4, 5, 10, 11, 14) 09/15/2015 24

Example (cont.) f = ac + abc + acd f = ac + ac + abd f = ac + ac + bcd f = (a + c)(a + c)(a + b + d) f = (a + c)(a + c)(b + c + d) 09/15/2015 25