I'm writing some code for implementing the Quine McCluskey algorithm and I simply need to clear out if my logic for implementation is ok.

I get some number of minterms and combine each of them so they produce an implicant, later I combine these implicants and consider them as prime implicants. So for the new prime implicants plus the unchecked implicants, I treat them as candidates for essential implicants.

So I'm talking about two loops here, for the total minterms right later for total implicants obtained before.

I've tested my code for a few examples and got good results so far but I need to know this works for n minterms.


1 Answer 1


For an optimal solution you need more than "two loops". The selection of a minimum number of implicants is a set cover problem and was shown to be NP-complete. Selecting a cover with a greedy algorithm just grabs the most promising implicants and is not guaranteed to arrive at an optimal solution.

A good overview on two-level logic minimization was published by Olivier Coudert. Chapter 3 describes the Quine-McCluskey algorithm. This algorithm is of interest for historical reasons but hardly used in practice any more.

For practical experiments, you could try tools like Logic Friday 1. It uses the two-level minimizer Espresso. Logic Friday features an exact/fast switch. It allows you to play with the trade-off between solution speed and optimality.

Another tool for experiments is Karma 3.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .