The Quine–McCluskey algorithm (QMC), also known as the method of prime implicants, is a method used for
minimization of
Boolean function
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ( ...
s that was developed by
Willard V. Quine in 1952
and extended by
Edward J. McCluskey
Edward Joseph McCluskey (October 16, 1929 – February 13, 2016) was a professor at Stanford University. He was a pioneer in the field of Electrical Engineering.
Biography
McCluskey worked on electronic switching systems at the Bell Teleph ...
in 1956.
As a general principle this approach had already been demonstrated by the logician
Hugh McColl
Hugh L. McColl Jr. (born 18 June 1935) is a fourth-generation banker and the former Chairman and CEO of Bank of America. Active in banking since around 1960, McColl was a driving force behind consolidating a series of progressively larger, mos ...
in 1878,
was proved by
Archie Blake in 1937,
and was rediscovered by Edward W. Samson and Burton E. Mills in 1954
and by Raymond J. Nelson in 1955.
Also in 1955, Paul W. Abrahams and John G. Nordahl
as well as
Albert A. Mullin and Wayne G. Kellner
proposed a decimal variant of the method.
The Quine–McCluskey algorithm is functionally identical to
Karnaugh mapping
The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 ''logica ...
, 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.
Complexity
Although more practical than
Karnaugh mapping
The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 ''logica ...
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
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
.
The
running time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
of the Quine–McCluskey algorithm grows
exponentially
Exponential may refer to any of several mathematical topics related to exponentiation, including:
*Exponential function, also:
**Matrix exponential, the matrix analogue to the above
* Exponential decay, decrease at a rate proportional to value
*Exp ...
with the number of variables. For a function of ''n'' variables the number of prime implicants can be as large as
,
e.g. for 32 variables there may be over 534 × 10
12 prime implicants. Functions with a large number of variables have to be minimized with potentially non-optimal
heuristic
A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, ...
methods, of which the
Espresso heuristic logic minimizer
The ESPRESSO logic minimizer is a computer program using heuristic and specific algorithms for efficiently reducing the complexity of digital logic gate circuits. ESPRESSO-I was originally developed at IBM by Robert K. Brayton et al. in 1982. ...
was the de facto standard in 1995.
Step two of the algorithm amounts to solving the
set cover problem
The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.
Given a set of elements (called the univ ...
;
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
instances of this problem may occur in this algorithm step.
Example
Input
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 implicants
First, we write the function as a table (where 'x' stands for don't care):
:
One can easily form the canonical
sum of products expression from this table, simply by summing the
minterm
In Boolean algebra, any Boolean function can be expressed in the canonical disjunctive normal form ( CDNF) or minterm canonical form and its dual canonical conjunctive normal form ( CCNF) or maxterm canonical form. Other canonical forms include ...
s (leaving out
don't-care terms) where the function evaluates to one:
:''f'' = 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 (names in parentheses), so they can be combined with minterms:
:
At this point, one can start combining minterms with other minterms. If two terms differ by only a single digit, 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 (). For instance
1000
and
1001
can be combined to give
100-
, indicating that both minterms imply the first digit is
1
and the next two are
0
.
:
When going from Size 2 to Size 4, treat
-
as a third bit value. Match up the
-
's first. The terms represent products and to combine two product terms they must have the same variables. One of the variables should be complemented in one term and uncomplemented in the other. The remaining variables present should agree. So to match two terms the
-
's must align and all but one of the other digits must be the same. For instance,
-110
and
-100
can be combined to give
-1-0
, as can
-110
and
-010
to give
--10
, but
-110
and
011-
cannot since the
-
's do not align.
-110
corresponds to BCD' while
011-
corresponds to A'BC, and BCD' + A'BC is not equivalent to a product term.
:
Note: In this example, none of the terms in the size 4 implicants table can be combined any further. In general this process should be continued (sizes 8, 16 etc.) until no more terms can be combined.
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 (these are the ones that have been marked with a "" in the previous step), 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.
:
To find the essential prime implicants, we run along the top row. We have to look for columns with only one "✓". If a column has only one "✓", this means that the minterm can only be covered by one prime implicant. This prime implicant is ''essential''.
For example: in the first column, with minterm 4, there is only one "✓". This means that m(4,12) is essential. So we place a star next to it. Minterm 15 also has only one "✓", so m(10,11,14,15) is also essential. Now all columns with one "✓" 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 Boolean algebra, Petrick's method (also known as ''Petrick function'' or ''branch-and-bound'' method) is a technique described by Stanley R. Petrick (1931–2006) in 1956 for determining all minimum sum-of-products solutions from a prime impl ...
. In the current example, the essential prime implicants do not handle all of the minterms, so, in this case, the essential implicants can be combined with one of the two non-essential ones to yield one equation:
:''f'' = BC'D' + AB' + AC
or
:''f'' = BC'D' + AD' + AC
Both of those final equations are functionally equivalent to the original, verbose equation:
:''f'' = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD.
See also
*
Blake canonical form
In Boolean logic, a formula for a Boolean function ''f'' is in Blake canonical form (BCF), also called the complete sum of prime implicants, the complete sum, or the disjunctive prime form, when it is a disjunction of all the prime implicants of ...
*
Buchberger's algorithm
In the theory of multivariate polynomials, Buchberger's algorithm is a method for transforming a given set of polynomials into a Gröbner basis, which is another set of polynomials that have the same common zeros and are more convenient for extract ...
– analogous algorithm for algebraic geometry
*
Petrick's method
In Boolean algebra, Petrick's method (also known as ''Petrick function'' or ''branch-and-bound'' method) is a technique described by Stanley R. Petrick (1931–2006) in 1956 for determining all minimum sum-of-products solutions from a prime impl ...
*
Qualitative comparative analysis
In statistics, qualitative comparative analysis (QCA) is a data analysis based on set theory to examine the relationship of conditions to outcome. QCA describes the relationship in terms of necessary conditions and sufficient conditions. The techn ...
(QCA)
References
Further reading
* (viii+635 pages) (NB. This book was reprinted by Chin Jih in 1969.)
* (47 pages)
* (4 pages)
*
*
https://archive.today/20180115131301/http://matwbn.icm.edu.pl/ksiazki/amc/amc13/amc13414.pdf] (7 pages)
*
(22 pages)
* (16 pages) (NB
QCA an open source, R based implementation used in the social sciences.)
External links
Quine-McCluskey algorithm implementation with a search of all solutions by Frédéric Carpon.
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
The Federal University of Rio Grande do Sul ( pt, Universidade Federal do Rio Grande do Sul, UFRGS) is a Brazilian public federal research university based in Porto Alegre, Rio Grande do Sul. UFRGS is among the largest and highest-rated univers ...
, Brazil.
BFunc QMC based Boolean logic simplifiers supporting up to 64 inputs / 64 outputs (independently) or 32 outputs (simultaneously), by António Costa
*
Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
br>
Implementationby Robert Dick, with a
optimized version
*
Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
br>
Implementationfor symbolically reducing Boolean expressions.
Quinessence an open source implementation written in Free Pascal by Marco Caminati.
minBoolan implementation by Andrey Popov.
an applet for a step by step analyze of the QMC- algorithm by Christian Roth
C++ implementationSourceForge.net C++ program implementing the algorithm.
Perl Moduleby Darren M. Kulp.
TutorialTutorial on Quine-McCluskey and Petrick's method.
PetrickC++ implementation (including Petrick) based on the tutorial above.
C programPublic Domain console based C program on SourceForge.net.
* For a fully worked out example visit: http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld024.htm
* The Boolean Bot: A JavaScript implementation for the web: http://booleanbot.com/
open source gui QMC minimizerComputer Simulation Codes for the Quine-McCluskey Method by Sourangsu Banerji.
{{DEFAULTSORT:Quine-Mccluskey Algorithm
Boolean algebra
Willard Van Orman Quine