Reencoding for Cycle-Time Minimization under Fixed Encoding Length

This paper presents efficient reencoding and resynthesis algorithms for cycle-time minimization of multilevel implementations of synchronous finite state machines (FSMs) under a fixed encoding length. The proposed technique is applicable to both gate-level and technology independent synchronous network representations. We present two algorithms for identifying useful reencodings -- one is based on Boolean cube representation applicable to technology independent synchronous networks and the other employs recursive learning techniques appropriate for gate netlists. We show that the proposed XOR/XNOR based reencoding technique explores a suffciently rich set of encodings to identify implementations with smaller cycle-times. The Boolean and structural interpretations of reencoding are explored and its relationship to isomorphic sequentially redundant faults is presented. We also show that the reencoded circuit always has a valid initial state and present a simple procedure to derive it. Th..