Learn to Code via Tutorials on Repl.it!

← Back to all posts
(Python) Quine-McCluskey Algorithm
h
FellowHashbrown

(Python) Quine-McCluskey Algorithm

What is it?

The Quine-McCluskey Algorithm is an algorithm developed by Willard Quine in the late 1950s which was then improved upon by Edward McCluskey. The purpose of this algorithm is to take the results of a logical expression or a boolean algebraic expression and simplify it to it's simplest form.

Examples

  • (p ^ q ^ r) v (p ^ q ^ ~r) v (p ^ ~q ^ ~r) simplifies to p ^ (q v ~r)
  • a or (a and b) simplifies to a

Requirements

  • Basic Knowledge of Python
  • Power Sets
  • Recursion

Quine-McCluskey Algorithm

Now first, in order to best explain the Quine-McCluskey Algorithm, we are going to set up an example of a modified truth table that will show you the values that will be used for this example.

Grouping

Let's say we have a logical expression that evaluates per the function f(a, b, c, d) = Σ m(0, 4, 5, 7, 8, 11, 12, 15)
Now what this means is that whenever the binary equivalents of the variables make the decimal value equal to any of these values, the expression is evaluating to true:

abcdbitsdecimal
000000000
010001004
010101015
011101117
100010008
1011101111
1100110012
1111111115

Now we group the bits by however many 1's there are in the binary value. Don't worry about the used column just yet. I will explain that a few steps down:

# of 1'sdecimalabcdused
000000yes
140100yes
81000yes
250101yes
121100yes
370111yes
111011yes
4151111yes

Now, each of these values becomes a minterm. What a minterm is is just something that holds information about where a decimal value, or values, evaluates to true and what binary value it holds. When we combine them, we only want to look for where there is a 1-bit difference in 2 minterms. The reason we do that is because we want to remove the bits that don't matter. For example, let's say we compare minterms 0 and 4. We see that there is only a 1-bit difference between them at the b variable. To put this into logical expression terms, this is really what we're doing:

ExpressionAction
(~a ^ ~b ^ ~c ^ ~d) v (~a ^ b ^ ~c ^ ~d)Given
(~a ^ ~c ^ ~d) ^ (~b v b)Distributive Law
(~a ^ ~c ^ ~d) ^ tIdentity Law
(~a ^ ~c ^ ~d)Tautology

Now, as you can see above, we were able to take out a common factor of (~a ^ ~c ^ ~d) and leave behind (~b v b). In logic, (~b v b) will always be true no matter the value of b. This is the reason we want to compare minterms that have only a 1-bit difference.

Comparing

After we compare each term in adjacent groups with one another, we get another table that looks like the following table. There is an extra column to keep track of whether or not we used the minterm specified when we try combining the minterms. Since we used all of the minterms in the earlier table, we know that we don't have to remember to use any of them. If we don't use a minterm, then that minterm must be one of the prime implicants, which is what is used to generate the simplified logical expression:

groupsmintermabcdused
0-1m(0, 4)0-00yes
m(0, 8)-000yes
1-2m(4, 5)010-no
m(4, 12)-100yes
m(8, 12)1-00yes
2-3m(5, 7)01-1no
3-4m(7, 15)-111no
m(11, 15)1-11no

Now that we've compared every term in adjacent groups with one another, we can move onto doing the same step again which will get us with 2 values.

Comparing (continued)

groupsmintermabcdused
0-1-1-2m(0, 4, 8, 12)--00no
m(0, 8, 4, 12)--00no

Now as you can see, these 2 minterms are actually the same exact minterm. Just because the order of the numbers is different doesn't make them any different in reality. Therefore, the order of the values in the minterms doesn't actually matter when combining them. However, we must make sure that minterms m(0, 4), m(0, 8), m(4, 12), and m(8, 12) are used which helps us simplify the expression.

Prime Implicant Table

From the minterms that aren't used, we create a table with the variables on the left and the values from the function at the beginning on the right. When we go through the unused minterms, we put X's in the columns that the minterm holds values for. For example m(0, 4, 8, 12) should have X's in columns 0, 4, 8, and 12. That part is pretty self-explanatory.

abcd04578111215
~c~dXXXX
~ab~cXX
~abdXX
bcdXX
acdXX

Once we have this table setup, we want to look for what is known as the essential prime implicants which are prime implicants that need to exist in order for the expression to evaluate to true at the values specified earlier. To find these essential prime implicants, we look for the numbers who have only 1 X in the entire column. In our case, those columns are 0, 8, 11, and 12. Once we find those essential prime implicants, we go to the row that contains that X and add it to our final expression. When we cover an expression from a row, we then ignore all the X's that exist in the rest of the column.

For example, since we see that 0, 8, and 12 are essential values, we add (~c ^ ~d) to the final expression and cross out all the columns that minterm covers. The reason we have (~c ^ ~d) as the expression for this minterm is because the binary equivalent is --00. Wherever there is a hyphen (-), we do not put the variable that corresponds to it. Whenever there is a 0, we put a NOT (~) operator in front of the variable that corresponds to it. Whenever there is a 1, we just put the variable itself.

Expression: (~c ^ ~d)

abcd04578111215
~c~dXXXX
~ab~cXX
~abdXX
bcdXX
acdXX

Now we have another essential value at column 11 so we need to add (a ^ c ^ d) to the final expression.

Expression: (~c ^ ~d) v (a ^ c ^ d)

abcd04578111215
~c~dXXXX
~ab~cXX
~abdXX
bcdXX
acdXX

Since we do not have any more essential prime implicants, we want to find which implicant(s) will create the simplest expression and covers the most values. In this case, we can see that m(5, 7) will cover the other 2 remaining columns:

Expression: (~c ^ ~d) v (a ^ c ^ d) v (~a ^ b ^ d)

abcd04578111215
~c~dXXXX
~ab~cXX
~abdXX
bcdXX
acdXX

Final Expression

Now, since we have covered every value in the prime implicant chart, the final expression is (~c ^ ~d) v (a ^ c ^ d) v (~a ^ b ^ d). To put that into perspective, the original expression was (~a ^ ~b ^ ~c ^ ~d) v (~a ^ b ^ ~c ^ ~d) v (~a ^ b ^ ~c ^ d) v (~a ^ b ^ c ^ d) v (a ^ ~b ^ ~c ^ ~d) v (a ^ ~b ^ c ^ d) v (a ^ b ^ ~c ^ ~d) v (a ^ b ^ c ^ d).

Now let's move onto the code that actually does all of this.


Quine-McCluskey Algorithm in Code

For this algorithm, I've created only 2 classes that do all of the hard work:

  • The Minterm class, which holds the values and the binary value of the minterm
  • The QuineMcCluskey class which actually solves for the simplified form of an expression

Minterm class

The Minterm class is actually quite simple and doesn't hold much at all.
First we have the basic built-in methods:

The __str__ method is there to print out a specific minterm nicely in the form of m(0, 4, 8, 12) = --00

Next, we have some basic getters and setters that are used in the QuineMcCluskey portion of the code:

These are all both documented and pretty self-explanatory so I don't think I need to really go over them much.

This next (and last) portion of code for the Minterm class is used when we combine minterms in the algorithm:

Now as you can see, this code will return a new Minterm object if 2 minterms can be combined with one another. For example, what this does is take a minterm, say m(0, 4) = 0-00, and another minterm, say m(8, 12) = 1-00, and it will combine them together which then becomes m(0, 4, 8, 12) = --00.

That is really all that needs to be done for the Minterm class. Now let's move on to the QuineMcCluskey class which has all the meat of the code.

QuineMcCluskey class

The QuineMcCluskey class has the majority of the functions that create an initial group, combine minterms from adjacent groups, solves the function, and then generates the function into a human-readable format.

First, we need the basic constructor and a function that gets the binary equivalent of a decimal value:

The reason we need the __get_bits function is to be able to get the binary equivalent of the values where the function evaluates to true. For example, 4 is 0100, 5 is 0101, and 7 is 0111 in our example. It's important to pad extra 0's to the beginning of the value to match that of the number of variables in the expression.

The Initial Group

Before beginning the process of getting a list of unused prime implicants, we need to create an initial group where each binary value is matched up with how many 1's the binary value has.

In essence, what this function does is create the groups of minterms based off of how many 1's there are in the binary values for the decimal values. In the case of our function from earlier, the list would look something like this:

Prime Implicants

The next step is to get all the prime implicants that could possibly cover the expression. Like mentioned earlier in the explanation of the Quine-McCluskey Algorithm, to get the prime implicants, we must compare every term in one group with every term in an adjacent group. That is what the following code does:

The first if statement is pretty simple to comprehend. All it's checking for is whether or not a parameter is given, which is used in the recursive call, and setting it to be the initial group if it is not given.

The next if statement is the base case of this recursive function. If there is only one group left, then only the prime implicants in that function will cover the expression given.

The else statement handles everything else about getting prime implicants. First, we set up which minterms are unused in the comparisons. Then we want to only compare groups that are adjacent to one another. So if there are 5 groups, we only want to compare group 0 and 1, 1 and 2, 2 and 3, and 3 and 4. That's only 4 comparisons. Finally, we want to keep track of these new groups once we compare minterms.

When we loop through the comparisons, we only go from the first group to the second to last group or else we would have an IndexError when the group2 = groups[compare + 1] line of code came up. Once we loop through each minterm in each group, we try to combine the 2 minterms. If the 2 minterms cannot be combined, nothing will happen. However, if the 2 minterms can be combined, we want to keep track of using the minterm. Then, we make sure that the resulting minterm does not already exist in the new group that it belongs to.

Once we finish with comparing minterms, we want to keep track of which minterms were not used, if there were any. Then we make the recursive call which uses the new list of groups to compare every minterm again. Each time the __get_prime_implicants function is run, it returns a list of unused minterms. At the end of the recursive call, we get a total list of all the minterms which become the prime implicants.

Power Set

A power set, for those who don't understand what it is, is just a set of combinations of an existing set. For example, let's take a set to be {1, 2, 3}. The power set would be, {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

The reason we need to understand what a power set is is because after the essential prime implicants are found (which will be explained right after this section), the power set function will determine which remaining implicants cover the remainder of the expression and which set has the fewest implicants.

There are a few things that go on in this function. First, the initial power set is created from the prime implicants given through the parameter. After that is done, we then iterate over each set to determine if the set contains minterms that cover the rest of the expression. When the smallest subset is found, a variable, minSet, is updated to keep track of the smallest set so that at the end, the smallest set is returned which includes the final prime implicant, or implicants, that cover the rest of the expression.

Solving

Now let's get on to actually solving the expression.

The basic function of the solve function is to:

  1. Get a list of prime implicants

  2. Find the essential prime implicants

    The final if statement in this block of code will determine if all the essential prime implicants are the only prime implicants needed to cover the expression.

  3. Use the __power_set function to find the final prime implicant(s) that cover the expression and return it along with the essential prime implicants

    The purpose of reassigning the prime_implicants list is to remove all the prime implicants that are in that list that are also an essential prime implicant.

Getting the Expression

The final part of this algorithm is to actually return an expression that is readable to the human eye.

The basis of the get_function function is to find the prime implicants from the __solve function, iterate through the prime implicants and their binary values, and then create proper variables (with/without a NOT operator).
If there are no prime implicants received after the __solve function is called, then the expression is always false. Therefore, a 0 is returned. If there is only 1 prime implicant that has a binary value of all hyphens (-), then the expression will always be true no matter what.

Conclusion

To conclude this tutorial, I went over the basics of the Quine-McCluskey Algorithm, how to do it by hand, and how to adapt it to code. If you want to see the simplifier in action, you can go to https://repl.it/@FellowHashbrown/Quine-McCluskey-Python. I also wrote it in Java and Node.js

If you have any suggestions or see any issues, please let me know that way I can fix it!
If you find any bugs in adaptation of the Quine-McCluskey Algorithm, definitely let me know either by leaving a comment, pinging me in Repl.it's Discord Server, or pinging me in my own Discord Server

Voters
Atias
programmeruser
AndrewCofer
fifiinart
PaoloAmoroso
21natzil
eankeen
a5rocks
timmy_i_chen
katyadee
Comments
hotnewtop
a5rocks

Very cool! Time to bookmark this for later reading lol (it's way long)

FellowHashbrown

@a5rocks yeah sorry it's so long. but i had to explain the algorithm and then the code for it. can't do one without the other