Eng262 lesson 7a: karnaugh maps and function minimizations

ENG262 Lesson 8: Karnaugh Maps and Function Minimization Learning Outcomes:
On successful completion of this topic you should be able to:
1. Translate a truth table into an algebraic expression.
2. Sketch a Karnaugh Map for a given logic function.
3. Minimize a logic function using a Karnaugh Map.
Translating Truth Tables into Algebraic Expressions
To generate the algebraic expression for the function F, we use the properties of AND and OR operators. Recal that the AND operation AB wil equal 1 only if A = 1 and
B = 1. Similarly, A’B wil equal 1 only if both A = 0 (so that A’ = 1) and B = 1. Fol owing this reasoning, each line of the truth table that has a function value of 1 can be represented by a corresponding AND term, as shown in the fol owing table.
F1 = A’B’
F2 = A’B
F3 = AB’
We can now reconstruct the function F by simply ORing the product terms F1, F2 and F3: that is, F = 1 if F1 = 1 or F2 = 1 or F3 = 1. This operation is shown in the fol owing
In algebraic notation, this operation is written as Notice that this procedure automatical y generates the function in a sum-of-products form.
It is also possible to generate the function in product-of-sums form. In this procedure,
terms are grouped that correspond to the zero entries for the function. This procedure tends to be a little less intuitive than the sum-of-products procedure.
The Minimization Problem
Usual y, the algebraic expression that is taken directly from the truth table is not in a minimum form. A minimum form for the example given by equation (1) can be obtained using the rules of Boolean algebra: F = A' B ' + A ' B + AB ' = A' B ' + A'B + A' B ' + AB '= A'(B ' + B) + ( A' + A) B ' Minimization using algebraic rules raises two issues: How do you know the tricks to use, such as adding the redundant term in equation (2)? How do you know when the minimum expression has been achieved? Answers to both questions are possible by introducing graphical minimization techniques thatmake it easier to see the tricks and to see that no further reductions are possible.
Karnaugh Maps
The Karnaugh Map is a re-structured version of a truth table. The cells in the Map are
arranged so that adjacent cells differ by the value of only one of the variables. The layout for a 2-variable system is shown in Figure 1.
Notice that the cells are arranged so that cells in adjacent horizontal or vertical locations differ by the value of only a single variable. For example, the two cells in the bottom row only differ in the value of B (0 in the left cell and 1 in the right cell).
The entries of this Map are fil ed in by the truth table entries of the function under study. For example, the entries for the function given in equation (1) are shown in Figure 2.
To minimize this function, we group adjacent cells that have “1” entries. For example, the two cells in the top row can be grouped, as shown in Figure 3. This group includes cells thatare 1’s when A = 0, irrespective of the value of B. This corresponds to the function Similarly, we can group the adjacent terms in the first column, as shown in Figure 4. This group includes cells that are 1’s when B = 0, irrespective of the value of A. This corresponds These two groupings cover al cells that are 1’s. Hence we can write the function as This is the same expression that was obtained in the algebraic minimization carried out in equation (2). Notice that in forming the groups for A’ and B’, the cell A’B’ appears in each group. This corresponds to adding the extra term in equation (2). But while this operation is not immediately obvious from looking at the algebraic expression, it is much easier to spotin the Karnaugh Map.
Three-Variable Maps
The template for a three-variable Karnaugh Map is shown in Figure 5.
Notice that adjacent cells in the horizontal direction differ by only variable. This also applies to the cells that wrap-around at the left and right edges of the map. For example, the bottom left hand cell differs from the bottom right hand cell in only the value for B (B = 0 in the left hand cell and B = 1 in the right hand cell).
Use a Karnaugh Map to minimize the function F = A’B’C + A’BC + A’BC’ + AB’C This function is entered into the map as shown in Figure 6.
Notice that it is only necessary to enter the “1” values into the map. We can group three pairs, as shown in Figure 7.
However, the two cells of the grouping A’C also appear in other groups. Hence adding A’C to the final function is unnecessary (and is clearly non-minimal). Hence, the final minimum form is Higher order groupings are possible: a grouping of 2 cells wil eliminate one variable from the group; a grouping of 4 cells wil eliminate two variables from the group. Use a Karnaugh Map to minimize the function F = A’B’C + A’BC + A’BC’ + AB’C + ABC The Karnaugh Map, with optimal groupings, is shown in Figure 8.
In this example, the group of 4 represents cells that are 1’s as long as C = 1, irrespective of the value for A and the value for B. The minimum sum-of-products expression is given by Four Variable Maps
The template for a four variable Karnaugh Map is shown in Figure 9.
The Karnaugh Map for a given function is shown in Figure 10.
Figure 10
The optimal grouping is shown in Figure 11.
Figure 11
The 4-group C’D and the 2-group A’B’D’ are clear cut. However, the cell AB’C’D’ can form a 2-group in one of two ways – it can combine with AB’C’D to form AB’C’; or it can combine with A’B’C’D’ to form B’C’D’. Hence there are two equal y valid minimal sum-of-product Even with the aid of a Karnaugh Map, it is stil possible to miss the best solution unless care is taken in identifying the best groupings.
 Karnaugh Maps for 5 and 6 variables are possible, but they are difficult to work with.
 The preceding minimizations are only valid for obtaining the minimal sum-of
products form. For a given function, the true minimal expression, in terms of
minimum number of gates and inputs, may be a product-of-sum expression, or it may be a hybrid (neither sum-of-products nor product-of-sums) expression. However, true minimal expressions may not be particularly useful. For example, it may not be possible to build a hybrid-form directly from NAND and/or NOR gates, in which case extra gates may be required in order to achieve a practical design.
Lesson prepared by: Greg Crebbin (2010)Adapted by: Sujeewa Hettiwatte (2013)

Source: http://cram.at/units/ENG262/Lessons/ENG262_2013_08.pdf