The Quine–McCluskey algorithm (QMC), also known as the method of prime implicants or the tabulation method, is a method used for minimization of Boolean functions that was developed by Willard V. Quine in 1952 and extended by Edward J. McCluskey in 1956. As a general principle this approach had already been demonstrated by the logician Hugh McColl 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, 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 F has been reached. The Quine-McCluskey algorithm works as follows:
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 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 3 n / n {\displaystyle 3^{n}/{\sqrt {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. For one natural class of functions f {\displaystyle f} , the precise complexity of finding all prime implicants is better-understood: Milan Mossé, Harry Sha, and Li-Yang Tan discovered a near-optimal algorithm for finding all prime implicants of a formula in conjunctive normal form. Step two of the algorithm amounts to solving the set cover problem; NP-hard instances of this problem may occur in this algorithm step.
Example
Input In this example, the input is a Boolean function in four variables, f : { 0 , 1 } 4 → { 0 , 1 } {\displaystyle f:\{0,1\}^{4}\to \{0,1\}} which evaluates to 1 {\displaystyle 1} on the values 4 , 8 , 10 , 11 , 12 {\displaystyle 4,8,10,11,12} and 15 {\displaystyle 15} , evaluates to an unknown value on 9 {\displaystyle 9} and 14 {\displaystyle 14} , and to 0 {\displaystyle 0} everywhere else (where these integers are interpreted in their binary form for input to f {\displaystyle f} for succinctness of notation). The inputs that evaluate to 1 {\displaystyle 1} are called 'minterms'. We encode all of this information by writing
f ( A , B , C , D ) = ∑ m ( 4 , 8 , 10 , 11 , 12 , 15 ) + d ( 9 , 14 ) . {\displaystyle f(A,B,C,D)=\sum m(4,8,10,11,12,15)+d(9,14).\,}
This expression says that the output function f will be 1 for the minterms 4 , 8 , 10 , 11 , 12 {\displaystyle 4,8,10,11,12} and 15 {\displaystyle 15} (denoted by the 'm' term) and that we don't care about the output for 9 {\displaystyle 9} and 14 {\displaystyle 14} combinations (denoted by the 'd' term). The summation symbol ∑ {\displaystyle \sum } denotes the logical sum (logical OR, or disjunction) of all the terms being summed over.
Step 1: Finding the 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 minterms (leaving out don't-care terms) where the function evaluates to one:
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 (names in parentheses), so they can be combined with minterms:
At this point, one can start combining minterms with other minterms in adjacent groups; as in, we compare minterms in nth group with (n+1)th group. So for the m4 minterm in with only one Number of 1s, we compare it to m9, m10, and m12 which have two Number of 1s. If two terms differ by only a single digit, that digit is replaced with a dash indicating that the digit doesn't matter. 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. Terms that can't be combined any more are marked with an asterisk (*).
… excerpt ends here. Continue reading the full article.
