Evolutionary Synthesis of Fast Constant-Coefficient Multipliers

Naofumi HOMMA  Takafumi AOKI  Tatsuo HIGUCHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E83-A   No.9   pp.1767-1777
Publication Date: 2000/09/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Nonlinear Problems
circuit design,  computer arithmetic,  arithmetic circuits,  evolvable hardware,  evolutionary computation,  

Full Text: PDF(982.5KB)>>
Buy this Article

This paper presents an efficient graph-based evolutionary optimization technique called Evolutionary Graph Generation (EGG), and its application to the design of fast constant-coefficient multipliers using parallel counter-tree architecture. An important feature of EGG is its capability to handle the general graph structures directly in evolution process instead of encoding the graph structures into indirect representations, such as bit strings and trees. This paper also addresses the major problem of EGG regarding the significant computation time required for verifying the function of generated circuits. To solve this problem, a new functional verification technique for arithmetic circuits is proposed. It is demonstrated that the EGG system can create efficient multiplier structures which are comparable or superior to the known conventional designs.