Toggle Equivalence Preserving (TEP) Logic Optimization

We describe a procedure (called the TEP procedure) that, given a multi-output circuit M, builds another multi-output circuit M* that is toggle equivalent to M. The TEP procedure can be used in the following two scenarios. First, since for single- output circuits toggle equivalence means functional equivalence, the TEP procedure can be used in "regular" logic synthesis. Second, the TEP procedure enables a powerful synthesis method called LS_TE (Logic Synthesis preserving Toggle Equivalence). Given a circuit N and its partitioning into subcircuits N_i LS_TE builds an optimized circuit N* by replacing subcircuits N_i with their toggle equivalent counterparts N_i. The replacement of N_i with N*_i is done by the TEP procedure. We give results of optimizing single-output circuits by the TEP procedure and some preliminary results of using the TEP procedure in LS_TE. These results show the promise of the TEP procedure and LS_TE.