Study Pages 221-235 in Book DDPP!

Karnaugh Maps

2/4/09

Study pages 221-235 in book DDPP!

2-variable Karnaugh Map (containing minterm numbers)

F(X,Y) =
0 / 2
1 / 3 / Y
X

3-variable Karnaugh Map (containing minterm numbers)

X / F(X,Y,Z) =
0 / 2 / 6 / 4
1 / 3 / 7 / 5 / Z
Y

4-variable Karnaugh Map (containing minterm numbers)

W / F(W,X,Y,Z) =
0 / 4 / 12 / 8
1 / 5 / 13 / 9 / Z
Y / 3 / 7 / 15 / 11
2 / 6 / 14 / 10
X

Example:

m / X / Y / Z / F / F(X,Y,Z) = (6,7) = (0,1,2,3,4,5)
0 / 0 / 0 / 0 / 0
1 / 0 / 0 / 1 / 0
2 / 0 / 1 / 0 / 0
3 / 0 / 1 / 1 / 0
4 / 1 / 0 / 0 / 0
5 / 1 / 0 / 1 / 0
6 / 1 / 1 / 0 / 1
7 / 1 / 1 / 1 / 1
X /
0 / 0 / 1 / 0
0 / 0 / 1 / 0 / Z
Y

EXAMPLE 2: F(X,Y,Z) = (2,3,6,7) = (0,1,4,5)

/ X /
0 / 1 / 1 / 0
0 / 1 / 1 / 0 / Z
Y
X /
1 / 0 / 0 / 1
1 / 0 / 0 / 1 / Z
Y

EXAMPLE 3: F(X,Y,Z) = (1,3,5,7) = (0,2,4,5)

X /
0 / 0 / 0 / 0
1 / 1 / 1 / 1 / Z
Y
X /
1 / 1 / 1 / 1
0 / 0 / 0 / 0 / Z
Y

EXAMPLE 4:

X /
0 / 0 / 1 / 0
0 / 0 / 1 / 1 / Z
Y
X /
1 / 1 / 0 / 1
1 / 1 / 0 / 0 / Z
Y

4-Variable map examples

W / F(W,X,Y,Z) / W / F(W,X,Y,Z)
0 / 4 / 12 / 8 / 1 / 0 / 0 / 0
1 / 5 / 13 / 9 / Z / 0 / 1 / 1 / 0 / Z
Y / 3 / 7 / 15 / 11 / Y / 0 / 1 / 1 / 0
2 / 6 / 14 / 10 / 0 / 0 / 0 / 1
X / X

F(W,X,Y,Z) = (0,5,7,10,13,15)

W / F(W,X,Y,Z) / W / F(W,X,Y,Z)
0 / 0 / 0 / 0 / 0 / 0 / 0 / 1
1 / 1 / 1 / 1 / Z / 0 / 0 / 0 / 1 / Z
Y / 0 / 0 / 0 / 0 / Y / 0 / 0 / 0 / 1
0 / 0 / 0 / 0 / 0 / 0 / 0 / 1
X / X

F(W,X,Y,Z) = (1,5,9,13)F(W,X,Y,Z) = (8,9,10,11)

W / F(W,X,Y,Z) / W / F(W,X,Y,Z)
0 / 1 / 1 / 0 / 0 / 0 / 0 / 0
0 / 0 / 0 / 0 / Z / 1 / 0 / 0 / 1 / Z
Y / 0 / 0 / 0 / 0 / Y / 1 / 0 / 0 / 1
0 / 1 / 1 / 0 / 0 / 0 / 0 / 0
X / X
W / F(W,X,Y,Z) / W / F(W,X,Y,Z)
0 / 0 / 0 / 0 / 1 / 0 / 0 / 1
1 / 1 / 1 / 1 / Z / 1 / 0 / 0 / 1 / Z
Y / 1 / 1 / 1 / 1 / Y / 1 / 0 / 0 / 1
0 / 0 / 0 / 0 / 1 / 0 / 0 / 1
X / X
W / F(W,X,Y,Z) / W / F(W,X,Y,Z)
1 / 0 / 0 / 1 / 1 / 0 / 0 / 1
0 / 0 / 0 / 0 / Z / 0 / 0 / 0 / 0 / Z
Y / 0 / 0 / 0 / 0 / Y / 1 / 1 / 1 / 1
1 / 0 / 0 / 1 / 1 / 0 / 0 / 1
X / X
W / F(W,X,Y,Z) / W / F(W,X,Y,Z)
0 / 0 / 1 / 0 / 1 / 0 / 0 / 1
1 / 1 / 1 / 0 / Z / 0 / 0 / 1 / 1 / Z
Y / 0 / 1 / 1 / 1 / Y / 0 / 0 / 1 / 1
0 / 1 / 0 / 0 / 1 / 1 / 1 / 1
X / X

Prime implicates and distinguished 1-cells.

W / G(W,X,Y,Z) / W / G(W,X,Y,Z)
1 / 1 / 0 / 0 / 1 / 1 / 0 / 0
0 / 1 / 1 / 0 / Z / 0 / 1 / 1 / 0 / Z
Y / 0 / 0 / 1 / 1 / Y / 0 / 0 / 1 / 1
1 / 0 / 0 / 1 / 1 / 0 / 0 / 1
X / X

How many prime implicants? ____

How many essential prime implicants? ____

W / G(W,X,Y,Z) / W / F(W,X,Y,Z)
1 / 1 / 0 / 0 / 1 / 1 / 0 / 0
0 / 1 / 1 / 0 / Z / 0 / 1 / 1 / 0 / Z
Y / 0 / 0 / 1 / 1 / Y / 1 / 1 / 1 / 1
1 / 0 / 0 / 1 / 1 / 0 / 0 / 1
X / X
W / F(W,X,Y,Z) / W / F(W,X,Y,Z)
0 / 1 / 0 / 0 / 0 / 1 / 1 / 0
0 / 1 / 1 / 0 / Z / 0 / 1 / 0 / 1 / Z
Y / 0 / 0 / 1 / 1 / Y / 1 / 1 / 0 / 0
0 / 0 / 0 / 0 / 1 / 1 / 1 / 0
X / X

Problem 4.13

b) / W / F(W,X,Y,Z) / c) / X / F(X,Y,Z)
0 / 1 / 0 / 0 / 0 / 1 / 1 / 0
1 / 1 / 0 / 1 / Z / 0 / 0 / 1 / 0 / Z
Y / 0 / 1 / 1 / 0 / Y
0 / 1 / 1 / 0
X

(b) F(W,X,Y,Z) = (1,4,5,6,7,9,14,15) – Enter 1’s in specified cells.

(c) F(X,Y,Z) = (0,1,3,4,5) – Enter 0’s in specified cells.

Problem 4.13

d) / W / F(W,X,Y,Z) / e) / A / F(A,B,C,D)
1 / 0 / 1 / 1 / 1 / 1 / 1 / 1
0 / 1 / 0 / 0 / Z / 0 / 1 / 0 / 0 /

D

Y / 0 / 1 / 1 / 0 /

C

/ 1 / 0 / 0 / 1
1 / 0 / 0 / 1 / 1 / 1 / 1 / 1
X / B

(d) F(W,X,Y,Z) = (0,2,5,7,8,10,13,15)

(e) F(A,B,C,D) = (1,7,9,13,15)

f) / A / F(A,B,C,D) / f) / A / F(A,B,C,D)
0 / 1 / 1 / 0 / 0 / 1 / 1 / 0
1 / 1 / 0 / 0 / D / 1 / 1 / 0 / 0 /

D

C / 0 / 0 / 1 / 0 /

C

/ 0 / 0 / 1 / 0
0 / 1 / 1 / 0 / 0 / 1 / 1 / 0
B / B

(f) F(A,B,C,D) = (1,4,5,7,12,14,15) = (0,2,3,7,8,9,10,11,13)

Example: (a). Obtain the equation for the simplest two-level AND-OR gate implementation of a 4-bit prime number detector. i.e. The output is 1 for minterms 1, 2, 3, 5, 7, 11, and 13. Let the input bits be W, X, Y, and Z. Assume the complement of each input bit is available.

(b). Convert the equation in (a) to the equations required for a two-levle NAND gate only implementation.

(c). Obtain the equation for the simplest two-level OR-AND implementation.

(d). Convert the equation in (c) to the equation for a NOR only implementation.

W / F(W,X,Y,Z) / W / F(W,X,Y,Z)
0 / 0 / 0 / 0 / / 0 / 0 / 0 / 0
1 / 1 / 1 / 0 / Z / 1 / 1 / 1 / 0 / Z

Y / 1 / 1 / 0 / 1 / Y / 1 / 1 / 0 / 1
1 / 0 / 0 / 0 / 1 / 0 / 0 / 0
X / X

(a)

(b)

(c)

(d)

Other examples

1. Plot the function on the Karnaugh map shown below.

W / F2
1 / 1 / 1
1 / 1 / Z
Y / 1 / 1
1 / 1 / 1
X
Map for problems 1 and 2.

1. Write the simplest possible expression for the function F2.

1. On Map (a), circle all prime implicants for the function F3. How many are there? 6
2. On Map (b), circle all essential prime implicants for the function F3. How many are there? 2

/ W / F3 / W / F3
0 / 1 / 1 / 1 / 0 / 1 / 1 / 1
0 / 1 / 0 / 0 / Z / 0 / 1 / 0 / 0 / Z
Y / 0 / 1 / 1 / 1 / Y / 0 / 1 / 1 / 1
0 / 0 / 1 / 1 / 0 / 0 / 1 / 1
X / X

Map (a)Map (b)

Maps for problems 3, and 4. Map (a). Circle all prime implicants. Map (b) Circle all essential prime implicants.

1. Write the simplest sum-of-product equation for F4.

1. Rewrite the equation in 11 to implement F4 using only NAND gates.

1. Write the simplest product-of-sums equation for F4.

1. Rewrite the equation in problem 13 to implement F4 using only NOR gates.

W / F4 / W / F4 / W / F4
0 / 0 / d / 1 / 0 / 0 / d / 1 / 0 / 0 / d / 1
/ 1 / 1 / d / 0 / Z / 1 / 1 / d / 0 / Z / 1 / 1 / d / 0 / Z
Y / 1 / 0 / d / d / Y / 1 / 0 / d / d / Y / 1 / 0 / d / d
1 / 0 / d / d / 1 / 0 / d / d / 1 / 0 / d / d
X / X / X

Three copies of the Map used in problem 5-8.

Homework: Due Wednesday February 9, 2009 Use the map on the next page.

1. (a). Obtain the equations for the simplest two-level AND-OR gate implementation of a 4-bit Fibonacii number detector. The Fibonacii numbers less than 16 are: 1, 2, 3, 5, 8 and 13. Let the input bits be W, X, Y, and Z. Assume the complement of each input bit is available.

(b). Convert the equation in (a) to the equations required for a two-levle NAND gate only implementation.

(c). Obtain the equation for the simplest two-level OR-AND implementation.

(d). Convert the equation in (c) to the equation for a NOR only implementation.

1. (a). Obtain the equations for the simplest two-level AND-OR gate implementation of a 4-bit input circuit that produces an output of 1 when the binary value of the input has an integer square root. Let the input bits be W, X, Y, and Z. Assume the complement of each input bit is available.

(b). Convert the equation in (a) to the equations required for a two-levle NAND gate only implementation.

(c). Obtain the equation for the simplest two-level OR-AND implementation.

(d). Convert the equation in (c) to the equation for a NOR only implementation.

1. (a). Obtain the equations for the simplest two-level AND-OR gate implementation of a 4-bit input circuit that produces an output of 1 when the binary value of the input is any prime number or any Fibonacii number or both. Let the input bits be W, X, Y, and Z. Assume the complement of each input bit is available.

(b). Convert the equation in (a) to the equations required for a two-levle NAND gate only implementation.

(c). Obtain the equation for the simplest two-level OR-AND implementation.

(d). Convert the equation in (c) to the equation for a NOR only implementation.

1. (a). Obtain the equations for the simplest two-level AND-OR gate implementation of a 4-bit input circuit that produces an output of 1 when the binary value of the input is any number with an integer square root number or any Fibonacii number or both[1]. Let the input bits be W, X, Y, and Z. Assume the complement of each input bit is available.

(b). Convert the equation in (a) to the equations required for a two-levle NAND gate only implementation.

(c). Obtain the equation for the simplest two-level OR-AND implementation.

(d). Convert the equation in (c) to the equation for a NOR only implementation.

W / F(W,X,Y,Z) / W / F(W,X,Y,Z)
0 / 4 / 12 / 8 / 0 / 4 / 12 / 8
1 / 5 / 13 / 9 / Z / 1 / 5 / 13 / 9 / Z
Y / 3 / 7 / 15 / 11 / Y / 3 / 7 / 15 / 11
2 / 6 / 14 / 10 / 2 / 6 / 14 / 10
X / X
W / F(W,X,Y,Z) / W / F(W,X,Y,Z)
0 / 4 / 12 / 8 / 0 / 4 / 12 / 8
1 / 5 / 13 / 9 / Z / 1 / 5 / 13 / 9 / Z
Y / 3 / 7 / 15 / 11 / Y / 3 / 7 / 15 / 11
2 / 6 / 14 / 10 / 2 / 6 / 14 / 10
X / X
W / F(W,X,Y,Z) / W / F(W,X,Y,Z)
0 / 4 / 12 / 8 / 0 / 4 / 12 / 8
1 / 5 / 13 / 9 / Z / 1 / 5 / 13 / 9 / Z
Y / 3 / 7 / 15 / 11 / Y / 3 / 7 / 15 / 11
2 / 6 / 14 / 10 / 2 / 6 / 14 / 10
X / X

1

[1] The map for 4 is the Karnaugh map for 1 ored with the Karnaugh map for 2.