The Quine–McCluskey algorithm (or the method of prime implicants) is a method used for minimization of Boolean functions that was developed by Willard V. Quine and extended by Edward J. McCluskey. It is functionally identical to Karnaugh mapping, but the tabular form makes it more efficient for use in computer algorithms, and it also gives a deterministic way to check that the minimal form of a Boolean function has been reached. It is sometimes referred to as the tabulation method.
The method involves two steps:
- Finding all prime implicants of the function.
- Use those prime implicants in a prime implicant chart to find the essential prime implicants of the function, as well as other prime implicants that are necessary to cover the function.
Although more practical than Karnaugh mapping when dealing with more than four variables, the Quine–McCluskey algorithm also has a limited range of use since the problem it solves is NP-complete. The running time of the Quine–McCluskey algorithm grows exponentially with the number of variables. For a function of n variables the number of prime implicants can be as large as 3nln(n), e.g. for 32 variables there may be over 534 * 1012 prime implicants. Functions with a large number of variables have to be minimized with potentially non-optimal heuristic methods, of which the Espresso heuristic logic minimizer was the de facto standard in 1995.[needs update]
In this example, the input is a Boolean function in four variables, which evaluates to on the values and , evaluates to an unknown value on and , and to everywhere else (where these integers are interpreted in their binary form for input to for succinctness of notation). The inputs that evaluate to are called 'minterms'. We encode all of this information by writing
This expression says that the output function f will be 1 for the minterms and (denoted by the 'm' term) and that we don't care about the output for and combinations (denoted by the 'd' term).
Step 1: finding prime implicantsEdit
First, we write the function as a table (where 'x' stands for don't care):
A B C D f m0 0 0 0 0 0 m1 0 0 0 1 0 m2 0 0 1 0 0 m3 0 0 1 1 0 m4 0 1 0 0 1 m5 0 1 0 1 0 m6 0 1 1 0 0 m7 0 1 1 1 0 m8 1 0 0 0 1 m9 1 0 0 1 x m10 1 0 1 0 1 m11 1 0 1 1 1 m12 1 1 0 0 1 m13 1 1 0 1 0 m14 1 1 1 0 x m15 1 1 1 1 1
- fA,B,C,D = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD.
which is not minimal. So to optimize, all minterms that evaluate to one are first placed in a minterm table. Don't-care terms are also added into this table, so they can be combined with minterms:
1 m4 0100 m8 1000 2 m9 1001 m10 1010 m12 1100 3 m11 1011 m14 1110 4 m15 1111
At this point, one can start combining minterms with other minterms. If two terms vary by only a single digit changing, that digit can be replaced with a dash indicating that the digit doesn't matter. Terms that can't be combined any more are marked with an asterisk (*). When going from Size 2 to Size 4, treat '-' as a third bit value. For instance, -110 and -100 can be combined, as well as -110 and -11-, but -110 and 011- cannot. (Trick: Match up the '-' first.)
Minterm 0-Cube Size 2 Implicants Size 4 Implicants 1 m4 0100 m(4,12) -100* m(8,9,10,11) 10--* m8 1000 m(8,9) 100- m(8,10,12,14) 1--0* — — m(8,10) 10-0 — — — m(8,12) 1-00 — 2 m9 1001 m(9,11) 10-1 m(10,11,14,15) 1-1-* m10 1010 m(10,11) 101- — — — m(10,14) 1-10 — m12 1100 m(12,14) 11-0 — 3 m11 1011 m(11,15) 1-11 — m14 1110 m(14,15) 111- — 4 m15 1111 — —
Note: In this example, none of the terms in the size 4 implicants table can be combined any further. Be aware that this processing should be continued otherwise (size 8 etc.).
Step 2: prime implicant chartEdit
None of the terms can be combined any further than this, so at this point we construct an essential prime implicant table. Along the side goes the prime implicants that have just been generated, and along the top go the minterms specified earlier. The don't care terms are not placed on top—they are omitted from this section because they are not necessary inputs.
4 8 10 11 12 15 ⇒ A B C D m(4,12)* ⇒ — 1 0 0 m(8,9,10,11) ⇒ 1 0 — — m(8,10,12,14) ⇒ 1 — — 0 m(10,11,14,15)* ⇒ 1 — 1 —
To find the essential prime implicants, we run along the top row. We have to look for columns with only 1 "✓". If a column has only 1 "✓", this means that the minterm can only be covered by 1 prime implicant. This prime implicant is essential.
For example: in the first column, with minterm 4, there is only 1 "✓". This means that m(4,12) is essential. So we place a star next to it. Minterm 15 also has only 1 "✓", so m(10,11,14,15) is also essential. Now all columns with 1 "✓" are covered.
The second prime implicant can be 'covered' by the third and fourth, and the third prime implicant can be 'covered' by the second and first, and neither is thus essential. If a prime implicant is essential then, as would be expected, it is necessary to include it in the minimized boolean equation. In some cases, the essential prime implicants do not cover all minterms, in which case additional procedures for chart reduction can be employed. The simplest "additional procedure" is trial and error, but a more systematic way is Petrick's method. In the current example, the essential prime implicants do not handle all of the minterms, so, in this case, one can combine the essential implicants with one of the two non-essential ones to yield one equation:
- fA,B,C,D = BC'D' + AB' + AC
- fA,B,C,D = BC'D' + AD' + AC
Both of those final equations are functionally equivalent to the original, verbose equation:
- fA,B,C,D = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD.
- Quine, Willard Van Orman (October 1952). "The Problem of Simplifying Truth Functions". The American Mathematical Monthly. 59 (8): 521–531. doi:10.2307/2308219. JSTOR 2308219.
- Quine, Willard Van Orman (November 1955). "A Way to Simplify Truth Functions". The American Mathematical Monthly. 62 (9): 627–631. doi:10.2307/2307285. hdl:10338.dmlcz/142789. JSTOR 2307285.
- McCluskey, Jr., Edward J. (November 1956). "Minimization of Boolean Functions". Bell System Technical Journal. 35 (6): 1417–1444. doi:10.1002/j.1538-7305.1956.tb03835.x. hdl:10338.dmlcz/102933. Retrieved 2014-08-24.
- Masek, William J. (1979). Some NP-complete set covering problems. unpublished.
- Czort, Sebastian Lukas Arne (1999). The complexity of minimizing disjunctive normal form formulas (Master's thesis). University of Aarhus.
- Umans, Christopher; Villa, Tiziano; Sangiovanni-Vincentelli, Alberto Luigi (2006-06-05). "Complexity of two-level logic minimization". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 25 (7): 1230–1246. doi:10.1109/TCAD.2005.855944.
- Nelson, Victor P.; Nagle, H. Troy; Carroll, Bill D.; Irwin, J. David (1995). Digital Logic Circuit Analysis and Design (2 ed.). Prentice Hall. p. 234. ISBN 978-0-13463894-2. Retrieved 2014-08-26.
- Feldman, Vitaly (2009). "Hardness of Approximate Two-Level Logic Minimization and PAC Learning with Membership Queries". Journal of Computer and System Sciences. 75: 13–25 (13–14). doi:10.1016/j.jcss.2008.07.007.
- Gimpel, James F. (1965). "A Method for Producing a Boolean Function Having an Arbitrary Prescribed Prime Implicant Table". IEEE Transactions on Computers. 14: 485–488.
- Paul, Wolfgang Jakob (1974). "Boolesche Minimalpolynome und Überdeckungsprobleme". Acta Informatica (in German). 4 (4): 321–336. doi:10.1007/BF00289615.
- Logic Friday program
- Curtis, H. Allen (1962). "Chapter 2.3. McCluskey's Method". A new approach to the design of switching circuits. The Bell Laboratories Series. Princeton, New Jersey, USA: D. van Nostrand Company, Inc. pp. 90–160.
- Quine-McCluskey Solver, by Hatem Hassan.
- Quine-McCluskey algorithm implementation with a search of all solutions, by Frédéric Carpon.
- Modified Quine-McCluskey Method, by Vitthal Jadhav, Amar Buchade.
- All about Quine-McClusky, article by Jack Crenshaw comparing Quine-McClusky to Karnaugh maps
- Karċma 3, A set of logic synthesis tools including Karnaugh maps, Quine-McCluskey minimization, BDDs, probabilities, teaching module and more. Logic Circuits Synthesis Labs (LogiCS) - UFRGS, Brazil.
- A. Costa BFunc, QMC based boolean logic simplifiers supporting up to 64 inputs / 64 outputs (independently) or 32 outputs (simultaneously)
- Python Implementation by Robert Dick, with an optimized version.
- Python Implementation for symbolically reducing Boolean expressions.
- Quinessence, an open source implementation written in Free Pascal by Marco Caminati.
- QCA an open source, R based implementation used in the social sciences, by Adrian Duşa
- A series of two articles describing the algorithm(s) implemented in R: first article and second article. The R implementation is exhaustive and it offers complete and exact solutions. It processes up to 20 input variables.
- minBool an implementation by Andrey Popov.
- QMC applet, an applet for a step by step analyze of the QMC- algorithm by Christian Roth
- C++ implementation SourceForge.net C++ program implementing the algorithm.
- Perl Module by Darren M. Kulp.
- Tutorial Tutorial on Quine-McCluskey and Petrick's method (pdf).
- Petrick C++ implementation (including Petrick) based on the tutorial above
- C program Public Domain console based C program on SourceForge.net.
- Tomaszewski, S. P., Celik, I. U., Antoniou, G. E., "WWW-based Boolean function minimization" INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS AND COMPUTER SCIENCE, VOL 13; PART 4, pages 577-584, 2003.
- For a fully worked out example visit: http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld024.htm
- An excellent resource detailing each step: Olivier Coudert "Two-level logic minimization: an overview" INTEGRATION, the VLSI journal, 17-2, pp. 97–140, October 1994
- open source gui QMC minimizer
- Computer Simulation Codes for the Quine-McCluskey Method, by Sourangsu Banerji.