Quine–McCluskey algorithm: Difference between revisions

Revision as of 11:08, 16 November 2005

Revision as of 12:04, 25 November 2005

Line 4:

#Finding all [[implicant|prime implicants]] of the function.

#Using those prime implicants to find the [[implicant|essential prime implicants]] of the function, as well as using 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 algorithm is [[NP-complete]]: the [[runtime]] of the Quine-McCluskey algorithm grows [[expontential growth|exponentially]] with the input size. It can be shown that for a function of ''n'' variables the upper bound on the number of prime implicants is 3^''n''/''n''. If ''n'' = 32 there may be over 6.1 * 10¹⁴, or 617 trillion prime implicants. Functions with a large number of variables have to be minimized with potentially non-optimal [[heuristic (computer science)|heuristic]] methods.

==Example==

Line 27 ⟶ 30:

m15 1 1 1 1 1

One can easily form the canonical [[sum of products]] expression from this table, simply by summing the minterms[[minterm]]s where the function evaluates to one:

<math>f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD</math>