Metamorphosis: state assignment by retiming and re-encoding

This paper presents Metamorphosis-a novel technique for optimal 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 encoding heuristics on the final design cost. The technique is illustrated through performance driven synthesis of FSM and extensions to handle other cost metrics is outlined.