Talk:Quine–McCluskey algorithm: Difference between revisions

Revision as of 07:52, 27 September 2005

Latest revision as of 14:43, 8 February 2024

(45 intermediate revisions by 27 users not shown)

Line 1:

{{WikiProject banner shell|class=Start|

{{WikiProject Mathematics }}

}}

== Error? ==

There seems to be an error. The article ends saying f.A,B,C,D := BC'D'+AD'+AC is "functionally equivalent to the original, verbose equation": f.A,B,C,D := A'BC'D'+...+AB'C'D+...

In the case (A B C D) = (1 0 0 1) the first expression evaluates to 0 but the second is 1.

(1 0 0 1) = m.9 is one of the "don't cares", but the sentence above says the expressions are "functionally equivalent", which is not so. I suggest the statement should make it clear they are functionally equivalent over the whole ___domain - {(1 0 0 1)}.

-ecb

[[Special:Contributions/70.156.123.197|70.156.123.197]] ([[User talk:70.156.123.197|talk]]) 07:35, 27 February 2012 (UTC)

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

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

== 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 necessarily give a complete solution, it leaves you with a list of essential prime implicants. If these 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 solution. [[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 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 concisely, 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:

<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>

: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. [[User:Deco|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. [[User:Deco|Deco]] 07:08, 2 June 2006 (UTC)

== 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 <math>AD'</math>. Yet this product is missing from the final solution. I double-checked, and the solution is correct, but what happened to the <math>AD'</math> term? At what step in the process was it rejected as redundant? [[User:Roachmeister|Roachmeister]] 20:08, 8 March 2006 (UTC)

==== Example-for people who don't need it; Garbage for people who do.

∑m(8,,,) +d() ← is that supposed to mean something? ∑ is "sum of". I am fairly mathematically literate, but not literate in more advanced logic. does m() imply some sort of set? and d() ...WTF is that. What a terrible article! In the table in the column f. WTF does x mean? No explanation?!?! I'd fix it if I could. It is broken.[[Special:Contributions/71.31.147.72|71.31.147.72]] ([[User talk:71.31.147.72|talk]]) 16:30, 18 December 2011 (UTC)

== Copyright violation ==

I noticed that the Complexity section, especially in [http://en.wikipedia.org/w/index.php?title=Quine–McCluskey_algorithm&oldid=29204996 its initial form] as added by [[User:Jkl]], is very similar to the last paragraph of [http://134.193.15.25/vu/course/cs281/lectures/simplification/quine-McCluskey.html 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? [[User:Deco|Deco]] 02:11, 2 June 2006 (UTC)

== New Java implementation ==

Hey all. Just letting you know that I've just posted [http://en.literateprograms.org/Quine-McCluskey_algorithm_(Java) 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. [[User:Deco|Deco]] 13:15, 2 June 2006 (UTC)

== Add don't-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. [[User:Fresheneesz|Fresheneesz]] 20:52, 14 October 2006 (UTC)

== Algorithm explanation ==

The article should explain why the algorithm works as it demonstrates it with the example.

== Complexity ==

Please check this [http://en.wikipedia.org/w/index.php?title=Quine%E2%80%93McCluskey_algorithm&oldid=156964914]:

::It can be shown that for a function of ''n'' variables the upper bound on the number of prime implicants is 3^''n''/''n''. If ''n'' = 32 there may be over 6.5 * 10¹⁵, prime implicants.

For ''n'' = 32 we have 3^''n''/''n'' &asymp; 5.79&times;10¹³, which is about 112 times less than 6.5&times;10¹⁵.

:::"It can be show", so either show it, or cite the proof.

Which value is correct then? --[[User:CiaPan|CiaPan]] 06:50, 13 September 2007 (UTC)

== Complexity? ==

If ''prime implicant'' refers to an irreducible sum of products term, and any boolean function of ''n'' variables can be written in less than 2^''n'' SOP terms, then then the upper bound of prime implicants is less than 2^''n'', since the number of reduced terms is always less than or equal to the number of outputs of a boolean function(which has 2^''n'' outputs). This means that either the complexity section of the article is either using incorrect terms (in which case ''implicants'' is meant, rather than ''prime implicants''), is grossly inaccurate, or should be clarified. [[User:Dany001|Dany001]] ([[User talk:Dany001|talk]]) 02:06, 10 July 2010 (UTC)

:Once prime implicants are known , one minimal set of prime implicants can be easily obtained by using a simple method described in " Efficient minimisation of Boolean functions " , V C Prasad , International journal of Electrical engineering Education , Oct.2008, pp.321-326 . <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/203.106.57.104|203.106.57.104]] ([[User talk:203.106.57.104|talk]]) 04:11, 23 May 2011 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

== Where did the stars come from? ==

In the algorithm, when the description moves from the first phase to the second phase, the article states "To find the essential prime implicants, we run along the top row. We have to look for columns with only 1 star." Sure enough, there are some asterisks in the table, but no indication why they're there or what process put them there. This is the first place on the page that the word "star" appears. It's like an entire paragraph is missing. --[[User:Mr z|Mr z]] ([[User talk:Mr z|talk]]) <span style="font-size: smaller;" class="autosigned"> — Preceding [[Wikipedia:Signatures|undated]] comment added 19:55, 3 April 2014 (UTC)</span><!--Template:Undated--> <!--Autosigned by SineBot-->

== References needed ==

References to the original publications of Quine and McCluskey need to be given. [[Special:Contributions/86.177.102.43|86.177.102.43]] ([[User talk:86.177.102.43|talk]]) 08:38, 28 April 2014 (UTC)

:Citations added for [https://en.wikipedia.org/w/index.php?title=Quine%E2%80%93McCluskey_algorithm&diff=622779356&oldid=622620764 Quine] and [https://en.wikipedia.org/w/index.php?title=Quine%E2%80%93McCluskey_algorithm&diff=622620764&oldid=619783539 McCluskey]. --[[Special:Contributions/50.53.43.58|50.53.43.58]] ([[User talk:50.53.43.58|talk]]) 15:13, 26 August 2014 (UTC)

== External links modified ==

Hello fellow Wikipedians,

I have just added archive links to {{plural:2|one external link|2 external links}} on [[Quine–McCluskey algorithm]]. Please take a moment to review [https://en.wikipedia.org/w/index.php?diff=prev&oldid=707331643 my edit]. If necessary, add {{tlx|cbignore}} after the link to keep me from modifying it. Alternatively, you can add {{tlx|nobots|deny{{=}}InternetArchiveBot}} to keep me off the page altogether. I made the following changes:

*Added archive http://web.archive.org/web/20160105204916/http://www.compasss.org/files/WPfiles/Dusa2007.pdf to http://www.compasss.org/files/WPfiles/Dusa2007.pdf

*Added archive http://web.archive.org/web/20160105204917/http://www.compasss.org/files/WPfiles/Dusa2007a.pdf to http://www.compasss.org/files/WPfiles/Dusa2007a.pdf

When you have finished reviewing my changes, please set the ''checked'' parameter below to '''true''' or '''failed''' to let others know (documentation at {{tl|Sourcecheck}}).

{{sourcecheck|checked=true}}

Cheers.—[[User:Cyberbot II|<sup style="color:green;font-family:Courier">cyberbot II</sup>]]<small><sub style="margin-left:-14.9ex;color:green;font-family:Comic Sans MS">[[User talk:Cyberbot II|<span style="color:green">Talk to my owner</span>]]:Online</sub></small> 06:24, 28 February 2016 (UTC)