Using genetic programing and multiplexers for the synthesis of logic circuits

This article introduces the circuit design problem as a synthesis procedure. An evolutionary technique denominated Genetic Programing (GP) is proposed as the main engine for the synthesis of logic circuits. This article argues that the synthesis of circuits using bottom-up procedures (such as GP) is at least as powerful as any top-down method, and that this is possible by means of the replication of a single element, the binary multiplexer. The properties of this device are described as a sound basis for the synthesis of logic circuits using GP. Several circuits are synthesized and contrasted against two design methods: the standard implementation of logic functions using multiplexers, and ordered binary decision diagrams.