Talk:Quine–McCluskey algorithm: Difference between revisions

Revision as of 08:34, 28 April 2014

Revision as of 08:36, 28 April 2014

Line 16:

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

== deterministicDeterministic?! ==

on the [[Karnaugh map]] page the following claim is made.

Line 24:

: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 nessacerallynecessarily give a complete soloutionsolution, it leaves you with a list of essential prime implicants. If theesethese 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 soloutionsolution. [[User:Plugwash|Plugwash]] 02:04, 26 December 2005 (UTC)

----

Line 32:

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 consiselyconcisely, 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.