Article

Article title EVOLUTIONARY SYNTHESIS OF FINITE STATE MACHINES
Authors A.N. Bereza, M.V. Lyashov
Section SECTION VI. COMPUTER COMPLEXES OF NEW GENERATION AND NEUROCOMPUTERS
Month, Year 07, 2011 @en
Index UDC 004.27; 007.52
DOI
Abstract A complex digital system consists of combinational and sequential logic circuits, and the behavior of sequential circuits can be described by a finite state machines. One of the most important steps in the synthesis of finite state machines is a state assignment. The state assignment task is searching the combinations triggers to the finite state machines. In modern systems, synthesis of coding the internal states of a finite automaton algorithms are used NOVA, MUSTANG and their modifications. However, state assignment of finite state machines is far from optimum. This article describes an evolutionary algorithm developed by coding the internal states of a finite state machines, which showed better results compared to traditional methods.

Download PDF

Keywords Evolutionary synthesis; NP task; finite state machines; genetic algorithms.
References 1. Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Логические основы проектирования дискретных устройств. – М.: Физматлит, 2007. – 592 с.
2. Соловьев В.В. Логическое проектирование цифровых систем на основе программируемых логических интегральных схем. – М.: Горячая Линия - Телеком, 2008. – 376 с.
3. Nedjah N. Evolvable Machines: Theory and Practice // Studies in Fuzziness and Soft Computing. – 2004. – Vol. 161. – 260 с.
4. Chyz˙ y M., Kosinґski W. Genetic Algorithm for the State Assignment Problem, Communications of the 10th International Symposium Intelligent Information Systems, Zakopane, Poland, 2001. – P. 7-11.
5. Belgasem A., Kalganova T. and Almaini A. (2002) Extrinsic Evolution of Finite State Machine. ACDM2002, UK. I. C. Paimee (Ed.) Published by Springer. – P. 157-168.
6. Гладков Л.А., Курейчик В.В. Генетические алгоритмы. – М.: Физматлит. 2006. – 320 с.
7. Ken McElvain. LGSynth93 Benchmark Set: Version 4.0. – Mentor Graphics. 1993. – 96 с.
8. Курейчик В.М. Биоиспирированный поиск с использованием сценарного подхода // Известия ЮФУ. Технические науки. – 2010. – № 7 (108). – С. 7-12.
9. Курейчик В.В., Курейчик В.М., Родзин С.И. Концепция эволюционных вычислений, инспирированных природными системами // Известия ЮФУ. Технические науки. – 2009. – № 4 (93). – C. 16-24.

Comments are closed.