Quine McKluskey Algorithm

• Download source files - 30.4 Kb

Introduction

The Quine McKluskey algorithm is used for minimization of logical (boolean) functions. This is an important aspect in all electrical circuits allowing cheaper components and assuring that the simplest solution (circuit) for a problem (purpose) is used. Whether you need to learn the algorithm, or you need help to understand it for your University classes, or you want to tech the algorithm to your students in a graphical, attractive way, or need to include it in your commercial electric-circuit simulation application, this article, and specially the attached code, is for you.

Requirements

The reader should have basic notions of boolean algebra (logical functions, and-or operators, minterms, etc.). Knowledge of the Quine McKluskey algorithm is optimal. Basic notions of C# and OOP are required for understanding the code, but you can use it fine without this.

The Algorithm

To properly understand the algorithm, I strongly suggest reading the following articles, written by a man with more didactic capabilities than me: Quine McKluskey Wikipedia article, and here you find a clear (but not so trivial) example.

The basic steps to follow are, as shown there:

Step 1: Separate the minterms into groups based on the number of 1's in their binary representations.

Step 2: Compare neighboring groups, and replace pairs of terms that have exactly one bit different. These terms are said to be adjacent. We can replace any two adjacent terms with a single term that contains a dash at the location of the unmatched bit. Be sure to mark the minterms that are used to create common terms so that they can be removed from the list.

Step 3: Repeat the search until no new adjacent terms are found. Two terms that already contain dashes are considered to be adjacent only if all dash positions match and all but one literal position contains the same value.

Step 4: Remove duplicates and list all unique surviving terms. Indicate which of the original minterms are covered by the surviving terms. These are called the implicants since they imply the existence of minterms in the original expression.

The code

The code that actually solves the minimization problem is isolated in the QM namespace. This class can and should be reused in case you want to replace the GUI, which is perfectly possible without many changes in code. The namespace contains a class: QMTools that handles non-algorithm related problems and the actual classes that deal with the algorithm.

Use

A lot of attention has been given to the interface, it should be easy to work with it in a mouse only way. You just click the rectangles on the Karnaugh map that should have the value 1 (true) and press Process. The status bar indicates what term the rectangle under the mouse represents and the number (base 10 value corresponding to the binary code ) of each minterm currently set to "true". Of course, you can choose the number of variables of your logical function between 2 and 6 if the default value (2) is too small. But keep in mind that for values greater than 4, using the Karnaugh maps becomes increasingly difficult. The algorithm works perfectly for greater values, but the interface cannot keep up with it, for lack of space. Instead, use a simple command line interface for logical function input if you want such functionality.

The output

Besides the minimized function (shown in a way that allows you to copy it), the code supplies the user with a series of lists that show exactly how each step of the algorithm has run, and the status after each step (minterms with checked or unchecked state).

My contribution

Besides the standard implementation of the algorithm, I added one last improvement. After step four (removal of duplicates), some implicants may make others obsolete (implicant A and implicant B may fully cover implicant C); this was solved by a Greedy method ( the implicant that covers the most uncovered elements is selected, until there are no uncovered elements left ) .

Conclusion

I hope my code made understanding the algorithm easier, or that it helped you save valuable time. Please feel free to comment, as your opinions and ideas are much appreciated.