How to Simplify Digital Functions Using the Quine-McCluskey Algorithm

Instructor: Meghalee Goswami

Meghalee has a masters of computer science and communication engineering.

This lesson explains how the Quine-McCluskey algorithm is used to simplify logic functions with 3 or more variables. It also discusses a distinguishing factor in this algorithm that can be automated. There are a lot of websites that use it to simplify logic functions.

The Quine-McCluskey Algorithm

The Quine-McCluskey algorithm uses a given function , which contains the sum of minterms or the sum of the products (SOP) to determine a simplified and reduced equivalent. If the expression does not have minterms then we need to evaluate the corresponding minterms before proceeding further. Minterms can be classified into two categories : prime implicants and essential prime implicants.

Prime Implicant

Prime implicants exist where a minterm cannot be grouped or ordered with another minterm for a possible reduction.

Essential Prime Implicant

With essential prime implicants, no minterm can be skipped according to the laws of simplification. For this reason, if a minterm has only one prime implicant, then no further reduction of that minterm is possible.

Lets consider the function : x+yz'

In this expression, x cannot be reduced further with the help of the next minterm yz' and vice versa. Therefore both the minterms of this expression are essential prime implicants.

Simplification Process

The following steps must be taken in the process of simplification:

  1. The first step would be to group the minterms according to the number of complemented variables. If one minterm has lesser complemented variables than the other, then it has to be placed first.
  2. For every complemented variable, we will use 1. For every non-complemented variable, we will use 0.
  3. We then group pairs together that are one bit apart, making n-1 pairs.
  4. The process of reduction continues until there are only essential prime implicants left.

Lets consider the following function to demonstrate this: xyz' + xy'z + xy'z' +x'yz + x'y'z

Figure 1: Explanation of Quine-McCluskey
Figure 1: Explanation of Quine-McCluskey

To simplify this function as shown in Figure 1, perform the following steps:

  1. Group the minterms according to the number of complemented variables : The function already follows this rule
  2. For every complemented variable we will use 1, and 0 for a variable that is not complemented : Column 3 demonstrates this rule.
  3. Group pairs together that are one bit apart : In this step we find out the minterms that are one bit apart.
  4. The first example is (1,4) which is minterm at row 1 and minterm at row 4. The result values are 110 and 100. Only the digit in between differs so we put an _ in column 4 in place of the digit that differs. Please note that we made n-1=4 pairs.

Now we write the prime implicants in the first column and the minterms in the exact order in the first row as shown in Figure 2.

Figure 2: Explanation of Reduction
Fig 2: Explanation of reduction

In Figure 2, we take the last column of each row from Figure 1 and write in the corresponding reduced minterm. Please note that in this step we omit the variables that fall under the underscores (_). For the first row of Figure 1, we have xyz' which results in 1_0, which means the corresponding reduced minterm will be xz'.

To unlock this lesson you must be a Study.com Member.
Create your account

Register to view this lesson

Are you a student or a teacher?

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back
What teachers are saying about Study.com
Try it risk-free for 30 days

Earning College Credit

Did you know… We have over 200 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it risk-free for 30 days!
Create an account
Support