Title :
LSAT-an algorithm for the synthesis of two level threshold gate networks
Author :
Oliveira, A.L. ; Sangiovanni-Vincentelli, A.
Author_Institution :
Dept. of EECS, California Univ., Berkeley, CA, USA
Abstract :
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.<>
Keywords :
computational complexity; logic CAD; threshold elements; threshold logic; branch and bound algorithm; run time polynomial; two level threshold gate networks; two-level minimization; Binary search trees; Boolean functions; Integrated circuit synthesis; Logic gates; Machine learning; Machine learning algorithms; Minimization methods; Network synthesis; Polynomials; Sorting;
Conference_Titel :
Computer-Aided Design, 1991. ICCAD-91. Digest of Technical Papers., 1991 IEEE International Conference on
Conference_Location :
Santa Clara, CA, USA
Print_ISBN :
0-8186-2157-5
DOI :
10.1109/ICCAD.1991.185211
