A New Paradigm for Dichotomy-based Constrained Encoding

Abstract

One essential step in sequential logic synthesis consists of finding a state encoding that meets some requirements, such as optimal implementation, or correctness in the case of asynchronous FSMs. Dichotomy-based constrained encoding is more general than other constrained encoding frameworks, but it is also more difficult to solve. We introduce a new formalization, called twin graph coloring, which leads to original exact and heuristic algorithms. Experimental results show that the resulting exact solver outperforms the previous approaches.

Relevant Papers

Transparencies