StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>If I understand what you're asking, you'll want to look into the general topics of <em>logic minimization</em> and/or <em>Boolean function simplification</em>. The references are mostly about general methods for eliminating redundancy in Boolean formulas that are disjunctions ("or"s) of terms that are conjunctions ("and"s). </p> <p>By hand, the standard method is called a Karnaugh map. The equivalent algorithm expressed in a way that's more amenable to computer implementation is Quine-McKlosky (also called the method of prime implicants). The minimization problem is NP-hard, and QM solves it exactly. </p> <p>Therefore I think QM is what you want for the "super-optimizer" you're trying to build. </p> <p>But the combination of NP-hard and exact solution means that QM is impractical for large problems, at least non-trivial ones. </p> <p>The <a href="http://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm" rel="nofollow">QM Algorithm</a> lays out the conjunctive terms (called minterms in this context) in a table and conducts searches for 1-bit differences between pairs of terms. These terms can be combined and the factor for the differing bit labeled "don't care" in further combinations. This is repeated with 2-bit, 4-bit, etc. subsets of bits. The exponential behavior results because choices are involved for the combinations of larger bit sets: choosing one rules out another. Therefore it is essentially a search problem.</p> <p>There is an enormous literature on heuristics to trim the search space, yet find "good" solutions that aren't necessarily optimal. A famous one is <a href="http://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer" rel="nofollow">Espresso</a>. However, since algorithm improvements translate directly to dollars in semiconductor manufacture, it's entirely possible that the best are proprietary and closely held. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload