Digital circuits are called combinational if
they are memoryless: they have outputs that depend only on the current
values of the inputs. Combinational circuits are generally thought f as
acyclic (i.e., feed-forward) structures. And yet, cyclic circuits can be
combinational. In previous work, we showed that introducing cycles permits
optimizations of area. We proposed a general methodology for the synthesis
of multilevel networks with cyclic topologies and incorporated it in a
logic synthesis environment. In trials, benchmark circuits were optimized
significantly, with improvements of up to 30% in the area.
In this paper, we discuss the role of combinationality
analysis in the context of synthesis. We present a symbolic framework for
analysis based on a first-cut strategy. Unlike previous approaches, our
method does not require ternary-valued simulation. It is formulated
recursively, and thus it permits us to cache analysis results for common
sub-networks through iterations of the synthesis process. We also discuss
timing analysis of cyclic combinational circuits.