Universal logic design algorithm and its application to the synthesis of two-level switching circuits

Abstract
A very efficient but little known logic design procedure is the search tree algorithm proposed by Thelen [1] for the generation of all prime implicants of a Boolean function. Besides the generation of prime implicants Thelen's algorithm can be used to solve various logic design problems, such as the computation of maximum compatibles, determination of a minimal cover and the computation of prime factors for multilevel logic synthesis [2, 3]. In the paper we present Thelen's algorithm and its application to the problems which arise in the logic design of two-level multiple-output switching circuits. We show that the logic minimisation procedures, such as the expansion of implicants, detection of essential primes, computation of a minimal cover and reduction of prime implicants can be reduced to one problem and efficiently solved by the use of Thelen's algorithm. Based on these new procedures we present two heuristic minimisation algorithms, an iterative Espresso-like minimiser and a very fast one-pass minimiser, and discuss their results. Both minimiser differ from known algorithms [4, 5, 6, 20] in that minimisation is based on only one fundamental (easily programmable) procedure and minimisation of incompletely specified Boolean functions is performed without use of the don't care set. Because of the latter aspect our design algorithms are especially suited for the minimisation of logic functions whose don't care set is large and/or not explicitly given. The algorithms have been successfully tested in the design of finite state machines and are part of the CAD-system CARLOS [7], a logic synthesis system for the design of multilevel CMOS switching circuits.

This publication has 2 references indexed in Scilit: