Click here to Skip to main content
Click here to Skip to main content

Quine McKluskey Algorithm

, 30 Sep 2006
Rate this:
Please Sign up or sign in to vote.
The Quine McKluskey algorithm is the most widely used algorithm for logical function minimisation. This article proposes a learning-oriented implementation using visual Karnaugh maps to simplify data input but also with increased usability in professional applications.

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.

Sample Image - quine.jpg

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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Dragos Sbirlea
Software Developer
Romania Romania
Dragos is currently a student at the Polytechnic University of Bucharest. He likes keeping up to date with new and amazing technologies and he hopes he will one day master the mechanisms behind modern day programming languages so that he can write the best possible code from a performance and maintainability point of view.
 
He keeps track of the things he learns on a daily basis on his blog, at http://picobit.wordpress.com/ .

Comments and Discussions

 
GeneralMy vote of 4 Pinmembersalarkia_saied3-May-11 5:12 
QuestionTranslation of comments in source code to English Pinmemberrbunn8381516-Feb-08 17:03 
Questionhow about a linux version? Pinmemberhildebrand5-Aug-07 3:34 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.140814.1 | Last Updated 30 Sep 2006
Article Copyright 2006 by Dragos Sbirlea
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid