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

6.10 QUINE–McCLUSKEY MINIMIZATION

The Karnaugh map method is used to minimize logic functions of up to five variables. For logic functions with more than five variables, the Karnaugh map method becomes impractical. The Karnaugh method uses maps, which become very difficult to design as the number of input variables increases. Pattern recognition of adjacent cells becomes tedious or impossible. An alternative method is the Quine–McCluskey method. Quine–McCluskey is based on the same basic principles of the Karnaugh map method. It uses an adjacency theorem to reduce minterms for which the logic function is equal to 1. Unlike a Karnaugh map, the Quine–McCluskey method uses tables, which provide simple pattern recognitions.

Figure 6.13 Karnaugh Maps with don't-Care States for Both SOP and POS Design

Quine–McCluskey method is a tabular method that has an advantage over Karnaugh maps when a large number of inputs are present. With more inputs, pattern recognition in Karnaugh maps can be tedious or sometimes even impossible. The Quine–McCluskey method does not require pattern recognition. It consists of two steps: (1) finding all prime implicants of the function, and (2) selecting a minimal set of prime implicants of the function. An implicant is the product of some of the variables (in complemented or uncomplemented form) for which the function is equal to 1. Minterms for which the function ...