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.

View Paper (PDF)

View Presentation (PowerPoint)