A Technology Mapping of FSMs Based on a Graph of Excitations and Outputs

TLDR

The graph of outputs, previously used for technology mapping of multi‑output functions in PAL‑based programmable structures, is generalized in this work. The study proposes a logic synthesis method for FSMs targeting PAL‑based complex programmable logic devices, illustrated with simple examples. The approach simultaneously synthesizes transition and output functions using a novel graph of excitations and outputs, and the algorithm is benchmarked against other methods on FSMs mapped to k‑term PAL logic blocks. The novel multilevel optimization reduces area and logic levels, outperforming other methods, especially for larger FSMs.

Abstract

A logic synthesis for finite-state machines (FSMs) aimed at programmable array logic (PAL)-based complex programmable logic devices is proposed here. This approach consists of the simultaneous synthesis of a transition function and an output function. The main contribution is the novel multilevel optimization of an FSM. In this process, a new form of graph is used, i.e., a graph of excitations and outputs. This is a generalization of the graph of outputs that has previously been used in the process of technology mapping of multi-output functions in PAL-based programmable structures. The main idea, the theoretical background, and a precise algorithm are illustrated by means of simple examples. The proposed algorithm was compared with other approaches by synthesizing the FSM benchmarks and mapping the solutions to k-term PAL-based logic blocks. The obtained results are compared on the basis of the area (number of logic blocks) and speed (number of logic levels). The proposed approach is especially effective for larger FSMs.