Content deleted Content added
how to make it deterministic |
|||
Line 12:
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. [[User:Plugwash|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 follows 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. (There may be a way to delete columns, I'm not sure.)
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:
<pre>
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;
}
</pre>
| |||