FSM State-Encoding for Area and Power Minimization Using Simulated Evolution Algorithm

Abstract

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 isgiven a Goodness value derived from a matrix representation of the desired adjacency graph (DAG) proposed byAmaral et.al [2]. We use the (DAGa) proposed in previous studies to optimize the area, and propose a new DAGpand employ it to reduce the power dissipation. In the process of evolution, those states that have high Goodness havea smaller probability of getting perturbed, while those with lower Goodness can be easily reallocated. States areassigned to cells of a Karnaugh-map, in a way that those states that have to be close in terms of Hamming distanceare assigned adjacent cells. Ordered weighed average (OWA) operator proposed by Yager [3] is used to combine thetwo objectives. Results are compared with those published in previous studies, for circuits obtained from the MCNCbenchmark suite. It was found that the SimE heuristic produces better quality results in most cases, and/or in lessertime, when compared to both deterministic heuristics and non-deterministic iterative heuristics such as GeneticAlgorithm.