State assignment of finite-state machines

The state-assignment problem of finite-state machines (FSMs) is addressed. State assignment is a mapping from the set of states (symbolic names) of an FSM to the set of binary codes with the objective of minimising the area o f the combinational circuit required to realise the FSM. It is one of the m ost important optimisation problems in the automatic synthesis of sequentia l circuits since it has a major impact on the area, speed, power and testab ility of the circuits. The problem of finding an optimal state assignment i s NP-hard. A new scheme is presented based on mean-field annealing (MFA) to solve the graph-embedding problem which is the main step in the state-assi gnment process. The MFA algorithm combines the characteristics of the simul ated annealing and the Hopfield neural network. To solve the problem by MFA , the graph-embedding problem is mapped into a neural network and an energy function is formulated. Experiments over the MCNC FSM benchmarks demonstra te that the proposed MFA algorithm can produce superior results compared wi th the specialised methods such as the MUSTANG, NOVA and genetic algorithm.