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

American Journal of Engineering and Applied Sciences

Walid M. Aly¹ 

关键词: Simulated annealing;    digital circuit design;    state assignment;   

DOI  :  10.3844/ajeassp.2009.703.707

学科分类：工程和技术（综合）

来源: Science Publications

【 摘 要 】

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.

【 授权许可】

Unknown