Karnaugh Maps

• Karnaugh Maps are covered in Chapter 5
• Karnaugh Maps are a way to simplify logic circuits using the Karnaugh Map method
• A Karnaugh Map is a graphical representation of the output for a given logic expression containing the same information as a truth table

Lesson outcomes

• After this lesson, students should be able to:
• Construct a Karnaugh Map based on the number of input variables (2-input, 3-input, and 4-input variables)
• Map values into the Karnaugh Map
• Simplify truth tables and Boolean expressions using Karnaugh Maps
• Understand the concept of "don't care" terms on Karnaugh Maps

Karnaugh Maps

• K-Maps contain a cell for each input combination
• A logic expression or truth table with n input variables has 2^n cells on the K-Map
• A 2-variable K-Map has 2^2 = 4 cells
• AB = 00 corresponds to cell A . B or cell 0
• AB = 01 corresponds to cell A . B or cell 1
• AB = 10 corresponds to cell A . B or cell 2
• AB = 11 corresponds to cell A . B or cell 3
• K-Map cells are labeled so that horizontally and vertically adjacent cells differ by only one variable
• For example: Cell A . B(0) and cell A . B(2) only differ in variable A
• Cell A . B(0) and cell A . B(1) only differ in variable B
• A 3 variable K-Map has 2^3 = 8 cells
• The labeling of a 3 variable K-Map is not in counting order
• The 3 variable cells are labeled as (0 1), (2 3), (6 7), and (4 5), so that horizontally and vertically adjacent cells only differ in one variable
• Cell (0) and cell (1) only have a difference in C
• Cell (2) and cell (3) only have a difference in C
• Cell (6) and cell (7) only have a difference in C
• Cell (4) and cell (5) only have a difference in B
• Cell (0) and cell (4) are considered adjacent as only A is different, the left and right sides of the map are connected and rolled into a cylinder
• A 4 variable K-Map has 2^4 = 16 cells
• The cells are labeled in the order of (0 1 3 2), (4 5 7 6), (12 13 15 14), and (8 9 11 10)
• Cell 0 is considered adjacent to cells 1, 4, 8, and 2
• Cell 1 is adjacent to cells 0, 3, 5, and 9

Simplification Using 2 Variable K-Map

• The following are the steps in simplifying a logic expression using a K-Map:
• Write a sum of product expression from the truth table
• Plot a 1 on the K-Map for each product term, or plot a 1 on the K-Map for each output, Y = 1
• Draw loops around adjacent cells containing two 1's on the K-Map, and the loops may overlap
• Repeat step 2 to 3
• Each loop produces a simplified product term, and the minimum product term for a 2 variable map is as follows:
• One cell group yields a 2 variable product term
• Two cell groups yields a 1 variable product term
• Four cell groups yield of 1 for the expression
• Logically OR the simplified product term
• The logic expression in the form of the sum of the product is Y = A . B + A . B + A . B, which can also be written as Y = ∑(1,2,3)
• There are 2 pairs of 1's that can be looped: cell (1 3) and cell (2 3), and each loop contains two 1's
• The loop for cell (1 3) produces a product term B, easily proven using Boolean algebra: A . B + A . B = A(B+B) = A
• The loop for cell (2 3) produces a product term A, easily proven using Boolean algebra: A . B + A . B = B(A+A) = B
• Logically OR the simplified product term, and the simplified Boolean expression becomes Y = A + B
• The loop for cell (0 1) produces A
• The loop for cell (0 2) produces B, and the simplified expression is Y = A + B, which is equivalent to A . B
• Cell 1 is not considered adjacent to cell 2, because both variables are different and not possible to form a loop
• The expression cannot be simplified, so the expression Y = A . B + A . B is equivalent to Y = A⊕B

Simplification Using 3 Variable K-Map

• A 3 variable K-Map allows loop containing two, four, and eight 1's
• A loop containing two 1's is illustrated by (0 1), (0 2), and (0 4)
• A loop containing four 1's is illustrated by (0 1 2 3), (2 3 6 7), (6 7 4 5), (0 1 4 5), (0 2 6 4), and (1 3 7 5)
• Here are the steps in simplifying a 3 variable K-Map:
• Draw a loop around adjacent cells containing four 1s, and a loop containing many 1's will produce a simpler product term, so find out of there are other possible loops containing four 1's, and the loops may overlap
• After finishing loops containing four 1's, draw loops containing two 1's
• Each loop produces a simplified product term, and the minimum product term for a 3 variable map is as follows:
• 1 cell group yields a 3 variable product term
• 2 cell groups yields a 2 variable product term
• 4 cell groups yields a 1 variable product term
• 8 cell groups yields of 1 for the expression
• Logically, OR the simplified product term
• For cell (01) This can be shown algebraically A.B.C = (A.B C + A.B .C = A. B(C + C)A.B
• The loop cell for (02) produces 0.2 This that can be algebraically is shown A.B.C = AB+ A.B .C AC (B+ B)+.
• The simplified expression is Y = A.B+A·C
• The loop for cell (2 6).
• The simplified expression is Y = A + B.C

Simplification Using 4 Variable K-Map

• A 4 variable K-Map allows loops containing two, four, eight, and sixteen 1's
• Loops containing two 1's are illustrated by (0 1), (0 4), (0 2), and (0 8)
• Loops containing four 1's are illustrated by (0 4 12 8), (0 1 3 2), (0 1 8 9), and (0 2 8 10)
• Loops containing eight 1's are illustrated by (0 1 3 2 4 5 7 6) and (0 1 3 2 8 9 11 10)
• Here are the steps in simplifying a 4 variable K-Map:
• Draw a loop around adjacent cells containing eight 1s, and a loop containing many 1's will produce a simpler product term, so find out if there are other possible loops containing eight 1's, and the loops may overlap
• After finishing loops containing eight 1's, draw loops containing four 1's
• Next, draw loops containing two 1's
• Each loop produces a simplified product term, and the minimum product term for a 4 variable map is as follows:
• 1 cell group yields a 4 variable product term
• 2 cell groups yield a 3 variable product term
• 4 cell groups yields a 2 variable product term
• 8 cell groups yields a 1 variable product term
• 16 cell groups yield of 1 for the expression
• Logically OR the simplified product term
• Loop (4576) produces A . B
• Loop (5 7 13 15) produces B . D
• Loop (3 7) produces A C . D
• The simplified expression Y = A . B + B . D + A C . D
• Connecting cell (1) and cell (9) forming a loop containing two 1's produces the term B . C . D
• Connecting cell (4 12) and cell (6 14) and forming a loop containing four 1's produces the term B.D
• Connecting cells at the four edges forming a loop containing four 1's (0 2 8 10) produces the term B . D

Simplifying Boolean Expressions Using Karnaugh Maps

• Simplifying Boolean expressions using K-Maps is simpler than simplifying Boolean algebra
• We can map each product term on the K-Map given the sum of product expression
• Product term A . B occupy cell (2 3); C occupies cell (1 3 7 5); A . B . C occupy Cell (6)
• The simplified expression is Y = B + C

Don't Care Term on Karnaugh Maps

• Some logic circuits are designed with certain input conditions for which there are no specific output levels, as the input conditions are never meant to occur
• Logic circuits have certain combinations of input with don't care output of 1 or 0
• Let's consider a logic circuit that detects an odd number from a BCD (Binary Coded Decimal) code where the code is represented from 0 to 9
• Six numbers that the code doesn't use: (1010, 1011, 1100, 1101, 1110, 1111)
• A BCD digit uses 4 bits
• Here are the logic levels to the BCD coded Karnaugh map:
• Given the logic levels to even, odd and not used numbers:
• Output (Y) = 1 for Odd Numbers = 1,3, 5,6 ,8
• Output (Y) = 0 for Even Numbers = 0,2,4,6,8
• Output (Y) = X for Not Used Numbers = 10,11,12,13,14,15
• X on the K-Map means that the cell can be a 1 or 0
• Cells containing 1's can be grouped together with cells containing X's to form a bigger loop
• The X's (11,13,15) is grouped around the adjacent cell's containing 1's
• Using the X's in a loop helps further simplify the expression
• The X's in cell (10, 12, 14) are ignored Simplified expression is Y = D

Questions test understanding of Karnaugh Maps (K-Maps) in digital logic circuit simplification, including adjacency, cell grouping, and interpreting simplified Boolean expressions.