Talk:Quine–McCluskey algorithm
From Wikipedia, the free encyclopedia
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)
Contents |
[edit] 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)
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;
}
- Note that it is precisely the backtracking algorithm part of it that makes the solution exponential time - we're trying to solve the set cover problem. A heuristic strategy described in that article allows us to find a solution at worst ln n times larger than the minimum, where n is the largest number of original terms implied by any one prime implicant. Deco 06:51, 2 June 2006 (UTC)
- Er, slight accuracy fix: it might be possible the number of prime implicants itself could be much larger than the number of input terms, in which case other parts of the algorithm could be exponential time and so could heuristics in this stage. But this seems pretty unlikely for your average formula. Deco 07:08, 2 June 2006 (UTC)
[edit] Question about the example
OK, I'm an undergrad in Computer Science, so I'm not qualified to actually "fix" this article. But, I do have a concern. I sat down and worked through the example given, and I'm not clear about one point. In step 1, the final "combination" chart arrives at 4 prime implicants. One of these is m(8,10,12,14)*. According to the chart, this represents the boolean AD'. Yet this product is missing from the final solution. I double-checked, and the solution is correct, but what happened to the AD' term? At what step in the process was it rejected as redundant? Roachmeister 20:08, 8 March 2006 (UTC)
[edit] Copyright violation
I noticed that the Complexity section, especially in its initial form as added by User:Jkl, is very similar to the last paragraph of this page. It was probably a copy-paste-and-tweak job. Do we need to erase this section? Could other material in the article be based too strongly on this site or others? Deco 02:11, 2 June 2006 (UTC)
[edit] New Java implementation
Hey all. Just letting you know that I've just posted a literate program implementing Quine-McCluskey in Java on my wiki, if anyone is interested. It's not optimal because I preferred heuristics over backtracking search, but it produces great results and it's very fast. May add a backtracking search option in the future. Will probably also do a C++ version. Deco 13:15, 2 June 2006 (UTC)
[edit] add dont-care stuff
This page completely ignores what you do with don't-care terms. For anyone interested, you use them in step one (use them exactly as if they were minterms), but in step 2 you omit them. That way you use them to combine, but don't use them as neccessary minterms - because of course they're not. Fresheneesz 20:52, 14 October 2006 (UTC)
