Toggle equivalence preserving logic synthesis

A method of producing a circuit comprising:

• using a computer running a process to produce a circuit N2(i) from a circuit N2(i-1) that is toggle equivalent to a first circuit (N1) that includes the acts of,
• identifying one or more output toggles in circuit N2(i-1) that lack a corresponding output toggle in a circuit N1;
• adding at least one first gate to circuit N2(i-1) that has the effect of removing at least one toggle of the one or more identified output toggles in circuit N2(i-1) that lack a corresponding output toggle in circuit N1;
• determining whether there are one or more output toggles in N1 that lack a corresponding output toggle in an intermediate circuit defined by N2(i-1) as modified by the addition of the at least one first gate;
• and
• when one or more corresponding toggles in the intermediate circuit are determined to be lacking, then adding one or more gates to circuit N2(i-1) that have the effect of adding at least one output toggle corresponding to at least one output toggle of N1 for which a corresponding toggle is determined to be lacking in the intermediate circuit.

A computer readable medium encoded with code to cause performance of a process of circuit synthesis comprising:

• building up a second circuit N2 that is toggle equivalent to a first circuit (N1), by using a computer running a process to produce sequence of circuits N2(l) through N2(k),
• wherein producing each circuit N2(i) in the sequence where i=1, . . . k, includes acts of,
• a) adding at least one first gate to a circuit N2(i-1);
• b) wherein adding the at least one first gate to the circuit N2(i-1) has the effect of eliminating at least one toggle of circuit N2(i-1) that lacks a corresponding output toggle in circuit N1;
• c) wherein N2(i) ) includes N2(i-1) as modified by the addition of the at least one first gate and outputs of N2(i-1) form a cut of N2(i);
• d) wherein output toggling of circuit N1 implies output toggling of circuit N2(i-1);
• and
• e) wherein output toggling of N2(i) strictly implies output toggling of N2(i-1).

A computer readable medium encoded with code to cause performance of a process of producing a circuit comprising:

• using a computer running a process to produce a circuit N2(i) from a circuit N2(i-1), that is toggle equivalent to a first circuit (N1), that includes the acts of,
• identifying one or more output toggles in circuit N2(i-1) that lack a corresponding output toggle in a circuit N1;
• adding at least one first gate to circuit N2(i-1) that has the effect of removing at least one toggle of the one or more identified output toggles in circuit N2(i-1) that lack a corresponding output toggle in circuit N1;
• determining whether there are one or more output toggles in N1 that lack a corresponding output toggle in an intermediate circuit defined by N2(i-1) as modified by the addition of the at least one first gate;
• and
• when one or more corresponding toggles in the intermediate circuit are determined to be lacking, then adding one or more gates to circuit N2(i-1) that have the effect of adding at least one output toggle corresponding to at least one output toggle of N1 for which a corresponding toggle is determined to be lacking in the intermediate circuit.

A system to synthesize a circuit comprising:

• means for building up second circuit N2 that is toggle equivalent to a first circuit (N1), by producing a sequence of circuits N2(l) through N2(k),
• wherein producing each circuit N2(i) in the sequence where i=1 . . . , k, includes acts of,
• a) adding at least one first gate to a circuit N2(i-1);
• b) wherein adding the at least one first gate to the circuit N2(i-1) has the effect of eliminating at least one toggle of circuit N2(i-1) that lacks a corresponding output toggle in circuit N1;
• c) wherein N2(i) includes N2(i-1) as modified by the addition of the at least one first gate and outputs of N2(i-1) form a cut of N2(i);
• d) wherein output toggling of circuit N1 implies output toggling of circuit N2(i-1);
• and
• e) wherein output toggling of N2(i) strictly implies output toggling of N2(i-1).