Heuristic State Reduction Methods of Incompletely Specified Machines Preceding to Satisfy Covering Condition

Masaki HASHIZUME  Takeomi TAMESADA  Takashi SHIMAMOTO  Akio SAKAMOTO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E81-A   No.6   pp.1045-1054
Publication Date: 1998/06/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section of Papers Selected from ITC-CSCC'97)
Category: VLSI Design Technology and CAD
Keyword: 
incompletely specified machine,  maximal compatible set,  state reduction,  

Full Text: PDF>>
Buy this Article



Summary: 
This paper presents two kinds of simplification methods for incompletely specified sequential machines. The strategy of the methods is that as many states in original machines are covered in the simplification processes as possible. The purpose of the methods is to derive a simplified machine having either the largest maximal compatible set or its subset. With the methods, one of the minimal machines can not be always derived, but a near-minimal machine can be obtained more quickly with less memory, since they need not derive all the compatible sets. In this paper, the effectiveness of the methods is checked by applying them to simplification problems of incompletely specified machines generated by using random numbers, and of the MCNC benchmark machines. The experimental results show that our methods can derive a simplified machine quickly, especially for machines having a great number of states or don't care rate.