Automated synthesis of finite state machines
L. N. Kannan, D. Sarma · 1990
This dissertation addresses the problem of automated synthesis of finite state machines from high-level descriptions. The aim of this research is to develop a system for the design of finite state machines by developing and implementing efficient algorithms to solve some of the optimization problems that arise in the synthesis of finite state machines. Specifically, the dissertation deals with the following aspects of finite state machine synthesis. (1) Finite state machine specification. Automated translation of HDL descriptions of finite state machines into state tables. (2) Finite state machine minimization. Development of fast heuristic algorithms for the efficient minimization of completely specified finite state machines. (3) Logic array optimization. Folding (compaction) of logic arrays using a combination of simulated annealing and heuristic methods to achieve fast, effective compaction. (4) Targets for finite state machine realization. Automated generation of the layout of the finite state machine using a storage logic array (SLA), or a programmable logic array (PLA) as the target. The above problems have been studied, and the techniques developed to solve them have been implemented in a set of computer programs: FDLC, FSMRED, GAMIN-SA, SLAGEN and MSLA. These are part of an integrated VSLI design system for the synthesis of finite state machines. The optimization techniques developed have been compared, using standard benchmarks, with the existing techniques and have been shown to perform extremely well.