摘要
The problem of state reduction in a finite state machine (FSM) is important to reduce the complexity of a sequential circuit. In this paper, we present an efficient algorithm for state minimization in incompletely specified state machines. This algorithm employs a tight lower bound and a fail-first heuristic, and generates a relatively small search space from the prime compatibles. It utilizes efficient pruning rules to further reduce the search space and finds a minimal closed cover. The technique guarantees the elimination of all the redundant states in a very short execution time. Experimental results with a large number of FSM's including the MCNC FSM benchmarks, are presented. The results are compared with other recent work in the area.
- 出版日期1993-6