2
\$\begingroup\$

While studying boolean function simplification I often find things about Karnaugh maps and the Quine–McCluskey algorithm, but I find little about the case of multiple output boolean functions.

In terms of digital circuits, I know that you can reuse the output of gates to get simpler circuits. But, is there a systematic way (algorithm) to get the optimal circuit according to some cost criterion (number of gates, size of gates, etc.)?

\$\endgroup\$
  • \$\begingroup\$ Cost has nothing to do with it. Concentrate on glory or self-satisfaction. \$\endgroup\$ – Andy aka Oct 15 '15 at 22:52
3
\$\begingroup\$

The optimization of such cost functions in strict mathematical sense will likely result in an NP-hard problem, meaning that you'll have to explore an exponentially growing set of combinations to find a true optimum. In real logic synthesis software, different heuristics are used to find a close-to-optimum solution in a realistic time.

One important thing you should keep in mind is that there are many constraints in real world circuits - simply implementing the right Boolean expression is not enough. There may be limits on propagation time. You are often limited to only a particular element (e.g. NAND) you can use in synthesis. In some circuits you may be required to eliminate race conditions. All these constraints will further complexify the optimization task.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

The problem of multi-level logic circuit optimization is much harder. That's why it's not taught in the introductory classes (and, if I may so, that's why some people think Karnaugh maps are all there is to it).

There tomes covering this, typically under the name of Logic Synthesis, but the essence is that there is no single answer; it depends on conflicting goals, what type of circuits you want to use etc.

You can look at http://web.cecs.pdx.edu/~mperkows/=FSM/finite-sm/node17.html to get an idea of the vast amount of research that went into this field. Citeseerx has a copy of a 1990 survey article by Brayton, Hachel and Sangiovanni-Vincentelli. These guys also wrote textbooks are often used to teach the topic. For some free on-line lecture you could start with https://www.youtube.com/watch?v=vRO_Bgyp9P4

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.