(Python) Quine-McCluskey Algorithm

# (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:
| a | b | c | d | bits | decimal |
|:-:|:-:|:-:|:-:|:----:|:-------:|
| 0 | 0 | 0 | 0 | `0000` | 0 |
| 0 | 1 | 0 | 0 | `0100` | 4 |
| 0 | 1 | 0 | 1 | `0101` | 5 |
| 0 | 1 | 1 | 1 | `0111` | 7 |
| 1 | 0 | 0 | 0 | `1000` | 8 |
| 1 | 0 | 1 | 1 | `1011` | 11 |
| 1 | 1 | 0 | 0 | `1100` | 12 |
| 1 | 1 | 1 | 1 | `1111` | 15 |
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's | decimal | a | b | c | d | used |
|:--------:|:-------:|:-:|:-:|:-:|:-:|:----:|
| 0 | 0 | 0 | 0 | 0 | 0 | yes |
| 1 | 4 | 0 | 1 | 0 | 0 | yes |
| | 8 | 1 | 0 | 0 | 0 | yes |
| 2 | 5 | 0 | 1 | 0 | 1 | yes |
| | 12 | 1 | 1 | 0 | 0 | yes |
| 3 | 7 | 0 | 1 | 1 | 1 | yes |
| | 11 | 1 | 0 | 1 | 1 | yes |
| 4 | 15 | 1 | 1 | 1 | 1 | yes |
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:
| Expression | Action |
|:----------:|:------:|
| `(~a ^ ~b ^ ~c ^ ~d) v (~a ^ b ^ ~c ^ ~d)` | Given |
| `(~a ^ ~c ^ ~d) ^ (~b v b)` | Distributive Law |
| `(~a ^ ~c ^ ~d) ^ t` | Identity 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:
| groups | minterm | a | b | c | d | used |
|:------:|:-------:|:-:|:-:|:-:|:-:|:----:|
| 0-1 | m(0, 4) | 0 | - | 0 | 0 | yes |
| | m(0, 8) | - | 0 | 0 | 0 | yes |
| 1-2 | m(4, 5) | 0 | 1 | 0 | - | no |
| | m(4, 12) | - | 1 | 0 | 0 | yes |
| | m(8, 12) | 1 | - | 0 | 0 | yes |
| 2-3 | m(5, 7) | 0 | 1 | - | 1 | no |
| 3-4 | m(7, 15) | - | 1 | 1 | 1 | no |
| | m(11, 15) | 1 | - | 1 | 1 | no |
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)
| groups | minterm | a | b | c | d | used |
|:------:|:-------:|:-:|:-:|:-:|:-:|:----:|
| 0-1-1-2 | m(0, 4, 8, 12) | - | - | 0 | 0 | no |
| | m(0, 8, 4, 12) | - | - | 0 | 0 | no |
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.
| a | b | c | d | 0 | 4 | 5 | 7 | 8 | 11 | 12 | 15 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:--:|:--:|:--:|
| | | ~c| ~d| X | X | | | X | | X | |
| ~a| b | ~c| | | X | X | | | | | |
| ~a| b | | d | | | X | X | | | | |
| | b | c | d | | | | X | | | | X |
| a | | c | d | | | | | | X | | X |
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)`
| a | b | c | d | 0 | 4 | 5 | 7 | 8 | 11 | 12 | 15 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:--:|:--:|:--:|
| | | ~c| ~d| ~~X~~ | ~~X~~ | | | ~~X~~ | | ~~X~~ | |
| ~a| b | ~c| | | ~~X~~ | X | | | | | |
| ~a| b | | d | | | X | X | | | | |
| | b | c | d | | | | X | | | | X |
| a | | c | d | | | | | | X | | X |
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)`
| a | b | c | d | 0 | 4 | 5 | 7 | 8 | 11 | 12 | 15 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:--:|:--:|:--:|
| | | ~~~c~~| ~~~d~~| ~~X~~ | ~~X~~ | | | ~~X~~ | | ~~X~~ | |
| ~a| b | ~c| | | ~~X~~ | X | | | | | |
| ~a| b | | d | | | X | X | | | | |
| | b | c | d | | | | X | | | | ~~X~~ |
| ~~a~~ | | ~~c~~ | ~~d~~ | | | | | | ~~X~~ | | ~~X~~ |
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)`
| a | b | c | d | 0 | 4 | 5 | 7 | 8 | 11 | 12 | 15 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:--:|:--:|:--:|
| | | ~~~c~~| ~~~d~~| ~~X~~ | ~~X~~ | | | ~~X~~ | | ~~X~~ | |
| ~a| b | ~c| | | ~~X~~ | ~~X~~ | | | | | |
| ~~~a~~| ~~b~~ | | ~~d~~ | | | ~~X~~ | ~~X~~ | | | | |
| | b | c | d | | | | ~~X~~ | | | | ~~X~~ |
| ~~a~~ | | ~~c~~ | ~~d~~ | | | | | | ~~X~~ | | ~~X~~ |
### 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:
```py
class Minterm:
def __init__(self, values, value):
self._values = values
self._value = value
self._used = False
self._values.sort()
def __str__(self):
values = ", ".join([str(value) for value in self._values])
return f"m({values}) = {self._value}"
def __eq__(self, minterm):
if type(minterm) != Minterm:
return False
return (
self._value == minterm._value and
self._values == minterm._values
)
```
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:
```py
def get_values(self):
"""Returns all the implicants that this minterm covers.
"""
return self._values
def get_value(self):
"""Returns the bit values ('-010', '1010', etc.) for this minterm.
"""
return self._value
def use(self):
"""Keeps track of when this minterm is "used" in a comparison.
"""
self._used = True
def used(self):
"""Returns whether or not this minterm was used.
"""
return self._used
```
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:
```py
def combine(self, minterm):
"""Combines this minterm with the specified minterm if possible.
"""
# Check if this minterm is the same as the one trying to be combined with
if self._value == minterm._value or self._values == minterm._values:
return None
# Keep track of the amount of difference between the value of the minterm
# and also keep track of the resulting string
diff = 0
result = ""
# Iterate through all the bit values
for char in range(len(self._value)):
# Check if this minterm and the combined minterm have a bit difference
if self._value[char] != minterm._value[char]:
diff += 1
result += "-"
# There is no difference
else:
result += self._value[char]
# The difference is greater than 1, these minterms cannot be combined
if diff > 1:
return None
return Minterm(self._values + minterm._values, result)
```
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:
```py
class QM:
"""A class to handle processing the Quine-McCluskey Algorithm.
"""
def __init__(self, variables, values):
self._variables = variables
self._values = values
def __get_bits(self, value):
"""Returns the binary digit for the specified value.
"""
# Pad the result with extra 0's at the beginning to match how many variables
# there are being used
return bin(value)[2:].rjust(len(self._variables), "0")
```
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.
```py
def __initial_group(self):
"""Creates the initial grouping for the bits from the values
given to the Quine-McCluskey Algorithm
"""
# Keep track of groups by 2-dimensional list
groups = []
for count in range(len(self._variables) + 1):
groups.append([])
# Iterate through values
for value in self._values:
# Count number of 1's in value's bit equivalent
count = self.__get_bits(value).count("1")
# Add count to proper group
groups[count].append(Minterm([value], self.__get_bits(value)))
return groups
```
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:
```py
groups = [
['m(0) = 0000'], # 0 1's
['m(4) = 0100', 'm(8) = 1000'], # 1 1's
['m(5) = 0101', 'm(12) = 1100'], # 2 1's
['m(7) = 0111', 'm(11) = 1011'], # 3 1's
['m(15) = 1111'] # 4 1's
]
```
#### Prime Implicants
The next step is to get all the prime implicants that could possibly cover the expression. Like [mentioned earlier](#comparing) 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:
```py
def __get_prime_implicants(self, groups = None):
"""Recursively gets the prime implicants for the expression.
"""
# Get initial group if group is None
if groups == None:
groups = self.__initial_group()
# If there is only 1 group, return all the minterms in it
if len(groups) == 1:
return groups[0]
# Try comparing the rest
else:
unused = []
comparisons = range(len(groups) - 1)
new_groups = [[] for c in comparisons]
for compare in comparisons:
group1 = groups[compare]
group2 = groups[compare + 1]
# Compare every term in group1 with every term in group2
for term1 in group1:
for term2 in group2:
# Try combining it
term3 = term1.combine(term2)
# Only add it to the new group if term3 is not None
# term3 will only be None if term1 and term2 could not
# be combined
if term3 != None:
term1.use()
term2.use()
if term3 not in new_groups[compare]:
new_groups[compare].append(term3)
# Get list of all unused minterms
for group in groups:
for term in group:
if not term.used() and term not in unused:
unused.append(term)
# Add recursive call
for term in self.__get_prime_implicants(new_groups):
if not term.used() and term not in unused:
unused.append(term)
return unused
```
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.
```py
def __power_set(self, values, prime_implicants):
"""Creates a power set of all valid prime implicants that covers
the rest of an expression. This is used after the essential prime implicants have been found.
"""
# Get the power set of all the prime_implicants
prime_implicants = list(prime_implicants)
power_set = []
# Iterate through decimal values from 1 to 2 ** size - 1
for i in range(1, 2 ** len(prime_implicants)):
current_set = []
# Get the binary value of the decimal value
bin_value = bin(i)[2:].rjust(len(prime_implicants), "0")
# Find which indexes have 1 in the bin_value string
for index in range(len(bin_value)):
if bin_value[index] == "1":
current_set.append(prime_implicants[index])
power_set.append(current_set)
# Remove all subsets that do not cover the rest of the implicants
new_power_set = []
for subset in power_set:
# Get all the values the set covers
temp_values = []
for implicant in subset:
for value in implicant.get_values():
if value not in temp_values and value in values:
temp_values.append(value)
temp_values.sort()
# Check if this subset covers the rest of the values
if temp_values == values:
if len(subset) < len(minSet):
minSet = subset
return minSet
```
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.
```py
def __solve(self):
"""Solves for the expression returning the minimal amount of prime implicants needed
to cover the expression.
"""
# Get the prime implicants
prime_implicants = self.__get_prime_implicants(self.__initial_group())
# Keep track of values with only 1 implicant
# These are the essential prime implicants
essential_prime_implicants = []
values_used = [False] * len(self._values)
for i in range(len(self._values)):
value = self._values[i]
uses = 0
last = None
for minterm in prime_implicants:
if value in minterm.get_values():
uses += 1
last = minterm
if uses == 1 and last not in essential_prime_implicants:
for v in last.get_values():
values_used[self._values.index(v)] = True
essential_prime_implicants.append(last)
# Check if all values were used
if values_used.count(False) == 0:
return essential_prime_implicants
# Keep track of prime implicants that cover as many values as possible
# with as few variables as possible
prime_implicants = [prime_implicant for prime_implicant in prime_implicants if prime_implicant not in essential_prime_implicants]
# Check if there is only one implicant left (very rare but just in case)
if len(prime_implicants) == 1:
return essential_prime_implicants + prime_implicants
# Create a power set from the remaining prime implicants and check which
# combination of prime implicants gets the simplest form
return essential_prime_implicants + self.__power_set([
self._values[index]
for index in range(len(self._values))
if not values_used[index]
], prime_implicants)
```
The basic function of the `solve` function is to:
1. Get a list of prime implicants
```py
# Get the prime implicants
prime_implicants = self.__get_prime_implicants(self.__initial_group())
```
2. Find the essential prime implicants
```py
# Keep track of values with only 1 implicant
# These are the essential prime implicants
essential_prime_implicants = []
values_used = [False] * len(self._values)
for i in range(len(self._values)):
value = self._values[i]
uses = 0
last = None
for minterm in prime_implicants:
if value in minterm.get_values():
uses += 1
last = minterm
if uses == 1 and last not in essential_prime_implicants:
for v in last.get_values():
values_used[self._values.index(v)] = True
essential_prime_implicants.append(last)
# Check if all values were used
if values_used.count(False) == 0:
return 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
```py
# Keep track of prime implicants that cover as many values as possible
prime_implicants = [prime_implicant for prime_implicant in prime_implicants if prime_implicant not in essential_prime_implicants]
# Check if there is only one implicant left (very rare, if not impossible, but just in case)
if len(prime_implicants) == 1:
return essential_prime_implicants + prime_implicants
# Create a power set from the remaining prime implicants and check which
# combination of prime implicants gets the simplest form
return essential_prime_implicants + self.__power_set([
self._values[index]
for index in range(len(self._values))
if not values_used[index]
], 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.
```py
# Get the prime implicants and variables
prime_implicants = self.__solve()
# Check if there are no prime_implicants; Always False
if len(prime_implicants) == 0:
return "0"
if len(prime_implicants) == 1:
if prime_implicants[0].get_value().count("-") == len(self._variables):
return "1"
result = ""
# Iterate through prime implicants
for j in range(len(prime_implicants)):
implicant = prime_implicants[j]
# Iterate through all bits in the implicants value
for i in range(len(implicant.get_value())):
if implicant.get_value()[i] == "0":
result += "NOT "
if implicant.get_value()[i] != "-":
result += self._variables[i]
if implicant.get_value().count("-", i + 1) < len(implicant.get_value()) - i - 1 and implicant.get_value()[i] != "-":
result += " AND "
if j < len(prime_implicants) - 1:
result += " OR "
return result
```
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](https://repl.it/@FellowHashbrown/Quine-McCluskey-Java) and [Node.js](https://repl.it/@FellowHashbrown/Quine-McCluskey-Nodejs)
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](https://discord.gg/W8yVrHt)