A Developmental Method for Construction of Arbitrarily Large Sorting Networks and Adders

Czech title

Vývojová metoda pro konstruckci libovolně velkých řadicích sítí a sčítaček

Type

report

Language

English

Authors

Bidlo Michal, doc. Ing., Ph.D. (DCSY)

URL

http://www.fit.vutbr.cz/~bidlom/Papers/2005/research_report2005.pdf

Keywords

Genetic algorithm, development, digital circuits design, sorting network, binary adder

Abstract

The paper deals with a non-traditional design method inspired by natural
ontogenesis (an embryonic approach) for construction of combinational logic
circuits (in particular sorting networks and adders). The general principle of the technique is based on a set of proper
instructions known beforehand that are repeatedly applied on the embryo
(a trivial instance of a problem) to construct more complex system. Genetic algorithm is used to find a suitable
sequence of instructions -- a prescription for the growth of the embryo. The system complexity can increase continually and infinitely. It is shown that
by employing of this approach the genetic algorithm is able to (1) rediscover the
principle of already known method and (2) find a novel algorithm, by means of
which we can obtain better solutions in comparison with a conventional method.

Annotation

The paper deals with a non-traditional design method inspired by natural
ontogenesis (an embryonic approach) for construction of combinational logic
circuits (in particular sorting networks and adders). The general principle of the technique is based on a set of proper
instructions known beforehand that are repeatedly applied on the embryo
(a trivial instance of a problem) to construct more complex system. Genetic algorithm is used to find a suitable
sequence of instructions -- a prescription for the growth of the embryo. The system complexity can increase continually and infinitely. It is shown that
by employing of this approach the genetic algorithm is able to (1) rediscover the
principle of already known method and (2) find a novel algorithm, by means of
which we can obtain better solutions in comparison with a conventional method.

Published

2005

Pages

8

Publisher

Faculty of Information Technology BUT

Place

Brno

BibTeX

@techreport{BUT57852,
  author="Michal {Bidlo}",
  title="A Developmental Method for Construction of Arbitrarily Large Sorting Networks and Adders",
  year="2005",
  publisher="Faculty of Information Technology BUT",
  address="Brno",
  pages="8",
  url="http://www.fit.vutbr.cz/~bidlom/Papers/2005/research_report2005.pdf"
}