Report Number: CSL-TR-94-626
Institution: Stanford University, Computer Systems Laboratory
Title: Synthesis and Optimization of Synchronous Logic Circuits
Author: Damiani, Maurizio
Date: June 1994
Abstract: The design automation of complex digital circuits offers
important benefits. It allows the designer to reduce design
time and errors, to explore more thoroughly the design space,
and to cope effectively with an ever-increasing project
This dissertation presents new algorithms for the logic
optimization of combinational and synchronous digital
circuits. These algorithms rely on a common paradigm. Namely,
global optimization is achieved by the iterative local
optimization of small subcircuits.
The dissertation first explores the combinational case.
Chapter 2 presents algorithms for the optimization of
subnetworks consisting of a single-output subcircuit. The
design space for this subcircuit is described implicitly by a
Boolean function, a so-called function . Efficient methods
for extracting this function are presented.
Chapter 3 is devoted to a novel method for the optimization
of multiple-output subcircuits. There, we introduce the
notion of compatible gates . Compatible gates represent
subsets of gates whose optimization is particularly simple.
The other three chapters are devoted to the optimization of
synchronous circuits. Following the lines of the
combinational case, we attempt the optimization of the
gate-level (rather than the state diagram -level)
representation. In Chapter 4 we focus on extending
combinational techniques to the sequential case. In
particular, we present algorithms for finding a synchronous
function that can be used in the optimization process.
Unlike the combinational case, however, this approach is
exact only for pipeline-like circuits. Exact approaches for
general, acyclic circuits are presented in Chapter 5. There,
we introduce the notion of synchronous recurrence equation.
Eventually, Chapter 6 presents methods for handling feedback