FSM state-encoding for area and power minimization using simulated evolution algorithm

In this paper we describe the engineering of a non-deterministic iterative heuristic [1] known as simulated evolution (SimE) to solve the well-known NP-hard state assignment problem (SAP). Each assignment of a code to a state is given a Goodness value derived from a matrix representation of the desired adjacency graph (DAG) proposed by Amaral et.al [2]. We use the (DAG_a) proposed in previous studies to optimize the area, and propose a new DAG _p and employ it to reduce the power dissipation. In the process of evolution, those states that have high Goodness have a smaller probability of getting perturbed, while those with lower Goodness can be easily reallocated. States are assigned to cells of a Karnaugh-map, in a way that those states that have to be close in terms of Hamming distance are assigned adjacent cells. Ordered weighed average (OWA) operator proposed by Yager [3] is used to combine the two objectives. Results are compared with those published in previous studies, for circuits obtained from the MCNC benchmark suite. It was found that the SimE heuristic produces better quality results in most cases, and/or in lesser time, when compared to both deterministic heuristics and non-deterministic iterative heuristics such as Genetic Algorithm.