CPLD-oriented Synthesis of Finite State Machines

The purpose of the paper is to present a new approach to FSM synthesis for PAL-based CPLDs. The proposed approach consists of the original method of the state assignment and PAL-oriented multi-level optimization. The aim of the proposed state assignment method is to minimize the number of the PAL-based macrocells by fitting the FSM to the structure of the CPLD as good as possible. The essence of PAL-oriented multi-level optimization is to search for multi-output implicants that can be shared by several functions. Results of experiments prove that the proposed algorithm leads to significant reduction of chip area in relation to the previously published methods and vendor-tools.