5
$\begingroup$

Karnaugh maps and the Quine–McCluskey algorithm can be good choices for coming up with fairly minimal logical expressions that match the requirements of a truth table.

What if I have a situation where I have $M$ input bits and $N$ output bits though?

A naive way to deal with it would be to solve each output bit independently and come up with $N$ logical expressions. The problem with that is that in circuitry or in CPU implementations, you can do multibit operations which can potentially handle a more optimal logical expression which takes into account several, if not all, of the bits at once.

Are there any algorithms to come up with a fairly minimal logical expression when you have $M$ input bits mapping to $N$ output bits?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ 25 years ago, I'd have suggested you to search for papers from IBM/ Berkeley about "Espresso". I can just guess that there are better things nowadays. $\endgroup$
    – AProgrammer
    Commented Dec 21, 2015 at 12:59
  • $\begingroup$ I can't find any more advanced algorithms on my own. Espresso and Espresso-exact (mincov) seem to be all I can find. Apparently espresso-exact uses a "tiling" algorithm, and the tiling problem is NP-Complete, so maybe espresso-exact (mincov) is the best algorithm known so far still? The info was useful, thanks for sharing (: $\endgroup$
    – Alan Wolfe
    Commented Dec 22, 2015 at 20:43
  • 2
    $\begingroup$ Did you look in EDA related publications (proceedings of conferences like DAC, IEEE publications)? I know there has been work with BDD as well. $\endgroup$
    – AProgrammer
    Commented Dec 22, 2015 at 21:03
  • 1
    $\begingroup$ My point being that EDA optimization starts with such boolean optimization and then maps boolean formula to gates (taking into account things other than just an abstract minimal expression like available gates in the library, timing constraints, physical position, ...). I doubt very much that the field has not progressed since 25 years ago and I'd be surprised that all progress was in taking the other factors into account. $\endgroup$
    – AProgrammer
    Commented Dec 22, 2015 at 21:19
  • $\begingroup$ Accepted answer was helpful and clear? Does the article suit your needs? $\endgroup$
    – Evil
    Commented Oct 22, 2016 at 0:27

1 Answer 1

Reset to default
4
+50
$\begingroup$

as you realize, while universal, Quine-Mcclusky is only a "bitwise" construction method (single bit output) that does not recognize/ exploit common subpatterns for multibit outputs. multibit function construction optimization is a very broad area handled by EE type papers/ applications/ algorithms, there are very many published. the general topic is "logic synthesis". there is also a very broad array of software built for this purpose both commercial and public domain. here is an example of a relatively recent survey of algorithms and also a technique of using known/ previously computed circuits in a library-like context. this paper is useful here in that it refs many of the top systems in use and gives a consolodated view that you seem to be asking for in particular.

Improve this answer
$\endgroup$
1
  • $\begingroup$ fyi from the (T)CS/ complexity study pov this problem is closely connected with "MCSP" minimum circuit size problem which has some illustrious bkg see eg RJLipton blog. it is a "very hard"/ intractable problem to find the optimim, finding optimum is only possible for small circuits, and all the software/ algorithms only uses heuristics which is acceptable for practical purposes (it is widespread in eg microprocessor design). $\endgroup$
    – vzn
    Commented Oct 16, 2016 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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