Quine-McCluskey

Today’s three things! The first is Quine-McCluskey!

Quine-McCluskey algorithm is a process of reducing a boolean function into a minimal min-term form. A boolean function’s input is n bits (allowed to be 0 or 1 at one time), and its output one bit (allowed to be 0, 1 or not specified). For inputs of less than four bits we can use Karnough mapping, but cases where a function’s inputs are more than four, Quine-McCluskey comes in.

The first step of this algorithm, works similar in principle to Karnough mapping, involves identifying non-reducible prime implicants. It is also trying to merge pairs of inputs giving output of 1 or not specified (which is also called min-terms) that are varied from each other by only single bit. For two min-terms that satisfy this criterion, a new “min-term” is produced from the two, only with the position of the different bits occupied by a symbol representing both 0 and 1. These new compressed “min-terms” are then again treated by the algorithm and might merge with other “min-terms”. Finally, those min-terms and the compressed ones that has never being used in compression are kept, and the rest are discarded.

Now we have a set of min-terms that has been compressed, but that might not be the minimal. We now need to proceed with the actual derivation of minimised expression. Here a prime implicant chart comes in. A prime implicant in this set of min-terms is the unique one that contains a particular original min-term. After laying out the compressed min-terms as rows and original min-terms as columns we have a table, and we can put stars in those cells to indicate that original min-term is covered by some compressed min-term. We can just pick out these prime implicants, removing the columns covered by them and repeat the process.

The worst case happens when there is no prime implicant left, but we still have original min-terms uncovered. We can use Petrick’s Method to determine the minimum cover, which will probably be explain later today/tomorrow.

And yes, this algorithm is HARD to follow, and grows exponentially in time. Unfortunately we might not be able to do better even with heuristics, since boolean function reduction is NP-complete. :O

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s