Automatic synthesis of digital circuits is pivotal for the design of integrated circuits with fast turn-around time. The quality of the synthesized circuits is measured by some figures of merit, such as, for example, silicon area, power consumption and switching-time performance. This project addresses the trade-offs in area (power) minimality and switching-time optimality. In particular, the search for a set of circuit transformations which can transform a circuit that is optimal in terms of area into another that is optimal in terms of timing. The objectives of the research are: (1) study a graph/algebraic model of combinational logic circuits; (2) use the model to define circuit transformations and determine their properties; (3) implement these transformations as a CAD tool program which can be used interactively (or not) in the search of good trade-off points between area (power) and timing. The theoretical part of this research is centered on algorithms based on graph theory and algebraic properties of Boolean functions. The experimental part addresses a computer implementation of the algorithms and their test on real circuit design examples. The impact of this research may be very profound on the CAD and designer community. Algorithms for synthesis and optimization of multiple-level logic are in high demand. The problem is well defined but not as well understood. Designers still rely on their ingenious expertise but cannot be supported yet by a well-defined theory based on sound mathematical foundations.
