Publication Details

How to Evolve Complex Combinational Circuits From Scratch?

VAŠÍČEK, Z.; SEKANINA, L. How to Evolve Complex Combinational Circuits From Scratch?. In 2014 IEEE International Conference on Evolvable Systems Proceedings. Piscataway: Institute of Electrical and Electronics Engineers, 2014. p. 133-140. ISBN: 978-1-4799-4480-4.
Czech title
Jak evolučně navrhovat složité kombinační obvody?
Type
conference paper
Language
English
Authors
Vašíček Zdeněk, doc. Ing., Ph.D. (DCSY)
Sekanina Lukáš, prof. Ing., Ph.D. (DCSY)
Keywords

evolutionary design, digital circuit, binary decision diagram

Abstract

One of the serious criticisms of the evolutionary circuit design method is that
it is not suitable for the design of complex large circuits. This problem is
especially visible in the evolutionary design of combinational circuits, such as
arithmetic circuits, in which a perfect response is requested for every possible
combination of inputs. This paper deals with a new method which enables us to
evolve complex circuits from a randomly seeded initial population and without
providing any information about the circuit structure to the evolutionary
algorithm. The proposed solution is based on an advanced approach to the
evaluation of candidate circuits. Every candidate circuit is transformed to
a corresponding binary decision diagram (BDD) and its functional similarity is
determined against the specification given as another BDD. The fitness value is
the Hamming distance between the output vectors of functions represented by the
two BDDs. It is shown in the paper that the BDD-based evaluation procedure can be
performed much faster than evaluating all possible assignments to the inputs. It
also significantly increases the success rate of the evolutionary design process.
The method is evaluated using selected benchmark circuits from the LGSynth91 set.
For example, a correct implementation was evolved for a 28-input frg1 circuit.
The evolved circuit contains less gates (a 57% reduction was obtained) than the
result of a conventional optimization conducted by ABC. 

Published
2014
Pages
133–140
Proceedings
2014 IEEE International Conference on Evolvable Systems Proceedings
Conference
IEEE Symposium Series on Computational Intelligence, Orlando, US
ISBN
978-1-4799-4480-4
Publisher
Institute of Electrical and Electronics Engineers
Place
Piscataway
DOI
10.1109/ICES.2014.7008732
EID Scopus
2-s2.0-84946687195
BibTeX 
@inproceedings{BUT111620,
  author="Zdeněk {Vašíček} and Lukáš {Sekanina}",
  title="How to Evolve Complex Combinational Circuits From Scratch?",
  booktitle="2014 IEEE International Conference on Evolvable Systems Proceedings",
  year="2014",
  pages="133--140",
  publisher="Institute of Electrical and Electronics Engineers",
  address="Piscataway",
  doi="10.1109/ICES.2014.7008732",
  isbn="978-1-4799-4480-4",
  url="https://www.fit.vut.cz/research/publication/10673/"
}
Files
Back to top