Exact Essential-Hazard-Free State Minimization of Incompletely Specified Asynchronous Sequential Machines

Cheng, Fu-Chiung; Plana, Luis A.

To insure correct dynamic behaviour of asynchronous sequential machines, hazards must be eliminated for they may cause malfunctions of the whole system. However, Hazard-free state minimization has received almost no prior attention in the literature. This paper describes an exact algorithm for essential-hazard-free state minimization of incompletely specified asynchronous sequential machines. Novel techniques for the elimination of apparent and potential essential hazards are proposed and exploited in our algorithm. The algorithm has been implemented and applied to over a dozen asynchronous sequential machines. Results are compared with results of non-essential-hazard-free method SIS. Most of the tested cases can be reduced to essential hazard free flow tables.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-033-94
Published Here
February 3, 2012