LSAT-an algorithm for the synthesis of two level threshold gate networks

The authors present an algorithm for the synthesis of two-level threshold gate networks inspired by techniques used in classical two-level minimization of logic circuits. They specifically address a restricted version of the problem where the on and off set minterms are explicitly listed. Experimental results show that a simple branch and bound algorithm can be used to obtain solutions close to the absolute minimum in a set of standard problems, outperforming other minimizers even when restricted to using only classic logic gates as building blocks. The algorithm has a run time polynomial in the input size and its performance degrades slowly with the size of the problem.<>