# How to generate shortest/smallest/cheapest gate network for a set of functions?

To make this most generic: I have a set of inputs I0, I1, ..., In, outputs O0, O1, ... Om and truth tables giving the desired values for each Oi for all input combinations.

I0 I1 I2 O0 O1
0  0  0  0  0
0  0  1  0  1
0  1  0  0  1
0  1  1  1  0
1  0  0  0  1
1  0  1  1  0
1  1  0  1  0
1  1  1  1  1


Now I know how to use a Karnaugh diagram to generate min terms for each output and build them with NOT, AND and OR gates. But in reality I only have gates with 2, 3, 4 or 8 inputs so for more inputs gates have to be chained in a tree leading to a lot of gates and long signal paths and I also have more gate types to take advantage of.

So my question is: How do I generate a gate network using any kind of gates optimized for either shortest path (fastest), least number of gates/wires (easiest to assemble) or least number of 7400 series chips (I'm running out of space :). Considering fanout limits would also be nice.

Is there something better than brute forcing all possible gate networks to see if any one of them gives the right result?

Note: Target goal would be something that can handle at least 16 inputs and 16 outputs.

• A LUT will be the fastest solution for anything beyond trivial equations, and only requires a single chip. – Ignacio Vazquez-Abrams Aug 30 '16 at 8:09
• Get a copy of Logic Friday. It's free. Accepts equations, schematics, or tables. And it does a lot of what you want using the Espresso heuristic logic minimizer. – jonk Aug 30 '16 at 8:24
• @jonk Logic Friday looks right from the little I saw on youtube. But no Linux version and doesn't run in wine. But it uses the Espresso heuristic logic minimizer, as you mention, which does have a Linux version, so I looked at that. Disapointingly that only seems to generate a sum of products. Same as I would do with a Karnaugh map. Is Logic Friday using something else or does it only look like it can do more than sum of products? – Goswin von Brederlow Aug 31 '16 at 0:45
• @IgnacioVazquez-Abrams A LUT for 16 inputs and 16 outputs requires 128kB of memory and 16 levels of multiplexers with a resulting path length of 17 gates. As sum of products you can do the same with a maximum path length of 5 gates. So no, LUTs are not faster. At a minimum you would want to minimize the functions so smaller LUTs can be used. – Goswin von Brederlow Aug 31 '16 at 0:53
• @GoswinvonBrederlow: Yeah. It does more. It will convert a table into a schematic, a schematic into a table, equations into either of those, and it will let you specify what logic you want to limit things to, as well. it will also generate product of sums as well as sum of products. – jonk Aug 31 '16 at 1:11