АЛГОРИТМ СИНТЕЗА КОМБИНАЦИОННЫХ ЛОГИЧЕСКИХ СХЕМ НА ОСНОВЕ ЭВОЛЮЦИОННОГО ПОДХОДА
Аннотация
Появление новых технологий изготовления компонентов цифровых электронных уст-
ройств привело к необходимости повышения эффективности методов автоматизирован-
ного проектирования. Увеличение требований к элементам вызывает рост размерности
решаемых задач. Для решения задач, которые ранее невозможно было автоматизировать
разрабатываются новые методы и программные приложения. Перед специалистами сто-
ит задача разработки фундаментальных принципов построения систем проектирования
нового поколения. Разработка устройств обладающих такими характеристиками как:
надежность, живучесть, автоматическое устранение повреждений, является актуальной
задачей. В данной работе предлагается подход к решению задачи синтеза комбинационныхсхем на основе использования методов эволюционного проектирования. Под эволюционным
проектированием технической системы понимается целенаправленное использование ком-
пьютерных моделей эволюции на всех стадиях разработки системы. Целью является обес-
печение возможности проектирования в полностью автоматическом режиме. Основная
идея самореконфигурируемых аппаратных систем состоит в том, чтобы вместо аппа-
ратных систем общего назначения использовать системы, которые могут адаптировать-
ся под специфику выполняемого программного обеспечения. Синтез программируемой схе-
мы строится по принципу «восходящего» проектирования – от низшего к высшему уровню.
Это позволяет конфигурировать аппаратную часть индивидуально, посредством про-
граммирования логических элементов. Для реализации данной задачи используют эволюци-
онные алгоритмы. Логические функции могут быть описаны комбинационными схемами.
Одним из достоинств комбинационных схем является их высокое быстродействие. Задача
состоит в разработке структуры комбинационной логической схемы на основе заданной
таблицы истинности и номенклатуры логических элементов. В работе был предложен
эволюционный алгоритм синтеза комбинационных логических схем. Были разработаны
методика кодирования альтернативных решений и модифицированные эволюционные опе-
раторы для синтеза новых решений. Выполнена программная реализация предложенного
алгоритма. Проведенные вычислительные эксперименты подтвердили правильность вы-
бранного подхода. Использование эволюционных методов для синтеза комбинационных
логических схем позволяет повысить интеллектуальность систем проектирования.
Литература
design automation. CRC Press, New York, USA, 2009.
2. Cohoon J.P., Karro J., Lienig J. Evolutionary Algorithms for the Physical Design of VLSI Circuits.
Advances in Evolutionary Computing: Theory and Applications, Ghosh A., Tsutsui S.
(eds.). Springer Verlag, London, 2003.
3. Baqais A.A.B. A Multi-view Comparison of Various Metaheuristic and Soft Computing Algorithms,
I.J. Mathematical Sciences and Computing, 2017, l.3 (4), pp. 8-19.
4. Tarasov V.B., Golubin A.V. Evolyutsionnoe proektirovanie: na granitse mezhdu
proektirovaniem i samoorganizatsiey [Evolutionary design: on the border between design
and self-organization], Izvestiya TRTU [Izvestiya TSURE], 2006, No. 8 (63), pp. 77-82.
5. Sushil J. Louis and Gregory J. Rawlins. Using genetic algorithms to design structures. Technical
Report 326, Computer Science Department, Indiana University. Bloomington, Indiana, 1991.
6. Koza J.R., Bennett F.H., Andre D., Keane M.A. Automated WYWIWYG design of both the
topology and component values of electrical circuits using genetic programming, Proceedings
of the First Annual Conference on Genetic Programming, Cambridge, Masachussetts, Stanford
University. The MIT Press, 1996, pp. 123-131.
7. Blondet B., Roxby P.J., Keller E., McMillan S., Sundararajan P. A Self-reconfiguring Platform
// Field-Programmable Logic and Applications. 13th International Conference, FPL 2003 Proceedings,
pp. 565-574.
8. Eldredge J.G., Hutchings B.L. Run-Time Reconfiguration: A Method for Enhancing the Functional
Density of SRAM-Based FPGAs, in Journal of VLSI Signal Processing, 1996, Vol. 12,
pp. 67-86.
9. Louis S.J., Rawlins G.J.E. Syntactic Analysis of Convergence in Genetic Algorithms. Foundations
of Genetic Algorithms, 2 ed. by L.D. Whitley. San Mateo, CA: Morgan Kaufmann, 1993, 141 p.
10. Louis S.J., Rawlins J.E. Designer genetic algorithms: genetic algorithms in structure design //
ICGA-91 // in Proceedings of the Fourth International Conference on Genetic Algorithms /
Belew, K.K. and Booker, L.B., eds. Booker, Morgan Kaufman, San Manteo, CA, 1991.
11. Higuchi T. et al. Evolvable hardware and its applications to pattern recognition and fault-tolerant
systems, in Towards Evolvable Hardware: An International Workshop, Lausanne, Swiss, 1995,
2. Chapter of book: Towards Evolvable Hardware: The evolutionary engineering approach,
Sanchez E., and Tomassini M., eds. Vol. 1062. LNCS, Springer-Verlag, 1996, 118 p.
12. Hemmi H., Mizoguchi J., Shimonara K. Development and evolution of hardware behaviours,
in Towards Evolvable Hardware: An International Workshop, Lausanne, Swiss, 1995, 2.
Chapter of book: Towards Evolvable Hardware: The evolutionary engineering approach,
Sanchez E., and Tomassini M. eds. Vol. 1062. LNCS, Springer-Verlag, 1996.
13. Zebulum R.S., Pacheco M.A., Vellasco M.M. Evolutionary Electronics: Automatic Design of
Electronic Circuits and Systems by Genetic Algorithms. USA, CRC Press LLC, 2002.
14. Yang S. Logic synthesis and optimization benchmark user guide version 3.0, MCNC, 1991.
15. Gladkov L., Kureychik Vl., Kureychik V., Sorokoletov P. Bio-inspired methods in optimization.
Moscow: Fizmatlit, 2009.
16. Gladkov L.A., Gladkova N.V., Gusev N.Y., Semushina N.S. Integrated approach to the solution
of computer-aided design problems, Proceedings of the 4th International Scientific Conference
“Intelligent Information Technologies for Industry” (IITI’19). Advances in Intelligent Systems
and Computing. Springer, Cham, 2020, Vol. 1156, pp. 465-476.
17. Gladkov L.A., Gladkova N.V., Leiba S.N., Strakhov N.E. Development and research of the
hybrid approach to the solution of optimization design problems, Advances in Intelligent Systems
and Computing. Vol. 875. International Conference on Intelligent Information Technologies
for Industry IITI'18. Springer Nature Switzerland AG, 2019, Vol. 2, pp. 246-257.
18. Gladkov L.A., Veselov G.E., Gladkova N.V. Development and research of algorithms for the
synthesis of combinational logic circuits based on the evolutionary approach, Lecture Notes in
Networks and Systems. Vol. 776 “Proceedings of the 7th International Scientific Conference
“Intelligent Information Technologies for Industry” (IITI’23)”. Springer Nature Switzerland
AG, 2023, Vol. 1, pp. 210-221.
19. Batyrshin I. etc. Fuzzy hybrid systems. Theory and practice. Moscow: Fizmatlit, 2007.
20. Borisov V., Kruglov V., Fedulov A. Nechetkie modeli i seti (Fuzzy models and networks).
Moscow: Goryachaya liniya – Telekom, 2007.
