IEICE TRANSACTIONS on Information
An lterative Improvement Method for State Minimization of Incompletely Specified Finite State Machines
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 two-level 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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E80-D No.10 pp.993-1000
- Publication Date
- 1997/10/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Issue on Synthesis and Verification of Hardware Design)
- Category
- Logic Design
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hiroyuki HIGUCHI, Yusuke MATSUNAGA, "An lterative Improvement Method for State Minimization of Incompletely Specified Finite State Machines" in IEICE TRANSACTIONS on Information,
vol. E80-D, no. 10, pp. 993-1000, October 1997, doi: .
Abstract: 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 two-level 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e80-d_10_993/_p
Copy
@ARTICLE{e80-d_10_993,
author={Hiroyuki HIGUCHI, Yusuke MATSUNAGA, },
journal={IEICE TRANSACTIONS on Information},
title={An lterative Improvement Method for State Minimization of Incompletely Specified Finite State Machines},
year={1997},
volume={E80-D},
number={10},
pages={993-1000},
abstract={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 two-level 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.},
keywords={},
doi={},
ISSN={},
month={October},}
Copy
TY - JOUR
TI - An lterative Improvement Method for State Minimization of Incompletely Specified Finite State Machines
T2 - IEICE TRANSACTIONS on Information
SP - 993
EP - 1000
AU - Hiroyuki HIGUCHI
AU - Yusuke MATSUNAGA
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E80-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 1997
AB - 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 two-level 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.
ER -
English
