# Algorithms for logical synthesis of multiple output bits?

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?

• 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. Dec 21, 2015 at 12:59
• 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 (: Dec 22, 2015 at 20:43
• Did you look in EDA related publications (proceedings of conferences like DAC, IEEE publications)? I know there has been work with BDD as well. Dec 22, 2015 at 21:03
• 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. Dec 22, 2015 at 21:19