الگوریتم اکتشافی برای به حداقل رساندن محدودیت نقص ماشین مشخص

Minimization of incompletely specified finite state machines (FSMs) is an important task in the optimal design of sequential circuits, since it enhances effective use of chip area, aid in test generation and coding. The state reduction techniques tend to be complex as minimization of incompletely specified FSM is an NP-complete problem. Most of the previous approaches start with the strategy of satisfying the cover condition and then handle the closure condition. Adequate attention was not given for solving the minimization problem by switching orders between the two conditions. In this paper we present a new heuristic algorithm that starts with the closure condition and then turns to the cover condition. The algorithm employs the void-prime concept to explore the search space efficiently and effectively. The algorithm is straightforward, easily programmable on a digital computer and more efficient than the existing techniques. The effectiveness of the proposed heuristic algorithm (designated as VOID) is demonstrated by comparing our results with the most recent work on a large number of FSMs, including the MCNC FSM benchmarks.

A finite state machine (FSM) is a model used for the development of various computation structures like sequential circuits, iterative networks, etc. In many areas like digital communication systems, digital control systems, microprocessor control circuits, communication protocols and so on, sequential machines are encountered. For various reasons, the state transitions or outputs are not completely specified. An incompletely specified FSM is the one where either the next state or the output is not specified for at least one (input, output) pair. It often happens that there exist some states whose functions can be accomplished by other states thereby reducing the number of states [22]. State reduction can make the machine operation easier for the designer to understand and reduce variables to be encoded, resulting in saving of the silicon area. State minimization also plays an important role in fault-detectable and fault-tolerant design of sequential machines. The problem of minimization of incompletely specified sequential machines is an NP-complete problem [3] and has been studied by several authors [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21] and [22]. The state minimization techniques, in general, involve the generation of suitable compatibility classes (such as maximal compatibles or prime compatibles) and derivation of a minimal closed cover. A general theory for incompletely specified machines was first developed by Paul and Unger [13]. Different compatible classes are being proposed by authors as a starting point to arrive at a reduced machine. The initial attempt was to use maximal compatibles as the input set. Pager [5], Higuchi et al. [7], Sanchez et al. [10], Kannan et al. [11] and Avedillo et al. [14] suggested the use of a set of maximal compatibles as the input set. Even though this class may represents a smaller input set, it is a well-known fact that a minimum closed cover composed uniquely of maximal compatibles is not guaranteed [5]. Later, Grasselli and Luccio [1] developed the concept of prime classes which assures a minimal solution. Prime classes were used by Rho et al. [8] and [9], Gupta et al. [15], Bennets [16], Ruchir et al. [18] and DeSarkar et al. [19]. The number of this class of compatibles might be too large which makes the generation procedure for this class of compatibles tedious. Compatible pairs is another input set which has received little attention [9] due to the fact that it generates a huge input set. Rao and Biswas [4] defined a set of symbolic compatibles which constituted a smaller set than prime compatibles and also guaranteed a solution. But generation of this class of compatibles involves elaborate deletion procedures. Several techniques have been proposed to derive a minimal closed cover from the compatibility classes. The existing techniques are tailored to address a particular class of input compatibles. Sanchez et al. [10] use a genetic algorithm to select a subset of maximal compatibles to find the solution. Kannan et al. [11] present two heuristic algorithms (Lean set and Large set approach) in which they start with a set of maximal compatibles and find the minimal cover by removing the repeated states and then adding the states to fulfill the closure constraints. Avedillo et al. [14] heuristic builds up closed cover by selecting maximal compatibles one by one until both covering and closure constraints are satisfied to generate near-minimal solutions. These algorithms assume that the minimal closed cover should contain at least one maximal compatible which is not the case. Grasselli and Luccio [1] used Integer Linear Programming approach which was enhanced by the application of bounds by Rho et al. [9] to find a minimal closed cover. Ruchir et al. [18] employed a tight lower bound and ordered generating sequence to create a smaller search space and to build up the solution by finding the extended closure class. Desarkar et al. [19] find all the prime closed sets of the machine and then look for the smallest set that cover all the states of a given machine. These methods are guaranteed to produce at least one minimum state cover, although they may yield a number of such covers. Gupta et al. [15] introduced some rules into the search for a closed cover with less computations. Several other techniques have been proposed (see [2] for an extensive bibliography). For a solution to the state minimization problem to be considered valid, it has to fulfill two conditions: (i) cover condition, which means that the solution has to contain all the states of FSM, (ii) closure condition, which means that for every compatible contained in the set, all its implied compatibles are also contained in the set. The solution fulfilling both the conditions is called a closed cover. The goal of the minimization problem is to find a minimal closed cover. Most of the previous approaches start with the strategy of first satisfying the cover condition and then handling the closure condition. Not much attention has been directed to explore solving the minimization problem by switching the order of the two conditions. Because of the intractable nature of the state minimization problem and its importance in the ever increasing demand for optimal design of sequential circuits, an efficient algorithm for the state minimization problem is desirable to obtain the best possible solution within an acceptable cpu time. We are presenting a new heuristic algorithm, designated as VOID, that starts with the closure condition and then turns to the cover condition by making use of void-primes. The rest of the paper is organized as follows: In Section 2, we briefly describe some basic definitions and notations that simplify our discussion. Section 3 describes the details of the proposed algorithm for state reduction with the help of an illustrative example. Experimental results are reported in Section 4 and finally, Section 5 concludes the paper.

State minimization of incompletely specified finite state machine is an important step in the FSM synthesis. In this paper we have presented an efficient algorithm for the state minimization problem. In contrast to the previous approaches, this algorithm starts with the closure constraint and then builds the solution to fulfill the cover constraint by making use of void-primes. The effectiveness of the proposed heuristic algorithm (designated as VOID) is demonstrated by comparing the results with the most recent work in the area on a large number of FSMs, including the MCNC FSM benchmarks. Although optimality of the solution is not guaranteed, in almost all of the examples we have tried, the algorithm gives the optimal results reported for these examples in literature. Future work will be directed towards making use of recent innovations in implicit methods [21] to represent the prime compatibles and to perform state minimization and state assignment concurrently [17].