Gate-level synthesis of Boolean functions using information theory concepts

Author

Aguirre, A.H. ; Coello, C.C.

Author_Institution

Dept. of Comput. Sci., Miner. de Valencia, Guanajuato, Mexico

fYear

2003

fDate

12-12 Sept. 2003

Firstpage

268

Lastpage

275

Abstract

In this paper we apply information theory concepts to evolutionary Boolean circuit synthesis. We discuss the schema destruction problem when simple conditional entropy is used as fitness function. The design problem is the synthesis of Boolean functions by using the minimum number of binary multiplexers. We show that the fitness landscape of normalized mutual information exhibits better characteristics for evolutionary search than the landscape of simple mutual information. A comparison of minimum evolved circuits shows the potential of information theory concepts.

Keywords

Boolean functions; equivalent circuits; genetic algorithms; information theory; logic design; Boolean function; Boolean functions; binary multiplexer; conditional entropy; evolutionary Boolean circuit synthesis; evolutionary search; fitness function; fitness landscape; gate-level synthesis; information theory; minimum evolved circuits; normalized mutual information; schema destruction problem; simple mutual information; Boolean functions; Circuit synthesis; Computer science; Decision trees; Entropy; Genetic communication; Genetic programming; Information theory; Multiplexing; Mutual information;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Science, 2003. ENC 2003. Proceedings of the Fourth Mexican International Conference on

Conference_Location

Tlaxcala, Mexico

Print_ISBN

0-7695-1915-6

Type

conf

DOI

10.1109/ENC.2003.1232904

Filename

1232904