Quine–McCluskey algorithm
Encyclopedia
The Quine–McCluskey algorithm (or the method of prime implicants) is a method used for minimization of boolean functions which was developed by W.V. Quine
and Edward J. McCluskey
. It is functionally identical to Karnaugh map
ping, 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:
it solves is NP-hard
: the runtime of the Quine–McCluskey algorithm grows exponentially
with the number of variables. It can be shown that for a function of n variables the upper bound on the number of prime implicants is 3n/n. If n = 32 there may be over 6.5 * 1015 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
is the de-facto standard.
One can easily form the canonical sum of products expression from this table, simply by summing the minterms (leaving out don't-care terms
) where the function evaluates to one:
Of course, that's certainly 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:
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 a "*". When going from Size 2 to Size 4, treat '-' as a third bit value. Ex: -110 and -100 or -11- can be combined, but not -110 and 011-. (Trick: Match up the '-' first.)
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).
Here, each of the essential prime implicants has been starred - 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 of these two equations:
Both of those final equations are functionally equivalent to the original, verbose equation:
Willard Van Orman Quine
Willard Van Orman Quine was an American philosopher and logician in the analytic tradition...
and Edward J. McCluskey
Edward J. McCluskey
Edward J. McCluskey in Orange, New Jersey, is a Professor Emeritus at Stanford University. He is a pioneer in the field of Electrical Engineering.-Biography:...
. It is functionally identical to Karnaugh map
Karnaugh map
The Karnaugh map , Maurice Karnaugh's 1953 refinement of Edward Veitch's 1952 Veitch diagram, is a method to simplify Boolean algebra expressions...
ping, 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 implicantsImplicantIn Boolean logic, an implicant is a "covering" of one or more minterms in a sum of products of a boolean function. Formally, a product term P in a sum of products is an implicant of the Boolean function F if P implies F...
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.
Complexity
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 problemBoolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
it solves is NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
: the runtime of the Quine–McCluskey algorithm grows exponentially
Exponential growth
Exponential growth occurs when the growth rate of a mathematical function is proportional to the function's current value...
with the number of variables. It can be shown that for a function of n variables the upper bound on the number of prime implicants is 3n/n. If n = 32 there may be over 6.5 * 1015 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
Espresso heuristic logic minimizer
The Espresso logic minimizer is a computer program using heuristic and specific algorithms for efficiently reducing the complexity of digital electronic gate circuits. Espresso was developed at IBM by Robert Brayton. Rudell later published the variant Espresso-MV in 1986 under the title...
is the de-facto standard.
Step 1: finding prime implicants
Minimizing an arbitrary function:| 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 |
One can easily form the canonical sum of products expression from this table, simply by summing the minterms (leaving out don't-care terms
Don't-care (logic)
In digital logic, a don't-care term is an input-sequence to a function that the designer does not care about, usually because that input would never happen, or because differences in that input would not result in any changes to the output...
) where the function evaluates to one:
Of course, that's certainly 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:
| Number of 1s | Minterm | Binary Representation |
|---|---|---|
| 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 a "*". When going from Size 2 to Size 4, treat '-' as a third bit value. Ex: -110 and -100 or -11- can be combined, but not -110 and 011-. (Trick: Match up the '-' first.)
| Number of 1s | 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 | -- |
| 2 | m9 | 1001 | m(8,12) 1-00 | m(10,11,14,15) 1-1-* |
| m10 | 1010 | -- | -- | |
| m12 | 1100 | m(9,11) 10-1 | -- | |
| -- | -- | -- | m(10,11) 101- | -- |
| 3 | m11 | 1011 | m(10,14) 1-10 | -- |
| m14 | 1110 | m(12,14) 11-0 | -- | |
| 4 | m15 | 1111 | m(11,15) 1-11 | -- |
| m(14,15) 111- |
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 chart
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)* | X | X | -100 | => | - | 1 | 0 | 0 | ||||
| m(8,9,10,11) | X | X | X | 10-- | => | 1 | 0 | - | - | |||
| m(8,10,12,14) | X | X | X | 1--0 | => | 1 | - | - | 0 | |||
| m(10,11,14,15)* | X | X | X | 1-1- | => | 1 | - | 1 | - |
Here, each of the essential prime implicants has been starred - 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
Petrick's method
In Boolean algebra, Petrick's method is a technique for determining all minimum sum-of-products solutions from a prime implicant chart...
. 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 of these two equations:
Both of those final equations are functionally equivalent to the original, verbose equation:
See also
- Boolean algebra (logic)
- Circuit minimizationCircuit minimizationIn Boolean algebra, circuit minimization is the problem of obtaining the smallest logic circuit that represents a given Boolean function or truth table...
- Karnaugh mapKarnaugh mapThe Karnaugh map , Maurice Karnaugh's 1953 refinement of Edward Veitch's 1952 Veitch diagram, is a method to simplify Boolean algebra expressions...
- Espresso heuristic minimization program
- Petrick's MethodPetrick's methodIn Boolean algebra, Petrick's method is a technique for determining all minimum sum-of-products solutions from a prime implicant chart...
- Willard Van Orman QuineWillard Van Orman QuineWillard Van Orman Quine was an American philosopher and logician in the analytic tradition...
- Buchberger's algorithmBuchberger's algorithmIn computational algebraic geometry and computational commutative algebra, Buchberger's algorithm is a method of transforming a given set of generators for a polynomial ideal into a Gröbner basis with respect to some monomial order. It was invented by Austrian mathematician Bruno Buchberger...
(analogous algorithm for algebraic geometry)
External links
- Quine-McCluskey algorithm implementation with a search of all solutions, by Frédéric Carpon.
- All about Quine-McClusky, article by Jack Crenshaw comparing Quine-McClusky to Karnaugh maps
- Kmap minimizer Flash application based on Quine-McCluskey Algorithm.
- Java-Applet Applet to minimize a boolean function based on QuineMcCluskey Algorithm. (German page)
- Karma 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.
- Lecture on the Quine–McCluskey algorithm
- A. Costa BFunc, QMC based boolean logic simplifiers supporting up to 64 inputs / 64 outputs (independently) or 32 outputs (simultaneously)
- Java applet to display all the generated primes.
- PythonPython (programming language)Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
Implementation by Robert Dick. - PythonPython (programming language)Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
Implementation for symbolically reducing Boolean expressions. - Quinessence, an open source implementation written in Free Pascal by Marco Caminati.
- A literate programLiterate programmingLiterate programming is an approach to programming introduced by Donald Knuth as an alternative to the structured programming paradigm of the 1970s....
written in Java implementing the Quine-McCluskey algorithm. - 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.
- http://www-ihs.theoinf.tu-ilmenau.de/~sane/projekte/qmc/embed_qmc.html, an applet for a step by step analyze of the QMC- algorithm by Christian Roth
- http://sourceforge.net/projects/qmcs SourceForge.net C++ program implementing the algorithm.
- Perl Module by Darren M. Kulp.
- http://sites.google.com/site/simpogical/download Tutorial on Quine-McCluskey and Petrick's method (pdf).
- 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