Talk:Quine–McCluskey algorithm

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

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? 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. 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:

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)

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)

==== 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.71.31.147.72 (talk) 16:30, 18 December 2011 (UTC)

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)

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)

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. 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 [1]:

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

For n = 32 we have 3ⁿ/n ≈ 5.79×10¹³, which is about 112 times less than 6.5×10¹⁵.

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

Which value is correct then? --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ⁿ SOP terms, then then the upper bound of prime implicants is less than 2ⁿ, since the number of reduced terms is always less than or equal to the number of outputs of a boolean function(which has 2ⁿ 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. 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 . —Preceding unsigned comment added by 203.106.57.104 (talk) 04:11, 23 May 2011 (UTC)

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. --Mr z (talk) — Preceding undated comment added 19:55, 3 April 2014 (UTC)

References needed

References to the original publications of Quine and McCluskey need to be given. 86.177.102.43 (talk) 08:38, 28 April 2014 (UTC)

Citations added for Quine and McCluskey. --50.53.43.58 (talk) 15:13, 26 August 2014 (UTC)

External links modified

Hello fellow Wikipedians,

I have just added archive links to 2 external links on Quine–McCluskey algorithm. Please take a moment to review my edit. If necessary, add {{cbignore}} after the link to keep me from modifying it. Alternatively, you can add {{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 {{Sourcecheck}}).

Y An editor has reviewed this edit and fixed any errors that were found.

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—^{cyberbot II}_{Talk to my owner:Online} 06:24, 28 February 2016 (UTC)