An exact optimization of two-level acyclic sequential circuits

Several algorithms for gate-level sequential circuit optimization have been reported in the literature. They perform operations similar to those in the more mature multilevel combinational domain while taking relationships across several time periods into account. These techniques are heuristic and their application ad hoc: there is no guarantee of optimality. We present a technique for producing an optimum two-level acyclic sequential circuit. While the circuit restrictions and cost function are limiting, the guarantee of optimality is novel and illuminating. The technique presented herein is useful for optimizing sub-circuits of a multilevel sequential circuit just as two-level combinatorial techniques have been in the combinational domain. Furthermore, the algorithm can be used to detect precisely circuits in which logic sharing across latch boundaries is actually possible- a hitherto unsolved problem