Metamorphosis: State Assignment by Retiming and Re-encoding

This paper presents Metamorphosis 1 -- a novel technique for optimal state assignment targeting multi-level logic implementations. We present a new formulation and synthesis techniques for the state assignment problem based on controlled retiming and re-encoding of a symbolically represented finite state machine (FSM) represented initially with a one-hot code. Metamorphosis is a new design paradigm that integrates the structural and behavioral design methodologies in a synergistic fashion and leverages the additional degrees of freedom to the synthesis of optimal FSM. The proposed technique differs drastically from previous approaches in that the encoding process is guided directly by the cost function (optimization criterion) rather than speculative estimates of the encoding heuristics on the final design cost. We present efficient encoding algorithms for both unconstrained and bit-constrained encoding problems. Another novel feature of Metamorphosis is that it permits the explora..