A new method for the state reduction of incompletely specified finite sequential machines
Abstract
A new method for the state reduction of incompletely specified Finite Sequential Machines is proposed. Fundamental theorem of minimization theory states that, given an incomplete state table, another state table specifying the same external behavior corresponds to each closed set of compatibility classes which covers all internal states of the given table. The new heuristic algorithm builds up a closed cover for a given state table selecting maximal compatibles (MCs) one by one until both covering and closure requirements are satisfied. Near-minimal solutions are so incrementally generated. The process is dynamic as the consequences of adding a particular MC are precisely determine. The new algorithm is designed for speed and has proven to be extremely valuable in situations where fast but good optimization is required. The algorithm has been programmed and results on a wide set of machines shown.
References
[1]
M. A. Perkowski, J. Liu: "Generation and Optimization of Finite State Machines from Parallel Program Graphs," DIADES Research Group Report 10/89, Dept. EE PSU.
[2]
R. Rudell, A. Sangivanni-Vincentelli and G. De Micheli: "A Finite-State Machine Sunthesis System," Proc. 1985 Int. Symp. on Circ. and Syst., Kyoto, Japan, pp. 647--650.
[3]
F. J. Hill and G. R. Peterson: "Switching Theory and Logical Design," John Wiley and Sons, 1981.
[4]
Z. Kohavi: "Switching and Finite Automata Theory". New York, McGraw Hill, 1970.
[5]
S. House: "A New Rule for Reducing CC Tables," IEEE Trans. on Computers (Short Notes), Nov. 1970.
[6]
J. L. Huertas and J. M. Quintana: "A New Method for the Efficient State-Assignment of PLA-Based Sequential Machines," Proc. 1988 Int. Conf. on CAD, pp. 156--159.
[7]
S. Ginsburg: "On the Reduction of Superfluous States in a Sequential Machine," The National Cash Register Company, Hawthorne, California, 1959.
[8]
M. C. Paul and S. H. Unger: "Minimizing the Number of States in Incompletely Specified Sequential Switching Functions," IRE Trans. on Computers, vol EC-8, pp. 356--367, Sept. 1959.
[9]
A. Grasselli and F. Luccio: "A Method for Minimizing the Number of Internal States in Incompletely Specified Sequential Networks," IEEE Trans. Electron. Comp., Vol. EC-14, pp. 350--359, June 1965.
[10]
R. G. Bennetts, J. L. Washington and D. W. Lewin: "A Computer Algorithm for State Table Reductions," IERE Radio and Electron. Eng., Vol. 42, pp. 513--520, Nov. 1972.
[11]
N. N. Biswas: "State Minimization of Incompletely Specified Sequential Machines," IEEE Trans. on. Computers, Vol. C-23, pp. 80--84, Jan. 1974.
[12]
S. C. De Sarkar, A. K. Basu and A. K. Choudhury: "Simplification of Incompletely Specified Flow Tables with the Help of Prime Closed Sets," IEEE Trans. on Computers (Short Notes), Vol. C-18, pp 953--956, Oct. 1969.
[13]
S. H. Unger: "Asynchronous Sequential Switching Circuits," Wiley-Interscience, New York, 1969.
[14]
B. E. Gillet: "Introduction to Operations Research," McGraw Hill, 1976.
[15]
R. W. House, L. D. Nelson and T. Rado: "Computer Studies of a Certain Class of Linear Integers Problems," in Recent Advances in Optimization Techniques, A. Lavi and T. P. Vogl, Eds. New York: Wiley 1966.
Recommendations
On state reduction of incompletely specified finite state machines
State reduction of incompletely specified finite state machines (ISFSMs) is an important task in optimization of sequential circuit design and known as an NP-complete problem. Removal of redundant states reduces the logic, because of this, chip area ...
State Minimization of Incompletely Specified Sequential Machines
This paper describes a new method for the state minimization of incompletely specified sequential machines. Previously described methods start with generating all maximal compatibles of states of the original incompletely specified machine and then try ...
State Reduction in Incompletely Specified Finite-State Machines
The problem of reducing the number of states in an arbitrary incompletely specified deterministic finite-state machine to k states (for a given k) has proven intractible to solution within "reasonable" time; most techniques seem to require exponential ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- EDAC Association
- SIGDA: ACM Special Interest Group on Design Automation
Publisher
IEEE Computer Society Press
Washington, DC, United States
Publication History
Published: 12 March 1990
Check for updates
Qualifiers
- Article
Upcoming Conference
DAC '25
- Sponsor:
- sigda
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 184Total Downloads
- Downloads (Last 12 months)11
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in