A method of automated synthesis of analog and/or digital electronic circuits involves evolution, either in software simulations or in hard- ware, directly on integrated-circuit chips. “Evolution” is used here in a quasi-genetic sense, signifying the construction and testing of a sequence of populations of circuits that function as incrementally better solutions of a given design problem. The evolution is guided by a search-and-optimization algorithm (in particular, a genetic algorithm) that operates in the space of possible circuits to find a circuit that exhibits the desired behavior.
In comparison with evolution by use of software circuit simulations, evolution in hardware can speed the search for a solution circuit by a few orders of magnitude. Moreover, because software simulations rely on mathematical circuit models of limited accuracy, a solution evolved in software can behave differently when downloaded in programmable hardware; such mismatches are avoided when evolution takes place directly in hardware.
A prior version of automated synthesis of electronic circuits in hardware was discussed in “Reconfigurable Arrays of Transistors for Evolvable Hardware” (NPO-20078), NASA Tech Briefs, Vol. 25, No. 2 (February 2001), page 36. To recapitulate: Very-large-scale integrated (VLSI) circuits would contain electronically reconfigurable arrays of transistors. Under the direction of genetic and/or other evolutionary algorithms, the configurations and thus the functionalities of the circuits would be made to evolve until at least one circuit exhibited a desired behavior or adapted to the environment in a prescribed way. Evolution would include selective, repetitive connection and/or disconnection of transistors, amplifiers, inverters, and/or other circuit building blocks.
The present version of automated synthesis of electronic circuits in either software simulation or hardware is based on the same general concept as that of the prior version, the main differences lying in the details of implementation. The figure schematically depicts the main steps of an automated evolutionary synthesis according to the present method. In the first step, a mathematical representation of a population of circuits (in this context, analogous to chromosomes) is generated randomly. The chromosomes are then converted into either (1) mathematical models of circuits or (2) strings of control bits that are downloaded to programmable hardware (if the circuits are to be evaluated directly in hardware). In the mathematical-model case, the simulation program compares the behaviors of the models with the desired behavior and the evolution is said to be “extrinsic”; in the programmable-hardware case, the physical behaviors of the hardware are compared with the desired behavior and the evolution is said to be “intrinsic.”
In either the intrinsic or the extrinsic case, the circuits are ranked according to how close their behaviors come to the desired behavior. A new population of circuits is generated from a selected pool of best circuits in the previous generation, subject to a such genetic operators as chromosome crossover and mutation. The process is repeated for many generations, yielding progressively better circuits. The criterion for stopping the evolution can be the reduction of error below a certain threshold, or reaching a predetermined number of generations. One or several solutions may be found among the individuals of the last generation.
The viability of this method has been demonstrated on a sequence of software prototypes. In a proposed hardware implementation, the basic circuit elements would be an array of metal oxide/semiconductor field-effect transistors interconnected via programmable switches. The circuit topology would be a function of the switch states (off or on), which would be specified by the strings of control bits. This programmable array of transistors could be modular, and modules could be cascaded and/or expanded to obtain circuits of greater complexity.
This work was done by Adrian Stoica and Carlos Salazar-Lazaro of Caltech for NASA’s Jet Propulsion Laboratory.
This invention is owned by NASA, and a patent application has been filed. Inquiries concerning nonexclusive or exclusive license for its commercial development should be addressed to
the Patent Counsel
NASA Management Office–JPL; (818) 354-7770.
Refer to NPO-20535.
This Brief includes a Technical Support Package (TSP).
Evolutionary Automated Synthesis of Electronic Circuits
(reference NPO-20535) is currently available for download from the TSP library.
Don't have an account? Sign up here.