Quine-McCluskey Method

Quine-McCluskey Method

Introduction

Using K-maps to find the minimised two-level form of a function is difficult for functions of more than 4 variables and nearly impossible for functions of more than 6 variables because it's hard to visualize and spot patterns in multidimensional space.
An alternative to using K-maps is the Quine-McCluskey algorithm. The Quine-McCluskey algorithm provides a systematic approach for finding the prime implicants and selecting a minimum cover. Because the algorithm is tedious it is better suited to machine implementation.

Quine-McCluskey Algorithm

With both the K-map method and Quine-McCluskey algorithm you are trying to find a minimum number of terms that cover all of the minterms in the function. For example, the two minterms AB'CD' and ABCD' are covered by the term ACD'
Both the K-map method and Quine-McCluskey algorithm go through the following 3 phases:
Step 1: find prime implicants.
Step 2: find essential prime implicants
Step 3: select a minimal set of remaining prime implicants that covers the on-set of the function
Example 1. Use the Quine-McCluskey algorithm to find the minimal sum-of-products form of the following function:

F = (0,9,13,15) d(7,12)

The following image shows the first step of the Quine-McCluskey algorithm where we identify prime implicants.

Figure 1. Using the Quine-McCluskey algorithm to find prime implicants.

Column 1 shows the indices of the minterms in the given function. Indices for don't-care values are marked with a (d). We use the don't-care values here while identifying prime implicants, but won't use them later when searching for a minimal subset of prime implicants that covers the minterms of the function.

Column 2 shows the minterm value written as a binary number. For example, 1001 = AB'C'D

Column 3 shows minterms in binary form grouped in ascending order by the number of 1's in the binary form of the minterm. The first group has 0 1's. The second group has 2 1's, etc.

Column 4 has an entry for every pair of terms that can be combined in the previous column. For example, 1001 can be combined with 1101 which results in 1-01. Or in Boolean algebra:

AB'C'D + ABC'D =
AC'D(B' + B) =
AC'D(1)
AC'D

Whenever a term is combined to create a smaller term we put a check beside the terms that were combined. This is so we can identify prime implicants at the end. The prime implicants are all terms that don't have a check. (Prime implicants are circles in the above image.)

Here we stop at column 4 because there are no terms in column 4 that can be combined.

The next step is to identify essential prime implicants and select a minimal subset of prime implicants that covers the on-set of the function. To find essential prime implicants first create a table. The columns are labeled with the minterms in the on-set of the function. (Notice, don't care values are not included.) The rows are labeled with the prime implicants found above. For each prime impilcant mark an X at the intersection of the row for the prime implicant and the column for all minterms covered by the prime implicant. Are there any columns with only 1 X? If so, the prime implicant that covers the minterm for the column is an essential prime implicant.

Figure 2. Selecting essential prime implicants with the Quine-McCluskey algorithm.

Essential prime implicants must be included in the final minimized form of the function:

F = A'B'C'D' + AC'D + ???

The final step is to select a minimal subset of remaining prime implicants that cover the remaining uncovered minterms in the on-set. In our example we could select either: -111 (BCD) or 11-1 (ABD). If we select BCD, the final answer is:

F = A'B'C'D' + AC'D + BCD