28-09-2017, 09:48 AM
The algorithm of Quine-McCluskey (or the method of implicantes primos) is a method used to minimize the 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 also gives a deterministic way to verify that the minimal form of a Boolean function has been reached.
It is sometimes referred to as a tabulation method.
The method involves two steps:
1. Find all the main implicants of the function.
2. Use the prime implicants in a main implicit letter to find the essential primary implicants of the function, as well as other prime implicants that are necessary to cover the function.
Although it is 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-hard: the execution time of the Quine- McCluskey grows exponentially with the number of variables. It can be shown that for a function of n variables the upper limit on the number of prime implicants is 3nln (n). If n = 32 there may be more than 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 in 1995.
