Metamorphosis: State Assignment by Retiming and Re-encoding

This paper presents Metamorphosis1 – a novel technique for op-timal state assignment targeting multi-level logic implementations. We present an elegant matrix formulation and a graph partitioning based synthesis technique which permits both bit-constrained and unconstrained encoding of a symbolic finite state machine (FSM) represented initially with a one-hot code. Optimal state encoding is achieved by controlled retiming/re-encoding and resynthesis of the symbolic FSM. The synthesis is guided directly by the cost function (optimization criterion) rather than speculative estimates of the en-coding heuristics on the final design cost. The technique is illustrated through performance driven synthesis of FSM and extensions to han-dle other cost metrics is outlined.