On the Optimization Power of Retiming and Resynthesis Transformation

Retiming and resynthesis transformations can be used for op-timizing the area, power, and delay of sequential circuits. Even though this technique has been known for more than a decade, its exact optimization capability has not been for-mally established. We show that retiming and resynthe-sis can exactly implement 1-step equivalent state transition graph transformations. This result is the strongest to date. We also show how the notions of retiming and resynthe-sis can be moderately extended to achieve more powerful state transition graph transformations. Our work will provide theoretical foundation for practical retiming and resynthesis based optimization and verification.