Solving the State Assignment Problem Using Stochastic Search Aided with Simulated Annealing
- 1 Technical and Vocational Institute, Egypt
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.
DOI: https://doi.org/10.3844/ajeassp.2009.703.707
Copyright: © 2009 Walid M. Aly. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
- 3,600 Views
- 2,773 Downloads
- 8 Citations
Download
Keywords
- Simulated annealing
- digital circuit design
- state assignment