ALGORITHM FOR SYNTHESIS OF COMBINATIONAL LOGIC CIRCUITS BASED ON THE EVOLUTIONARY APPROACH
Abstract
The emergence of new technologies for manufacturing components of digital electronic devices
has led to the need to improve the efficiency of computer-aided design methods. Increasing
requirements for elements causes an increase in the size of the problems being solved. To solve
problems that were previously impossible to automate, new methods and software applications are
being developed. Specialists are faced with the task of developing fundamental principles for constructing
next-generation design systems. The development of devices with such characteristics as
reliability, survivability, and automatic damage repair is an urgent task. This paper proposes an
approach to solving the problem of synthesizing combinational circuits based on the use of evolutionary
design methods. Evolutionary design of a technical system refers to the purposeful use of
computer models of evolution at all stages of system development. The goal is to enable fully automatic
design. The main idea of self-reconfigurable hardware systems is to replace generalpurpose
hardware systems with systems that can adapt to the specifics of the software being executed.
The synthesis of a programmable circuit is based on the principle of “bottom-up” design –
from the lowest to the highest level. This allows you to configure the hardware individually by
programming logic elements. To implement this task, evolutionary algorithms are used. Logic
functions can be described by combinational circuits. One of the advantages of combinational
circuits is their high performance. The task is to develop the structure of a combinational logic
circuit based on a given truth table and nomenclature of logical elements. The work proposed an
evolutionary algorithm for the synthesis of combinational logic circuits. A technique for encoding
alternative solutions and modified evolutionary operators for synthesizing new solutions were
developed. A software implementation of the proposed algorithm has been completed. The computational
experiments carried out confirmed the correctness of the chosen approach. The use of
evolutionary methods for the synthesis of combinational logic circuits makes it possible to increase
the intelligence of design systems.
References
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.
