Research Article Open Access

Solving the State Assignment Problem Using Stochastic Search Aided with Simulated Annealing

Walid M. Aly1
  • 1 ,
American Journal of Engineering and Applied Sciences
Volume 2 No. 4, 2009, 703-707

DOI: https://doi.org/10.3844/ajeassp.2009.703.707

Submitted On: 25 July 2009 Published On: 31 December 2009

How to Cite: Aly, W. M. (2009). Solving the State Assignment Problem Using Stochastic Search Aided with Simulated Annealing. American Journal of Engineering and Applied Sciences, 2(4), 703-707. https://doi.org/10.3844/ajeassp.2009.703.707

Abstract

Problem statement: Solving the state assignment problem means finding the optimum assignment for each state within a sequential digital circuit. These optimum assignments will result in decreasing the hardware realization cost and increasing the reliability of the digital circuit. Unfortunately, the state assignment problem belongs to the class of nondeterministic polynomial time problems (NP complete) which requires heavy computations. Different attempts have been made towards solving the problem with reasonable recourses. Approach: This study presented a methodology for solving the state assignment problem, the methodology conducted a neighborhood search while using a heuristic to determine the fitness of solution. To avoid being trapped at a local optimum solution, a metaheuristic (simulated annealing) was utilized for deciding whether a new solution should be accepted. A case study was included to demonstrate the proposed procedure efficiency. Results: The proposed approach finds the optimum assignment for the case study. Conclusion: In this study, we explored the usage of a stochastic search technique inspired by simulated annealing to solve the problem of the state assignment problem. This proved the efficiency of the methodology.

  • 1,191 Views
  • 1,525 Downloads
  • 5 Citations

Download

Keywords

  • Simulated annealing
  • digital circuit design
  • state assignment