STATE MERGING AND STATE SPLITTING VIA STATE ASSIGNMENT - A NEW FSM SYNTHESIS ALGORITHM

In the paper the authors describe a state assignment algorithm for FSM s which produces an assignment of non-necessarily distinct, and eventu ally, incompletely specified codes. In this new approach, state reduct ion and state assignment are dealt with concurrently, and a restricted state splitting technique is explored. The algorithm is particularly appropriate for machines with compatibility relations among its states because the potentials of state merging are exploited during the stat e assignment step. The input to SMAS, the program implementing the alg orithm, is a symbolic cover of the FSM. The output is a Boolean repres entation of both next state and output functions suitable to minimise with ESPRESSO. The machines in the MCNC benchmark set are used to test the new algorithm and to compare it with a well known state assignmen t program.