Quine McKluskey Procedure
for Circuit Minimization

The practical use of algebraic manipulation, Venn diagrams or Karnaugh maps for minimization of Boolean expressions is limited to problems with a few variables.  The Quine-McKluskey procedure for minimization can be implemented as a computer algorithm and is applicable to expressions with any number of variables.

Example: Given the boolean expression

F(p,q,r,s,t)=m(0,1,3, 4,6,11,14,15,16,18,24,27,28,31)

minimize using the Quine-McKluskey procedure.  In this example there are 5 variables p, q, r, s and t which give us 32 possible minterms (0 - 31).

Step 1: Separate the minterms into groups based on the number of 1's in their  binary representations.

Step 2: Compare neighboring groups and replace pairs of terms that have exactly one bit different. These terms are said to be adjacent.  We can replace any two adjacent terms with a single term that contains a dash at the location of the unmatched bit.  Be sure to mark the minterms that are used to create common terms so that they can be removed from the list.

Step 3: Repeat the search until no new adjacent terms are found.  Two terms that already contain dashes are considered to be adjacent only if all dash positions match and all but one literal position contains the same value.

Step 4: Remove duplicates and list all unique surviving terms. Indicate which of the original minterms are covered by the surviving terms.  These are called the implicants since they imply the existence of minterms in the original expression.

More than one minterm is covered by each implicant and some minterms are covered by more than one implicant.  We need to find the smallest number of implicants that cover all minterms.  These will be called the prime implicants.

Step 5: Notice that the prime implicants VI, IX, X and XI shown above are the only ones that cover minterms 18, 14, 28 and 31 respectively.  These implicants must be included in our selected list.  They are called essential prime implicants.

Step 6: Next we must select the minimum number of remaining implicants so as to cover all minterms. This is not an easy problem, in general.  Can you find a better (i.e. smaller) set of prime implicants that cover all the minterms in this example?

Step 7: Finally we use the selected set of prime implicants to generate a simplified Boolean expression.

Recall that in its original form F( ) was composed of 14 five-variable minterms.

Homework: Use the Quine-McKluskey procedure to find a minimal representation of the following Boolean expression:

F(w,x,y,z) = m(0,1,2,5,6,9,11,14,15)

This course material has been converted to electronic format for use at
Murray State University, and the
Dept. of Computer Science and Information Systems

Use of this material for educational purposes only is governed by
the definition of Fair Use (Section 107) of the U.S. Copyright Act.
Course material is the property of  R. A. Pilgrim