
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

An lterative Improvement Method for State Minimization of Incompletely Specified Finite State Machines
Hiroyuki HIGUCHI Yusuke MATSUNAGA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E80D
No.10
pp.9931000 Publication Date: 1997/10/25 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Issue on Synthesis and Verification of Hardware Design) Category: Logic Design Keyword: state minimization, state reduction, finite state machines, binate covering problem, compatible sets,
Full Text: PDF>>
Summary:
This paper proposes a heuristic algorithm for state minimization of incompletely specified finite state machines (FSMs). The strategy is similar to that in ESPRESSO, a wellknown heuristic algorithm for twolevel logic minimization. It consists of generating an initial solution, the set of maximal compatibles, and attempting to apply a series of transformations to the solution. The main transformation is to reduce each compatible in the solution and delete unnecessary compatibles by iterative improvements. Other transformations, such as expansion and merging of compatibles, are also introduced for further reduction. When the number of compatibles is likely to be too large to handle explicitly, they are represented by a Binary Decision Diagram. Experimental results show that the proposed method finds better solutions in shorter CPU times for most of the examples than conventional methods.

