Talk:Quine–McCluskey algorithm

I am suffering difficulty in Digital Logic Design Please help me in this case

What are you having problems with? Kobold 20:58, 27 September 2005 (UTC)[reply]

deterministic?!

on the Karnaugh map page the following claim is made.

For expressions having more than four variables, the Quine-McCluskey algorithm, also called the method of prime implicants, should be used.

This algorithm uses a deterministic approach to simplification of boolean expressions. Thus, following the steps of this alternate algorithm ensures that the simplest expression can be found.

yet this algorithm (at least as described) does not nessacerally give a complete soloution, it leaves you with a list of essential prime implicants. If theese do not cover the equation it does not give a method for selecting which of the remaining prime implicants are to be used to get a minimal soloution. Plugwash 02:04, 26 December 2005 (UTC)[reply]

Yeah, this article could be improved quite a bit. The way you get a minimal solution (there can be several) is by using what's called a backtracking algorithm. The general idea is this:

You reduce the table deterministically as much as possible like this: If you have a minterm that's only covered by one implicant, you have to choose it. If you have an implicant that covers a subset of the minterms some other implicant covers, you can delete that row. If you have a minterm that is covered by a superset of the implicants some other minterm is covered by, you can delete that column.

More consisely, delete rows that are subsets of other rows and columns that are supersets of other columns.

Usually you'll solve the table, but sometimes the table can't be reduced - this corresponds to cyclic patterns if you look at a kmap. So in your recursive function, you would have to make an arbitrary choice. Instead, you make every possible choice, and then make recursive calls for each of the resultant tables. Whichever of the choices enables you to finish with the fewest implicants is what you choose.

For example:

list<Implicant> recursiveMinCover(Table table)
{
        list<Implicant> necessary;

        necessary = table.deterministicReduce();
        if(table.size() == 0)
                return necessary;

        int shortest = infinity;
        list<Implicant> chosen;

        for(each implicant in the table) {
                temptable = table;
                temptable.removeImplicant(implicant);
                candidate = recursiveMinCover(temptable);

                if(candidate.size() < shortest) {
                        shortest = candidate.size();
                        chosen = necessary + implicant + candidate;      
                } 
        }

        return chosen;
}