FACTORIZING FSMS WITH MODIFY AND RESTORE METHOD

Implementation of large finite-state machines (FSM's) as smaller inter acting machines, by factorizing them and interconnecting the factored and factoring FSM's in such a way so as to maintain the functionality of the original machine usually leads to an improvement in the perform ance (that is, reduction in delay) of the original machine, Exact fact ors, if present in an FSM, can result in the most effective way of fac torization, However, it has been found that most of the FSM's are not exact factorizable. In this paper, we have presented a scheme called t he modify and restore (MAR) method which attempts to make FSM's exact factorizable even if the original FSM is not directly exact factorizab le. This is done by making minor changes in the next state space of th e original FSM while maintaining the functionality of the FSM by a res toring logic, We have tested the effectiveness of our method of factor ization followed by state assignment for both two-level and multilevel implementations, Experimental results on the MCNC benchmark examples have shown significant improvement in delays of the final realization.