Reencoding for cycle-time minimization under fixed encoding length

The 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 sufficiently 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. The effectiveness of the proposed technique is illustrated on a large set of benchmark circuits which indicates an average cycle time improvement of 15.26% for a small area overhead of 3.56% over that of performance driven combinational logic optimization.