Tangen, Uwe, Rudolf M. Füchslin, Thomas Maeke, and John S. McCaskill. “Progress in digital evolution: 4-bit multiplier evolved using reconfigurable hardware.” Preprint. http://www. biomip. de/Uwe/publications/Multi_a. pdf (2003).
URL1 URL2
The evolution of circuits for digital logic mappings such as multiplication is difficult both because of the size of the search space and because of the intrinsic complexity of common mappings in compact representations. We have investigated the task of finding a feed-forward 4-bit multiplier circuit in which the allowed logical depth precludes the decomposition of the problem into carry chain additions. A full 4-bit multiplier is one of 28∗23= 22048 different 8-bit to 8-bit mappings implemented by a Boolean logic feed forward pipelined network, able to multiply two binary numbers ranging from [0 … 15] to produce an 8-bit product in the range [0…225]. The logic resources provided were 64 4-input Boolean function generators arranged in four feed forward layers. Each of the four inputs of a function generator has access to one of the outputs of the preceding 16 function generators. In addition to the Boolean functions in these generators, the routing topology of the feed-forward network is also being evolved. Employing a special 8/10-bit coding and more than a billion fitness evaluations (about an hour real time on MereGenTM) a fully functional multiplier could be evolved. Several simpler sub-problems have also been studied, as well as the correlation structure of the fitness landscape and the value of neutral evolution. It turns out that the fitness-landscape is much richer than previously imagined.