Introduction to Digital Systems: Modeling, Synthesis, and Simulation Using VHDL

6.3 KARNAUGH MAPS

Earlier it was explained that the key to finding the minimum-cost expression for a given logic function is to reduce the number of product (or sum) terms needed in the expression by applying Boolean algebra theorems. Karnaugh mapping is a method used to simplify a truth table using sum of products or product of sums along with simultaneous optimization of the output function. Karnaugh maps are the graphical equivalent of a truth table. In other words, Karnaugh maps are an easy way of designing and optimizing a circuit from a truth table. Consider the function f in Figure 6.1.

Figure 6.1 Truth Table Sample

The canonical (not reduced) SOP expression for the logic function f consists of the minterms m₀, m₂, m₄, m₅, and m₆, and can be written

Using Boolean algebraic manipulations, the logic function f can be simplified in the following steps:

The minimum expression for the logic function f can be written

The expression above can be checked by comparing it with the truth table. The expression has the product term because f = 1 when z = 0, regardless of the values ...