State reduction of incompletely specified finite sequential machines
Orhan Uçar · 2005
This paper is concerned with the problem of synthesizing a class of digital circuits, sequential circuits, more specifically state reduction of of incompletely specified sequential circuits. State reduction is an important step in the design of the synchronous and asynchronous sequential circuits. The algorithms which are developed for state reduction, are also applied to other steps of the logic synthesis, such as multiple-output Boolean minimization, state encoding and unite/binate covering problems. In this paper three algorithms are presented to find a minimal equivalent of a given incompletely specified finite sequential machine. These algorithms use a new concept; closed paths constituted by compatibles or prime compatibles. This closed paths concept and an algorithm which uses this concept is not observed in the literature. These algorithms are implemented in an efficient computer program SRC (State Reduction and Covering). SRC is run and tested on several FSMs including the MCNC FSM benchmarks and the results are given in conclusion. From the test results, it can be seen that, despite of the limited computing resources, SRC is more efficient on all benchmarks, especially on the critical benchmarks. Using these algorithms, MORP (Multiple Output Reduction Program) developed to realize m Boolean functions with n variables. State reduction methods which are developed in this work, are also applied to state encoding problem and a computer program, OPASKOD (Race-free State Assignment Program) developed.