Baldwinian learning utilizing genetic and heuristic algorithms for logic synthesis and minimization of incompletely specified data with Generalized Reed-Muller (AND-EXOR) forms

This research applies a new heuristic combined with a genetic algorithm (GA ) to the task of logic minimization for incompletely specified data, with b oth single and multi-outputs, using the Generalized Reed-Muller (GRM) equat ion form. The GRM equation type is a canonical expression of the Exclusive- Or Sum-of-Products (ESOPs) type, in which for every subset of input variabl es there exists not more than one term with arbitrary polarities of all var iables. This AND-EXOR implementation has been shown to be economical, gener ally requiring fewer gates and connections than that of AND-OR logic. GRM l ogic is also highly testable, making it desirable for FPGA designs. The min imization results of this new algorithm tested on a number of binary benchm arks are given. This minimization algorithm utilizes a GA with a two-level fitness calculation, which combines human-designed heuristics with the evol utionary process, employing Baldwinian learning. In this algorithm, first a pure GA creates certain constraints for the selection of chromosomes, crea ting only genotypes (polarity vectors), The phenotypes (GRMs) are then lear ned in the environment and contribute to the GA fitness (which is the total number of terms of the best GRM for each output), providing indirect feedb ack as to the quality of the genotypes (polarity vectors) but the genotype chromosomes (polarity vectors) remain unchanged. In this process, the impro vement in genotype chromosomes (polarity vectors) is the product of the evo lutionary processes from the GA only. The environmental learning is achieve d using a human-designed GRM minimization heuristic. As much previous resea rch has presented the merit of AND-EXOR logic for its high density and test ability, this research is the first application of the GRM (a canonical AND -EXOR form) to the minimization of incompletely specified data. (C) 2001 Pu blished by Elsevier Science B.V.